Στοχαστική Βελτιστοποίηση
Μέθοδοι στοχαστικής βελτιστοποίησης ονομάζονται οι μέθοδοι βελτιστοποίησης που παράγουν και χρησιμοποιούν τυχαίες μεταβλητές. Περιλαμβάνουν τις μεθόδους επίλυσης στοχαστικών προβλημάτων, δηλαδή προβλημάτων που εμφανίζουν τυχαίες μεταβλητές στην ίδια την διατύπωσή τους (ήτοι τυχαίες συναρτήσεις στόχου ή τυχαίους περιορισμούς) και μεθόδους επίλυσης μη-στοχαστικών προβλημάτων χρησιμοποιώντας τυχαίες επαναλήψεις. Ορισμένες μεθοδολογίες στοχαστικής βελτιστοποίησης χρησιμοποιούν τυχαίες επαναλήψεις για την επίλυση στοχαστικών προβλημάτων, συνδυάζοντας και τις δύο έννοιες της στοχαστικής βελτιστοποίησης. [1] Οι στοχαστικές μέθοδοι βελτιστοποίησης γενικεύουν τις αιτιοκρατικές μεθόδους βελτιστοποίησης αιτιοκρατικών προβλημάτων.
Μέθοδοι για στοχαστικά προβλήματα
[Επεξεργασία | επεξεργασία κώδικα]Μερικώς τυχαία δεδομένα εισόδου, και συνεπώς τυχαίες συναρτήσεις στόχου, προκύπτουν σε εφαρμογές όπως η εκτίμηση και ο έλεγχος σε πραγματικό χρόνο, η βελτιστοποίηση με την χρήση προσομοιώσεων Monte Carlo ως εκτιμήσεων ενός πραγματικού συστήματος, [2] [3] και προβλήματα όπου υπάρχει τυχαίο πειραματικό σφάλμα στις μετρήσεις του κριτηρίου. Σε τέτοιες περιπτώσεις, η γνώση ότι οι τιμές της συνάρτησης μολύνονται από τυχαίο "θόρυβο" οδηγεί σε αλγόριθμους που χρησιμοποιούν εργαλεία στατιστικής συμπερασματολογίας για να εκτιμήσουν τις "αληθείς" τιμές της συνάρτησης και να λάβουν στατιστικά βέλτιστες αποφάσεις για τα επόμενα βήματα. Στις μεθόδους αυτής της κατηγορίας περιλαμβάνονται:
- Η στοχαστική προσέγγιση (ΣΠ), των Robbins και Monro (1951) [4]
- Η στοχαστική κάθοδος κλίσης
- Η ΣΠ πεπερασμένης διαφοράς των Kiefer και Wolfowitz (1952) [5]
- Η ΣΠ ταυτόχρονης διαταραχής του Spall (1992) [6]
- Η βελτιστοποίηση σεναρίων
Μέθοδοι τυχαιοποιημένης αναζήτησης
[Επεξεργασία | επεξεργασία κώδικα]Από την άλλη πλευρά, ακόμα και όταν το σύνολο δεδομένων αποτελείται από ακριβείς μετρήσεις, μερικές μέθοδοι εισάγουν τυχαία στοιχεία στη διαδικασία αναζήτησης για να επιταχύνουν την πρόοδό της. [7] Μια τέτοια τυχαιότητα μπορεί επίσης να κάνει τη μέθοδο λιγότερο ευαίσθητη σε σφάλματα μοντελοποίησης. Περαιτέρω, η εγχυόμενη τυχαιότητα μπορεί να επιτρέψει στη μέθοδο να ξεφεύγει από τοπικά βέλτιστα και τελικά να προσεγγίσει το ολικό βέλτιστο. Πράγματι, η αρχή της τυχαιοποίησης είναι γνωστό ότι αποτελεί απλό και αποτελεσματικό τρόπο για την απόκτηση αλγορίθμων με σχεδόν εγγυημένες καλές επιδόσεις ομοιόμορφα σε πολλά σύνολα δεδομένων, για πολλά είδη προβλημάτων. Στοχαστικές μέθοδοι βελτιστοποίησης αυτού του είδους περιλαμβάνουν:
- Την προσομοίωση ανόπτησης των S. Kirkpatrick, CD Gelatt και MP Vecchi (1983) [8]
- Την κβαντική ανόπτηση
- Τις Συλλογές Πιθανοτήτων των DH Wolpert, SR Bieniawski και DG Rajnarayan (2011) [9]
- Την αντιδραστική βελτιστοποίηση αναζήτησης των Roberto Battiti, G. Tecchiolli (1994), [10] που αναθεωρήθηκε πρόσφατα στο βιβλίο αναφοράς [11]
- Την μέθοδο διασταυρούμενης εντροπίας των Rubinstein και Kroese (2004) [12]
- Την τυχαία αναζήτηση του Anatoly Zhigljavsky (1991) [13]
- Την πληροφοριακή αναζήτηση [14]
- Την στοχαστική σήραγγα [15]
- Την παράλληλη σκλήρυνση γνώστη και ως ανταλλαγή αντιγράφων [16]
- Τηνστοχαστική αναρρίχηση λόφου
- Τους αλγόριθμους σμήνους
- Τους εξελικτικούς αλγόριθμος, συμπεριλαμβανομένων:
- Τους γενετικούς αλγόριθμους του Holland (1975) [17]
- Τις στρατηγικές εξέλιξης
- Τον αλγόριθμο βελτιστοποίησης και τροποποίησης αντικειμένων καταρράκτη (2016) [18]
Αντίθετα, κάποιοι συγγραφείς έχουν υποστηρίξει ότι η τυχαιοποίηση μπορεί να βελτιώσει έναν ντετερμινιστικό αλγόριθμο μόνο αν ο ντετερμινιστικός αλγόριθμος ήταν εξαρχής κακά σχεδιασμένος. [19] Ο Fred W. Glover [20] υποστηρίζει ότι η εξάρτηση από τυχαία στοιχεία μπορεί να εμποδίσει την ανάπτυξη εφυέστερων και αποτελεσματικότερων αιτιοκρατικών μεθόδων. Ο τρόπος με τον οποίο παρουσιάζονται συνήθως τα αποτελέσματα των αλγορίθμων στοχαστικής βελτιστοποίησης (π.χ. παρουσιάζοντας μόνο τον μέσο όρο ή ακόμα και την βέλτιστη N δοκιμών χωρίς καμία αναφορά στην εξάπλωση), μπορεί επίσης να οδηγήσει σε μια μεροληψία υπέρ της τυχαιότητας.
Δείτε επίσης
[Επεξεργασία | επεξεργασία κώδικα]- Ολική βελτιστοποίηση
- Μηχανική μάθηση
- Βελτιστοποίηση σεναρίων
- Γκαουσιανή διαδικασία
- Μοντέλο Χώρου Κατάστασης
- Μοντέλο προγνωστικού ελέγχου
- Μη γραμμικός προγραμματισμός
- Εντροπική αξία υπό κίνδυνο
Βιβλιογραφικές αναφορές
[Επεξεργασία | επεξεργασία κώδικα]- ↑ Spall, 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:.
- ↑ 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:. https://archive.org/details/sim_annals-of-mathematical-statistics_1951-09_22_3/page/400.
- ↑ J. Kiefer; J. Wolfowitz (1952). «Stochastic Estimation of the Maximum of a Regression Function». Annals of Mathematical Statistics 23 (3): 462–466. doi:. https://archive.org/details/sim_annals-of-mathematical-statistics_1952-09_23_3/page/462.
- ↑ Spall, J. C. (1992). «Multivariate Stochastic Approximation Using a Simultaneous Perturbation Gradient Approximation». IEEE Transactions on Automatic Control 37 (3): 332–341. doi:. http://www.jhuapl.edu/SPSA.
- ↑ Holger H. Hoos and Thomas Stützle, Stochastic Local Search: Foundations and Applications, Morgan Kaufmann / Elsevier, 2004.
- ↑ S. Kirkpatrick; C. D. Gelatt; M. P. Vecchi (1983). «Optimization by Simulated Annealing». Science 220 (4598): 671–680. doi:. PMID 17813860. Bibcode: 1983Sci...220..671K. http://citeseer.ist.psu.edu/kirkpatrick83optimization.html.
- ↑ D.H. Wolpert; S.R. Bieniawski; D.G. Rajnarayan (2011). Probability Collectives in Optimization. http://www.santafe.edu/research/working-papers/abstract/f752fdb9c2b41e4e04947d7531421d61/.
- ↑ Battiti, Roberto; Gianpietro Tecchiolli (1994). «The reactive tabu search». ORSA Journal on Computing 6 (2): 126–140. doi:. http://rtm.science.unitn.it/~battiti/archive/TheReactiveTabuSearch.PDF.
- ↑ Battiti, Roberto· Mauro Brunato (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. and Ben-Gal I. (2014). A Group-Testing Algorithm with Online Informational Learning. IIE Transactions, 46:2, 164-184. Αρχειοθετήθηκε από το πρωτότυπο στις 2016-11-05. https://web.archive.org/web/20161105103321/http://www.eng.tau.ac.il/~bengal/GTA.pdf. Ανακτήθηκε στις 2020-01-26.
- ↑ W. Wenzel; K. Hamacher (1999). «Stochastic tunneling approach for global optimization of complex potential energy landscapes». Phys. Rev. Lett. 82 (15): 3003. doi:. Bibcode: 1999PhRvL..82.3003W.
- ↑ E. Marinari; G. Parisi (1992). «Simulated tempering: A new monte carlo scheme». Europhys. Lett. 19 (6): 451–458. doi:. Bibcode: 1992EL.....19..451M.
- ↑ Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley. ISBN 978-0-201-15767-3. Αρχειοθετήθηκε από το πρωτότυπο στις 19 Ιουλίου 2006. Ανακτήθηκε στις 28 Ιανουαρίου 2020.
- ↑ Tavridovich, S. A. (2017). «COOMA: an object-oriented stochastic optimization algorithm». International Journal of Advanced Studies 7 (2): 26–47. doi:. http://journal-s.org/index.php/ijas/article/view/10121/pdf.
- ↑ http://lesswrong.com/lw/vp/worse_than_random/
- ↑ Glover, F. (2007). «Tabu search—uncharted domains». Annals of Operations Research 149: 89–98. doi:.
Περαιτέρω ανάγνωση
[Επεξεργασία | επεξεργασία κώδικα]- Michalewicz, Z. και Fogel, DB (2000), How to Solve It: Modern Heuristics, Springer-Verlag, Νέα Υόρκη.
- " PSA: Ένας νέος αλγόριθμος βελτιστοποίησης βασισμένος στους κανόνες επιβίωσης του porcellio scaber ", Y. Zhang και S. Li