第7章模擬退火算法

1、2021-11-251模擬退火算法模擬退火算法第第三三講講搜索原理搜索原理2021-11-252 遺傳算法具有隱并行性，它可容易改造成為并行遺傳算法具有隱并行性，它可容易改造成為并行/分布式分布式算法，用來(lái)解決那些復(fù)雜性問(wèn)題。算法，用來(lái)解決那些復(fù)雜性問(wèn)題。到目前，遺傳算法的理論機(jī)制仍不是很清楚，這可到目前，遺傳算法的理論機(jī)制仍不是很清楚，這可能和生命科學(xué)的研究一樣，將是一個(gè)永恒的研究課題，能和生命科學(xué)的研究一樣，將是一個(gè)永恒的研究課題，但也是一個(gè)難題。已有很多學(xué)者對(duì)遺傳算法作了一些深但也是一個(gè)難題。已有很多學(xué)者對(duì)遺傳算法作了一些深入的研究，近幾十年來(lái)，遺傳算法的文獻(xiàn)已相當(dāng)多，由入的研究，近幾十

2、年來(lái)，遺傳算法的文獻(xiàn)已相當(dāng)多，由于本書(shū)篇幅所限，僅介紹了遺傳算法的一些基本知識(shí)。于本書(shū)篇幅所限，僅介紹了遺傳算法的一些基本知識(shí)。 2021-11-253模擬退火算法模擬退火算法模擬退火算法來(lái)源于固體退火原理，將固體加溫至充模擬退火算法來(lái)源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，變?yōu)闊o(wú)序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。根據(jù)能減為最小。根據(jù)Metrop

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

4、迭代，并逐步衰減t值，值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過(guò)程。退火過(guò)特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過(guò)程。退火過(guò)程由冷卻進(jìn)度表程由冷卻進(jìn)度表(Cooling Schedule)控制，包括控制參數(shù)控制，包括控制參數(shù)的初值的初值t及其衰減因子及其衰減因子t、每個(gè)、每個(gè)t值時(shí)的迭代次數(shù)值時(shí)的迭代次數(shù)L和停止和停止條件條件S。 2021-11-2542021-11-255模擬退火算法的模型模擬退火算法的模型模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解

5、三部分。三部分。模擬退火的基本思想模擬退火的基本思想:(1) 初始化：初始溫度初始化：初始溫度T(充分大充分大)，初始解狀態(tài)，初始解狀態(tài)S(是算是算法迭代的起點(diǎn)法迭代的起點(diǎn))， 每個(gè)每個(gè)T值的迭代次數(shù)值的迭代次數(shù)L(2) 對(duì)對(duì)k=1，L做第做第(3)至第至第6步：步：(3) 產(chǎn)生新解產(chǎn)生新解S(4) 計(jì)算增量計(jì)算增量t=C(S)-C(S)，其中，其中C(S)為評(píng)價(jià)函數(shù)為評(píng)價(jià)函數(shù)(5) 若若t0，然后轉(zhuǎn)第，然后轉(zhuǎn)第2步。步。2021-11-2562021-11-2572021-11-258模擬退火算法新解的產(chǎn)生和接受可分為如下四模擬退火算法新解的產(chǎn)生和接受可分為如下四個(gè)步驟：個(gè)步驟： 第一步是由

6、一個(gè)產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個(gè)位于解空間第一步是由一個(gè)產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個(gè)位于解空間的新解；為便于后續(xù)的計(jì)算和接受，減少算法耗時(shí)，通的新解；為便于后續(xù)的計(jì)算和接受，減少算法耗時(shí)，通常選擇由當(dāng)前新解經(jīng)過(guò)簡(jiǎn)單地變換即可產(chǎn)生新解的方法，常選擇由當(dāng)前新解經(jīng)過(guò)簡(jiǎn)單地變換即可產(chǎn)生新解的方法，如對(duì)構(gòu)成新解的全部或部分元素進(jìn)行置換、互換等，注如對(duì)構(gòu)成新解的全部或部分元素進(jìn)行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域結(jié)構(gòu)，意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域結(jié)構(gòu)，因而對(duì)冷卻進(jìn)度表的選取有一定的影響。因而對(duì)冷卻進(jìn)度表的選取有一定的影響。 第二步是計(jì)算與新解所對(duì)應(yīng)的目標(biāo)函數(shù)差。因?yàn)槟繕?biāo)函第二

