Луус – Яакола - Luus–Jaakola

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

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

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

Мотивация

Когда текущая позиция Икс далека от оптимума, вероятность обнаружения улучшения с помощью равномерной случайной выборки равна 1/2.
По мере приближения к оптимуму вероятность обнаружения дальнейших улучшений за счет единообразной выборки уменьшается до нуля, если диапазон выборки d остается фиксированным.

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

Эвристический

Позволять ж: ℝп → ℝ - функция пригодности или стоимости, которую необходимо минимизировать. Позволять Икс ∈ ℝп обозначить позицию или вариант решения в поисковой области. Эвристика LJ повторяет следующие шаги:

  • Инициализировать Икс ~ U(бвот,бвверх) со случайным униформа позиция в пространстве поиска, где бвот и бвверх - нижняя и верхняя границы соответственно.
  • Установите начальный диапазон выборки, чтобы охватить все пространство поиска (или его часть): d = бвверх − бвот
  • Пока не будет выполнен критерий завершения (например, количество выполненных итераций или достижение адекватной пригодности), повторите следующее:
    • Выберите случайный вектор а ~ U(−d, d)
    • Добавьте это в текущую позицию Икс создать новую потенциальную позицию у = Икс + а
    • Если (ж(у) < ж(Икс)) затем перейдите в новое положение, установив Икс = у, в противном случае уменьшите диапазон выборки: d = 0.95 d
  • Сейчас же Икс занимает лучшую позицию.

Вариации

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

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

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

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

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

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

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

Смотрите также

Рекомендации

  1. ^ а б c d Наир, Г. Гопалакришнан (1979). «О сходимости метода поиска ЖЖ». Журнал теории оптимизации и приложений. 28 (3): 429–434. Дои:10.1007 / BF00933384. МИСТЕР  0543384.CS1 maint: ref = harv (связь)
  2. ^ Luus, R .; Яакола, T.H.I. (1973). «Оптимизация прямым поиском и систематическим уменьшением размера поисковой области». Журнал Айше. 19 (4): 760–766. Дои:10.1002 / aic.690190413.
  3. ^ Бойков, Р .; Hansel, B .; Луус, Р. (1993). «Применение прямой поисковой оптимизации к задачам оптимального управления». Венгерский журнал промышленной химии. 21: 177–185.
  4. ^ Хейнянен, Ээро (октябрь 2018 г.). Метод автоматической настройки ПИД-регулятора после оптимизации Лууса-Яаколы (PDF) (Магистерская диссертация под ред.). Тампере, Финляндия: Технологический университет Тампере. Получено 1 февраля, 2019.
  5. ^ Spaans, R .; Луус Р. (1992). «Важность сокращения поисковой области в случайной оптимизации». Журнал теории оптимизации и приложений. 75: 635–638. Дои:10.1007 / BF00940497. МИСТЕР  1194836.
  6. ^ Папангелакис, В.Г .; Луус, Р. (1993). «Оптимизация реактора в процессе окисления под давлением». Proc. Int. Symp. по моделированию, моделированию и управлению металлургическими процессами. С. 159–171.
  7. ^ Lee, Y.P .; Rangaiah, G.P .; Луус, Р. (1999). «Расчет фазового и химического равновесия методом прямой поисковой оптимизации». Компьютеры и химическая инженерия. 23 (9): 1183–1191. Дои:10.1016 / с0098-1354 (99) 00283-5.
  8. ^ Луус, Рейн (2010). «Формулировка и иллюстрация процедуры оптимизации Лууса-Яаколы». В Рангала, Гаде Панду (ред.). Стохастическая глобальная оптимизация: методы и приложения в химической инженерии. World Scientific Pub Co Inc., стр. 17–56. ISBN  978-9814299206.
  9. ^ Немировский и Юдин (1983, п. 7)

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

  10. ^ Наир (1979, п. 433)

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