Ottimizzazione stocastica

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. 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

I 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, 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)
- l'origine del gradiente stocastico
- l'approssimazione stocastica di differenza finita di Kiefer e Wolfowitz(1952)
- l'approssimazione stocastica delle perturbazioni simultanee di Spall(1992)

Metodi di ricerca casuali

D'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)
il metodo dell'entropia incrociata di Rubinstein e Kroese (2004)
la ricerca casuale di Zhigljaysky(1991)
la tecnica del salto del bacino nota anche come tecnica Monte Carlo con la minimizzazione
l'inserzione stocastica
la moderazione parallela detta anche dello scambio ripetuto
la scalata della collina stocastica
gli algoritmi dello sciame
gli algoritmi evolutivi
- l'algoritmo genetico di Goldberg(1989)

Note

↑ 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.
1 2 3 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

Collegamenti esterni

Software

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

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica

[spall2003-1] Spall, J. C., Introduction to Stochastic Search and Optimization, Wiley, 2003.

[fu2002-2] 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.

[RM1951-3] Robbins, H., Monro, S., A Stochastic Approximation Method, in Annals of Mathematical Statistics, vol. 22, 1951, pp. 400–407, DOI:10.1214/aoms/1177729586.

[KW1952-4] 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.

[spall1992-5] 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.

[kirk1983-6] 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.

[rubkro-7] Rubinstein, R. Y., Kroese, D. P., The Cross-Entropy Method, Springer-Verlag, 2004, ISBN 978-0-387-21240-1.

[zhigl1991-8] Zhigljavsky, A. A., Theory of Global Random Search, Kluwer Academic, 1991.

[naye1991-9] 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.

[wenzelwww-10] 1 2 3 W. Wenzel, Stochastic Optimization Methods, su iwrwww1.fzk.de. URL consultato il 24 aprile 2009 (archiviato dall'url originale il 1º giugno 2009).

[wenz1999-11] 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.

[mari1992-12] 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.

[gold1991-13] Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989 (archiviato dall'url originale il 19 luglio 2006).