Случайная оптимизация - Random optimization
Случайная оптимизация (RO) семейство числовых оптимизация методы, не требующие градиент проблемы, которая должна быть оптимизирована, и, следовательно, RO можно использовать для функций, которые не непрерывный или же дифференцируемый. Такие методы оптимизации также известны как методы прямого поиска, методы без производных или методы черного ящика.
Название случайная оптимизация приписывается Матиасу [1] кто сделал раннее представление RO вместе с основным математическим анализом. RO работает, итеративно перемещаясь к лучшим позициям в пространстве поиска, которые выбираются с использованием, например, а нормальное распределение вокруг текущей позиции.
Алгоритм
Позволять ж: ℝп → ℝ - функция пригодности или стоимости, которую необходимо минимизировать. Позволять Икс ∈ ℝп обозначить позицию или вариант решения в поисковой области. Тогда основной алгоритм RO можно описать как:
- Инициализировать Икс со случайной позицией в пространстве поиска.
- До тех пор, пока не будет выполнен критерий завершения (например, количество выполненных итераций или достижение адекватной пригодности), повторите следующее:
- Образец новой позиции у добавив нормально распределенный случайный вектор в текущую позицию Икс
- Если (ж(у) < ж(Икс)) затем перейдите в новую позицию, установив Икс = у
- Сейчас же Икс занимает лучшую позицию.
Этот алгоритм соответствует (1 + 1) стратегия эволюции с постоянным размером шага.
Схождение и варианты
Матиас показал, что базовая форма РО сходится к оптимуму простого унимодальная функция используя предельно стойкий который показывает, что сходимость к оптимуму обязательно произойдет, если будет выполнено потенциально бесконечное количество итераций. Однако это доказательство бесполезно на практике, потому что может быть выполнено только конечное число итераций. Фактически, такое теоретическое доказательство предела также покажет, что чисто случайная выборка пространства поиска неизбежно приведет к выборке, сколь угодно близкой к оптимальной.
Математический анализ также проводит Баба. [2] и Солис и Уэтс [3] установить, что конвергенция к области, окружающей оптимум, неизбежна при некоторых мягких условиях для вариантов RO, использующих другие распределения вероятностей для отбора проб. Оценка количества итераций, необходимых для достижения оптимума, получена Dorea.[4] Сарма критикует эти анализы посредством эмпирических экспериментов. [5] который использовал варианты оптимизатора Бабы и Дореи для решения двух реальных проблем, показывая, что к оптимуму нужно подходить очень медленно, и, кроме того, эти методы фактически не могли найти решение адекватной пригодности, если только процесс не был запущен достаточно близко к оптимуму. начать с.
Смотрите также
- Случайный поиск - это тесно связанное семейство методов оптимизации, выборка которых гиперсфера вместо нормального распределения.
- Луус – Яакола является тесно связанным методом оптимизации с использованием равномерное распределение в его выборке и простой формуле для экспоненциального уменьшения диапазона выборки.
- Поиск по шаблону выполняет шаги по осям пространства поиска, используя экспоненциально уменьшающиеся размеры шага.
- Стохастическая оптимизация
Рекомендации
- ^ Матиас, Дж. (1965). «Случайная оптимизация». Автоматизация и дистанционное управление. 26 (2): 246–253.
- ^ Баба, Н. (1981). «Сходимость метода случайной оптимизации для задач оптимизации с ограничениями». Журнал теории оптимизации и приложений. 33 (4): 451–461. Дои:10.1007 / bf00935752.
- ^ Solis, F.J .; Мокрый, R.J-B. (1981). «Минимизация методами случайного поиска». Математика исследования операций. 6 (1): 19–30. Дои:10.1287 / moor.6.1.19.
- ^ Дореа, C.C.Y. (1983). «Ожидаемое количество шагов случайного метода оптимизации». Журнал теории оптимизации и приложений. 39 (3): 165–171. Дои:10.1007 / bf00934526.
- ^ Сарма, М. (1990). «О сходимости методов случайной оптимизации Бабы и Дореи». Журнал теории оптимизации и приложений. 66 (2): 337–343. Дои:10.1007 / bf00939542.