Адаптивный кейс-менеджмент
- 1 year ago
- 0
- 0
Адаптивный координатный спуск — улучшенный вариант алгоритма координатного спуска для неразделимой оптимизации , использующий технику адаптивного кодирования . Адаптивный координатный спуск последовательно строит преобразования координатной системы так, что новые координаты максимально декоррелированы по отношению к целевой функции. Было показано, что адаптивный координатный спуск конкурентен с передовыми эволюционными алгоритмами и обладает следующими свойствами инвариантности :
адаптивное кодирование (b), в основном базирующееся на методе главных компонент (a), используется для расширения метода координатного спуска (c) для решения неразделимых задач оптимизации (d).
Адаптация приемлемой координатной системы позволяет методу адаптивного координатного спуска превзойти координатный спуск на неразделимых функциях. Следующий рисунок показывает сходимость обоих алгоритмов для двумерной функции Розенброка до целевого значения функции начиная с точки .
Адаптивный координатный спуск достигает целевого значения всего за 325 вычислений функции (примерно в 70 раз быстрее координатного спуска), что сравнимо с методами, основанными на градиентах . Алгоритм имеет линейную сложность по времени, если обновлять систему координат каждые D итераций, и пригоден для нелинейных задач оптимизации большого размера (D>>100).
Первые подходы к оптимизации с использованием адаптации системы координат были предложены уже в 1960-е годы (например, методы Розенброка ). Алгоритм PRincipal Axis (PRAXIS), известный также как алгоритм Брента — алгоритм без вычисления производной, в котором предполагается квадратичная форма оптимизируемой функции и периодически обновляется набор направлений поиска . Алгоритм, однако, не инвариантен относительно масштабирования целевой функции и может привести к неудаче при некоторых сохраняющих ранг преобразованиях (например, может привести целевую функцию к неквадратичной форме) .
Описан пример применения адаптивного координатного спуска с адаптацией шага и локальным вращением координат для планирования пути робота-манипулятора в трёхмерном пространстве со статическими многоугольными препятствиями .