模擬退火演算法概述
模擬退火演算法（Simulated Annealing，簡稱SA）的思想最早是由Metropolis等提出的。其出發點是基於物理中固體物質的退火過程與一般的組合最佳化問題之間的相似性。
模擬退火法是一種通用的最佳化演算法，其物理退火過程由以下三部分組成：
加溫過程。其目的是增強粒子的熱運動，使其偏離平衡位置。當溫度足夠高時，固體將熔為液體，從而消除系統原先存在的非均勻狀態
等溫過程。對於與周圍環境交換熱量而溫度不變的封閉系統，系統狀態的自發變化總是朝自由能減少的方向進行的，當自由能達到最小時，系統達到平衡狀態。
冷卻過程。使粒子熱運動減弱，系統能量下降，得到晶體結構。
加溫過程相當於對演算法設定初值，等溫過程對應演算法的Metropolis抽樣過程，冷卻過程對應控制引數的下降。
這裡能量的變化就是目標函式，我們要得到的最優解就是能量最低態。
其中Metropolis準則是SA演算法收斂於全域性最優解的關鍵所在，Metropolis準則以一定的機率接受惡化解，這樣就使演算法跳離區域性最優的陷阱。
SA演算法的Metropolis準則允許接受一定的惡化解，具體來講，是以一定機率來接受非最優解。
舉個例子，相當於保留一些“潛力股”，使解空間裡有更多的可能性。對比輪盤賭法，從機率論來講，它是對非最優解給予機率0，即全部拋棄。
模擬退火本身是求一個最小值問題，但可以轉化為求最大值問題，只需要對目標函式加個負號或者取倒數。
演算法步驟
其中，P為演算法選擇較差解的機率；T 為溫度的模擬引數；
當T很大時，圖片，此時演算法以較大機率選擇非當前最優解；P的值隨著T的減小而減小；
當T趨於0時，圖片，此時演算法幾乎只選擇最優解，等同於貪心演算法。
演算法特點
• 與遺傳演算法、粒子群最佳化演算法和蟻群演算法等不同，模擬退火演算法不屬於群最佳化演算法，不需要初始化種群操作。
• 收斂速度較慢。原因在於
（1）它初始溫度一般設定得很高，而終止溫度設定得低，這樣才符合物體規律，認為物質處於最低能量平衡點；
（2）它接受惡化解，並不是全程都在收斂的過程中。這一點可以類比GA中的變異，使得它不是持續在收斂的，所以耗時更多一些。
• 溫度管理（起始、終止溫度）、退火速度（衰減函式）等對尋優結果均有影響。比如T的衰減速度如果太快，就會導致可能尋找不到全域性最優解。
模擬退火演算法MATLAB實現
【例1】一元/多元函式最佳化
一元函式：x = ［1，2］範圍內 y = sin（10*pi*x） / x 的極值
二元函式：
在x，y都是［-5，5］範圍內找z = x。^2 + y。^2 - 10*cos（2*pi*x） - 10*cos（2*pi*y） + 20 的極值
【例2】TSP問題
我們的TSP中城市是自己虛擬的14座城市。
main。m：
計算距離的函式Distance。m：
畫出路徑的函式DrawPath。m：
輸出路徑函式OutputPath。m：
PathLength。m：
增加隨機擾動產生新解NewAnswer。m：
我們的做法是隨機產生兩個城市讓他們交換位置，從而得到一個新的路徑。當然，這只是這個問題的一個做法，也有其他“增加隨機擾動”的做法，而且對於多元函式問題更加簡單，只要在當前解的附近增加一些小的值即可。
Metropolis準則的實現：
程式結果：
【例3】
選擇30個點作為模擬研究物件，它們在座標平面的座標 （Location）如表1所示。
採用上述程式中隨機排列的方法產生初始路徑 ，其 排列結果如圖1所示 。選擇接受函式為Boltzmann 機率分佈函式，溫度的起始值為70，溫度下降律為0。5，經過執行最終得到結果如圖2所示，由該 圖可知經過最佳化後找到了最小路徑。
