Стохастическая оптимизация
Методы стохастической оптимизации ( СО ) — это оптимизации методы , которые генерируют и используют случайные величины . В стохастических задачах случайные величины появляются в формулировке самой задачи оптимизации, которая включает в себя случайные целевые функции или случайные ограничения. К методам стохастической оптимизации также относятся методы со случайными итерациями. Некоторые методы стохастической оптимизации используют случайные итерации для решения стохастических задач, сочетая оба значения стохастической оптимизации. [1] Методы стохастической оптимизации обобщают детерминированные методы для решения детерминированных задач.
Методы для стохастических функций
[ редактировать ]Частично случайные входные данные возникают в таких областях, как оценка и контроль в реальном времени, оптимизация на основе моделирования, где моделирование Монте-Карло запускается как оценка реальной системы. [2] [3] и задачи, в которых имеется экспериментальная (случайная) ошибка измерения критерия. В таких случаях знание того, что значения функции загрязнены случайным «шумом», естественным образом приводит к алгоритмам, которые используют инструменты статистического вывода для оценки «истинных» значений функции и/или принятия статистически оптимальных решений о следующих шагах. К методам этого класса относятся:
- стохастическая аппроксимация (СА) Роббинса и Монро (1951). [4]
- стохастический градиентный спуск
- конечных разностях SA в Кифера и Вулфовица (1952) [5]
- одновременное возмущение SA по Споллу (1992) [6]
- оптимизация сценария
Методы рандомизированного поиска
[ редактировать ]С другой стороны, даже если набор данных состоит из точных измерений, некоторые методы вносят случайность в процесс поиска, чтобы ускорить прогресс. [7] Такая случайность также может сделать метод менее чувствительным к ошибкам моделирования. Еще одним преимуществом является то, что случайность в процессе поиска может использоваться для получения интервальных оценок минимума функции с помощью статистики экстремальных значений. [8] [9] Кроме того, введенная случайность может позволить методу избежать локального оптимума и в конечном итоге приблизиться к глобальному оптимуму. Действительно, этот принцип рандомизации известен как простой и эффективный способ получить алгоритмы с почти наверняка хорошей производительностью и равномерно для многих наборов данных для решения многих видов задач. К методам стохастической оптимизации такого рода относятся:
- имитация отжига С. Киркпатриком, К.Д. Гелаттом и М.П. Векки (1983). [10]
- квантовый отжиг
- Коллективы вероятностей Д. Х. Вулперта, С. Р. Бенявского и Д. Г. Раджнараяна (2011) [11]
- реактивная поисковая оптимизация (RSO) , Роберто Баттити Дж. Теккиолли (1994), [12] недавно просмотрено в справочнике [13]
- метод перекрестной энтропии Рубинштейна ( и Крозе 2004) [14]
- случайный поиск Анатолия Жиглявского (1991) [15]
- Информационный поиск [16]
- стохастическое туннелирование [17]
- параллельная закалка или обмен репликами [18]
- стохастическое восхождение на холм
- роевые алгоритмы
- эволюционные алгоритмы
- генетические алгоритмы Холланда (1975) [19]
- стратегии эволюции
- алгоритм каскадной оптимизации и модификации объектов (2016) [20]
Напротив, некоторые авторы утверждают, что рандомизация может улучшить детерминированный алгоритм только в том случае, если детерминированный алгоритм изначально был плохо спроектирован. [21] Фред В. Гловер [22] утверждает, что использование случайных элементов может помешать разработке более интеллектуальных и детерминированных компонентов. Способ, которым обычно представляются результаты алгоритмов стохастической оптимизации (например, представление только среднего или даже лучшего из N прогонов без какого-либо упоминания о разбросе), также может привести к положительному смещению в сторону случайности.
См. также
[ редактировать ]- Глобальная оптимизация
- Машинное обучение
- Оптимизация сценария
- Гауссов процесс
- Государственная космическая модель
- Модель прогнозирующего управления
- Нелинейное программирование
- Энтропийное значение под угрозой
Ссылки
[ редактировать ]- ^ Сполл, Дж. К. (2003). Введение в стохастический поиск и оптимизацию . Уайли. ISBN 978-0-471-33052-3 .
- ^ Фу, MC (2002). «Оптимизация для моделирования: теория против практики». ИНФОРМС Журнал по вычислительной технике . 14 (3): 192–227. дои : 10.1287/ijoc.14.3.192.113 .
- ^ MC Кампи и С. Гаратти. Точная осуществимость рандомизированных решений неопределенных выпуклых программ. SIAM J. on Optimization, 19, № 3: 1211–1230, 2008. [1]
- ^ Роббинс, Х.; Монро, С. (1951). «Метод стохастической аппроксимации» . Анналы математической статистики . 22 (3): 400–407. дои : 10.1214/aoms/1177729586 .
- ^ Дж. Кифер ; Дж. Вулфовиц (1952). «Стохастическая оценка максимума функции регрессии» . Анналы математической статистики . 23 (3): 462–466. дои : 10.1214/aoms/1177729392 .
- ^ Сполл, Дж. К. (1992). «Многомерная стохастическая аппроксимация с использованием одновременной аппроксимации градиента возмущений» . Транзакции IEEE при автоматическом управлении . 37 (3): 332–341. CiteSeerX 10.1.1.19.4562 . дои : 10.1109/9.119632 .
- ^ Хольгер Х. Хоос и Томас Штютцле, Стохастический локальный поиск: основы и приложения , Морган Кауфманн / Elsevier , 2004.
- ^ М. де Карвальо (2011). «Доверительные интервалы для минимума функции с использованием статистики экстремальных значений» (PDF) . Международный журнал математического моделирования и численной оптимизации . 2 (3): 288–296. дои : 10.1504/IJMMNO.2011.040793 .
- ^ М. де Карвалью (2012). «Обобщение метода Солиса-Ветса» (PDF) . Журнал статистического планирования и выводов . 142 (3): 633–644. дои : 10.1016/j.jspi.2011.08.016 .
- ^ С. Киркпатрик; CD Гелатт; Депутат Векки (1983). «Оптимизация путем моделирования отжига» . Наука . 220 (4598): 671–680. Бибкод : 1983Sci...220..671K . CiteSeerX 10.1.1.123.7607 . дои : 10.1126/science.220.4598.671 . ПМИД 17813860 . S2CID 205939 .
- ^ Д. Х. Вулперт; С.Р. Бенявский; Д.Г. Раджнараян (2011). «Коллективы вероятностей в оптимизации» . Институт Санта-Фе .
- ^ Баттити, Роберто; Джанпьетро Теккиолли (1994). «Реактивный табу-поиск» (PDF) . Журнал ORSA по вычислительной технике . 6 (2): 126–140. дои : 10.1287/ijoc.6.2.126 .
- ^ Баттити, Роберто; Мауро Брунато; Франко Массия (2008). Реактивный поиск и интеллектуальная оптимизация . Спрингер Верлаг . ISBN 978-0-387-09623-0 .
- ^ Рубинштейн, RY ; Крозе, Д.П. (2004). Метод перекрестной энтропии . Спрингер-Верлаг. ISBN 978-0-387-21240-1 .
- ^ Жиглявский, А.А. (1991). Теория глобального случайного поиска . Клювер Академик. ISBN 978-0-7923-1122-5 .
- ^ Каган Э.; Бен-Гал И. (2014). «Алгоритм группового тестирования с информационным онлайн-обучением». Операции IIE . 46 (2): 164–184. дои : 10.1080/0740817X.2013.803639 . S2CID 18588494 .
- ^ В. Венцель; К. Хамахер (1999). «Стохастический туннельный подход для глобальной оптимизации сложных потенциальных энергетических ландшафтов». Физ. Преподобный Летт . 82 (15): 3003. arXiv : Physics/9903008 . Бибкод : 1999PhRvL..82.3003W . doi : 10.1103/PhysRevLett.82.3003 . S2CID 5113626 .
- ^ Э. Маринари; Г. Паризи (1992). «Имитация закалки: новая схема Монте-Карло». Еврофиз. Летт . 19 (6): 451–458. arXiv : hep-lat/9205018 . Бибкод : 1992EL.....19..451M . дои : 10.1209/0295-5075/19/6/002 . S2CID 12321327 .
- ^ Гольдберг, Делавэр (1989). Генетические алгоритмы в поиске, оптимизации и машинном обучении . Аддисон-Уэсли. ISBN 978-0-201-15767-3 . Архивировано из оригинала 19 июля 2006 г.
- ^ Тавридович, С.А. (2017). «COOMA: объектно-ориентированный алгоритм стохастической оптимизации» . Международный журнал перспективных исследований . 7 (2): 26–47. дои : 10.12731/2227-930x-2017-2-26-47 .
- ^ Юдковский, Элиэзер. «Хуже, чем случайное — меньше неправильного» .
- ^ Гловер, Ф. (2007). «Табу-поиск - неизведанные домены». Анналы исследования операций . 149 : 89–98. CiteSeerX 10.1.1.417.8223 . дои : 10.1007/s10479-006-0113-9 . S2CID 6854578 .
Дальнейшее чтение
[ редактировать ]- Михалевич З. и Фогель Д.Б. (2000), « Как решить проблему: современная эвристика» , Springer-Verlag, Нью-Йорк.