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

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

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

Алгоритм

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

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

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

Схождение и варианты

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

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

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

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

Ссылки