Qual è la differenza tra Stochastic Hill Climbing e Simulated Annealing?

Question

Sto leggendo della ricerca locale: alpinismo, e i suoi tipi e ricottura simulata

Una delle versioni di hill climbing è "hill climbing stocastico", che ha la seguente definizione:

L'arrampicata stocastica in collina non esamina tutto il suo vicino prima di spostarsi. Piuttosto, questo algoritmo di ricerca seleziona un nodo vicino a caso e decide se sceglierlo come stato corrente o esaminare un altro stato

Alcune fonti hanno affermato che può essere utilizzato per evitare ottimali locali.

Poi stavo leggendo della ricottura simulata e della sua definizione:

Ad ogni iterazione, viene scelta una mossa casuale. Se migliora la situazione, la mossa viene accettata, altrimenti viene accettata con una probabilità inferiore a 1

Allora, qual è la principale differenza tra i due approcci? Lo stocastico sceglie solo un successore casuale (in salita)? Se sceglie solo (successori in salita), come evita gli ottimi locali?

Answer 1

Il libro di Russell e Norvig (3a edizione) descrive questi due algoritmi (sezione 4.1.1., P. 122) e questo libro è il riferimento che dovresti generalmente usare quando studi gli algoritmi di ricerca nell'intelligenza artificiale. Ho familiarità con il simulated annealing (SA), dato che l'ho implementato in passato per risolvere un problema combinatorio, ma non ho molta familiarità con l'arrampicata stocastica (SHC), quindi lasciatemi citare le parti del libro che descrivono SHC .

L'arrampicata stocastica sceglie a caso tra i movimenti in salita; la probabilità di selezione può variare con la pendenza del movimento in salita. Questo di solito converge più lentamente rispetto alla salita più ripida, ma in alcuni paesaggi statali trova soluzioni migliori.

Quindi, SHC sceglie a caso una "mossa in salita", ovvero una mossa che migliora la funzione obiettivo (ad esempio, se stai cercando di risolvere il problema del venditore ambulante , una "mossa in salita" potrebbe essere qualsiasi modifica al ciclo hamiltoniano corrente , una soluzione, in modo che il nuovo ciclo halmitoniano abbia un costo più breve) tra le mosse in salita (quindi tra alcune serie di mosse che migliorano l'obiettivo).

Nella ricottura simulata , esegui qualche movimento. Se quella mossa porta a una soluzione migliore, mantieni sempre la soluzione migliore. Se porta a una soluzione peggiore, accetti quella soluzione peggiore con una certa probabilità. Ci sono altri dettagli, come il modo in cui accetti la soluzione peggiore (che puoi trovare nel libro di Russell e Norvig), ma questo dovrebbe già chiarire che SA è diversa da SHC: SA può accettare soluzioni peggiori per sfuggire ai minimi locali, mentre SHC accetta solo movimenti in salita.