Hill climbing iterativo
L'algoritmo hill climbing iterativo è una versione dell'algoritmo di ricerca locale hill climbing in cui sono effettuati diversi tentativi di ricerca locale prima di restituire in output il risultato dell'elaborazione. A ogni ciclo ( iterazione ) l'algoritmo esplora lo spazio di ricerca a partire da un nodo iniziale differente. La selezione del nodo iniziale può essere determinata da una funzione euristica ( ricerca informata ) oppure da una funzione stocastica ( hill climbing stocastico ). A partire dal nodo iniziale l'algoritmo elabora il percorso verso il nodo vicino con valore più alto fino a individuare il nodo con valore maggiore. La soluzione finale dell'iterazione viene confrontata con la precedente e, se risulta essere migliore, viene sostituita a quest'ultima. Infine l'algoritmo si riavvia per iniziare una nuova iterazione a partire da un nodo iniziale diverso dal precedente.
L'algoritmo hill climbing iterativo effettua un numero predeterminato di iterazioni. Al termine di tutte le iterazioni restituisce in output la migliore soluzione possibile. La soluzione elaborata dall'algoritmo hill climbing iterativo riduce il rischio di fallimento rispetto all'algoritmo hill climbing tradizionale. Ad esempio, se un algoritmo hill climbing tradizionale ha un tasso di errore pari al 80%. In altri termini, l'algoritmo hill climbing tradizionale fornisce 8 volte su 10 un risultato sub-ottimale, bloccandosi in situazioni di massimo locale, e soltanto 2 volte su 10 fornisce un risultato di massimo globale. La probabilità di successo è quindi pari a p=0.20 (20%). Nel caso dell'algoritmo hill climbing iterativo la probabilità di successo aumenta ad ogni ulteriore iterazione. In media, riavviando l'algoritmo hill climbing per 1/p volte è possibile individuare un risultato di massimo globale. Ad esempio, se il tasso di successo dell'algoritmo è pari al 20%, riavviandolo 5 volte (1 / 0.20) si ottiene una probabilità teorica di successo pari al 100%.
Costo e tempo delle iterazioni. Ogni riavvio ( iterazione ) aumenta il tempo di elaborazione dell'algoritmo Per determinare il numero di iterazioni dell'algoritmo è opportuno considerare sia la probabilità attesa di successo e sia il costo complessivo delle iterazioni necessarie.
