Адаптивный координатный спуск
Улучшение алгоритма координатного спуска

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

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

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

Адаптация соответствующей системы координат позволяет адаптивному спуску по координатам превосходить спуск по координатам на неразделимых функциях. Следующий рисунок иллюстрирует сходимость обоих алгоритмов на двумерной функции Розенброка до значения целевой функции , начиная с начальной точки . 10 − 10 {\displaystyle 10^{-10}} х 0 = ( − 3 , − 4 ) {\displaystyle x_{0}=(-3,-4)}

Метод адаптивного спуска по координатам достигает целевого значения всего за 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). Алгоритмы минимизации без производных . Prentice-Hall.
  4. ^ Али, У.; Кикмайер-Раст, МД (2008). «Реализация и применение трехраундовой пользовательской стратегии для улучшенной минимизации главной оси». Журнал прикладных количественных методов . С.  505–513 .
  5. ^ Павлов, Д. (2006). «Планирование пути манипулятора в трехмерном пространстве». Computer Science--Theory and Applications . Springer. С.  505–513 .
  • ИСХОДНЫЙ КОД ACD ACD — это исходный код MATLAB для адаптивного координатного спуска.
Взято с "https://en.wikipedia.org/w/index.php?title=Адаптивный_координатный_спуск&oldid=1249472970"