1、2022-4-81模擬退火算法模擬退火算法第第三三講講搜索原理搜索原理2022-4-82 遺傳算法具有隱并行性，它可容易改造成為并行遺傳算法具有隱并行性，它可容易改造成為并行/分布式分布式算法，用來解決那些復雜性問題。算法，用來解決那些復雜性問題。到目前，遺傳算法的理論機制仍不是很清楚，這可到目前，遺傳算法的理論機制仍不是很清楚，這可能和生命科學的研究一樣，將是一個永恒的研究課題，能和生命科學的研究一樣，將是一個永恒的研究課題，但也是一個難題。已有很多學者對遺傳算法作了一些深但也是一個難題。已有很多學者對遺傳算法作了一些深入的研究，近幾十年來，遺傳算法的文獻已相當多，由入的研究，近幾十年來，遺

2、傳算法的文獻已相當多，由于本書篇幅所限，僅介紹了遺傳算法的一些基本知識。于本書篇幅所限，僅介紹了遺傳算法的一些基本知識。 2022-4-83模擬退火算法模擬退火算法模擬退火算法來源于固體退火原理，將固體加溫至充模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最后在常溫時達到基態，內在每個溫度都達到平衡態，最后在常溫時達到基態，內能減為最小。根據能減為最小。根據Metropolis準則

3、，粒子在溫度準則，粒子在溫度T時趨于時趨于平衡的概率為平衡的概率為e-E/(kT)，其中，其中E為溫度為溫度T時的內能，時的內能，E為為其改變量，其改變量，k為為Boltzmann常數。用固體退火模擬組合優常數。用固體退火模擬組合優化問題，將內能化問題，將內能E模擬為目標函數值模擬為目標函數值f，溫度，溫度T演化成控制演化成控制參數參數t，即得到解組合優化問題的模擬退火算法：由初始，即得到解組合優化問題的模擬退火算法：由初始解解i和控制參數初值和控制參數初值t開始，對當前解重復開始，對當前解重復“產生新解產生新解計計算目標函數差算目標函數差接受或舍棄接受或舍棄”的迭代，并逐步衰減的迭代，并逐步

4、衰減t值，值，算法終止時的當前解即為所得近似最優解，這是基于蒙算法終止時的當前解即為所得近似最優解，這是基于蒙特卡羅迭代求解法的一種啟發式隨機搜索過程。退火過特卡羅迭代求解法的一種啟發式隨機搜索過程。退火過程由冷卻進度表程由冷卻進度表(Cooling Schedule)控制，包括控制參數控制，包括控制參數的初值的初值t及其衰減因子及其衰減因子t、每個、每個t值時的迭代次數值時的迭代次數L和停止和停止條件條件S。 2022-4-842022-4-85模擬退火算法的模型模擬退火算法的模型模擬退火算法可以分解為解空間、目標函數和初始解模擬退火算法可以分解為解空間、目標函數和初始解三部分。三部分。模擬

5、退火的基本思想模擬退火的基本思想:(1) 初始化：初始溫度初始化：初始溫度T(充分大充分大)，初始解狀態，初始解狀態S(是算是算法迭代的起點法迭代的起點)， 每個每個T值的迭代次數值的迭代次數L(2) 對對k=1，L做第做第(3)至第至第6步：步：(3) 產生新解產生新解S(4) 計算增量計算增量t=C(S)-C(S)，其中，其中C(S)為評價函數為評價函數(5) 若若t0，然后轉第，然后轉第2步。步。2022-4-862022-4-872022-4-88模擬退火算法新解的產生和接受可分為如下四模擬退火算法新解的產生和接受可分為如下四個步驟：個步驟： 第一步是由一個產生函數從當前解產生一個位于

6、解空間第一步是由一個產生函數從當前解產生一個位于解空間的新解；為便于后續的計算和接受，減少算法耗時，通的新解；為便于后續的計算和接受，減少算法耗時，通常選擇由當前新解經過簡單地變換即可產生新解的方法，常選擇由當前新解經過簡單地變換即可產生新解的方法，如對構成新解的全部或部分元素進行置換、互換等，注如對構成新解的全部或部分元素進行置換、互換等，注意到產生新解的變換方法決定了當前新解的鄰域結構，意到產生新解的變換方法決定了當前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響。因而對冷卻進度表的選取有一定的影響。 第二步是計算與新解所對應的目標函數差。因為目標函第二步是計算與新解所對應的目標函數差

