第5章模擬退火算法

模擬退火算法（SimulatedAnnealing,簡稱SA）是Kirkpatrick等人于1982年提出的一種適合求解大規模組合優化問題，特別是NP-難問題的通用啟發式算法．算法思想源于對固體物質退火過程的模擬；采用Metropolis接受準則；并用一組稱之為冷卻進度表的參數控制算法進程，使算法在多項式時間里給出一個近似最優解．SA的物理背景：固體物質退火過程．使算法跳離局部最優的關鍵：Metropolis接受準則．算法應用的前提：冷卻進度表的合理選擇．1主要內容5.1固體退火過程和Metropolis準則5.2模擬退火算法的基本思想和步驟5.3模擬退火算法關鍵參數和操作的設計5.4模擬退火算法實現與應用5.5模擬退火算法的改進25.1固體退火過程和Metropolis準則

固體物質退火是先將固體加熱至熔化，再徐徐冷卻使之凝固成規整晶體的熱力學過程.固體物質的退火過程由三部分組成：加溫過程等溫過程冷卻過程對于固體在恒定溫度下達到熱平衡的過程模擬，Metropolis等人在1953年提出了“重要性采樣法”，即以概率接受新狀態．若Ej<Ei則接受新狀態j為當前狀態（“重要”狀態）；若Ej>Ei，要依據概率來確定．35.2模擬退火算法的基本思想和步驟

1.固體退火與組合優化之間的相似性固體退火概念與優化問題的對應關系

42.算法思想和步驟

Metropolis算法：從某一初始狀態出發，通過計算系統的時間演化過程，求出系統最終達到的狀態．SA：從某個初始解出發，經過大量解的變換后，求得給定控制參數值t時優化問題的相對最優解．然后，減少t的值，重復執行Metropolis算法，就可以在t趨于零時，求得優化問題的全局最優解．

SA由與Metropolis準則對應的轉移概率Pt確定是否接受從當前解xi到新解xj的轉移，即

5ProcedureSimulated_Annealing;Begin

任選一個初始解x0；確定初始溫度t0和每一個t值下進行迭代的次數L；

xi:=x0;（置初始解為當前解）

k

:=0;（溫度變化計數器置0）Repeat

l

:=0;（迭代次數計數器）Repeat

從鄰域N(xi)中隨機選一xj；計算Δf=f(xj)-f(xi)；if(Δf≤0)thenxi:=xj;elseifexp(-Δf/tk)>random[0,1]thenxi:=xj;

l

:=l+1;untill=L;

k

:=k+1;tk

:=t(k);until滿足終止條件；End;63.模擬退火算法的特點分析

SA依據Metropolis準則接受新解，因此除接受優化解外，還在一定范圍內接受惡化解，這正是SA與局部搜索算法的本質區別所在．SA具有如下特點：

(1)優于局部搜索算法．

(2)若在每個t值都達到平衡分布，且所構造的鄰域結構能使解空間中的任何兩個狀態可達，則SA漸近收斂于全局最優解．(3)隨著控制參數t值的減小，算法返回某個全局最優解的概率單調增大.7與局部搜索算法相比，SA的性能可概括為高效、健壯、通用和靈活．

(1)高效性．SA可在較短時間里求得更好的最終解．(2)健壯性（魯棒性，robust）．即算法的最終解并不十分依賴初始解的選?。?3)通用性和靈活性．SA能應用于求解多種組合優化問題，為一個問題編制的程序可以有效地用于其它問題．85.3SA關鍵參數及其操作設計

SA主要包括“三函數兩準則”：解產生函數（鄰域結構）、解接受函數、溫度更新函數、內循環終止準則和外循環終止準則．

1.解產生函數（鄰域結構）

通常選擇當前解經簡單變換即可產生新解的方法．盡可能保證產生的候選解遍布整個解空間．應能使解空間中的任何兩個狀態可達．2.解接受函數

判斷新解是否被接受的依據是Metropolis準則：93.初始溫度

從理論上說，初始溫度t0應使平穩分布中每一狀態被接受的概率相等，也就是使若取P＝0.9，則在Δf

=100時，t0＞949．在實際應用中可用以下方法進行簡單地估計：

