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

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

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

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

Если хорошие части пространства поиска занимают 5% объема, то вероятность попадания в хорошую конфигурацию составляет 5%. Вероятность найти хотя бы одну хорошую конфигурацию превышает 95% после 60 попыток (, используя метод обратной вероятности).

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

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

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

Варианты

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

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

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

Примечания

Категория:Алгоритмы и методы оптимизации Категория:Стохастическая оптимизация Категория:Метаэвристики