Луус-Яакола

В вычислительной технике Луус -Яакола (LJ) обозначает эвристику для глобальной оптимизации действительной функции. ^{[ 1 ]} В инженерном использовании LJ не является алгоритмом , завершающимся оптимальным решением; это также не итеративный метод , генерирующий последовательность точек, сходящуюся к оптимальному решению (если оно существует). Однако при применении к дважды непрерывно дифференцируемой функции эвристика LJ является правильным итеративным методом, который генерирует последовательность, имеющую сходящуюся подпоследовательность; для этого класса задач рекомендуется метод Ньютона , который имеет квадратичную скорость сходимости, в то время как для эвристики LJ не проводился анализ скорости сходимости. ^{[ 1 ]} На практике эвристика LJ рекомендуется для функций, которые не должны быть ни выпуклыми , ни дифференцируемыми , ни локально липшицевыми : эвристика LJ не использует градиент или субградиент, если таковые имеются, что позволяет применять ее к недифференцируемым и невыпуклым задачам. .

Предложено Луусом и Яаколой, ^{[ 2 ]} LJ генерирует последовательность итераций. Следующая итерация выбирается из выборки из окрестности текущей позиции с использованием равномерного распределения . С каждой итерацией окрестность уменьшается, что заставляет подпоследовательность итераций сходиться к точке кластера. ^{[ 1 ]}

Луус применил ЖЖ для оптимального контроля , ^{[ 3 ]} ^{[ 4 ]} конструкция трансформатора , ^{[ 5 ]} металлургические процессы , ^{[ 6 ]} и химическое машиностроение . ^{[ 7 ]}

Мотивация

На каждом этапе эвристика LJ поддерживает блок, из которого она выбирает точки случайным образом, используя равномерное распределение по блоку. Для унимодальной функции вероятность уменьшения целевой функции уменьшается по мере приближения ящика к минимуму. На рисунке представлен одномерный пример.

эвристика

Позволять $f:\mathbb {R} ^{n}\rightarrow \mathbb {R}$ быть функцией приспособленности или затрат, которую необходимо минимизировать. Позволять ${\textbf {x}}\in \mathbb {R} ^{n}$ обозначают позицию или возможное решение в пространстве поиска. Эвристика ЖЖ повторяет следующие шаги:

Инициализируйте x ~ U ( b _lo , b _up ) случайной однородной позицией в пространстве поиска, где b _lo и b _up — нижняя и верхняя границы соответственно.
Установите начальный диапазон выборки, чтобы охватить все пространство поиска (или его часть): d = b _up − b _lo
Пока не будет достигнут критерий завершения (например, количество выполненных итераций или достижение адекватной пригодности), повторяйте следующее:
- Выберите случайный вектор a ~ U (− d , d )
- Добавьте это к текущей позиции x, чтобы создать новую потенциальную позицию y = x + a.
- Если ( f ( y ) < f ( x )) затем перейдите в новую позицию, установив x = y , в противном случае уменьшите диапазон выборки: d = 0,95 d
Теперь x занимает наилучшую найденную позицию.

Вариации

Луус отмечает, что предложенные на сегодняшний день алгоритмы ARS (адаптивного случайного поиска) различаются по многим аспектам. ^{[ 8 ]}

Процедура генерации случайных пробных точек.
Количество внутренних циклов (NIL, количество точек случайного поиска в каждом цикле).
Количество циклов (NEL, количество внешних контуров).
Коэффициент сокращения размера области поиска. (Некоторые примерные значения составляют от 0,95 до 0,60.)
- Является ли скорость сокращения региона одинаковой для всех переменных или разной для каждой переменной (так называемый алгоритм M-LJ).
- Является ли скорость сокращения региона постоянной или следует другому распределению (например, Гауссу).
Включить ли поиск по строке.
Следует ли рассматривать ограничения случайных точек в качестве критериев приемки или включать квадратичный штраф.

Конвергенция

Наир доказал анализ сходимости. Для дважды непрерывно дифференцируемых функций эвристика LJ генерирует последовательность итераций, имеющую сходящую подпоследовательность. ^{[ 1 ]} Для этого класса задач метод Ньютона является обычным методом оптимизации и обладает квадратичной сходимостью ( независимо от размерности пространства, которое может быть банаховым , согласно , анализу Канторовича ).

Однако, согласно анализу Юдина и Немировского, сложность минимизации в худшем случае в классе унимодальных функций растет экспоненциально с увеличением размерности задачи. Анализ Юдина-Немировского подразумевает, что ни один метод не может быть быстрым при решении многомерных задач, которым не хватает выпуклости:

«Катастрофический рост [количества итераций, необходимых для достижения приближенного решения заданной точности] при [увеличении числа измерений до бесконечности] показывает, что бессмысленно ставить вопрос о построении универсальных методов решения... задач любой заметной размерности «вообще». Интересно отметить, что тот же [вывод] справедлив для ... задач, порожденных униэкстремальными [то есть унимодальными] (но не выпуклыми) функциями». ^{[ 9 ]}

Применительно к дважды непрерывно дифференцируемым задачам скорость сходимости эвристики LJ снижается по мере увеличения числа измерений. ^{[ 10 ]}

См. также

Случайная оптимизация — это родственное семейство методов оптимизации, в которых используется выборка из общих распределений, например равномерного распределения.
Случайный поиск — это родственное семейство методов оптимизации, которые выбирают из общих распределений, например, равномерного распределения на единичной сфере .
Поиск по шаблону используется при зашумленных наблюдениях, особенно в методологии поверхности отклика в химической технологии . Они не требуют от пользователей программирования градиентов или гессианов.