(1)Δf=(目標函數值的上界)－(目標函數值的下界)．(2)隨機產生若干個解，求所有解對間的目標函數差，然后取其中的最大者作為Δf．

104.溫度更新函數

表示溫度下降的方式并控制溫度下降的速度．常用的溫度更新函數是tk+1=αtk，0<α<1，通常α=0.75~0.99．

5.內循環終止準則

用于決定在各溫度下產生候選解的數目，即每一個tk值下進行迭代的次數L．

L往往只能取一個近似的足夠大的數，如L=100n～300n，其中n為問題的規模．還可用如下的抽樣穩定準則來判斷L是否足夠大：(1)目標函數的均值是否穩定．(2)連續若干步的目標值變化較?。?/p>

116.外循環終止準則

用于決定SA何時結束．常用的終止準則有：(1)設定終止溫度．在實際應用中，可以給定一個足夠小的正數ε，當溫度tk≤ε時，算法終止．(2)給定一個確定的外循環總迭代次數．(3)給定當前的最好解保持不變的最大連續迭代次數．

7.冷卻進度表

初始溫度t0，溫度更新函數tk+1=αtk，每一個tk值下進行迭代的次數L和外循環終止準則稱為模擬退火過程的冷卻進度表，是SA應用的關鍵參數．這些參數之間存在相互影響．125.4模擬退火算法實現與應用

討論如何在SA所提供的通用算法框架下，針對具體問題予以實現．對問題的簡明描述：解空間：指問題的所有可能解的集合，它限定了初始解選取和新解產生時的范圍．目標函數：通常表述為若干優化目標的一個和式．目標函數值不一定就是問題的優化目標值，但其對應關系應是明顯的．此外，目標函數式應當是易于計算的．初始解：可以考慮隨機生成．131.旅行商問題

設有n個城市和距離矩陣D=(dij)，其中dij表示城市i到城市j的距離．問題是要找遍訪每個城市恰好一次的一條回路，且其路徑長度為最短．求解TSP的模擬退火算法描述如下：解空間：可表示為{1,2,…,n}的所有循環排列的集合，即S={(π1,π2,…,πn)|(π1,π2,…,πn)為{1,2,…,n}的循環排列}．πi=j表示在第i個次序訪問城市j，并約定πn+1=π1．初始解：可選為（1,2,…,n）．

目標函數：訪問所有城市的一個回路的長度14新解的產生：設用以下方法產生（分別或交替使用）①2-交換．任選訪問的序號u和v（設u<v），逆轉u和v及其之間的訪問順序．當前解：π1…πu-1

πu

πu+1

…πv-1

πv

πv+1…πn

新解：π1…πu-1

πvπv-1…πu+1πuπv+1…πn

②3-交換．任選序號u、v和w（設u<v<w），將u和v之間的子路徑插到w之后訪問．當前解：π1…πu-1

πu…πv

πv+1…

πw

πw+1…πn新解：π1…πu-1

πv+1…

πw

πu…πv

πw+1…πn目標函數差（2-交換）15當距離矩陣D=（dij）為對稱矩陣時，因為dij=dji，上式可簡化為

目標函數差（３-交換）162.0－1背包問題（Zero-oneKnapsackProblem）

給定一個裝載量為M的背包及n件物品，物品i的重量和價值分別為wi和ci，i=1,2,…,n．要求選擇若干件物品裝入背包，使其價值之和為最大．設則問題的數學模型為

xi∈{0,1},i=1,2,…,n17求解0-1背包問題的模擬退火算法描述如下：解空間S={(x1,x2,…,xn)|w1x1+…+wnxn≤M,xi∈{0,1}}

目標函數f(x1,x2,…,xn)=c1x1+c2

x2+…+cnxn→max新解的產生

隨機選取物品i，執行下列三種操作之一：

①若i不在背包中，則將其裝入背包．

②若i不在背包中，則將其裝入背包，同時從背包中隨機取出另一物品j．

③若i已在背包中，則將其取出，并同時隨機裝入另一物品j．

歸納：xi:=1－xi，且（或）xj:=1－xj，i≠j

18背包價值差（目標函數差）及重量差根據產生新解的三種可能，相應的背包價值差為

為判定解的可行性，求出對應的背包重量差為

其中Δm為當前背包重量m的增量．

19接受準則：是增加了可行性測定的Metropolis準則