Случайный поиск (RS) - это семейство методов численной оптимизации, которые не требуют оптимизации градиента задачи, и, следовательно, RS можно использовать для функций, которые не являются непрерывными или дифференцируемыми . Такие методы оптимизации также известны как методы прямого поиска, методы без производных или методы черного ящика.
Название «случайный поиск» принадлежит Растригину [1], который сделал раннее представление RS вместе с основным математическим анализом. RS работает, итеративно перемещаясь к лучшим позициям в пространстве поиска, которые берутся из гиперсферы, окружающей текущее положение.
Описанный здесь алгоритм представляет собой тип локального случайного поиска, в котором каждая итерация зависит от решения-кандидата предыдущей итерации. Существуют альтернативные методы случайного поиска, которые выбираются из всего пространства поиска (например, чистый случайный поиск или равномерный глобальный случайный поиск), но они не описаны в этой статье.
Алгоритм [ править ]
Пусть f : ℝ n → ℝ - функция приспособленности или стоимости, которую необходимо минимизировать. Пусть x ∈ ℝ n обозначает позицию или возможное решение в пространстве поиска. Тогда основной алгоритм RS может быть описан как:
- Инициализируйте x случайной позицией в пространстве поиска.
- Пока не будет выполнен критерий завершения (например, количество выполненных итераций или достижение адекватной пригодности), повторите следующее:
- Сделайте выборку новой позиции y из гиперсферы заданного радиуса, окружающей текущую позицию x (см., Например , технику Марсальи для выборки гиперсферы).
- Если f ( y ) < f ( x ), перейдите в новую позицию, установив x = y
Варианты [ править ]
В литературе представлен ряд вариантов RS:
- Случайный поиск с фиксированным размером шага (FSSRS) - это базовый алгоритм Растригина [1] , который производит выборку из гиперсферы фиксированного радиуса.
- Случайный поиск оптимального размера шага (OSSRS) Шумером и Стейглицем [2] - это в первую очередь теоретическое исследование того, как оптимально настроить радиус гиперсферы, чтобы обеспечить быструю сходимость к оптимуму. Фактическая реализация OSSRS должна приближать этот оптимальный радиус путем повторной выборки и поэтому требует больших затрат на выполнение.
- Адаптивный случайный поиск размера шага (ASSRS) Шумера и Стейглица [2] пытается эвристически адаптировать радиус гиперсферы: генерируются два новых возможных решения, одно с текущим номинальным размером шага, а другое - с большим размером шага. Больший размер шага становится новым номинальным размером шага тогда и только тогда, когда он приводит к большему улучшению. Если в течение нескольких итераций ни один из шагов не приводит к улучшению, номинальный размер шага уменьшается.
- Оптимизированный случайный поиск относительного размера шага (ORSSRS) Шрака и Чойта [3] аппроксимирует оптимальный размер шага простым экспоненциальным уменьшением. Однако формула для вычисления коэффициента уменьшения несколько сложна.
См. Также [ править ]
- Случайная оптимизация - это тесно связанное семейство методов оптимизации, которые выбирают из нормального распределения вместо гиперсферы.
- Luus – Jaakola - это тесно связанный метод оптимизации, использующий равномерное распределение в его выборке и простую формулу для экспоненциального уменьшения диапазона выборки.
- Поиск по шаблону выполняет шаги по осям пространства поиска с использованием экспоненциально уменьшающихся размеров шага.
Ссылки [ править ]
- ^ а б Растригин, Л.А. (1963). «Сходимость метода случайного поиска в экстремальном управлении многопараметрической системой». Автоматизация и телемеханика . 24 (10): 1337–1342.
- ^ a b Шумер, Массачусетс; Стейглиц, К. (1968). «Адаптивный случайный поиск размера шага». IEEE Transactions по автоматическому контролю . 13 (3): 270–276. CiteSeerX 10.1.1.118.9779 . DOI : 10,1109 / tac.1968.1098903 .
- ^ Schrack, G .; Чойт, М. (1976). «Оптимизированный случайный поиск с относительным размером шага». Математическое программирование . 10 (1): 230–244. DOI : 10.1007 / bf01580669 .
