模擬退火算法中的鄰居選擇

選擇鄰居時應考慮算法的溫度？例如，如果在挑選鄰居時溫度高，應該進行置換？或者溫度是否僅影響接受概率？模擬退火算法中的鄰居選擇

2013-04-06 Undefined

後者是真的：只有接受概率受溫度的影響。溫度越高，接受越「惡劣」的移動以擺脫局部最佳狀態。如果您預先選擇能量值較低的鄰居，您基本上會反駁Simulated Annealing的想法，並將其變爲貪婪搜索。從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.

來源

2013-04-06 17:44:04

鑑於僞代碼，它是沒有定義的鄰居是如何計算的。因此，沒有顯示溫度不是計算的一部分。 – John 2015-06-11 20:31:59

我也有過同樣的問題，但我想從另一個崗位Basics of Simulated Annealing in Python答案表明T可以與選擇的鄰居是相當合理的。

選擇鄰居也取決於你的問題。限制鄰里的主要原因是，一旦你找到了一個體面的解決方案，即使你後來轉向更糟糕的解決方案，你至少留在附近。直覺是大多數目標函數都是平滑的，所以好的解決方案將靠近其他好的解決方案。所以你需要一個足夠小的鄰域，讓你靠近好的解決方案，但足夠大讓你能夠快速找到它們。你可以嘗試的一件事是隨着時間的推移減少鄰域（例如，使其與溫度成比例）。 - 亨斯13年11月4日在20:58

來源

2014-10-10 08:39:40 user3675927

這是從維基百科的說明，其中指出，溫度實際上應該計算一些問題。

有效的候選代

啓發式的更精確的說法是，一個應該嘗試第一個候選狀態s'的其中P（E（S），E（S'），T）是大。對於上面的「標準」接受函數P，這意味着E（s'） - E（s）在T或更小的數量級上。因此，在上述旅行商例如，可以使用一個鄰居（）函數，交換兩個隨機城市，那裏選擇一個城市對的概率也消失了超越T.他們的距離增加

這是否暗示溫度可能是確定鄰居時的相關因素。關於如何編寫鄰居功能

來源

2015-06-11 20:27:34 John

模擬退火算法中的鄰居選擇

回答

相關問題