Стохастическая оптимизация - Stochastic optimization

Эта статья о итерационные методы. Для моделирования (и оптимизации) решений в условиях неопределенности см. стохастическое программирование. В контексте теории управления см. стохастический контроль.

Стохастическая оптимизация (ТАК) методы оптимизация методы которые создают и используют случайные переменные. Для стохастических задач случайные величины появляются в формулировке самой задачи оптимизации, которая включает случайные целевые функции или случайные ограничения. К методам стохастической оптимизации также относятся методы со случайными итерациями. Некоторые методы стохастической оптимизации используют случайные итерации для решения стохастических задач, объединяя оба значения стохастической оптимизации.[1]Методы стохастической оптимизации обобщают детерминированный методы для детерминированных задач.

Методы стохастических функций

Частично случайные входные данные возникают в таких областях, как оценка и управление в реальном времени, оптимизация на основе моделирования, где Моделирование Монте-Карло выполняются как оценки реальной системы,[2] [3] и проблемы, в которых есть экспериментальная (случайная) ошибка в измерениях критерия. В таких случаях знание того, что значения функции загрязнены случайным «шумом», естественным образом приводит к алгоритмам, использующим статистические выводы инструменты для оценки «истинных» значений функции и / или принятия статистически оптимальных решений о следующих шагах. К методам этого класса относятся:

Рандомизированные методы поиска

Смотрите также: Метаэвристический

С другой стороны, даже когда набор данных состоит из точных измерений, некоторые методы вносят случайность в процесс поиска для ускорения прогресса.[7] Такая случайность также может сделать метод менее чувствительным к ошибкам моделирования. Кроме того, введенная случайность может позволить способу выйти из локального оптимума и в конечном итоге приблизиться к глобальному оптимуму. Действительно, это рандомизация принцип известен как простой и эффективный способ получения алгоритмов с почти наверняка хорошая производительность, одинаковая для многих наборов данных, для многих видов проблем. К таким методам стохастической оптимизации относятся:

Напротив, некоторые авторы утверждали, что рандомизация может улучшить детерминированный алгоритм, только если детерминированный алгоритм изначально был плохо спроектирован.[19] Фред В. Гловер [20] утверждает, что использование случайных элементов может помешать разработке более интеллектуальных и более детерминированных компонентов. Способ, которым обычно представлены результаты алгоритмов стохастической оптимизации (например, представляя только среднее или даже лучшее из N прогонов без какого-либо упоминания о разбросе), также может привести к положительному смещению в сторону случайности.

Смотрите также

Рекомендации

  1. ^ Сполл, Дж. К. (2003). Введение в стохастический поиск и оптимизацию. Вайли. ISBN  978-0-471-33052-3.
  2. ^ Фу, М. С. (2002). «Оптимизация для моделирования: теория против практики». ИНФОРМС Журнал по вычислительной технике. 14 (3): 192–227. Дои:10.1287 / ijoc.14.3.192.113.
  3. ^ M.C. Кампи и С. Гаратти. Точная выполнимость рандомизированных решений неопределенно выпуклых программ. SIAM J. по оптимизации, 19, № 3: 1211–1230, 2008.[1]
  4. ^ Роббинс, H .; Монро, С. (1951). «Метод стохастической аппроксимации». Анналы математической статистики. 22 (3): 400–407. Дои:10.1214 / aoms / 1177729586.
  5. ^ Дж. Кифер; Дж. Вулфовиц (1952). «Стохастическая оценка максимума функции регрессии». Анналы математической статистики. 23 (3): 462–466. Дои:10.1214 / aoms / 1177729392.
  6. ^ Сполл, Дж. К. (1992). "Многомерная стохастическая аппроксимация с использованием градиентной аппроксимации одновременных возмущений". IEEE Transactions по автоматическому контролю. 37 (3): 332–341. CiteSeerX  10.1.1.19.4562. Дои:10.1109/9.119632.
  7. ^ Хольгер Х. Хус и Томас Штютцле, Стохастический локальный поиск: основы и приложения, Морган Кауфманн / Эльзевир, 2004.
  8. ^ С. Киркпатрик; К. Д. Гелатт; М. П. Векки (1983). «Оптимизация путем имитации отжига». Наука. 220 (4598): 671–680. Bibcode:1983Научный ... 220..671K. CiteSeerX  10.1.1.123.7607. Дои:10.1126 / science.220.4598.671. PMID  17813860.
  9. ^ Д. Х. Вольперт; S.R. Бенявский; Д.Г. Раджнараян (2011). C.R. Rao; В. Говиндараджу (ред.). "Коллективы вероятностей в оптимизации". Цитировать журнал требует | журнал = (помощь)CS1 maint: несколько имен: список редакторов (связь)
  10. ^ Баттити, Роберто; Джанпьетро Теккиолли (1994). «Реактивный табу-поиск» (PDF). Журнал ORSA по вычислительной технике. 6 (2): 126–140. Дои:10.1287 / ijoc.6.2.126.
  11. ^ Баттити, Роберто; Мауро Брунато; Франко Маскиа (2008). Реактивный поиск и интеллектуальная оптимизация. Springer Verlag. ISBN  978-0-387-09623-0.
  12. ^ Рубинштейн, Р. Ю.; Круз, Д. П. (2004). Метод кросс-энтропии. Springer-Verlag. ISBN  978-0-387-21240-1.
  13. ^ Жиглявский, А.А. (1991). Теория глобального случайного поиска. Kluwer Academic. ISBN  978-0-7923-1122-5.
  14. ^ Каган Э., Бен-Гал И. (2014). «Алгоритм группового тестирования с интерактивным информационным обучением» (PDF). IIE Transactions, 46: 2, 164-184. Цитировать журнал требует | журнал = (помощь)
  15. ^ В. Венцель; К. Хамахер (1999). «Стохастический туннельный подход для глобальной оптимизации сложных ландшафтов потенциальной энергии». Phys. Rev. Lett. 82 (15): 3003. arXiv:физика / 9903008. Bibcode:1999PhRvL..82.3003W. Дои:10.1103 / PhysRevLett.82.3003.
  16. ^ Э. Маринари; Г. Паризи (1992). «Имитация темперирования: новая схема Монте-Карло». Europhys. Латыш. 19 (6): 451–458. arXiv:геп-лат / 9205018. Bibcode:1992ЭЛ ..... 19..451М. Дои:10.1209/0295-5075/19/6/002.
  17. ^ Голдберг, Д. Э. (1989). Генетические алгоритмы в поиске, оптимизации и машинном обучении. Эддисон-Уэсли. ISBN  978-0-201-15767-3. Архивировано из оригинал 19 июля 2006 г.
  18. ^ Тавридович, С. А. (2017). «COOMA: объектно-ориентированный алгоритм стохастической оптимизации». Международный журнал перспективных исследований. 7 (2): 26–47. Дои:10.12731 / 2227-930x-2017-2-26-47.
  19. ^ http://lesswrong.com/lw/vp/worse_than_random/
  20. ^ Гловер, Ф. (2007). «Табу-поиск - неизведанные области». Анналы исследований операций. 149: 89–98. CiteSeerX  10.1.1.417.8223. Дои:10.1007 / s10479-006-0113-9.

дальнейшее чтение

внешняя ссылка