高等運籌學(xué)(第5章)

第5章模擬退火算法

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

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

1.固體退火與組合優(yōu)化之間的相似性固體退火概念與優(yōu)化問題的對應(yīng)關(guān)系

42.算法思想和步驟

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

SA由與Metropolis準(zhǔn)則對應(yīng)的轉(zhuǎn)移概率Pt確定是否接受從當(dāng)前解xi到新解xj的轉(zhuǎn)移，即

5ProcedureSimulated_Annealing;Begin

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

xi:=x0;（置初始解為當(dāng)前解）

k

:=0;（溫度變化計數(shù)器置0）Repeat

l

:=0;（迭代次數(shù)計數(shù)器）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依據(jù)Metropolis準(zhǔn)則接受新解，因此除接受優(yōu)化解外，還在一定范圍內(nèi)接受惡化解，這正是SA與局部搜索算法的本質(zhì)區(qū)別所在．SA具有如下特點：

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

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

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

SA主要包括“三函數(shù)兩準(zhǔn)則”：解產(chǎn)生函數(shù)（鄰域結(jié)構(gòu)）、解接受函數(shù)、溫度更新函數(shù)、內(nèi)循環(huán)終止準(zhǔn)則和外循環(huán)終止準(zhǔn)則．

1.解產(chǎn)生函數(shù)（鄰域結(jié)構(gòu)）

通常選擇當(dāng)前解經(jīng)簡單變換即可產(chǎn)生新解的方法．盡可能保證產(chǎn)生的候選解遍布整個解空間．應(yīng)能使解空間中的任何兩個狀態(tài)可達．2.解接受函數(shù)

判斷新解是否被接受的依據(jù)是Metropolis準(zhǔn)則：93.初始溫度

從理論上說，初始溫度t0應(yīng)使平穩(wěn)分布中每一狀態(tài)被接受的概率相等，也就是使若取P＝0.9，則在Δf

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

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

104.溫度更新函數(shù)

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

5.內(nèi)循環(huán)終止準(zhǔn)則

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

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

116.外循環(huán)終止準(zhǔn)則

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

7.冷卻進度表

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

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

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

目標(biāo)函數(shù)：訪問所有城市的一個回路的長度14新解的產(chǎn)生：設(shè)用以下方法產(chǎn)生（分別或交替使用）①2-交換．任選訪問的序號u和v（設(shè)u<v），逆轉(zhuǎn)u和v及其之間的訪問順序．當(dāng)前解：π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（設(shè)u<v<w），將u和v之間的子路徑插到w之后訪問．當(dāng)前解：π1…πu-1

πu…πv

πv+1…

πw

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

πv+1…

πw

πu…πv

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

目標(biāo)函數(shù)差（３-交換）162.0－1背包問題（Zero-oneKnapsackProblem）

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

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

目標(biāo)函數(shù)f(x1,x2,…,xn)=c1x1+c2

x2+…+cnxn→max新解的產(chǎn)生

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

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

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

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

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

18背包價值差（目標(biāo)函數(shù)差）及重量差根據(jù)產(chǎn)生新解的三種可能，相應(yīng)的背包價值差為

為判定解的可行性，求出對應(yīng)的背包重量差為

其中Δm為當(dāng)前背包重量m的增量．

19接受準(zhǔn)則：是增加了可行性測定的Metropolis準(zhǔn)則