Podczas wybierania sąsiada należy wziąć pod uwagę temperaturę algorytmu? Na przykład, jeśli temperatura jest wysoka, przy wyborze sąsiada należy dokonać permutacji? Czy temperatura ma wpływ tylko na prawdopodobieństwo akceptacji?Wybór sąsiada w algorytmie symulowanego wyżarzania
To ostatnie jest prawdą: na prawdopodobieństwo wpływu ma tylko temperatura. Im wyższa temperatura, tym bardziej "złe" ruchy są akceptowane, aby uciec od lokalnej optymalności. Jeśli wybierzesz sąsiadów o niskich wartościach energii, zasadniczo zaprzeczysz idei symulowanego wyżarzania i przekształcisz je w chciwe poszukiwania.
Pseudokod od 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.
Miałem też to samo pytanie, ale myślę, że odpowiedź z innego wątku Basics of Simulated Annealing in Python proponuje T może być związane z wyboru sąsiadów jest dość rozsądna.
Wybór sąsiadów zależy również od Twojego problemu. Głównym powodem ograniczenia sąsiedztwa jest to, że gdy znajdziesz już przyzwoite rozwiązanie, nawet jeśli później przejdziesz do gorszego rozwiązania, przynajmniej pozostaniesz w sąsiedztwie. Intuicją jest to, że większość obiektywnych funkcji jest nieco gładka, więc dobre rozwiązania będą znajdować się w pobliżu innych dobrych rozwiązań. Potrzebujesz więc dzielnicy, która jest wystarczająco mała, by trzymać Cię w pobliżu dobrych rozwiązań, ale wystarczająco dużych, byś mógł szybko je znaleźć. Jedną rzeczą, którą możesz wypróbować, to zmniejszenie okolicy w czasie (np. Uczynić ją proporcjonalną do temperatury). - hunse listopad 4 '13 o 20:58
Oto opis z wikipedia, która stwierdza, że temperatura powinna być w rzeczywistości obliczona dla niektórych problemów.
Efektywne generacja kandydat
Bardziej precyzyjne określenie heurystyki jest to, że jeden powinien spróbować pierwszych państw kandydujących s'dla których P (E (s), E (s'), T) jest duży. Dla "standardowej" funkcji akceptacji P powyżej oznacza to, że E (s ') - E (s) jest rzędu T lub mniej. Tak więc, w przykładzie komiwojażera powyżej, można użyć sąsiada() funkcja, która zamienia dwie losowe miast, gdzie prawdopodobieństwo wyboru parę miasta znika jak ich odległość zwiększa się poza T.
To implikuje Temperatura może być istotnym czynnikiem przy ustalaniu sąsiada.
Więcej przydatnych czytanie o tym, jak napisać funkcję sąsiada: How to efficiently select neighbour in 1-dimensional and n-dimensional space for Simulated Annealing
Zważywszy, że pseudo kod, to nie jest zdefiniowane, jak sąsiad jest obliczana. Dlatego nie wykazano, że temperatura nie jest częścią obliczeń. – John