Stochastická optimalizace - Stochastic optimization - Wikipedia

Tento článek je o iterační metody. Modelování (a optimalizace) rozhodnutí za nejistoty viz stochastické programování. Kontext teorie řízení viz stochastická kontrola.

Stochastická optimalizace (TAK) metody jsou optimalizace metody které generují a používají náhodné proměnné. U stochastických problémů se náhodné proměnné objevují ve formulaci samotného problému optimalizace, který zahrnuje náhodné objektivní funkce nebo náhodná omezení. Stochastické optimalizační metody zahrnují také metody s náhodnými iteracemi. Některé metody stochastické optimalizace používají k řešení stochastických problémů náhodné iterace, které kombinují oba významy stochastické optimalizace.[1]Metody stochastické optimalizace se zobecňují deterministický metody pro deterministické problémy.

Metody pro stochastické funkce

Částečně náhodná vstupní data vznikají v takových oblastech, jako je odhad a řízení v reálném čase, kde je optimalizace založená na simulaci Simulace Monte Carlo jsou spuštěny jako odhady skutečného systému,[2] [3] a problémy, u kterých došlo k experimentální (náhodné) chybě v měření kritéria. V takových případech vede znalost, že funkční hodnoty jsou kontaminovány náhodným „šumem“, přirozeně k použitým algoritmům statistická inference nástroje pro odhad „skutečných“ hodnot funkce a / nebo pro statisticky optimální rozhodnutí o dalších krocích. Mezi metody této třídy patří:

Náhodné metody vyhledávání

Viz také: Metaheuristické

Na druhou stranu, i když soubor dat Skládá se z přesných měření, některé metody zavádějí do procesu hledání náhodnost, aby se urychlil pokrok.[7] Taková náhodnost může také snížit citlivost metody na chyby modelování. Vložená náhodnost může dále umožnit metodě uniknout z lokálního optima a nakonec se přiblížit globálnímu optimu. Opravdu tohle randomizace Princip je znám jako jednoduchý a efektivní způsob získávání algoritmů pomocí skoro jistý dobrý výkon rovnoměrně napříč mnoha datovými sadami pro mnoho druhů problémů. Stochastické optimalizační metody tohoto druhu zahrnují:

Na rozdíl od toho někteří autoři tvrdili, že randomizace může vylepšit deterministický algoritmus, pouze pokud byl deterministický algoritmus nejprve špatně navržen.[19] Fred W. Glover [20] tvrdí, že spoléhání se na náhodné prvky může bránit vývoji inteligentnějších a lépe deterministických složek. Způsob, jakým jsou obvykle prezentovány výsledky stochastických optimalizačních algoritmů (např. Prezentace pouze průměrných nebo dokonce nejlepších z N běhů bez jakékoli zmínky o rozpětí), může také vést k pozitivnímu zkreslení směrem k náhodnosti.

Viz také

Reference

  1. ^ Spall, J. C. (2003). Úvod do stochastického vyhledávání a optimalizace. Wiley. ISBN  978-0-471-33052-3.
  2. ^ Fu, M. C. (2002). "Optimalizace pro simulaci: Teorie vs. praxe". INFORMS Journal o práci na počítači. 14 (3): 192–227. doi:10.1287 / ijoc.14.3.192.113.
  3. ^ M.C. Campi a S. Garatti. Přesná proveditelnost náhodných řešení nejistých konvexních programů. SIAM J. on Optimization, 19, no. 3: 1211–1230, 2008.[1]
  4. ^ Robbins, H .; Monro, S. (1951). „Metoda stochastické aproximace“. Annals of Mathematical Statistics. 22 (3): 400–407. doi:10.1214 / aoms / 1177729586.
  5. ^ J. Kiefer; J. Wolfowitz (1952). „Stochastický odhad maxima regresní funkce“. Annals of Mathematical Statistics. 23 (3): 462–466. doi:10.1214 / aoms / 1177729392.
  6. ^ Spall, J. C. (1992). „Mnohorozměrná stochastická aproximace pomocí simulace simulace simultánní odchylky přechodu“. Transakce IEEE na automatickém ovládání. 37 (3): 332–341. CiteSeerX  10.1.1.19.4562. doi:10.1109/9.119632.
  7. ^ Holger H. Hoos a Thomas Stützle, Stochastické místní vyhledávání: Nadace a aplikace, Morgan Kaufmann / Elsevier, 2004.
  8. ^ S. Kirkpatrick; C. D. Gelatt; M. P. Vecchi (1983). „Optimalizace simulovaným žíháním“. Věda. 220 (4598): 671–680. Bibcode:1983Sci ... 220..671K. CiteSeerX  10.1.1.123.7607. doi:10.1126 / science.220.4598.671. PMID  17813860.
  9. ^ D.H. Wolpert; S.R. Bieniawski; D.G. Rajnarayan (2011). CR Rao; V. Govindaraju (ed.). „Pravděpodobné kolektivy v optimalizaci“. Citovat deník vyžaduje | deník = (Pomoc)CS1 maint: více jmen: seznam editorů (odkaz)
  10. ^ Battiti, Roberto; Gianpietro Tecchiolli (1994). „Reaktivní vyhledávání tabu“ (PDF). ORSA Journal on Computing. 6 (2): 126–140. doi:10.1287 / ijoc.6.2.126.
  11. ^ Battiti, Roberto; Mauro Brunato; Franco Mascia (2008). Reaktivní vyhledávání a inteligentní optimalizace. Springer Verlag. ISBN  978-0-387-09623-0.
  12. ^ Rubinstein, R. Y .; Kroese, D. P. (2004). Metoda křížové entropie. Springer-Verlag. ISBN  978-0-387-21240-1.
  13. ^ Zhigljavsky, A. A. (1991). Teorie globálního náhodného vyhledávání. Kluwer Academic. ISBN  978-0-7923-1122-5.
  14. ^ Kagan E. a Ben-Gal I. (2014). „Algoritmus skupinového testování s online informačním učením“ (PDF). Transakce IIE, 46: 2, 164-184. Citovat deník vyžaduje | deník = (Pomoc)
  15. ^ W. Wenzel; K. Hamacher (1999). „Stochastický tunelovací přístup pro globální optimalizaci složitých potenciálních energetických krajin“. Phys. Rev. Lett. 82 (15): 3003. arXiv:fyzika / 9903008. Bibcode:1999PhRvL..82.3003W. doi:10.1103 / PhysRevLett.82.3003.
  16. ^ E. Marinari; G. Parisi (1992). "Simulované temperování: Nové schéma Monte Carlo". Europhys. Lett. 19 (6): 451–458. arXiv:hep-lat / 9205018. Bibcode:1992EL ..... 19..451M. doi:10.1209/0295-5075/19/6/002.
  17. ^ Goldberg, D. E. (1989). Genetické algoritmy ve vyhledávání, optimalizaci a strojovém učení. Addison-Wesley. ISBN  978-0-201-15767-3. Archivovány od originál dne 19. 7. 2006.
  18. ^ Tavridovich, S.A. (2017). „COOMA: objektově orientovaný stochastický optimalizační algoritmus“. International Journal of Advanced Studies. 7 (2): 26–47. doi:10.12731 / 2227-930x-2017-2-26-47.
  19. ^ http://lesswrong.com/lw/vp/worse_than_random/
  20. ^ Glover, F. (2007). "Vyhledávání v Tabu - nezmapované domény". Annals of Operations Research. 149: 89–98. CiteSeerX  10.1.1.417.8223. doi:10.1007 / s10479-006-0113-9.

Další čtení

externí odkazy