7、步是計(jì)算與新解所對(duì)應(yīng)的目標(biāo)函數(shù)差。因?yàn)槟繕?biāo)函數(shù)差僅由變換部分產(chǎn)生，所以目標(biāo)函數(shù)差的計(jì)算最好按數(shù)差僅由變換部分產(chǎn)生，所以目標(biāo)函數(shù)差的計(jì)算最好按增量計(jì)算。事實(shí)表明，對(duì)大多數(shù)應(yīng)用而言，這是計(jì)算目增量計(jì)算。事實(shí)表明，對(duì)大多數(shù)應(yīng)用而言，這是計(jì)算目標(biāo)函數(shù)差的最快方法。標(biāo)函數(shù)差的最快方法。2021-11-259 第三步是判斷新解是否被接受第三步是判斷新解是否被接受,判斷的依據(jù)是一個(gè)接受準(zhǔn)判斷的依據(jù)是一個(gè)接受準(zhǔn)則，最常用的接受準(zhǔn)則是則，最常用的接受準(zhǔn)則是Metropo1is準(zhǔn)則準(zhǔn)則: 若若t0則接受則接受S作為新的當(dāng)前解作為新的當(dāng)前解S，否則以概率，否則以概率exp(-t/T)接受接受S作為新作為新的當(dāng)前解的

8、當(dāng)前解S。第四步是當(dāng)新解被確定接受時(shí)，用新解代替當(dāng)前解，第四步是當(dāng)新解被確定接受時(shí)，用新解代替當(dāng)前解，這只需將當(dāng)前解中對(duì)應(yīng)于產(chǎn)生新解時(shí)的變換部分予以實(shí)這只需將當(dāng)前解中對(duì)應(yīng)于產(chǎn)生新解時(shí)的變換部分予以實(shí)現(xiàn)，同時(shí)修正目標(biāo)函數(shù)值即可。此時(shí)，當(dāng)前解實(shí)現(xiàn)了一現(xiàn)，同時(shí)修正目標(biāo)函數(shù)值即可。此時(shí)，當(dāng)前解實(shí)現(xiàn)了一次迭代?？稍诖嘶A(chǔ)上開(kāi)始下一輪試驗(yàn)。而當(dāng)新解被判次迭代?？稍诖嘶A(chǔ)上開(kāi)始下一輪試驗(yàn)。而當(dāng)新解被判定為舍棄時(shí)，則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗(yàn)。定為舍棄時(shí)，則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗(yàn)。2021-11-2510 模擬退火算法與初始值無(wú)關(guān)，算法求得的解與初始解狀模擬退火算法與初始值無(wú)關(guān)，算法求得的解與

9、初始解狀態(tài)態(tài)S(是算法迭代的起點(diǎn)是算法迭代的起點(diǎn))無(wú)關(guān)；模擬退火算法具有漸近收無(wú)關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率斂性，已在理論上被證明是一種以概率l 收斂于全局最優(yōu)收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。解的全局優(yōu)化算法；模擬退火算法具有并行性。2021-11-2511模擬退火算法的簡(jiǎn)單應(yīng)用模擬退火算法的簡(jiǎn)單應(yīng)用 作為模擬退火算法應(yīng)用，討論貨郎擔(dān)問(wèn)題作為模擬退火算法應(yīng)用，討論貨郎擔(dān)問(wèn)題(Travelling Salesman Problem，簡(jiǎn)記為，簡(jiǎn)記為TSP)：設(shè)有：設(shè)有n個(gè)城市，用數(shù)碼個(gè)城市，用數(shù)碼1,n代表。城市代表。城市i和城市和城市j之間

10、的距離為之間的距離為d(i，j) i, j=1,nTSP問(wèn)題是要找遍訪每個(gè)域市恰好一次的一條問(wèn)題是要找遍訪每個(gè)域市恰好一次的一條回路，且其路徑總長(zhǎng)度為最短回路，且其路徑總長(zhǎng)度為最短.。2021-11-2512 解空間：解空間：它為問(wèn)題的所有可能它為問(wèn)題的所有可能(可行的或包括不可行的可行的或包括不可行的)解的集合，它限定了初始解選取和新解產(chǎn)生時(shí)的解的集合，它限定了初始解選取和新解產(chǎn)生時(shí)的范圍。對(duì)無(wú)約束的優(yōu)化問(wèn)題，任一可能解范圍。對(duì)無(wú)約束的優(yōu)化問(wèn)題，任一可能解(possible solution)即為一可行解即為一可行解(feasible solution)，因此解空間就是所有可行解的集合；而在

