확률적 최적화

Stochastic optimization
이 글은 반복적인 방법에 관한 것이다. 불확실한 상태에서 의사결정을 모델링(및 최적화)하려면 확률적 프로그래밍을 참조하십시오. 제어 이론의 맥락은 확률적 제어를 참조하십시오.

확률적 최적화(SO) 방법은 랜덤 변수를 생성하고 사용하는 최적화 방법이다. 확률적 문제의 경우 무작위 변수는 무작위 목적 함수 또는 무작위 제약 조건을 포함하는 최적화 문제 자체의 공식에 나타난다. 확률적 최적화 방법에는 무작위 반복이 있는 방법들도 포함된다. 일부 확률적 최적화 방법은 확률적 최적화의 두 의미를 결합하여 확률적 문제를 해결하기 위해 무작위 반복을 사용한다.[1] 확률적 최적화 방법은 결정론적 문제에 대한 결정론적 방법을 일반화한다.

확률 함수 방법

부분적인 무작위 입력 데이터는 실시간 추정 및 제어, 몬테카를로 시뮬레이션을 실제 시스템의 추정치로 실행하는 시뮬레이션 기반 최적화,[2] 기준 측정에 실험(랜덤) 오류가 있는 문제 등에서 발생한다. 이러한 경우 함수 값이 무작위 "소음"에 의해 오염된다는 지식은 자연스럽게 통계적 추론 도구를 사용하여 함수의 "진정한" 값을 추정하거나 다음 단계에 대해 통계적으로 최적의 결정을 내리는 알고리즘으로 이어진다. 이 세분류의 방법에는 다음이 포함된다.

임의 검색 방법

참고 항목: 메타휴리스틱

한편, 데이터 세트가 정밀한 측정으로 구성된 경우에도, 일부 방법은 진행 속도를 높이기 위해 검색 프로세스에 랜덤성을 도입한다.[7] 그러한 무작위성은 또한 방법을 모델링 오류에 덜 민감하게 만들 수 있다. 또한 주입된 무작위성은 국소 최적에서 벗어나 결국 글로벌 최적치에 근접하는 방법을 가능하게 할 수 있다. 실제로, 이러한 무작위화 원리는 많은 종류의 문제에 대해 많은 데이터 집합에 걸쳐 거의 일정한 우수한 성능을 가진 알고리즘을 얻는 간단하고 효과적인 방법이라고 알려져 있다. 이러한 종류의 확률적 최적화 방법에는 다음이 포함된다.

이와는 대조적으로, 일부 저자들은 무작위화가 결정론적 알고리즘이 애초에 제대로 설계되지 않은 경우에만 결정론적 알고리즘을 개선할 수 있다고 주장해왔다.[19] Fred W. Glover는[20] 무작위 요소에 의존하는 것이 더 지적이고 더 나은 결정론적 요소의 개발을 방해할 수 있다고 주장한다. 확률적 최적화 알고리즘의 결과가 대개 제시되는 방식(예를 들어, 확산에 대한 언급 없이 N 런 중에서 평균 또는 최고만을 제시하는 방식)도 무작위성에 대한 긍정적 편향을 초래할 수 있다.

참고 항목

참조

  1. ^ Spall, J. C. (2003). Introduction to Stochastic Search and Optimization. Wiley. ISBN 978-0-471-33052-3.
  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. 캄피와 S. 가랏티. 불확실한 볼록 프로그램의 무작위 해결의 정확한 타당성 최적화 관련 SIAM J. 19, 3번: 1211–1230, 2008.[1]
  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. Kiefer; 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. CiteSeerX 10.1.1.19.4562. doi:10.1109/9.119632.
  7. ^ 홀거 H. Hohs and Thomas Stüzle, Stochastic Local Search: 기초와 응용, Morgan Kaufmann / Exvier, 2004.
  8. ^ S. Kirkpatrick; C. D. Gelatt; M. P. Vecchi (1983). "Optimization by Simulated Annealing". Science. 220 (4598): 671–680. Bibcode:1983Sci...220..671K. CiteSeerX 10.1.1.123.7607. doi:10.1126/science.220.4598.671. PMID 17813860. S2CID 205939.
  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 978-0-387-09623-0.
  12. ^ Rubinstein, R. Y.; Kroese, D. P. (2004). The Cross-Entropy Method. Springer-Verlag. ISBN 978-0-387-21240-1.
  13. ^ Zhigljavsky, A. A. (1991). Theory of Global Random Search. Kluwer Academic. ISBN 978-0-7923-1122-5.
  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. S2CID 18588494.
  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. S2CID 5113626.
  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. S2CID 12321327.
  17. ^ Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley. ISBN 978-0-201-15767-3. Archived from the original on 2006-07-19.
  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. CiteSeerX 10.1.1.417.8223. doi:10.1007/s10479-006-0113-9. S2CID 6854578.

추가 읽기

외부 링크