Ottimizzazione stocastica

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica sorgente]

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:

Metodi di ricerca casuali[modifica | modifica sorgente]

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:

Voci correlate[modifica | modifica sorgente]

Riferimenti[modifica | modifica sorgente]

  1. ^ Spall, J. C., Introduction to Stochastic Search and Optimization, Wiley, 2003.
  2. ^ Fu, M. C., Optimization for Simulation: Theory vs. Practice in INFORMS Journal on Computing, vol. 14, 2002, pp. 192–227, DOI:10.1287/ijoc.14.3.192.113.
  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.
  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.
  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.
  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.
  7. ^ Rubinstein, R. Y., Kroese, D. P., The Cross-Entropy Method, Springer-Verlag, 2004, ISBN 978-0-387-21240-1.
  8. ^ Zhigljavsky, A. A., Theory of Global Random Search, Kluwer Academic, 1991.
  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.
  10. ^ a b c W. Wenzel, Stochastic Optimization Methods. URL consultato il 24 aprile 2009.
  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.
  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.
  13. ^ Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989.
  • Michalewicz, Z. and Fogel, D. B. (2000), How to Solve It: Modern Heuristics, Springer-Verlag, New York.

Collegamenti esterni[modifica | modifica sorgente]

Software[modifica | modifica sorgente]

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