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