Στοχαστική Βελτιστοποίηση

Μέθοδοι στοχαστικής βελτιστοποίησης ονομάζονται οι μέθοδοι βελτιστοποίησης που παράγουν και χρησιμοποιούν τυχαίες μεταβλητές. Περιλαμβάνουν τις μεθόδους επίλυσης στοχαστικών προβλημάτων, δηλαδή προβλημάτων που εμφανίζουν τυχαίες μεταβλητές στην ίδια την διατύπωσή τους (ήτοι τυχαίες συναρτήσεις στόχου ή τυχαίους περιορισμούς) και μεθόδους επίλυσης μη-στοχαστικών προβλημάτων χρησιμοποιώντας τυχαίες επαναλήψεις. Ορισμένες μεθοδολογίες στοχαστικής βελτιστοποίησης χρησιμοποιούν τυχαίες επαναλήψεις για την επίλυση στοχαστικών προβλημάτων, συνδυάζοντας και τις δύο έννοιες της στοχαστικής βελτιστοποίησης.  Οι στοχαστικές μέθοδοι βελτιστοποίησης γενικεύουν τις αιτιοκρατικές μεθόδους βελτιστοποίησης αιτιοκρατικών προβλημάτων. 

 Μέθοδοι για στοχαστικά προβλήματα 
Μερικώς τυχαία δεδομένα εισόδου, και συνεπώς τυχαίες συναρτήσεις στόχου, προκύπτουν σε εφαρμογές όπως η εκτίμηση και ο έλεγχος σε πραγματικό χρόνο, η βελτιστοποίηση με την χρήση προσομοιώσεων Monte Carlo ως εκτιμήσεων ενός πραγματικού συστήματος,  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 και Monro (1951)  
 Η στοχαστική κάθοδος κλίσης 
 Η ΣΠ πεπερασμένης διαφοράς των Kiefer και Wolfowitz (1952)  
 Η ΣΠ ταυτόχρονης διαταραχής του Spall (1992)  
 Η βελτιστοποίηση σεναρίων 

 Μέθοδοι τυχαιοποιημένης αναζήτησης 
Από την άλλη πλευρά, ακόμα και όταν το σύνολο δεδομένων αποτελείται από ακριβείς μετρήσεις, μερικές μέθοδοι εισάγουν τυχαία στοιχεία στη διαδικασία αναζήτησης για να επιταχύνουν την πρόοδό της. Holger H. Hoos and Thomas Stützle, Stochastic Local Search: Foundations and Applications, Morgan Kaufmann / Elsevier, 2004. Μια τέτοια τυχαιότητα μπορεί επίσης να κάνει τη μέθοδο λιγότερο ευαίσθητη σε σφάλματα μοντελοποίησης. Περαιτέρω, η εγχυόμενη τυχαιότητα μπορεί να επιτρέψει στη μέθοδο να ξεφεύγει από τοπικά βέλτιστα και τελικά να προσεγγίσει το ολικό βέλτιστο. Πράγματι, η αρχή της τυχαιοποίησης είναι γνωστό ότι αποτελεί απλό και αποτελεσματικό τρόπο για την απόκτηση αλγορίθμων με σχεδόν εγγυημένες καλές επιδόσεις ομοιόμορφα σε πολλά σύνολα δεδομένων, για πολλά είδη προβλημάτων. Στοχαστικές μέθοδοι βελτιστοποίησης αυτού του είδους περιλαμβάνουν: 

 Την προσομοίωση ανόπτησης των S. Kirkpatrick, CD Gelatt και MP Vecchi (1983)  
 Την κβαντική ανόπτηση 
 Τις Συλλογές Πιθανοτήτων των DH Wolpert, SR Bieniawski και DG Rajnarayan (2011)  
 Την αντιδραστική βελτιστοποίηση αναζήτησης των Roberto Battiti, G. Tecchiolli (1994),  που αναθεωρήθηκε πρόσφατα στο βιβλίο αναφοράς  
 Την μέθοδο διασταυρούμενης εντροπίας των Rubinstein και Kroese (2004)  
 Την τυχαία αναζήτηση του Anatoly Zhigljavsky (1991)  
 Την πληροφοριακή αναζήτηση  
 Την στοχαστική σήραγγα  
 Την παράλληλη σκλήρυνση γνώστη και ως ανταλλαγή αντιγράφων  
 Τηνστοχαστική αναρρίχηση λόφου 
 Τους αλγόριθμους σμήνους 
 Τους εξελικτικούς αλγόριθμος, συμπεριλαμβανομένων: 
 Τους γενετικούς αλγόριθμους του Holland (1975)  
 Τις στρατηγικές εξέλιξης 
 Τον αλγόριθμο βελτιστοποίησης και τροποποίησης αντικειμένων καταρράκτη (2016)  

Αντίθετα, κάποιοι συγγραφείς έχουν υποστηρίξει ότι η τυχαιοποίηση μπορεί να βελτιώσει έναν ντετερμινιστικό αλγόριθμο μόνο αν ο ντετερμινιστικός αλγόριθμος ήταν εξαρχής κακά σχεδιασμένος. http://lesswrong.com/lw/vp/worse_than_random/ Ο Fred W. Glover  υποστηρίζει ότι η εξάρτηση από τυχαία στοιχεία μπορεί να εμποδίσει την ανάπτυξη εφυέστερων και αποτελεσματικότερων αιτιοκρατικών μεθόδων. Ο τρόπος με τον οποίο παρουσιάζονται συνήθως τα αποτελέσματα των αλγορίθμων στοχαστικής βελτιστοποίησης (π.χ. παρουσιάζοντας μόνο τον μέσο όρο ή ακόμα και την βέλτιστη N δοκιμών χωρίς καμία αναφορά στην εξάπλωση), μπορεί επίσης να οδηγήσει σε μια μεροληψία υπέρ της τυχαιότητας. 

 Δείτε επίσης 

 Ολική βελτιστοποίηση 
 Μηχανική μάθηση 
 Βελτιστοποίηση σεναρίων 
 Γκαουσιανή διαδικασία 
 Μοντέλο Χώρου Κατάστασης 
 Μοντέλο προγνωστικού ελέγχου 
 Μη γραμμικός προγραμματισμός 
 Εντροπική αξία υπό κίνδυνο 

 Βιβλιογραφικές αναφορές 

 Περαιτέρω ανάγνωση 

 Michalewicz, Z. και Fogel, DB (2000), How to Solve It: Modern Heuristics, Springer-Verlag, Νέα Υόρκη. 
 " PSA: Ένας νέος αλγόριθμος βελτιστοποίησης βασισμένος στους κανόνες επιβίωσης του porcellio scaber ", Y. Zhang και S. Li 

 Εξωτερικοί σύνδεσμοι 

 COSP

Κατηγορία:Βελτιστοποίηση