Случайный поиск

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

Истоки

В 1953 году Андерсон рассмотрел прогресс методов поиска максимума или минимума задач с использованием ряда предположений, распределённых с некоторым порядком или шаблоном в пространстве поиска параметров, например, запутанный план с экспоненциально распределенными интервалами/шагами. Этот поиск продолжается последовательно по каждому параметру и итеративно уточняет лучшие предположения из последней последовательности. Шаблон может быть сеточным поиском всех параметров, последовательным поиском по каждому параметру или комбинацией того и другого. Метод был разработан для скрининга экспериментальных условий в химических реакциях рядом учёных, перечисленных в статье Андерсона. Код MATLAB, воспроизводящий последовательную процедуру для общей нелинейной регрессии примера математической модели, можно найти здесь (JCFit @ GitHub).

Название «случайный поиск» приписывается Растригину, который одним из первых представил этот метод вместе с базовым математическим анализом. Случайный поиск работает путём итеративного перемещения к лучшим позициям в пространстве поиска, которые выбираются из гиперсферы, окружающей текущую позицию.

Случайный поиск использовался в искусственных нейронных сетях для оптимизации гиперпараметров.

Если хорошие части пространства поиска занимают 5% объема, то вероятность попадания в хорошую конфигурацию составляет 5%. Вероятность найти хотя бы одну хорошую конфигурацию превышает 95% после 60 попыток ($1-0{,}95^{60}=0{,}953>0{,}95$, используя метод обратной вероятности).

Алгоритм

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

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

1. Инициализировать x случайной точкой в пространстве поиска.
2. Повторять следующие шаги до тех пор, пока не будет достигнут критерий завершения (например, выполнено заданное количество итераций или достигнута достаточная целевая функция):
   1. Выбрать новое положение y из гиперсферы заданного радиуса, окружающей текущее положение x (см., например, метод Марсальи для выборки из гиперсферы.)
   2. Если $f(\mathbf {y} )<f(\mathbf {x} )$ то перейти к новому положению, присвоив $\mathbf {x} =\mathbf {y}$

Варианты

Схема случайного поиска на примере задачи нелинейной регрессии. Цель — минимизировать значение штрафной функции. В правом нижнем углу представлены несколько примеров методов: 1. Неструктурированный случайный поиск, 2. Структурированный случайный поиск, 3. Алгоритм Гаусса — Ньютона, 4. Алгоритм Левенберга — Марквардта. Методы 1 и 2 не требуют знания градиента, тогда как методы 3 и 4 требуют его вычисления и обычно минимизируют одновременно по параметрам A и k (на схеме показано только измерение k).

Истинный случайный поиск полностью зависит от удачи и может быть как очень затратным, так и очень успешным, в то время как структурированный случайный поиск является стратегическим. В литературе представлен ряд вариантов случайного поиска с использованием структурированной выборки в пространстве поиска:

• Процедура Фридмана-Сэвиджа: последовательный поиск каждого параметра с набором предположений, имеющих пространственный шаблон между начальным предположением и границами. Пример шагов с экспоненциальным распределением можно найти в коде MATLAB (JCFit @ GitHub). Этот пример кода сходится на 1-2 порядка медленнее, чем алгоритм Левенберга — Марквардта, пример которого также представлен на GitHub.
• Случайный поиск с фиксированным шагом в базовом алгоритме Растригина, который выбирает пробы из гиперсферы фиксированного радиуса.
• Случайный поиск с оптимальным размером шага Шумера и Стейнглица представляет собой в первую очередь теоретическое исследование того, как оптимально настроить радиус гиперсферы для быстрого схождения к оптимуму. Реальная реализация метода требует аппроксимации этого оптимального радиуса путём многократной выборки, что делает её дорогостоящей в исполнении.
• Случайный поиск с адаптивным размером шага, также предложенный Шумером и Стейнглицем, пытается эвристически адаптировать радиус гиперсферы — генерируются два новых кандидатных решения, одно с текущим номинальным размером шага, а другое с бо́льшим размером шага. Бо́льший размер шага становится новым номинальным размером шага только в том случае, если он приводит к большему улучшению. Если в течение нескольких итераций ни один из шагов не приводит к улучшению, номинальный размер шага уменьшается.
• Случайный поиск с оптимизированным относительным размером шага Шрака и Чойта аппроксимирует оптимальный размер шага путём простого экспоненциального уменьшения. Однако формула для вычисления коэффициента уменьшения является несколько сложной.

См. также

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