Адаптивный спуск по координатам
Адаптивный спуск по координатам [1] представляет собой усовершенствование координатного спуска алгоритма до неразделимой оптимизации за счет использования адаптивного кодирования . [2] Подход адаптивного спуска по координатам постепенно выстраивает преобразование системы координат таким образом, чтобы новые координаты были максимально декоррелированы по отношению к целевой функции. Показано, что адаптивный координатный спуск конкурентоспособен по сравнению с современными эволюционными алгоритмами и обладает следующими свойствами инвариантности:
- Инвариантность относительно монотонных преобразований функции (масштабирования)
- Инвариантность относительно ортогональных преобразований пространства поиска (вращения).
CMA Обновление адаптивного кодирования, подобное (b), в основном основанное на анализе главных компонентов (a), используется для расширения метода спуска по координатам (c) для оптимизации неразделимых задач (d).
Адаптация соответствующей системы координат позволяет адаптивному спуску по координатам превосходить спуск по координатам для неразделимых функций. На следующем рисунке показана сходимость обоих алгоритмов на двумерной функции Розенброка до значения целевой функции. , начиная с начальной точки .
Метод адаптивного координатного спуска достигает целевого значения всего после 325 вычислений функции (примерно в 70 раз быстрее, чем координатный спуск), что сопоставимо с методами, основанными на градиенте . Алгоритм имеет линейную временную сложность, если система координат обновляется каждые D итераций, он также подходит для крупномасштабной (D>>100) нелинейной оптимизации.
Соответствующие подходы
[ редактировать ]Первые подходы к оптимизации с использованием адаптивной системы координат были предложены уже в 1960-х годах (см., например, метод Розенброка ). Алгоритм PRincipal Axis (PRAXIS), также называемый алгоритмом Брента, представляет собой алгоритм без производных, который принимает квадратичную форму оптимизируемой функции и неоднократно обновляет набор сопряженных направлений поиска. [3] Алгоритм, однако, не инвариантен к масштабированию целевой функции и может дать сбой при определенных преобразованиях, сохраняющих ранг (например, приведет к неквадратичной форме целевой функции). Недавний анализ PRAXIS можно найти в. [4] О практическом применении см. [5] где был предложен подход адаптивного спуска координат с адаптацией размера шага и вращением местной системы координат.для планирования траектории робота-манипулятора в трехмерном пространстве со статическими полигональными препятствиями.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Лощилов И.; М. Шенауэр; М. Себаг (2011). «Адаптивный координатный спуск» (PDF) . Конференция по генетическим и эволюционным вычислениям (GECCO) . АКМ Пресс. стр. 885–892.
- ^ Николаус Хансен. « Адаптивное кодирование: как сделать инвариант системы координат поиска ». Параллельное решение проблем из природы - PPSN X, сентябрь 2008 г., Дортмунд, Германия. стр.205-214, 2008.
- ^ Брент, Р.П. (1972). Алгоритмы минимизации без производных . Прентис-Холл.
- ^ Али, У.; Кикмайер-Руст, доктор медицины (2008). «Реализация и применение трехраундовой пользовательской стратегии для улучшенной минимизации главной оси». Журнал прикладных количественных методов . стр. 505–513.
- ^ Павлов, Д. (2006). «Планирование пути манипулятора в трехмерном пространстве». Информатика – теория и приложения . Спрингер. стр. 505–513.
Внешние ссылки
[ редактировать ]- ИСХОДНЫЙ КОД ACD ACD — это исходный код MATLAB для адаптивного спуска по координатам.