7、。因為目標函數差僅由變換部分產生，所以目標函數差的計算最好按數差僅由變換部分產生，所以目標函數差的計算最好按增量計算。事實表明，對大多數應用而言，這是計算目增量計算。事實表明，對大多數應用而言，這是計算目標函數差的最快方法。標函數差的最快方法。2022-4-89 第三步是判斷新解是否被接受第三步是判斷新解是否被接受,判斷的依據是一個接受準判斷的依據是一個接受準則，最常用的接受準則是則，最常用的接受準則是Metropo1is準則準則: 若若t0則接受則接受S作為新的當前解作為新的當前解S，否則以概率，否則以概率exp(-t/T)接受接受S作為新作為新的當前解的當前解S。第四步是當新解被確定接受時

8、，用新解代替當前解，第四步是當新解被確定接受時，用新解代替當前解，這只需將當前解中對應于產生新解時的變換部分予以實這只需將當前解中對應于產生新解時的變換部分予以實現，同時修正目標函數值即可。此時，當前解實現了一現，同時修正目標函數值即可。此時，當前解實現了一次迭代。可在此基礎上開始下一輪試驗。而當新解被判次迭代。可在此基礎上開始下一輪試驗。而當新解被判定為舍棄時，則在原當前解的基礎上繼續下一輪試驗。定為舍棄時，則在原當前解的基礎上繼續下一輪試驗。2022-4-810 模擬退火算法與初始值無關，算法求得的解與初始解狀模擬退火算法與初始值無關，算法求得的解與初始解狀態態S(是算法迭代的起點是算法迭

9、代的起點)無關；模擬退火算法具有漸近收無關；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率斂性，已在理論上被證明是一種以概率l 收斂于全局最優收斂于全局最優解的全局優化算法；模擬退火算法具有并行性。解的全局優化算法；模擬退火算法具有并行性。2022-4-811模擬退火算法的簡單應用模擬退火算法的簡單應用 作為模擬退火算法應用，討論貨郎擔問題作為模擬退火算法應用，討論貨郎擔問題(Travelling Salesman Problem，簡記為，簡記為TSP)：設有：設有n個城市，用數碼個城市，用數碼1,n代表。城市代表。城市i和城市和城市j之間的距離為之間的距離為d(i，j) i, j=

10、1,nTSP問題是要找遍訪每個域市恰好一次的一條問題是要找遍訪每個域市恰好一次的一條回路，且其路徑總長度為最短回路，且其路徑總長度為最短.。2022-4-812 解空間：解空間：它為問題的所有可能它為問題的所有可能(可行的或包括不可行的可行的或包括不可行的)解的集合，它限定了初始解選取和新解產生時的解的集合，它限定了初始解選取和新解產生時的范圍。對無約束的優化問題，任一可能解范圍。對無約束的優化問題，任一可能解(possible solution)即為一可行解即為一可行解(feasible solution)，因此解空間就是所有可行解的集合；而在許多組因此解空間就是所有可行解的集合；而在許多組

11、合優化問題中，一個解除滿足目標函數最優的要合優化問題中，一個解除滿足目標函數最優的要求外，還必須滿足一組約束求外，還必須滿足一組約束(constraint)，因此在，因此在解集中可能包含一些不可行解解集中可能包含一些不可行解(infeasible so1ution)。為此，可以限定解空間僅為所有可行。為此，可以限定解空間僅為所有可行解的集合，即在構造解時就考慮到對解的約束；解的集合，即在構造解時就考慮到對解的約束；也可允許解空間包含不可行解，而在目標函數中也可允許解空間包含不可行解，而在目標函數中加上所謂罰函數加上所謂罰函數(penalty function)以以“懲罰懲罰”不不可行解的出現。

12、可行解的出現。2022-4-813 目標函數：目標函數：它是對問題的優化目標的數學描述，通常表它是對問題的優化目標的數學描述，通常表述為若干優化目標的一個和式。目標函數的選取述為若干優化目標的一個和式。目標函數的選取必須正確體現對問題的整體優化要求。例如，如必須正確體現對問題的整體優化要求。例如，如上所述，當解空間包含不可行解時，目標函數中上所述，當解空間包含不可行解時，目標函數中應包含對不可行解的罰函數項，借此將一個有約應包含對不可行解的罰函數項，借此將一個有約束的優化問題轉化為無約束的優化問題。一般地，束的優化問題轉化為無約束的優化問題。一般地，目標函數值不一定就是問題的優化目標值，但其目

