Случайная оптимизация

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

Название «случайная оптимизация» приписывают Матиасу. который сделал раннюю презентацию RO вместе с базовым математическим анализом. RO работает путем итеративного перемещения к лучшим позициям в пространстве поиска, которые выбираются с использованием, например, нормального распределения, окружающего текущую позицию.

Алгоритм

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

• Инициализируйте x случайной позицией в пространстве поиска.
• Пока не будет выполнен критерий завершения (например, количество выполненных итераций или достижение адекватной пригодности), повторяйте следующее:
  • Возьмите новую позицию y, добавив нормально распределенный случайный вектор к текущей позиции x.
  • Если ( f ( y ) < f ( x )) то перейдите в новую позицию, установив x = y
• Теперь x занимает наилучшую найденную позицию.

Этот алгоритм соответствует стратегии эволюции (1+1) с постоянным размером шага.

Конвергенция и варианты

Матьяс показал, что базовая форма RO сходится к оптимуму простой унимодальной функции , используя доказательство предела , которое показывает, что сходимость к оптимуму обязательно произойдет, если будет выполнено потенциально бесконечное количество итераций. Однако это доказательство бесполезно на практике, поскольку можно выполнить только конечное число итераций. Фактически, такое теоретическое доказательство предела также покажет, что чисто случайная выборка пространства поиска неизбежно приведет к выборке, сколь угодно близкой к оптимальной.

Математический анализ также проводит Баба. и Солис и Ветс установить, что сходимость к области, окружающей оптимум, неизбежна при некоторых мягких условиях для вариантов RO, используя другие распределения вероятностей для выборки. Оценка количества итераций, необходимых для достижения оптимума, получена Дореа. Этот анализ подвергается критике Сармы в эмпирических экспериментах. который использовал варианты оптимизатора Бабы и Дореа для решения двух реальных задач, показав, что к оптимуму нужно приближаться очень медленно, и, более того, эти методы фактически были неспособны найти решение, подходящее для адекватной пригодности, если только процесс не был начат достаточно близко к оптимуму. для начала.

См. также

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