Стохастическая оптимизация - Stochastic optimization
Стохастическая оптимизация ( SO ) метода оптимизация методы , которые генерируют и используют случайные переменные . Для стохастических задач случайные величины появляются в формулировке самой задачи оптимизации, которая включает случайные целевые функции или случайные ограничения. К методам стохастической оптимизации также относятся методы со случайными итерациями. Некоторые методы стохастической оптимизации используют случайные итерации для решения стохастических задач, объединяя оба значения стохастической оптимизации. Методы стохастической оптимизации обобщают детерминированные методы для детерминированных задач.
Методы для стохастических функций
Частично случайные входные данные возникают в таких областях, как оценка и управление в реальном времени, оптимизация на основе моделирования, когда моделирование методом Монте-Карло выполняется как оценки реальной системы, а также проблемы, при которых существует экспериментальная (случайная) ошибка в измерениях критерия. В таких случаях знание того, что значения функции загрязнены случайным «шумом», естественным образом приводит к алгоритмам, которые используют инструменты статистического вывода для оценки «истинных» значений функции и / или принятия статистически оптимальных решений относительно следующих шагов. К методам этого класса относятся:
- стохастическая аппроксимация (SA), Роббинс и Монро (1951)
- стохастический градиентный спуск
- конечно-разностная СА Кифера и Вулфовица (1952)
- одновременное возмущение SA по Споллу (1992)
- оптимизация сценария
Рандомизированные методы поиска
С другой стороны, даже когда набор данных состоит из точных измерений, некоторые методы вводят случайность в процесс поиска для ускорения прогресса. Такая случайность также может сделать метод менее чувствительным к ошибкам моделирования. Кроме того, введенная случайность может позволить способу выйти из локального оптимума и в конечном итоге приблизиться к глобальному оптимуму. В самом деле, этот принцип рандомизации, как известно, является простым и эффективным способом получения алгоритмов с почти гарантированной хорошей производительностью равномерно по множеству наборов данных для многих видов проблем. К таким методам стохастической оптимизации относятся:
- моделирование отжига С. Киркпатрик, С. Д. Гелатт и М. П. Векки (1983)
- квантовый отжиг
- Коллективы вероятностей Д.Х. Вольперта, С.Р. Бенявского и Д.Г. Раджнараяна (2011)
- реактивная поисковая оптимизация (RSO) от Роберто Баттити , Г. Tecchiolli (1994), недавно рассмотрела в справочнике
- кросс-энтропийный метод Рубинштейна и Крозе (2004)
- случайный поиск по Анатолию Зхиглхавски (1991)
- Информационный поиск
- стохастическое туннелирование
- параллельное темперирование, также известное как обмен репликами
- стохастическое восхождение на холм
- алгоритмы роя
-
эволюционные алгоритмы
- генетические алгоритмы Голландии (1975)
- стратегии эволюции
- каскадный алгоритм оптимизации и модификации объекта (2016)
Напротив, некоторые авторы утверждали, что рандомизация может улучшить детерминированный алгоритм только в том случае, если детерминированный алгоритм изначально был плохо спроектирован. Фред В. Гловер утверждает, что использование случайных элементов может помешать разработке более интеллектуальных и более детерминированных компонентов. Способ, которым обычно представлены результаты алгоритмов стохастической оптимизации (например, представление только среднего или даже лучшего из N прогонов без какого-либо упоминания о разбросе), также может привести к положительному смещению в сторону случайности.
Смотрите также
- Глобальная оптимизация
- Машинное обучение
- Оптимизация сценария
- Гауссовский процесс
- Модель государственного пространства
- Прогностический контроль модели
- Нелинейное программирование
- Энтропийная ценность под угрозой
Рекомендации
дальнейшее чтение
- Михалевич З. и Фогель Д. Б. (2000), Как решить: современная эвристика , Springer-Verlag, Нью-Йорк.
- « PSA: новый алгоритм оптимизации, основанный на правилах выживания porcellio scaber », Ю. Чжан и С. Ли