Случайный поиск - Random search
Случайный поиск (RS) - это семейство методов численной оптимизации, которые не требуют оптимизации градиента задачи, и, следовательно, RS можно использовать для функций, которые не являются непрерывными или дифференцируемыми . Такие методы оптимизации также известны как методы прямого поиска, методы без производных или методы черного ящика.
Название «случайный поиск» принадлежит Растригину, который сделал раннее представление RS вместе с основным математическим анализом. RS работает, итеративно перемещаясь к лучшим позициям в пространстве поиска, которые берутся из гиперсферы, окружающей текущее положение.
Описанный здесь алгоритм представляет собой тип локального случайного поиска, где каждая итерация зависит от решения-кандидата предыдущей итерации. Существуют альтернативные методы случайного поиска, которые выбираются из всего пространства поиска (например, чистый случайный поиск или равномерный глобальный случайный поиск), но они не описаны в этой статье.
Алгоритм
Пусть f : ℝ n → ℝ - функция пригодности или стоимости, которую необходимо минимизировать. Пусть x ∈ ℝ n обозначает позицию или возможное решение в пространстве поиска. Тогда основной алгоритм RS может быть описан как:
- Инициализируйте x произвольной позицией в пространстве поиска.
- До тех пор, пока не будет выполнен критерий завершения (например, количество выполненных итераций или достижение адекватной пригодности), повторите следующее:
- Сделайте выборку новой позиции y из гиперсферы заданного радиуса, окружающей текущую позицию x (см., Например , технику Марсальи для выборки гиперсферы).
- Если f ( y ) < f ( x ), перейдите в новую позицию, установив x = y
Варианты
В литературе представлен ряд вариантов RS:
- Случайный поиск с фиксированным размером шага (FSSRS) - это базовый алгоритм Растригина, который производит выборку из гиперсферы фиксированного радиуса.
- Случайный поиск оптимального размера шага (OSSRS) Шумера и Стейглица - это в первую очередь теоретическое исследование того, как оптимально настроить радиус гиперсферы, чтобы обеспечить быстрое схождение к оптимуму. Фактическая реализация OSSRS должна приближать этот оптимальный радиус путем повторной выборки и поэтому требует больших затрат на выполнение.
- Адаптивный случайный поиск размера шага (ASSRS) Шумера и Стейглица пытается эвристически адаптировать радиус гиперсферы: генерируются два новых возможных решения, одно с текущим номинальным размером шага, а другое - с большим размером шага. Больший размер шага становится новым номинальным размером шага тогда и только тогда, когда он приводит к большему улучшению. Если в течение нескольких итераций ни один из шагов не приводит к улучшению, номинальный размер шага уменьшается.
- Оптимизированный случайный поиск относительного размера шага (ORSSRS) Шрака и Чойта аппроксимирует оптимальный размер шага простым экспоненциальным уменьшением. Однако формула для вычисления коэффициента уменьшения несколько сложна.
Смотрите также
- Случайная оптимизация - это тесно связанное семейство методов оптимизации, которые выбирают из нормального распределения вместо гиперсферы.
- Luus – Jaakola - это тесно связанный метод оптимизации, использующий равномерное распределение в выборке и простую формулу для экспоненциального уменьшения диапазона выборки.
- Поиск по шаблону выполняет шаги по осям пространства поиска с использованием экспоненциально уменьшающихся размеров шага.