Случайная оптимизация (RO) - это семейство методов численной оптимизации, которые не требуют оптимизации градиента задачи, и, следовательно, RO можно использовать для функций, которые не являются непрерывными или дифференцируемыми . Такие методы оптимизации также известны как методы прямого поиска, методы без производных или методы черного ящика.
Название «случайная оптимизация» приписывается Матиасу [1], который сделал раннее представление RO наряду с основным математическим анализом. RO работает путем итеративного перемещения к лучшим позициям в пространстве поиска, которые выбираются с использованием, например, нормального распределения, окружающего текущее положение.
Алгоритм [ править ]
Пусть f : ℝ n → ℝ - функция приспособленности или стоимости, которую необходимо минимизировать. Пусть x ∈ ℝ n обозначает позицию или возможное решение в пространстве поиска. Тогда основной алгоритм RO можно описать как:
- Инициализируйте x случайной позицией в пространстве поиска.
- Пока не будет выполнен критерий завершения (например, количество выполненных итераций или достижение адекватной пригодности), повторите следующее:
- Выберите новую позицию y , добавив нормально распределенный случайный вектор к текущей позиции x
- Если ( f ( y ) < f ( x )), перейдите в новую позицию, установив x = y
- Теперь x занимает наилучшую позицию.
Этот алгоритм соответствует (1 + 1) стратегии эволюции с постоянным размером шага.
Конвергенция и варианты [ править ]
Матиас показал, что базовая форма RO сходится к оптимуму простой унимодальной функции , используя предельное доказательство, которое показывает, что сходимость к оптимуму обязательно произойдет, если выполняется потенциально бесконечное количество итераций. Однако это доказательство бесполезно на практике, потому что может быть выполнено только конечное число итераций. Фактически, такое теоретическое доказательство предела также покажет, что чисто случайная выборка из пространства поиска неизбежно приведет к выборке, сколь угодно близкой к оптимальной.
Математический анализ также проводится Баба [2] и Солисом и Ветсом [3], чтобы установить, что схождение к области, окружающей оптимум, неизбежно при некоторых мягких условиях для вариантов RO с использованием других распределений вероятностей для выборки. Оценка количества итераций, необходимых для достижения оптимума, получена Dorea. [4] Сарма критикует эти анализы в ходе эмпирических экспериментов [5] который использовал варианты оптимизатора Бабы и Дореи для решения двух реальных проблем, показывая, что к оптимуму нужно приближаться очень медленно, и, кроме того, что методы фактически не могли найти решение, подходящее для адекватной пригодности, если только процесс не был запущен достаточно близко к оптимуму. начать с.
См. Также [ править ]
- Случайный поиск - это тесно связанное семейство методов оптимизации, которые выбирают из гиперсферы, а не из нормального распределения.
- Luus – Jaakola - это тесно связанный метод оптимизации, использующий равномерное распределение в его выборке и простую формулу для экспоненциального уменьшения диапазона выборки.
- Поиск по шаблону выполняет шаги по осям пространства поиска с использованием экспоненциально уменьшающихся размеров шага.
- Стохастическая оптимизация
Ссылки [ править ]
- ^ Матиас, J. (1965). «Случайная оптимизация» . Автоматизация и телемеханика . 26 (2): 246–253.
- ^ Баба, Н. (1981). «Сходимость метода случайной оптимизации для задач оптимизации с ограничениями». Журнал теории оптимизации и приложений . 33 (4): 451–461. DOI : 10.1007 / bf00935752 .
- ^ Солис, FJ; Влажный, RJ-B. (1981). «Минимизация методами случайного поиска». Математика исследования операций . 6 (1): 19–30. DOI : 10.1287 / moor.6.1.19 .
- ^ Dorea, CCY (1983). «Ожидаемое количество шагов случайного метода оптимизации». Журнал теории оптимизации и приложений . 39 (3): 165–171. DOI : 10.1007 / bf00934526 .
- ^ Сарма, MS (1990). «О сходимости методов случайной оптимизации Бабы и Дореи». Журнал теории оптимизации и приложений . 66 (2): 337–343. DOI : 10.1007 / bf00939542 .
