Адаптивный координатный спуск
Адаптивный координатный спускШаблон:Sfn — улучшенный вариант алгоритма координатного спуска для неразделимой оптимизации, использующий технику адаптивного кодированияШаблон:Sfn. Адаптивный координатный спуск последовательно строит преобразования координатной системы так, что новые координаты максимально декоррелированы по отношению к целевой функции. Было показано, что адаптивный координатный спуск конкурентен с передовыми эволюционными алгоритмами и обладает следующими свойствами инвариантности:
- инвариантность относительно монотонного изменения функции (масштабирование)
- инвариантность относительно ортогональных преобразований пространства поиска (вращения).
Шаблон:Нп5 адаптивное кодирование (b), в основном базирующееся на методе главных компонент (a), используется для расширения метода координатного спуска (c) для решения неразделимых задач оптимизации (d).
Адаптация приемлемой координатной системы позволяет методу адаптивного координатного спуска превзойти координатный спуск на неразделимых функциях. Следующий рисунок показывает сходимость обоих алгоритмов для двумерной функции Розенброка до целевого значения функции начиная с точки .
Адаптивный координатный спуск достигает целевого значения всего за 325 вычислений функции (примерно в 70 раз быстрее координатного спуска), что сравнимо с методами, основанными на градиентах. Алгоритм имеет линейную сложность по времени, если обновлять систему координат каждые D итераций, и пригоден для нелинейных задач оптимизации большого размера (D>>100).
Связанные подходы
Первые подходы к оптимизации с использованием адаптации системы координат были предложены уже в 1960-е годы (например, методы Розенброка). Алгоритм PRincipal Axis (PRAXIS), известный также как алгоритм Брента — алгоритм без вычисления производной, в котором предполагается квадратичная форма оптимизируемой функции и периодически обновляется набор направлений поискаШаблон:Sfn.
Алгоритм, однако, не инвариантен относительно масштабирования целевой функции и может привести к неудаче при некоторых сохраняющих ранг преобразованиях (например, может привести целевую функцию к неквадратичной форме)Шаблон:Sfn.
Описан пример применения адаптивного координатного спуска с адаптацией шага и локальным вращением координат для планирования пути робота-манипулятора в трёхмерном пространстве со статическими многоугольными препятствиямиШаблон:Sfn.
Примечания
Литература
Ссылки
- Source code ACD ACD is a MATLAB source code for Adaptive Coordinate Descent