Contraddizione di annealing simulato?

Question

Contraddizione di annealing simulato?

#1 da (1 voti)

0

L'intera idea di ricottura simulata è quella di evitare di rimanere bloccati negli ottimums locali, motivo per cui a volte viene accettata una soluzione peggiore.

Tuttavia, la ricottura simulata accetterà automaticamente una soluzione superiore a quella corrente. Quindi, se sei in un optimum locale, la ricottura simulata ti farà uscire per una singola iterazione e poi ti rimetterà a posto in quanto accetterà l'optimum locale con probabilità 1, giusto?

So che sì, se la temperatura è ancora elevata, allora puoi scappare da quell'ottimo locale, ma se la temperatura si è raffreddata e hai ancora l'optimum locale sbagliato, allora sei praticamente bloccato lì, corretto ??

algorithms

posta extremeaxe5 23.11.2014 - 11:38

fonte

1 risposta

Leggi altre domande sui tag algorithms

MapReduce un pattern architettonico? [chiuso] Fornisci immagini web ad alta risoluzione e lascia che il browser lo riduca. Una cattiva idea?

score 1 · Answer 1

Se è in un optimum locale, qualsiasi scelta del vicino è peggiore e accettata con una probabilità a seconda della temperatura, sì. Nota la dicitura qualsiasi scelta del vicino : ci sono tipicamente dozzine di vicini o più, e ad ogni iterazione ne viene esaminata solo una. In questo modo lo stato può facilmente allontanarsi di molti passi dal precedente locale ottimale. Dal momento che è piuttosto improbabile scegliere nuovamente i vicini esatti e tornare sullo stesso percorso, potrebbe scivolare verso un minimo diverso (lo spazio di ricerca è solitamente di alta dimensione, quindi l'intuizione 2D sottovaluta il numero di percorsi disponibili).

E sì, anche dopo molte iterazioni potrebbe ancora essere in un optimum locale piuttosto che in uno globale. Va bene. SA è un meta-euristico, è usato quando una soluzione esatta non è fattibile. Un minimo locale trovato dopo molte iterazioni, con una buona scelta di parametri, sarà comunque di gran lunga migliore di quello che possono produrre approcci più semplicistici. Forse il suo costo è solo ε lontano dall'ottimo globale, ma estremamente distante spazialmente. (Ovviamente, in altri casi la soluzione è semplicemente una cagata e parametri diversi o un metaeuristico diverso potrebbero funzionare meglio.)