Ссылки

^ Перейти обратно: ^а ^б ^с ^д Наир, Г. Гопалакришнан (1979). «О сходимости метода поиска ЖЖ». Журнал теории оптимизации и приложений . 28 (3): 429–434. дои : 10.1007/BF00933384 . МР 0543384 .
^ Луус, Р.; Яакола, THI (1973). «Оптимизация путем прямого поиска и систематического уменьшения размера области поиска». Журнал Айше . 19 (4): 760–766. дои : 10.1002/aic.690190413 .
^ Бойков Р.; Гензель, Б.; Луус, Р. (1993). «Применение прямой поисковой оптимизации к задачам оптимального управления». Венгерский журнал промышленной химии . 21 : 177–185.
^ Хейнянен, Ээро (октябрь 2018 г.). Метод автоматической настройки ПИД-регулятора после оптимизации Лууса-Яаколы (PDF) (под ред. Магистерской диссертации). Тампере, Финляндия: Технологический университет Тампере . Проверено 1 февраля 2019 г.
^ Спаанс, Р.; Луус, Р. (1992). «Важность сокращения области поиска при случайной оптимизации». Журнал теории оптимизации и приложений . 75 : 635–638. дои : 10.1007/BF00940497 . МР 1194836 .
^ Папангелакис, В.Г.; Луус, Р. (1993). «Оптимизация реактора в процессе автоклавного окисления». Учеб. Межд. Симп. по моделированию, моделированию и управлению металлургическими процессами . стр. 159–171.
^ Ли, Ю.П.; Рангаиа, врач общей практики; Луус, Р. (1999). «Расчеты фазового и химического равновесия методом прямой поисковой оптимизации». Компьютеры и химическая инженерия . 23 (9): 1183–1191. дои : 10.1016/s0098-1354(99)00283-5 .
^ Луус, Рейн (2010). «Формулировка и иллюстрация процедуры оптимизации Лууса-Яаколы». В Рангале, Гаде Панду (ред.). Стохастическая глобальная оптимизация: методы и приложения в химической технологии . World Scientific Pub Co Inc., стр. 17–56. ISBN 978-9814299206 .
^ Немировский А.С.; Юдин, Д.Б. (1983). Сложность задач и эффективность методов оптимизации . Серия Wiley-Interscience по дискретной математике (Перевод Э. Р. Доусона из русского (1979) (М.: Наука) изд.). Нью-Йорк: John Wiley & Sons, Inc., с. 7. ISBN 0-471-10345-4 . МР 0702836 . На странице 7 подведены итоги более позднего обсуждения Немировского и Юдина (1983 , стр. 36–39).
^ Наир (1979) , с. 433.

[nair79convergence-1] Перейти обратно: ^а ^б ^с ^д Наир, Г. Гопалакришнан (1979). «О сходимости метода поиска ЖЖ». Журнал теории оптимизации и приложений . 28 (3): 429–434. дои : 10.1007/BF00933384 . МР 0543384 .

[luus73optimization-2] Луус, Р.; Яакола, THI (1973). «Оптимизация путем прямого поиска и систематического уменьшения размера области поиска». Журнал Айше . 19 (4): 760–766. дои : 10.1002/aic.690190413 .

[bojkov93application-3] Бойков Р.; Гензель, Б.; Луус, Р. (1993). «Применение прямой поисковой оптимизации к задачам оптимального управления». Венгерский журнал промышленной химии . 21 : 177–185.

[Hein-4] Хейнянен, Ээро (октябрь 2018 г.). Метод автоматической настройки ПИД-регулятора после оптимизации Лууса-Яаколы (PDF) (под ред. Магистерской диссертации). Тампере, Финляндия: Технологический университет Тампере . Проверено 1 февраля 2019 г.

[spaans92importance-5] Спаанс, Р.; Луус, Р. (1992). «Важность сокращения области поиска при случайной оптимизации». Журнал теории оптимизации и приложений . 75 : 635–638. дои : 10.1007/BF00940497 . МР 1194836 .

[papangelakis93reactor-6] Папангелакис, В.Г.; Луус, Р. (1993). «Оптимизация реактора в процессе автоклавного окисления». Учеб. Межд. Симп. по моделированию, моделированию и управлению металлургическими процессами . стр. 159–171.

[lee99phase-7] Ли, Ю.П.; Рангаиа, врач общей практики; Луус, Р. (1999). «Расчеты фазового и химического равновесия методом прямой поисковой оптимизации». Компьютеры и химическая инженерия . 23 (9): 1183–1191. дои : 10.1016/s0098-1354(99)00283-5 .

[8] Луус, Рейн (2010). «Формулировка и иллюстрация процедуры оптимизации Лууса-Яаколы». В Рангале, Гаде Панду (ред.). Стохастическая глобальная оптимизация: методы и приложения в химической технологии . World Scientific Pub Co Inc., стр. 17–56. ISBN 978-9814299206 .

[9] Немировский А.С.; Юдин, Д.Б. (1983). Сложность задач и эффективность методов оптимизации . Серия Wiley-Interscience по дискретной математике (Перевод Э. Р. Доусона из русского (1979) (М.: Наука) изд.). Нью-Йорк: John Wiley & Sons, Inc., с. 7. ISBN 0-471-10345-4 . МР 0702836 . На странице 7 подведены итоги более позднего обсуждения Немировского и Юдина (1983 , стр. 36–39).

[FOOTNOTENair1979433-10] Наир (1979) , с. 433.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]