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 l'ottimizzazione del formicaio l'ottimizzazione dello sciame di particelle l'algoritmo delle api la ricerca della diffusione stocastica gli algoritmi evolutivi l'algoritmo genetico di Goldberg(1989)
Note
Michalewicz, Z. and Fogel, D. B. (2000), How to Solve It: Modern Heuristics, Springer-Verlag, New York.
Voci correlate Ottimizzazione globale Programmazione stocastica Apprendimento automatico Ottimizzazione (matematica) Ottimizzazione (informatica)
Collegamenti esterni Software
FortSP solver(FortSP)
Categoria:Ottimizzazione Categoria:Algoritmi di ottimizzazione