11、許多組因此解空間就是所有可行解的集合；而在許多組合優(yōu)化問(wèn)題中，一個(gè)解除滿足目標(biāo)函數(shù)最優(yōu)的要合優(yōu)化問(wèn)題中，一個(gè)解除滿足目標(biāo)函數(shù)最優(yōu)的要求外，還必須滿足一組約束求外，還必須滿足一組約束(constraint)，因此在，因此在解集中可能包含一些不可行解解集中可能包含一些不可行解(infeasible so1ution)。為此，可以限定解空間僅為所有可行。為此，可以限定解空間僅為所有可行解的集合，即在構(gòu)造解時(shí)就考慮到對(duì)解的約束；解的集合，即在構(gòu)造解時(shí)就考慮到對(duì)解的約束；也可允許解空間包含不可行解，而在目標(biāo)函數(shù)中也可允許解空間包含不可行解，而在目標(biāo)函數(shù)中加上所謂罰函數(shù)加上所謂罰函數(shù)(penalty fu

12、nction)以以“懲罰懲罰”不不可行解的出現(xiàn)?？尚薪獾某霈F(xiàn)。2021-11-2513 目標(biāo)函數(shù)：目標(biāo)函數(shù)：它是對(duì)問(wèn)題的優(yōu)化目標(biāo)的數(shù)學(xué)描述，通常表它是對(duì)問(wèn)題的優(yōu)化目標(biāo)的數(shù)學(xué)描述，通常表述為若干優(yōu)化目標(biāo)的一個(gè)和式。目標(biāo)函數(shù)的選取述為若干優(yōu)化目標(biāo)的一個(gè)和式。目標(biāo)函數(shù)的選取必須正確體現(xiàn)對(duì)問(wèn)題的整體優(yōu)化要求。例如，如必須正確體現(xiàn)對(duì)問(wèn)題的整體優(yōu)化要求。例如，如上所述，當(dāng)解空間包含不可行解時(shí)，目標(biāo)函數(shù)中上所述，當(dāng)解空間包含不可行解時(shí)，目標(biāo)函數(shù)中應(yīng)包含對(duì)不可行解的罰函數(shù)項(xiàng)，借此將一個(gè)有約應(yīng)包含對(duì)不可行解的罰函數(shù)項(xiàng)，借此將一個(gè)有約束的優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束的優(yōu)化問(wèn)題。一般地，束的優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束的優(yōu)化問(wèn)題。

13、一般地，目標(biāo)函數(shù)值不一定就是問(wèn)題的優(yōu)化目標(biāo)值，但其目標(biāo)函數(shù)值不一定就是問(wèn)題的優(yōu)化目標(biāo)值，但其對(duì)應(yīng)關(guān)系應(yīng)是顯明的。此外，目標(biāo)函數(shù)式應(yīng)當(dāng)是對(duì)應(yīng)關(guān)系應(yīng)是顯明的。此外，目標(biāo)函數(shù)式應(yīng)當(dāng)是易于計(jì)算的，這將有利于在優(yōu)化過(guò)程中簡(jiǎn)化目標(biāo)易于計(jì)算的，這將有利于在優(yōu)化過(guò)程中簡(jiǎn)化目標(biāo)函數(shù)差的計(jì)算以提高算法的效率。函數(shù)差的計(jì)算以提高算法的效率。2021-11-2514 初始解：初始解：是算法迭代的起點(diǎn)，試驗(yàn)表明，模擬退火算是算法迭代的起點(diǎn)，試驗(yàn)表明，模擬退火算法是魯棒的法是魯棒的(Robust)，即最終解的求得幾乎不依，即最終解的求得幾乎不依賴于初始解的選取。賴于初始解的選取。2021-11-2515 求解求解TSP的

14、模擬退火算法模型可描述如下：的模擬退火算法模型可描述如下：解空間解空間 解空間解空間S是遍訪每個(gè)城市恰好一次的所有回路，是遍訪每個(gè)城市恰好一次的所有回路，是是1，n的所有循環(huán)排列的集合，的所有循環(huán)排列的集合，S中的成員記為中的成員記為(w1,w2 ,，wn)，并記，并記wn+1= w1。初始解可選為。初始解可選為(1，n)目標(biāo)函數(shù)目標(biāo)函數(shù) 此時(shí)的目標(biāo)函數(shù)即為訪問(wèn)所有城市的路徑此時(shí)的目標(biāo)函數(shù)即為訪問(wèn)所有城市的路徑總長(zhǎng)度或稱為代價(jià)函數(shù)：總長(zhǎng)度或稱為代價(jià)函數(shù)： 我們要求此代價(jià)函數(shù)的最小值。我們要求此代價(jià)函數(shù)的最小值。2021-11-2516 新解的產(chǎn)生新解的產(chǎn)生 隨機(jī)產(chǎn)生隨機(jī)產(chǎn)生1和和n之間的兩相異

