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

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

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

Название «случайный поиск» приписывается Растригину ^[3] , который сделал раннюю презентацию RS вместе с базовым математическим анализом. RS работает путем итеративного перемещения к лучшим позициям в пространстве поиска, которые выбираются из гиперсферы, окружающей текущую позицию.

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

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

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

Алгоритм

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

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

Варианты

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

Действительно случайный поиск — это чистое везение, и варьируется от очень затратного до очень удачного, но структурированный случайный поиск — стратегический. В литературе представлено несколько вариантов RS со структурированной выборкой в ​​поисковом пространстве:

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

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

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

Ссылки

1. Андерсон, Р. Л. (1953). «Последние достижения в поиске наилучших условий эксплуатации». Журнал Американской статистической ассоциации . 48 (264): 789–798. doi :10.2307/2281072. JSTOR  2281072.
2. "GitHub - Jixin Chen/jcfit: Алгоритм случайного поиска для подгонки общих математических моделей". GitHub .
3. Rastrigin, LA (1963). «Сходимость метода случайного поиска при экстремальном управлении многопараметрической системой». Автоматика и телемеханика . 24 (11): 1337–1342 . Получено 30 ноября 2021 г. 1964 г. перевод на русский язык Автомат. и Телемех, страницы 1467–1473
4. Бергстра, Дж.; Бенгио, И. (2012). «Случайный поиск для оптимизации гиперпараметров» (PDF) . Журнал исследований машинного обучения . 13 : 281–305.
5. Фридман, М.; Сэвидж, Л. Дж. (1947). Планирование экспериментов по поиску максимумов, глава 13 книги «Методы статистического анализа» под редакцией Эйзенхарта, Хастея и Уоллиса. McGraw-Hill Book Co., Нью-Йорк. С. 363–372 . Получено 30 ноября 2021 г. — через Милтона Фридмана из Института Гувера при Стэнфордском университете.
6. Шумер, MA; Штейглиц, K. (1968). «Случайный поиск с адаптивным размером шага». Труды IEEE по автоматическому управлению . 13 (3): 270–276. CiteSeerX 10.1.1.118.9779 . doi :10.1109/tac.1968.1098903. 
7. Шрак, Г.; Чойт, М. (1976). «Случайный поиск с оптимизированным относительным размером шага». Математическое программирование . 10 (1): 230–244. doi :10.1007/bf01580669.