Jump to content

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

(Перенаправлено со стохастического поиска )

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

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

[ редактировать ]

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

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

[ редактировать ]

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

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

См. также

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

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

[ редактировать ]
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 47b6b47d5d990de9bb61d9711ef3a4b4__1708459380
URL1:https://arc.ask3.ru/arc/aa/47/b4/47b6b47d5d990de9bb61d9711ef3a4b4.html
Заголовок, (Title) документа по адресу, URL1:
Stochastic optimization - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)