13、標函數值不一定就是問題的優化目標值，但其對應關系應是顯明的。此外，目標函數式應當是對應關系應是顯明的。此外，目標函數式應當是易于計算的，這將有利于在優化過程中簡化目標易于計算的，這將有利于在優化過程中簡化目標函數差的計算以提高算法的效率。函數差的計算以提高算法的效率。2022-4-814 初始解：初始解：是算法迭代的起點，試驗表明，模擬退火算是算法迭代的起點，試驗表明，模擬退火算法是魯棒的法是魯棒的(Robust)，即最終解的求得幾乎不依，即最終解的求得幾乎不依賴于初始解的選取。賴于初始解的選取。2022-4-815 求解求解TSP的模擬退火算法模型可描述如下：的模擬退火算法模型可描述如下：解

14、空間解空間 解空間解空間S是遍訪每個城市恰好一次的所有回路，是遍訪每個城市恰好一次的所有回路，是是1，n的所有循環排列的集合，的所有循環排列的集合，S中的成員記為中的成員記為(w1,w2 ,，wn)，并記，并記wn+1= w1。初始解可選為。初始解可選為(1，n)目標函數目標函數 此時的目標函數即為訪問所有城市的路徑此時的目標函數即為訪問所有城市的路徑總長度或稱為代價函數：總長度或稱為代價函數： 我們要求此代價函數的最小值。我們要求此代價函數的最小值。2022-4-816 新解的產生新解的產生 隨機產生隨機產生1和和n之間的兩相異數之間的兩相異數k和和m，若，若km，則將，則將(w1, w2

15、,，wk , wk+1 ,，wm ,，wn)變為：變為：(wm, wm-1 ,，w1 , wm+1 ,，wk-1 ,wn , wn-1 ,，wk). 上述變換方法可簡單說成是上述變換方法可簡單說成是“逆轉中間或者逆轉兩端逆轉中間或者逆轉兩端”。也可以采用其他的變換方法，有些變換有獨特的優也可以采用其他的變換方法，有些變換有獨特的優越性，有時也將它們交替使用，得到一種更好方法。越性，有時也將它們交替使用，得到一種更好方法。 2022-4-817 代價函數差代價函數差 設將設將(w1, w2 ,，wn)變換為變換為(u1, u2 ,，un), 則代價函數差為：則代價函數差為： 2022-4-818

16、根據上述分析，可寫出用模擬退火算法求解根據上述分析，可寫出用模擬退火算法求解TSP問題的偽程序：問題的偽程序：Procedure TSPSA:begin init-of-T; T為初始溫度為初始溫度S=1，n; S為初始值為初始值termination=false;while termination=falsebegin for i=1 to L dobegingenerate(Sform S); 從當前回路從當前回路S產生新回路產生新回路St:=f(S)-f(S);f(S)為路徑總長為路徑總長IF(tRandom-of-0,1)S=S;IF the-halt-condition-is-TRU

17、E THEN termination=true;End;T_lower;End;End2022-4-8192022-4-8202022-4-821 模擬退火算法的應用很廣泛，可以較高的效率求模擬退火算法的應用很廣泛，可以較高的效率求解最大截問題解最大截問題(Max Cut Problem)、0-1背包問題背包問題(Zero One Knapsack Problem)、圖著色問題、圖著色問題(Graph Colouring Problem)、調度問題、調度問題(Scheduling Problem)等等。等等。 2022-4-8223.5.3 3.5.3 模擬退火算法的參數控制問題模擬退火算法的

18、參數控制問題 模擬退火算法的應用很廣泛，可以求解模擬退火算法的應用很廣泛，可以求解NP完完全問題，但其參數難以控制，其主要問題有以下全問題，但其參數難以控制，其主要問題有以下三點：三點：(1) 溫度溫度T的初始值設置問題。的初始值設置問題。溫度溫度T的初始值設置是影響模擬退火算法全的初始值設置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優解的可能性大，但因此要花費大量索到全局最優解的可能性大，但因此要花費大量的計算時間；反之，則可節約計算時間，但全局的計算時間；反之，則可節約計算時間，但全局搜索性能可能受到影響。實際應用過程中，初始搜索性能可能受到影響。實際應用過程中，初始溫度一般需要依據實驗結果進行若干次調整。溫度一般需要依據實驗結果進行若干次調整。 2022-4-823 (2) 退火速度問題。退火速度問題。模擬退火算法的全局搜索性能也與退火速度密切相模擬退火算法的全局搜索性能也與退火速度密切相關。一般來說，同一溫度下的關。一般來說，同一溫度下的“充分充分”搜索搜索(退火退火)是相當是