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

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

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

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

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

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

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

Алгоритм

Пусть $f : ℝ н \to ℝ$ — функция приспособленности или стоимости, которую необходимо минимизировать. Пусть $х € ℝ н$ обозначают позицию или возможное решение в пространстве поиска. Базовый алгоритм RS можно описать так:

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

Варианты

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

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

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

См. также

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

Ссылки

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

[Anderson_1953_JASA_random_search-1] Андерсон, Р.Л. (1953). «Последние достижения в поиске лучших условий эксплуатации». Журнал Американской статистической ассоциации . 48 (264): 789–798. дои : 10.2307/2281072 . JSTOR 2281072 .

[nkchenjx_jcfit_GitHub-2] Jump up to: ^а ^б «GitHub — Jixin Chen/jcfit: алгоритм случайного поиска для подгонки общих математических моделей» . Гитхаб .

[rastrigin63convergence-3] Jump up to: ^а ^б Растригин Л.А. (1963). «Сходимость метода случайного поиска в экстремальном управлении многопараметрической системой» . Автоматизация и дистанционное управление . 24 (11): 1337–1342 . Проверено 30 ноября 2021 г. 1964 г. перевод русского автомата. и Телемех стр. 1467–1473

[BergstraBengiio2012JMLR_RS-4] Бергстра, Дж.; Бенджио, Ю. (2012). «Случайный поиск для оптимизации гиперпараметров» (PDF) . Журнал исследований машинного обучения . 13 : 281–305.

[Friedman-Savage_random_search-5] Фридман, М.; Сэвидж, ЖЖ (1947). Планирование экспериментов по поиску максимумов, глава 13 «Методов статистического анализа» под редакцией Эйзенхарта, Хастей и Уоллиса . McGraw-Hill Book Co., Нью-Йорк. стр. 363–372 . Получено 30 ноября 2021 г. - через Милтона Фридмана из Гуверовского института Стэнфордского университета.

[schumer68adaptive-6] Jump up to: ^а ^б Шумер, Массачусетс; Стейглиц, К. (1968). «Случайный поиск с адаптивным размером шага». Транзакции IEEE при автоматическом управлении . 13 (3): 270–276. CiteSeerX 10.1.1.118.9779 . дои : 10.1109/tac.1968.1098903 .

[schrack76optimized-7] Шрак, Г.; Чойт, М. (1976). «Оптимизированный случайный поиск с относительным размером шага». Математическое программирование . 10 (1): 230–244. дои : 10.1007/bf01580669 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]