Quando si seleziona un vicino, è necessario considerare la temperatura dell'algoritmo? Quindi, per esempio, se la temperatura è alta quando si sceglie un vicino dovrebbe essere permutata la permutazione? O la temperatura influisce solo sulla probabilità di accettazione?Selezione del vicino nell'algoritmo di ricottura simulata
Quest'ultimo è vero: solo la probabilità di accettazione è influenzata dalla temperatura. Più alta è la temperatura, più mosse "cattive" vengono accettate per sfuggire all'ottima locale. Se preselezioni i vicini con bassi valori di energia, fondamentalmente contraddirai l'idea di Simulated Annealing e la trasformerai in una ricerca avida.
Pseudocodice da Wikipedia:
s ← s0; e ← E(s) // Initial state, energy.
sbest ← s; ebest ← e // Initial "best" solution
k ← 0 // Energy evaluation count.
while k < kmax and e > emax // While time left & not good enough:
T ← temperature(k/kmax) // Temperature calculation.
snew ← neighbour(s) // Pick some neighbour.
enew ← E(snew) // Compute its energy.
if P(e, enew, T) > random() then // Should we move to it?
s ← snew; e ← enew // Yes, change state.
if enew < ebest then // Is this a new best?
sbest ← snew; ebest ← enew // Save 'new neighbour' to 'best found'.
k ← k + 1 // One more evaluation done
return sbest // Return the best solution found.
Ho anche avuto la stessa domanda, ma penso che la risposta da un altro post Basics of Simulated Annealing in Python suggerisce T può essere correlato alla scelta di vicini di casa è abbastanza ragionevole.
La scelta dei vicini dipenderà anche dal problema. Il motivo principale per limitare il vicinato è che, una volta trovata una soluzione decente, anche se in seguito si passa a una soluzione peggiore, almeno si resta nei paraggi. L'intuizione è che la maggior parte delle funzioni obiettive sono alquanto lisce, quindi buone soluzioni si troveranno vicino ad altre buone soluzioni. Quindi hai bisogno di un quartiere abbastanza piccolo da tenerti vicino a soluzioni valide, ma abbastanza grande da permetterti di trovarli rapidamente. Una cosa che puoi provare è diminuire il vicinato nel tempo (ad esempio, renderlo proporzionale alla temperatura). - hunse 4 novembre 13 alle 20:58
Ecco la descrizione di wikipedia che afferma che la temperatura dovrebbe essere calcolata per alcuni problemi.
generazione candidato efficiente
una dichiarazione più precisa della euristica è che si dovrebbe provare primi stati candidati s'per la quale P (E (s), E (s'), T) è grande. Per la funzione di accettazione "standard" P sopra, significa che E (s ') - E (s) è nell'ordine di T o meno. Così, nell'esempio commesso viaggiatore sopra, si potrebbe usare un vicino di casa() funzione che scambia due città casuali, dove la probabilità di scegliere una coppia di città svanisce come la loro distanza aumenta oltre T.
Questo implica quella Temperatura può essere un fattore rilevante per determinare il vicino.
lettura più utili su come scrivere funzioni prossimo: How to efficiently select neighbour in 1-dimensional and n-dimensional space for Simulated Annealing
Dato che pseudo codice, non è definito come vicino di casa viene calcolato. Pertanto, non è dimostrato che la temperatura non faccia parte del calcolo. – John