第3章 模擬退火算法

1、第三章第三章 模擬退火算法模擬退火算法（Simulated AnnealingSimulated Annealing）050010001500200025003000-3-2-10123xf(x)搜索問題描述搜索問題描述除高度信息外，對環(huán)境除高度信息外，對環(huán)境沒有任何感知能力沒有任何感知能力最優(yōu)解位于海拔最優(yōu)解位于海拔最高處最高處可以任意可以任意方式移動方式移動搜索問題描述搜索問題描述nLandscape with various featuresObjectivefunctionshoulderglobal maxlocal maxflat local maxcurrent stateSta

2、te space搜索算法搜索算法n盲目搜索盲目搜索還是還是啟發(fā)式搜索啟發(fā)式搜索？n按照預定的控制策略實行搜索，在搜索過程中按照預定的控制策略實行搜索，在搜索過程中獲取的中間信息不用來改進控制策略，稱為盲獲取的中間信息不用來改進控制策略，稱為盲目搜索，反之，稱為啟發(fā)式搜索。目搜索，反之，稱為啟發(fā)式搜索。n關于關于“啟發(fā)式啟發(fā)式”，可有兩種看法：，可有兩種看法：n1) 任何有助于找到問題的最優(yōu)解，但不能保證找到任何有助于找到問題的最優(yōu)解，但不能保證找到最優(yōu)解的方法均是啟發(fā)式方法；最優(yōu)解的方法均是啟發(fā)式方法；n2) 有助于加速求解過程和找到較優(yōu)解的方法是啟發(fā)有助于加速求解過程和找到較優(yōu)解的方法是啟發(fā)

