模擬退火算法的改進(jìn)

1、模擬退火算法 模擬退火算法模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。根據(jù) Metropolis 準(zhǔn)則，粒子在溫度 T 時(shí)趨于平衡的概率為 e-ΔE/(kT)，其中 E 為溫度 T 時(shí)的內(nèi)能，ΔE 為其改變量，k 為 Boltzmann 常數(shù)。用固體退火模擬組合優(yōu)化問題，將內(nèi)能 E

2、 模擬為目標(biāo)函數(shù)值 f，溫度 T 演化成控制參數(shù) t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解 i 和控制參數(shù)初值 t 開始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減 t 值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過程。退火過程由冷卻進(jìn)度表(Cooling Schedule)控制，包括控制參數(shù)的初值 t 及其衰減因子Δt、每個(gè) t 值時(shí)的迭代次數(shù) L 和停止

3、條件 S。 模擬退火算法的模型 模擬退火算法的模型模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。模擬退火的基本思想 模擬退火的基本思想:(1) 初始化：初始溫度 T(充分大)，初始解狀態(tài) S(是算法迭代的起點(diǎn))， 每個(gè) T 值的迭代次數(shù) L(2) 對(duì) k=1，……，L 做第(3)至第 6 步：(3) 產(chǎn)生新解 S′(4) 計(jì)算增量Δt′=C(S′)-C(S)，其中 C(S)為評(píng)價(jià)函數(shù)(5) 若Δt′0，然后轉(zhuǎn)第 2 步。模擬退火

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

5、以目標(biāo)函數(shù)差的計(jì)算最好按增量計(jì)算。事實(shí)表明，對(duì)大多數(shù)應(yīng)用而言，這是計(jì)算目標(biāo)函數(shù)差的最快方法。第三步是判斷新解是否被接受,判斷的依據(jù)是一個(gè)接受準(zhǔn)則，最常用的接受準(zhǔn)則是 Metropo1is 準(zhǔn)則: 若Δt′<0 則接受 S′作為新的當(dāng)前解 S，否則以概率 exp(-Δt′/T)接受 S′作為新的當(dāng)前解 S。第四步是當(dāng)新解被確定接受時(shí)，用新解代替當(dāng)前解，這只需將當(dāng)前解中對(duì)應(yīng)于產(chǎn)生新解時(shí)的變換部分予以實(shí)現(xiàn)，同時(shí)修正目標(biāo)函數(shù)值即可。此時(shí)，

6、當(dāng)前解實(shí)現(xiàn)了一次迭代?？稍诖嘶A(chǔ)上開始下一輪試驗(yàn)。而當(dāng)新解被判定為舍棄時(shí)，則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗(yàn)。模擬退火算法與初始值無關(guān)，算法求得的解與初始解狀態(tài) S(是算法迭代的起點(diǎn))無關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率 l 收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。模擬退火算法的改進(jìn) 模擬退火算法的改進(jìn)在確保一定要求的優(yōu)化質(zhì)量基礎(chǔ)上,提高模擬退火的搜索效率(時(shí)間性能),是對(duì) SA 算法進(jìn)行改進(jìn)的

7、主要內(nèi)容.可行的方案包括:(1) 設(shè)計(jì)合適的狀態(tài)產(chǎn)生函數(shù),使其根據(jù)搜索進(jìn)程的需要表現(xiàn)出狀態(tài)的全空間分散性或局部區(qū)域性.(2) 設(shè)計(jì)高效的退火歷程.(3) 避免狀態(tài)的迂回搜索(4) 采用并行搜索結(jié)構(gòu).(5) 為避免陷入局部極小,改進(jìn)對(duì)溫度的控制方式.(6) 選擇合適的初始狀態(tài).(7) 設(shè)計(jì)合適的算法終止準(zhǔn)則.此外,對(duì)模擬退火算法的改進(jìn),也可通過增加某些環(huán)節(jié)而實(shí)現(xiàn).主要的改進(jìn)方式包括:(1) 增加升溫或重升溫過程.在算法進(jìn)程的適當(dāng)時(shí)機(jī),將溫

8、度適當(dāng)提高,從而可激活各狀態(tài)的接受概率, 以調(diào)整搜索進(jìn)程中的當(dāng)前狀態(tài),避免算法在局部極小解處停滯不前.(2) 增加記憶功能.為避免搜索進(jìn)程中由于執(zhí)行概率接受環(huán)節(jié)而遺失當(dāng)前遇到的最優(yōu)解,可通過增加存儲(chǔ)環(huán)節(jié),將”Best So Far”的狀態(tài)記憶下來.(3) 增加補(bǔ)充搜索進(jìn)程.即在退火進(jìn)程結(jié)束后,以搜索到的最優(yōu)解為初始狀態(tài),再次執(zhí)行模擬退火過程或局部趨化性搜索.(4) 對(duì)每一當(dāng)前狀態(tài),采用多次搜索策略, 以概率接受區(qū)域內(nèi)的最優(yōu)狀態(tài),而非標(biāo)

9、準(zhǔn) SA 的單次比較方式.(5) 結(jié)合其他搜索機(jī)制的算法,如遺傳算法,混沌搜索等.(6) 上述各方法的綜合應(yīng)用.下面介紹一種對(duì)退火過程和抽樣過程進(jìn)行修改的兩階段改進(jìn)策略.熟知，模擬退火算法在局部極小解處有機(jī)會(huì)跳出并最終趨于全局最優(yōu)的根本原因是算法通過概率判斷來接受新狀態(tài)，這在理論上了已得到嚴(yán)格證明，即當(dāng)初溫充分高，降溫足夠慢，每一溫度下抽樣足夠長(zhǎng)，最終溫度趨于零時(shí)，算法最終以概率 1 收斂到時(shí)全局最優(yōu)解。但由于全局收斂條件難以實(shí)現(xiàn)，并且

10、“概率接受”使得當(dāng)前狀態(tài)可能比搜索軌跡中的某些中間狀態(tài)要差，從而實(shí)際算法往往最終得到近似最優(yōu)解，甚至可能比中間經(jīng)歷的最好解差，而且搜索效率較差。為了不遺失”Best So Far”的狀態(tài)，并提高搜索效率，改進(jìn)的做法是：在算法搜索過程中保留中間最優(yōu)解，并即時(shí)更新；設(shè)置雙閾值使得在盡量保持最優(yōu)性的前提下減少計(jì)算量，即在各溫度下當(dāng)前狀態(tài)連接 step1 步保持不變認(rèn)為 Metropolis 抽樣穩(wěn)定，若連續(xù) step2次退溫進(jìn)程中所得的最優(yōu)解