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^[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

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^[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

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)^[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

^ 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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]