擬退火演算法
① 模擬退火演算法里的溫度代表什麼
模擬退火演算法中的「溫度」是一個用於控制演算法搜索過程和接受新解概率的參數。以下是關於模擬退火演算法中溫度的幾個關鍵點：
控制搜索過程：
- 在模擬退火演算法中，溫度逐漸降低的過程模擬了金屬退火時溫度逐漸下降的過程。隨著溫度的降低，演算法從廣泛搜索逐漸過渡到精細搜索，從而增加找到全局最優解的概率。
接受新解的概率：
- 溫度決定了演算法接受新解的概率。在高溫階段，演算法更容易接受較差的新解，以增加探索空間的機會；而在低溫階段，演算法則更傾向於接受較好的新解，以穩定收斂到最優解。
與應用場合相關：
- 溫度所代表的具體含義取決於模擬退火演算法的應用場合。例如，在聚類分析中，溫度可能代表聚類參數需要優化的某個或某幾個指標。這些指標在演算法運行過程中會被不斷調整，以尋找最優的聚類結果。
演算法參數：
- 溫度是模擬退火演算法中的一個關鍵參數，其初始值、降溫速率和終止條件等都會影響演算法的性能和結果。因此，在實際應用中，需要根據具體問題對溫度參數進行合理設置和調整。
綜上所述，模擬退火演算法中的「溫度」是一個用於控制搜索過程和接受新解概率的重要參數，其具體含義和取值取決於演算法的應用場合和問題需求。
② 白話解析模擬退火演算法
介紹模擬退火演算法前，先要了解爬山演算法。爬山演算法是一種簡單的貪心搜索演算法，其每次從當前解的臨近解空間中選擇一個最優解作為當前解，直到達到一個局部最優解。然而，爬山演算法的主要缺點是它容易陷入局部最優解，而未必能搜索到全局最優解。以圖1為例，假設C點為當前解，爬山演算法搜索到A點這個局部最優解就會停止搜索，因為在A點無論向那個方向小幅度移動都不能得到更優的解。
而模擬退火演算法(SA, Simulated Annealing)引入了隨機因素，成為了貪心演算法的一種變形。它以一定的概率接受比當前解更差的解，從而有可能跳出局部最優解，達到全局最優解。以圖1為例，模擬退火演算法在搜索到局部最優解A後，會以一定的概率接受到E的移動。經過幾次這樣的移動，可能到達D點，從而跳出局部最大值A。
模擬退火演算法的實現可以分為兩部分。首先，若移動後得到更優解，則總是接受該移動；其次，若移動後的解比當前解要差，則以一定的概率接受移動，這個概率會隨著時間推移逐漸降低。這里的「一定的概率」與金屬冶煉的退火過程有關，也正因為如此，模擬退火演算法得名。
具體演算法描述中，出現能量差為dE的降溫概率為P(dE)，公式為P(dE) = exp( dE/(kT) )。這里，溫度T在高溫時，出現一次能量差為dE的降溫的概率較大；溫度越低，則出現降溫的概率就越小。由於dE總是小於0（否則就不叫退火了），所以P(dE)的函數取值范圍是(0,1)。隨著溫度T的降低，P(dE)會逐漸降低。我們將一次向較差解的移動看做一次溫度跳變過程，以概率P(dE)來接受這樣的移動。
爬山演算法與模擬退火的比喻有助於理解：爬山演算法像是醉酒的兔子隨機跳躍，雖然可能抵達高點，但不一定是最高峰；模擬退火則像是在清醒後更明智地跳躍，最終可能達到更高的地方。
模擬退火演算法的偽代碼如下：通過循環控制溫度T的變化，當T超過T_min時繼續搜索。在每次迭代中，計算移動後得到的評價函數值dE，若dE大於等於0，則接受移動；若dE小於0，以一定概率接受移動並降溫。調整降溫速度的參數r以優化搜索過程。
解決旅行商問題時，模擬退火演算法可以提供一條近似最優路徑，通過產生新路徑、計算路徑長度並根據概率接受新路徑的方法實現。產生新路徑的策略有多種，包括交換節點順序、逆轉節點順序或移動節點等。
總體而言，模擬退火演算法是一種隨機演算法，不一定能找到全局最優解，但能較快地找到問題的近似最優解。通過適當參數設置，其搜索效率相較於窮舉法更優。