Адаптивный координатный спуск - Adaptive coordinate descent

Адаптивный координатный спуск[1] это улучшение координатный спуск алгоритм неразрывно оптимизация с использованием адаптивное кодирование.[2] Подход с адаптивным спуском координат постепенно строит преобразование системы координат так, чтобы новые координаты были как можно более декоррелированы по отношению к целевой функции. Было показано, что адаптивный координатный спуск может конкурировать с современными технологиями. эволюционные алгоритмы и обладает следующими свойствами инвариантности:

  1. Инвариантность относительно монотонных преобразований функции (масштабирование)
  2. Инвариантность относительно ортогональные преобразования пространства поиска (вращение).

CMA -подобное обновление адаптивного кодирования (b) в основном на основе Анализ главных компонентов (a) используется для распространения метода координатного спуска (c) на оптимизацию неразделимых задач (d).

Адаптивный координатный спуск illustration.png

Адаптация соответствующей системы координат позволяет адаптивному координатному спуску превзойти координатный спуск для неотделимых функций. На следующем рисунке показана сходимость обоих алгоритмов на двумерном Функция Розенброка до значения целевой функции , начиная с начальной точки .

Rosenbrock2D.png

Метод адаптивного координатного спуска достигает целевого значения после всего лишь 325 вычислений функций (примерно в 70 раз быстрее, чем координатный спуск), что сопоставимо с градиентные методы. Алгоритм имеет линейную временную сложность, если обновлять систему координат каждые D итераций, он также подходит для крупномасштабной (D >> 100) нелинейной оптимизации.

Соответствующие подходы

Первые подходы к оптимизации с использованием адаптивной системы координат были предложены еще в 1960-х годах (см., Например, Метод Розенброка ). Алгоритм PRincipal Axis (PRAXIS), также называемый алгоритмом Брента, представляет собой алгоритм без производных, который принимает квадратичную форму оптимизированной функции и многократно обновляет набор сопряженных направлений поиска.[3]Однако алгоритм не инвариантен к масштабированию целевой функции и может дать сбой при определенных преобразованиях, сохраняющих ранг (например, приведет к неквадратичной форме целевой функции). Последний анализ PRAXIS можно найти в.[4]Для практического применения см.[5] где предложен подход адаптивного координатного спуска с адаптацией размера шага и поворотом локальной системы координат для планирования пути робот-манипулятор в трехмерном пространстве со статическими полигональными препятствиями.

Смотрите также

Рекомендации

  1. ^ Лощилов, И .; М. Шенауэр; М. Себаг (2011). «Адаптивный координатный спуск» (PDF). Конференция по генетическим и эволюционным вычислениям (GECCO). ACM Press. С. 885–892.
  2. ^ Николаус Хансен. "Адаптивное кодирование: как сделать поисковую систему координат неизменной ". Параллельное решение проблем с натуры - PPSN X, сентябрь 2008 г., Дортмунд, Германия. С. 205-214, 2008.
  3. ^ Брент, Р. П. (1972). Алгоритмы минимизации без производных. Прентис-Холл.
  4. ^ Али, У .; Кикмайер-Раст, доктор медицины (2008). «Реализация и применение трехсторонней пользовательской стратегии для улучшенной минимизации главной оси». Журнал прикладных количественных методов. С. 505–513.
  5. ^ Павлов, Д. (2006). «Планирование траектории манипулятора в трехмерном пространстве». Компьютерные науки - теория и приложения. Springer. С. 505–513.

внешняя ссылка

  • ИСХОДНЫЙ КОД ACD ACD - это исходный код MATLAB для адаптивного координатного спуска.