3、式方法。式方法。搜索算法搜索算法n盲目搜索盲目搜索n深度優(yōu)先、廣度優(yōu)先、代價優(yōu)先、向前、向后、雙深度優(yōu)先、廣度優(yōu)先、代價優(yōu)先、向前、向后、雙向。向。n啟發(fā)式搜索啟發(fā)式搜索n爬山法、模擬退火算法、遺傳算法、粒子群算法、爬山法、模擬退火算法、遺傳算法、粒子群算法、蟻群算法。蟻群算法。貪心算法貪心算法n隨機選定一個初始解隨機選定一個初始解x0；nDo while （終止條件不滿足）終止條件不滿足）n在某個鄰域函數(shù)所定義的鄰域范圍內，按照某個在某個鄰域函數(shù)所定義的鄰域范圍內，按照某個（隨機）擾動（隨機）擾動 產生策略，得到一個新解產生策略，得到一個新解xi；n對新解進行評估，得對新解進行評估，得f(x

4、i)；n如果如果f(xi) f(xi)（或者或者f(xi) f(xi) 且且f(xi) f(xij)（或者或者f(xi) f(xi) 且且f(xi) f(xij)（或者或者f(xi) Tmin /降溫過程降溫過程nfor j = 1k /等溫過程等溫過程n對當前最優(yōu)解對當前最優(yōu)解xbest按照某一鄰域函數(shù)，產生一新的解按照某一鄰域函數(shù)，產生一新的解xnew。計算新計算新的目標函數(shù)值的目標函數(shù)值E(xnew) ，并計算目標函數(shù)值的增量，并計算目標函數(shù)值的增量 E = E(xnew) - E(xbest) 。n如果如果 E 0，則則xbest = xnew；n如果如果 E 0，則則p = exp(

5、- E /T(i);n如果如果c = random0,1 p， xbest = xnew; 否則否則 xbest = xbest。nEnd forn按照溫度控制策略更新按照溫度控制策略更新T；nEnd Don輸出當前最優(yōu)點，計算結束。輸出當前最優(yōu)點，計算結束。模擬退火算法（要素）模擬退火算法（要素）1、狀態(tài)空間與狀態(tài)產生函數(shù)（鄰域函數(shù)）、狀態(tài)空間與狀態(tài)產生函數(shù)（鄰域函數(shù)）n搜索空間也稱為狀態(tài)空間，它由經過編碼的可行解的搜索空間也稱為狀態(tài)空間，它由經過編碼的可行解的集合所組成。集合所組成。n狀態(tài)產生函數(shù)狀態(tài)產生函數(shù)(鄰域函數(shù)鄰域函數(shù))應盡可能保證產生的候選解能應盡可能保證產生的候選解能遍布全部解

6、空間。通常由兩部分組成，即遍布全部解空間。通常由兩部分組成，即產生候選解產生候選解的方式的方式和和候選解產生的概率分布候選解產生的概率分布。n候選解一般按照某一概率分布對解空間進行隨機采樣候選解一般按照某一概率分布對解空間進行隨機采樣來獲得。來獲得。n概率分布可以是均勻分布、正態(tài)分布、指數(shù)分布等等。概率分布可以是均勻分布、正態(tài)分布、指數(shù)分布等等。模擬退火算法（要素）模擬退火算法（要素）2、狀態(tài)轉移概率（接受概率）、狀態(tài)轉移概率（接受概率） pn狀態(tài)轉移概率是指從一個狀態(tài)狀態(tài)轉移概率是指從一個狀態(tài)xold(一個可行解一個可行解)向另一向另一個狀態(tài)個狀態(tài)xnew(另一個可行解另一個可行解)的轉移概

7、率的轉移概率;n通俗的理解是接受一個新解為當前解的概率通俗的理解是接受一個新解為當前解的概率;n它與當前的溫度參數(shù)它與當前的溫度參數(shù)T有關，隨溫度下降而減小。有關，隨溫度下降而減小。n一般采用一般采用Metropolis準則準則)()()()(exp()()(1oldnewoldnewoldnewxExEifTxExExExEifp模擬退火算法（要素）模擬退火算法（要素）3、冷卻進度表、冷卻進度表T(t)冷卻進度表是指從某一高溫狀態(tài)冷卻進度表是指從某一高溫狀態(tài)To向低溫狀態(tài)冷卻時的降向低溫狀態(tài)冷卻時的降溫管理表。溫管理表。假設時刻假設時刻t的溫度用的溫度用T(t)來表示，則來表示，則經典模擬退

8、火算法的降經典模擬退火算法的降溫方式溫方式為：為：而而快速模擬退火算法的降溫方式快速模擬退火算法的降溫方式為：為：這兩種方式都能夠使得模擬退火算法收斂于全局最小點。這兩種方式都能夠使得模擬退火算法收斂于全局最小點。)1lg()(0tTtTtTtT1)(002004006008001000204060801001201400200400600800100005101520253035404550)1lg()(0tTtTtTtT1)(0模擬退火算法（要素）模擬退火算法（要素）4、初始溫度、初始溫度T0實驗表明，初溫越大，獲得高質量解的幾率越大，但實驗表明，初溫越大，獲得高質量解的幾率越大，但花費的

9、計算時間將增加。因此，初溫的確定應折衷考花費的計算時間將增加。因此，初溫的確定應折衷考慮優(yōu)化質量和優(yōu)化效率，常用方法包括：慮優(yōu)化質量和優(yōu)化效率，常用方法包括：(1) 均勻抽樣一組狀態(tài)，以各狀態(tài)目標值的方差為初溫。均勻抽樣一組狀態(tài)，以各狀態(tài)目標值的方差為初溫。(2) 隨機產生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標值差隨機產生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標值差| max|，然后依據差值，利用一定的函數(shù)確定初溫。比如，然后依據差值，利用一定的函數(shù)確定初溫。比如，t0= max/pr ，其中其中pr為初始接受概率。為初始接受概率。(3) 利用經驗公式給出。利用經驗公式給出。模擬退火算法（要素）模擬退火

10、算法（要素）5、內循環(huán)終止準則、內循環(huán)終止準則或稱或稱Metropolis抽樣穩(wěn)定準則，用于決定在各溫度抽樣穩(wěn)定準則，用于決定在各溫度下產生候選解的數(shù)目。常用的抽樣穩(wěn)定準則包括：下產生候選解的數(shù)目。常用的抽樣穩(wěn)定準則包括：(1) 檢驗目標函數(shù)的均值是否穩(wěn)定；檢驗目標函數(shù)的均值是否穩(wěn)定；(2) 連續(xù)若干步的目標值變化較??；連續(xù)若干步的目標值變化較小；(3) 按一定的步數(shù)抽樣。按一定的步數(shù)抽樣。模擬退火算法（要素）模擬退火算法（要素）6、外循環(huán)終止準則、外循環(huán)終止準則即算法終止準則，常用的包括：即算法終止準則，常用的包括：(1) 設置終止溫度的閾值；設置終止溫度的閾值；(2) 設置外循環(huán)迭代次數(shù)；

11、設置外循環(huán)迭代次數(shù)；(3) 算法搜索到的最優(yōu)值連續(xù)若干步保持不變；算法搜索到的最優(yōu)值連續(xù)若干步保持不變；(4) 檢驗系統(tǒng)熵是否穩(wěn)定。檢驗系統(tǒng)熵是否穩(wěn)定。模擬退火算法的改進模擬退火算法的改進(1) 設計合適的狀態(tài)產生函數(shù)，使其根據搜索進程的需要設計合適的狀態(tài)產生函數(shù)，使其根據搜索進程的需要表現(xiàn)出狀態(tài)的全空間分散性或局部區(qū)域性。表現(xiàn)出狀態(tài)的全空間分散性或局部區(qū)域性。(2) 設計高效的退火策略（不同問題的最佳退火策略可能設計高效的退火策略（不同問題的最佳退火策略可能不同）。不同）。(3) 避免狀態(tài)的迂回搜索。避免狀態(tài)的迂回搜索。(4) 采用并行搜索結構。采用并行搜索結構。(5) 為避免陷入局部極小，

12、改進對溫度的單調控制方式為避免陷入局部極小，改進對溫度的單調控制方式(6) 選擇合適的初始狀態(tài)。選擇合適的初始狀態(tài)。(7) 設計合適的算法終止準則。設計合適的算法終止準則。模擬退火算法的改進模擬退火算法的改進也可通過增加某些環(huán)節(jié)而實現(xiàn)對模擬退火算法的改進。主要的改也可通過增加某些環(huán)節(jié)而實現(xiàn)對模擬退火算法的改進。主要的改進方式包括：進方式包括：(1) 增加升溫或重升溫過程增加升溫或重升溫過程。在算法進程的適當時機，將溫度適當提。在算法進程的適當時機，將溫度適當提高，從而可激活各狀態(tài)的接受概率，以調整搜索進程中的當前狀高，從而可激活各狀態(tài)的接受概率，以調整搜索進程中的當前狀態(tài)，避免算法在局部極小解

13、處停滯不前。態(tài)，避免算法在局部極小解處停滯不前。(2) 增加記憶功能增加記憶功能。為避免搜索過程中由于執(zhí)行概率接受環(huán)節(jié)而遺失。為避免搜索過程中由于執(zhí)行概率接受環(huán)節(jié)而遺失當前遇到的最優(yōu)解，可通過增加存儲環(huán)節(jié)，將當前遇到的最優(yōu)解，可通過增加存儲環(huán)節(jié)，將“Best So Far”的的狀態(tài)記憶下來。狀態(tài)記憶下來。(3) 增加補充搜索過程增加補充搜索過程。即在退火過程結束后，以搜索到的最優(yōu)解為。即在退火過程結束后，以搜索到的最優(yōu)解為初始狀態(tài)，再次執(zhí)行模擬退火過程或局部性搜索。初始狀態(tài)，再次執(zhí)行模擬退火過程或局部性搜索。(4) 對每一當前狀態(tài)，采用多次搜索策略，以概率接受區(qū)域內的最優(yōu)對每一當前狀態(tài)，采用多次搜索策略，以概率接受區(qū)域內的最優(yōu)狀態(tài)，而非標準狀態(tài)，而非標準SA的單次比較方式。的單次比較方式。(5) 結合其他搜索機制的算法，如遺傳算法、混沌搜索等。結合其他搜索機制的算法，如遺傳算法、混沌搜索等。(6)上述各方法的綜合應用。上述各方法的綜合應用。算法實現(xiàn)與應用算法實現(xiàn)與應用nTSP問題的求解問題的求解n編碼（城市