15、數(shù)之間的兩相異數(shù)k和和m，若，若km，則將，則將(w1, w2 ,，wk , wk+1 ,，wm ,，wn)變?yōu)椋鹤優(yōu)椋?wm, wm-1 ,，w1 , wm+1 ,，wk-1 ,wn , wn-1 ,，wk). 上述變換方法可簡(jiǎn)單說(shuō)成是上述變換方法可簡(jiǎn)單說(shuō)成是“逆轉(zhuǎn)中間或者逆轉(zhuǎn)兩端逆轉(zhuǎn)中間或者逆轉(zhuǎn)兩端”。也可以采用其他的變換方法，有些變換有獨(dú)特的優(yōu)也可以采用其他的變換方法，有些變換有獨(dú)特的優(yōu)越性，有時(shí)也將它們交替使用，得到一種更好方法。越性，有時(shí)也將它們交替使用，得到一種更好方法。 2021-11-2517 代價(jià)函數(shù)差代價(jià)函數(shù)差 設(shè)將設(shè)將(w1, w2 ,，wn)變換為變換為(u1, u2

16、,，un), 則代價(jià)函數(shù)差為：則代價(jià)函數(shù)差為： 2021-11-2518根據(jù)上述分析，可寫出用模擬退火算法求解根據(jù)上述分析，可寫出用模擬退火算法求解TSP問(wèn)題的偽程序：?jiǎn)栴}的偽程序：Procedure TSPSA:begin init-of-T; T為初始溫度為初始溫度S=1，n; S為初始值為初始值termination=false;while termination=falsebegin for i=1 to L dobegingenerate(Sform S); 從當(dāng)前回路從當(dāng)前回路S產(chǎn)生新回路產(chǎn)生新回路St:=f(S)-f(S);f(S)為路徑總長(zhǎng)為路徑總長(zhǎng)IF(tRandom-of-

17、0,1)S=S;IF the-halt-condition-is-TRUE THEN termination=true;End;T_lower;End;End2021-11-25192021-11-25202021-11-2521 模擬退火算法的應(yīng)用很廣泛，可以較高的效率求模擬退火算法的應(yīng)用很廣泛，可以較高的效率求解最大截問(wèn)題解最大截問(wèn)題(Max Cut Problem)、0-1背包問(wèn)題背包問(wèn)題(Zero One Knapsack Problem)、圖著色問(wèn)題、圖著色問(wèn)題(Graph Colouring Problem)、調(diào)度問(wèn)題、調(diào)度問(wèn)題(Scheduling Problem)等等。等等。

18、2021-11-25223.5.3 3.5.3 模擬退火算法的參數(shù)控制問(wèn)題模擬退火算法的參數(shù)控制問(wèn)題 模擬退火算法的應(yīng)用很廣泛，可以求解模擬退火算法的應(yīng)用很廣泛，可以求解NP完完全問(wèn)題，但其參數(shù)難以控制，其主要問(wèn)題有以下全問(wèn)題，但其參數(shù)難以控制，其主要問(wèn)題有以下三點(diǎn)：三點(diǎn)：(1) 溫度溫度T的初始值設(shè)置問(wèn)題。的初始值設(shè)置問(wèn)題。溫度溫度T的初始值設(shè)置是影響模擬退火算法全的初始值設(shè)置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優(yōu)解的可能性大，但因此要花費(fèi)大量索到全局最優(yōu)解的可能性大，但因此要花費(fèi)大量的計(jì)算時(shí)間；反之，則可節(jié)約計(jì)算時(shí)間，但全局的計(jì)算時(shí)間；反之，則可節(jié)約計(jì)算時(shí)間，但全局搜索性能可能受到影響。實(shí)際應(yīng)用過(guò)程中，初始搜索性能可能受到影響。實(shí)際應(yīng)用過(guò)程中，初始溫度一般需要依據(jù)實(shí)驗(yàn)結(jié)果進(jìn)行若干次調(diào)整。溫度一般需要依據(jù)實(shí)驗(yàn)結(jié)果進(jìn)行若干次調(diào)整。 2021-11-2523 (2) 退火速度問(wèn)題。退火速度問(wèn)題。模擬退火算法的全局搜索性能也與退火速度密切相模擬退火算法的全局搜索性能也與退火速度密切相關(guān)。一般來(lái)說(shuō)，同一溫度下的關(guān)。一般來(lái)說(shuō)，同一溫度下的“充分充分”搜索搜索(退火退火)是