I metodi di ottimizzazione stocastica (OS) sono algoritmi di ottimizzazione che incorporano elementi probabilistici (casuali), sia nei dati del problema (la funzione obiettivo, le approssimazioni, ecc) o nell'algoritmo stesso (attraverso valori parametrici casuali, scelte casuali, ecc.) o in entrambi[1]. Il concetto contrasta con i metodi di ottimizzazione deterministica dove i valori della funzione obiettivo sono per ipotesi esatti, e la computazione è completamente determinata dai valori esemplificati fino ad adesso.
Metodi per funzioni stocastiche
modificaI dati di input parzialmente casuali sorgono per esempio in stime e controlli in tempo reale, ottimizzazioni basate su simulazioni dove vengono usate simulazioni di Monte Carlo come stime di un sistema reale[2], e problemi dove c'è un errore sperimentale (casuale) nelle misurazioni del criterio. In tali casi, il sapere che i valori della funzione sono affetti da rumore casuale conduce in modo naturale ad algoritmi che usano strumenti di inferenza statistica per stimare i veri valori della funzione e/o ricavare decisioni statisticamente ottimali riguardo ai passi successivi. I metodi di questa classe includono:
- l'approssimazione stocastica (SA) di Robbins e Monro (1951)[3]
- l'origine del gradiente stocastico
- l'approssimazione stocastica di differenza finita di Kiefer e Wolfowitz(1952) [4]
- l'approssimazione stocastica delle perturbazioni simultanee di Spall(1992) [5]
Metodi di ricerca casuali
modificaD'altra parte, anche quando i dati sono esatti, è qualche volta utile aggiungere deliberatamente la casualità in essi per cercare processi come strumenti di accelerazione della convergenza e rendere l'algoritmo meno dipendente dagli errori di modellazione. Inoltre la casualità indotta può fornire l'impulso necessario per staccarsi da una soluzione limitata quando si è alla ricerca di un rimedio globale. Infatti questo principio di casualizzazione è noto per essere un metodo semplice ed efficace per ottenere algoritmi con una buona performance quasi certa che attraversa uniformemente tutti gli insiemi di dati, per qualsiasi tipo di problema. I metodi di ottimizzazione stocastica di questo tipo includono:
- il simulated annealing di S. Kirkpatrick, C. D. Gelatt e M. P. Vecchi (1983)[6]
- il metodo dell'entropia incrociata di Rubinstein e Kroese (2004)[7]
- la ricerca casuale di Zhigljaysky(1991)[8]
- la tecnica del salto del bacino nota anche come tecnica Monte Carlo con la minimizzazione[9][10]
- l'inserzione stocastica[10][11]
- la moderazione parallela detta anche dello scambio ripetuto[10][12]
- la scalata della collina stocastica
- gli algoritmi dello sciame
- gli algoritmi evolutivi
- l'algoritmo genetico di Goldberg(1989)[13]
Note
modifica- ^ Spall, J. C., Introduction to Stochastic Search and Optimization, Wiley, 2003.
- ^ Fu, M. C., Optimization for Simulation: Theory vs. Practice, in INFORMS Journal on Computing, (con discussioni di S. Andradóttir, P. Glynn e J. P. Kelly), vol. 14, 2002, pp. 192–227, DOI:10.1287/ijoc.14.3.192.113.
- ^ Robbins, H., Monro, S., A Stochastic Approximation Method, in Annals of Mathematical Statistics, vol. 22, 1951, pp. 400–407, DOI:10.1214/aoms/1177729586.
- ^ J. Kiefer, J. Wolfowitz, Stochastic Estimation of the Maximum of a Regression Function, in Annals of Mathematical Statistics, vol. 23, 1952, pp. 462–466, DOI:10.1214/aoms/1177729392.
- ^ Spall, J. C., Multivariate Stochastic Approximation Using a Simultaneous Perturbation Gradient Approximation, in IEEE Transactions on Automatic Control, vol. 37, 1992, pp. 332–341, DOI:10.1109/9.119632.
- ^ S. Kirkpatrick, C. D. Gelatt; M. P. Vecchi, Optimization by Simulated Annealing, in Science, vol. 220, n. 4598, 1983, pp. 671–680, DOI:10.1126/science.220.4598.671, PMID 17813860.
- ^ Rubinstein, R. Y., Kroese, D. P., The Cross-Entropy Method, Springer-Verlag, 2004, ISBN 978-0-387-21240-1.
- ^ Zhigljavsky, A. A., Theory of Global Random Search, Kluwer Academic, 1991.
- ^ Akbar Nayeem, Jorge Vila; Harold A. Scheraga, A comparative study of the simulated-annealing and monte carlo-with-minimization approaches to the minimum-energy structures of polypeptides: [met]-enkephalin, in J. Comp. Chem., vol. 12, n. 5, 1991, pp. 594–605, DOI:10.1002/jcc.540120509.
- ^ a b c W. Wenzel, Stochastic Optimization Methods, su iwrwww1.fzk.de. URL consultato il 24 aprile 2009 (archiviato dall'url originale il 1º giugno 2009).
- ^ W. Wenzel, K. Hamacher, Stochastic tunneling approach for global optimization of complex potential energy landscapes, in Phys. Rev. Lett., vol. 82, 1999, p. 3003, DOI:10.1103/PhysRevLett.82.3003.
- ^ E. Marinari, G. Parisi, Simulated tempering: A new monte carlo scheme, in Europhys. Lett., vol. 19, 1992, p. 451, DOI:10.1209/0295-5075/19/6/002.
- ^ Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989 (archiviato dall'url originale il 19 luglio 2006).
- Michalewicz, Z. and Fogel, D. B. (2000), How to Solve It: Modern Heuristics, Springer-Verlag, New York.
Voci correlate
modifica- Ottimizzazione globale
- Programmazione stocastica
- Apprendimento automatico
- Ottimizzazione (matematica)
- Ottimizzazione (informatica)
Collegamenti esterni
modificaSoftware
modifica- AIMMS, su aimms.com. URL consultato il 12 novembre 2009 (archiviato dall'url originale il 3 marzo 2010).
- FortSP solver(FortSP)
- SPInE, su optirisk-systems.com.
- XPRESS-SP[collegamento interrotto], su dash-optimization.com.
| Controllo di autorità | GND (DE) 4057625-5 |
|---|
