Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Методи стохастичної оптимізації CO це методи оптимізації які генерують і використовують випадкові величини Для стохастич

Стохастична оптимізація

Стохастична оптимізація

Методи стохастичної оптимізації (CO) — це методи оптимізації, які генерують і використовують випадкові величини. Для стохастичних задач випадкові величини з'являються у формулюванні самої задачі оптимізації, що включає випадкові цільові функції або випадкові обмеження (англ. constraints). Методи стохастичної оптимізації також включають методи з випадковими ітераціями. Деякі методи стохастичної оптимізації використовують випадкові ітерації для вирішення стохастичних задач, поєднуючи обидва значення стохастичної оптимізації. Методи стохастичної оптимізації узагальнюють детерміновані методи для детермінованих задач.

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

Частково-випадкові вхідні дані виникають під час процесу оцінювання та контролю у реальному часі, оптимізації на основі моделювання (при оцінюванні фактичної системи завдяки методу Монте-Карло) та в задачах, де присутня експериментальна (випадкова) похибка під час вимірювання критеріїв. У таких випадках знання про те, що серед значень функції присутній випадковий «шум», природньо призводить до алгоритмів, які використовують інструменти статистичного висновування для оцінки «справжніх» значень функції та/або прийняття статистично оптимальних рішень щодо наступних кроків. Методи цього класу включають:

Випадкові методи пошуку

Див. також: Метаевристика

З іншого боку, навіть коли набір даних складається з точних вимірювань, деякі методи вводять випадковість у процес пошуку для прискорення прогресу. Така випадковість також може зробити метод менш чутливим до похибок моделювання. Крім того, введена випадковість може дозволити методу уникнути локального оптимуму і в кінцевому підсумку наблизитися до глобального оптимуму. Дійсно, цей принцип рандомізації, як відомо, є простим та ефективним способом отримання алгоритмів із майже певною ефективністю для багатьох наборів даних багатьох видів задач. До таких методів стохастичної оптимізації належать:

Деякі автори навпаки стверджують, що рандомізація може покращити детермінований алгоритм лише в тому випадку, якщо він був погано розроблений з самого початку. [en] стверджує, що зловживання випадковими елементами може запобігти розвитку більш розумних і кращих детермінованих компонентів. Спосіб, яким зазвичай представлені результати алгоритмів стохастичної оптимізації (наприклад, представлення лише середнього або навіть найкращого з N запусків без жодної згадки про розповсюдження), також може призвести до позитивного зміщення у бік випадковості.

Див. також

Примітки

  1. Spall, J. C. (2003). Introduction to Stochastic Search and Optimization. Wiley. ISBN .
  2. Fu, M. C. (2002). Optimization for Simulation: Theory vs. Practice. INFORMS Journal on Computing. 14 (3): 192—227. doi:10.1287/ijoc.14.3.192.113.
  3. M.C. Campi and S. Garatti. The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs. SIAM J. on Optimization, 19, no.3: 1211—1230, 2008.
  4. Robbins, H.; Monro, S. (1951). A Stochastic Approximation Method. Annals of Mathematical Statistics. 22 (3): 400—407. doi:10.1214/aoms/1177729586.
  5. ; J. Wolfowitz (1952). Stochastic Estimation of the Maximum of a Regression Function. Annals of Mathematical Statistics. 23 (3): 462—466. doi:10.1214/aoms/1177729392.
  6. Spall, J. C. (1992). Multivariate Stochastic Approximation Using a Simultaneous Perturbation Gradient Approximation. IEEE Transactions on Automatic Control. 37 (3): 332—341.
  7. Holger H. Hoos and Thomas Stützle, Stochastic Local Search: Foundations and Applications, / Elsevier, 2004.
  8. S. Kirkpatrick; C. D. Gelatt; M. P. Vecchi (1983). Optimization by Simulated Annealing. Science. 220 (4598): 671—680. Bibcode:1983Sci...220..671K. PMID 17813860.
  9. D.H. Wolpert; S.R. Bieniawski; D.G. Rajnarayan (2011). Probability Collectives in Optimization. Santa Fe Institute.
  10. Battiti, Roberto; Gianpietro Tecchiolli (1994). The reactive tabu search (PDF). ORSA Journal on Computing. 6 (2): 126—140. doi:10.1287/ijoc.6.2.126.
  11. Battiti, Roberto; Mauro Brunato; Franco Mascia (2008). Reactive Search and Intelligent Optimization. Springer Verlag. ISBN .
  12. Rubinstein, R. Y.; Kroese, D. P. (2004). The Cross-Entropy Method. Springer-Verlag. ISBN .
  13. Zhigljavsky, A. A. (1991). Theory of Global Random Search. Kluwer Academic. ISBN .
  14. Kagan E.; Ben-Gal I. (2014). A Group-Testing Algorithm with Online Informational Learning. IIE Transactions. 46 (2): 164—184. doi:10.1080/0740817X.2013.803639.
  15. W. Wenzel; K. Hamacher (1999). Stochastic tunneling approach for global optimization of complex potential energy landscapes. Phys. Rev. Lett. 82 (15): 3003. arXiv:physics/9903008. Bibcode:1999PhRvL..82.3003W. doi:10.1103/PhysRevLett.82.3003.
  16. E. Marinari; G. Parisi (1992). Simulated tempering: A new monte carlo scheme. 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). . Addison-Wesley. ISBN . Архів оригіналу за 19 липня 2006.
  18. Tavridovich, S. A. (2017). COOMA: an object-oriented stochastic optimization algorithm. 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). Tabu search—uncharted domains. Annals of Operations Research. 149: 89—98.

Література

Посилання

  • COSP

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Metodi stohastichnoyi optimizaciyi CO ce metodi optimizaciyi yaki generuyut i vikoristovuyut vipadkovi velichini Dlya stohastichnih zadach vipadkovi velichini z yavlyayutsya u formulyuvanni samoyi zadachi optimizaciyi sho vklyuchaye vipadkovi cilovi funkciyi abo vipadkovi obmezhennya angl constraints Metodi stohastichnoyi optimizaciyi takozh vklyuchayut metodi z vipadkovimi iteraciyami Deyaki metodi stohastichnoyi optimizaciyi vikoristovuyut vipadkovi iteraciyi dlya virishennya stohastichnih zadach poyednuyuchi obidva znachennya stohastichnoyi optimizaciyi Metodi stohastichnoyi optimizaciyi uzagalnyuyut determinovani metodi dlya determinovanih zadach Metodi stohastichnih funkcijChastkovo vipadkovi vhidni dani vinikayut pid chas procesu ocinyuvannya ta kontrolyu u realnomu chasi optimizaciyi na osnovi modelyuvannya pri ocinyuvanni faktichnoyi sistemi zavdyaki metodu Monte Karlo ta v zadachah de prisutnya eksperimentalna vipadkova pohibka pid chas vimiryuvannya kriteriyiv U takih vipadkah znannya pro te sho sered znachen funkciyi prisutnij vipadkovij shum prirodno prizvodit do algoritmiv yaki vikoristovuyut instrumenti statistichnogo visnovuvannya dlya ocinki spravzhnih znachen funkciyi ta abo prijnyattya statistichno optimalnih rishen shodo nastupnih krokiv Metodi cogo klasu vklyuchayut en za Robbinsom i Monro 1951 stohastichnij gradiyentnij spusk skinchenno rizniceve stohastichne nablizhennya za Kiferom i Vulfovicem 1952 en za Spollom 1992 en Vipadkovi metodi poshukuDiv takozh Metaevristika Z inshogo boku navit koli nabir danih skladayetsya z tochnih vimiryuvan deyaki metodi vvodyat vipadkovist u proces poshuku dlya priskorennya progresu Taka vipadkovist takozh mozhe zrobiti metod mensh chutlivim do pohibok modelyuvannya Krim togo vvedena vipadkovist mozhe dozvoliti metodu uniknuti lokalnogo optimumu i v kincevomu pidsumku nablizitisya do globalnogo optimumu Dijsno cej princip randomizaciyi yak vidomo ye prostim ta efektivnim sposobom otrimannya algoritmiv iz majzhe pevnoyu efektivnistyu dlya bagatoh naboriv danih bagatoh vidiv zadach Do takih metodiv stohastichnoyi optimizaciyi nalezhat algoritm imitaciyi vidpalu za S Kirkpatrikom K D Gelattom i M P Vekki 1983 en kolektivi jmovirnostej za D H Volpertom S R Byenyavskim ta D G Radzhnarayanom 2011 en angl Reactive Search Optimization za en G Tekkiolli 1994 metod perehresnoyi entropiyi za Rubinshtejnom i en 2004 vipadkovij poshuk za en 1991 informacijnij poshuk en en abo obmin replikami en kolektivni algoritmi evolyucijni algoritmi genetichni algoritmi Hollanda 1975 evolyucijni strategiyi en optimizaciyi ta modifikaciyi ob yektiv 2016 Deyaki avtori navpaki stverdzhuyut sho randomizaciya mozhe pokrashiti determinovanij algoritm lishe v tomu vipadku yaksho vin buv pogano rozroblenij z samogo pochatku en stverdzhuye sho zlovzhivannya vipadkovimi elementami mozhe zapobigti rozvitku bilsh rozumnih i krashih determinovanih komponentiv Sposib yakim zazvichaj predstavleni rezultati algoritmiv stohastichnoyi optimizaciyi napriklad predstavlennya lishe serednogo abo navit najkrashogo z N zapuskiv bez zhodnoyi zgadki pro rozpovsyudzhennya takozh mozhe prizvesti do pozitivnogo zmishennya u bik vipadkovosti Div takozhGlobalna optimizaciya Mashinne navchannya en Gaussivskij proces Model prostoru staniv Upravlinnya z prognozuyuchimi modelyami Nelinijne programuvannya en PrimitkiSpall J C 2003 Introduction to Stochastic Search and Optimization Wiley ISBN 978 0 471 33052 3 Fu M C 2002 Optimization for Simulation Theory vs Practice INFORMS Journal on Computing 14 3 192 227 doi 10 1287 ijoc 14 3 192 113 M C Campi and S Garatti The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs SIAM J on Optimization 19 no 3 1211 1230 2008 Robbins H Monro S 1951 A Stochastic Approximation Method Annals of Mathematical Statistics 22 3 400 407 doi 10 1214 aoms 1177729586 J Wolfowitz 1952 Stochastic Estimation of the Maximum of a Regression Function Annals of Mathematical Statistics 23 3 462 466 doi 10 1214 aoms 1177729392 Spall J C 1992 Multivariate Stochastic Approximation Using a Simultaneous Perturbation Gradient Approximation IEEE Transactions on Automatic Control 37 3 332 341 Holger H Hoos and Thomas Stutzle Stochastic Local Search Foundations and Applications Elsevier 2004 S Kirkpatrick C D Gelatt M P Vecchi 1983 Optimization by Simulated Annealing Science 220 4598 671 680 Bibcode 1983Sci 220 671K PMID 17813860 D H Wolpert S R Bieniawski D G Rajnarayan 2011 Probability Collectives in Optimization Santa Fe Institute Battiti Roberto Gianpietro Tecchiolli 1994 The reactive tabu search PDF ORSA Journal on Computing 6 2 126 140 doi 10 1287 ijoc 6 2 126 Battiti Roberto Mauro Brunato Franco Mascia 2008 Reactive Search and Intelligent Optimization Springer Verlag ISBN 978 0 387 09623 0 Rubinstein R Y Kroese D P 2004 The Cross Entropy Method Springer Verlag ISBN 978 0 387 21240 1 Zhigljavsky A A 1991 Theory of Global Random Search Kluwer Academic ISBN 978 0 7923 1122 5 Kagan E Ben Gal I 2014 A Group Testing Algorithm with Online Informational Learning IIE Transactions 46 2 164 184 doi 10 1080 0740817X 2013 803639 W Wenzel K Hamacher 1999 Stochastic tunneling approach for global optimization of complex potential energy landscapes Phys Rev Lett 82 15 3003 arXiv physics 9903008 Bibcode 1999PhRvL 82 3003W doi 10 1103 PhysRevLett 82 3003 E Marinari G Parisi 1992 Simulated tempering A new monte carlo scheme Europhys Lett 19 6 451 458 arXiv hep lat 9205018 Bibcode 1992EL 19 451M doi 10 1209 0295 5075 19 6 002 Goldberg D E 1989 Addison Wesley ISBN 978 0 201 15767 3 Arhiv originalu za 19 lipnya 2006 Tavridovich S A 2017 COOMA an object oriented stochastic optimization algorithm International Journal of Advanced Studies 7 2 26 47 doi 10 12731 2227 930x 2017 2 26 47 http lesswrong com lw vp worse than random Glover F 2007 Tabu search uncharted domains Annals of Operations Research 149 89 98 LiteraturaMichalewicz Z and Fogel D B 2000 How to Solve It Modern Heuristics Springer Verlag New York PSA A novel optimization algorithm based on survival rules of porcellio scaber Y Zhang and S LiPosilannyaCOSP

Дата публікації:
Топ