模擬退火算法研究概況

1、模擬退火算法文獻(xiàn)綜述呂正祥 交控15011模擬退火算法簡(jiǎn)述1.1模擬退火算法的來源模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。 模擬退火算法(Simulated Annealing，SA)最早由Kirkpatrick等應(yīng)用于組合優(yōu)化領(lǐng)域，它是基于Monte-Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。模擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降,結(jié)合概率突跳特性

2、在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。模擬退火算法是一種通用的優(yōu)化算法，理論上算法具有概率的全局優(yōu)化性能,目前已在工程中得到了廣泛應(yīng)用，諸如VLSI、生產(chǎn)調(diào)度、控制工程、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、信號(hào)處理等領(lǐng)域。 模擬退火算法是通過賦予搜索過程一種時(shí)變且最終趨于零的概率突跳性，從而可有效避免陷入局部極小并最終趨于全局最優(yōu)的串行結(jié)構(gòu)的優(yōu)化算法。1.2模擬退火算法的模型 模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。 1.3模擬退火的基本思想 (1) 初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點(diǎn))， 每個(gè)T值的迭代次數(shù)L (2)

3、對(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則接受S作為新的當(dāng)前解，否則以概率exp(-t/T)接受S作為新的當(dāng)前解. (6) 如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。終止條件通常取為連續(xù)若干個(gè)新解都沒有被接受時(shí)終止算法。 (7) T逐漸減少，且T->0，然后轉(zhuǎn)第2步。2.模擬退火算法流程2.1模擬退火算法流程圖2.2模擬退火算法中參數(shù)的選擇2.2.1冷卻進(jìn)度表我們稱調(diào)整模擬退火法的一系列重要參數(shù)為冷卻進(jìn)度表。它控制參數(shù)T的初值及其衰減函數(shù)，對(duì)應(yīng)的MARKOV鏈長(zhǎng)度和停止條件，非常重

4、要。一個(gè)冷卻進(jìn)度表應(yīng)當(dāng)規(guī)定下述參數(shù)：1控制參數(shù)t的初值t0;2控制參數(shù)t的衰減函數(shù)；3馬爾可夫鏈的長(zhǎng)度Lk。（即每一次隨機(jī)游走過程，要迭代多少次，才能趨于一個(gè)準(zhǔn)平衡分布，即一個(gè)局部收斂解位置）4結(jié)束條件的選擇2.2.2有效的冷卻進(jìn)度表判據(jù)：一算法的收斂：主要取決于衰減函數(shù)和馬可夫鏈的長(zhǎng)度及停止準(zhǔn)則的選擇二算法的實(shí)驗(yàn)性能：最終解的質(zhì)量和CPU的時(shí)間  參數(shù)的選取：一）控制參數(shù)初值T0的選取一般要求初始值t0的值要充分大，即一開始即處于高溫狀態(tài)，且Metropolis的接收率約為1。(1) 均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值的方差為初溫。(2) 隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的

5、最大目標(biāo)值差|max|，然后依據(jù)差值，利用一定的函數(shù)確定初溫。比如，t0=max/pr ，其中pr為初始接受概率。二）衰減函數(shù)的選取衰減函數(shù)用于控制溫度的退火速度，一個(gè)常用的函數(shù)為：T(n + 1) = K*T(n)，其中K是一個(gè)非常接近于1的常數(shù)。三）馬可夫鏈長(zhǎng)度L的選取原則是：在衰減參數(shù)T的衰減函數(shù)已選定的前提下，L應(yīng)選得在控制參數(shù)的每一取值上都能恢復(fù)準(zhǔn)平衡。四）終止條件有很多種終止條件的選擇，各種不同的條件對(duì)算法的性能和解的質(zhì)量有很大影響，我們只介紹一個(gè)常用的終止條件。即上一個(gè)最優(yōu)解與最新的一個(gè)最優(yōu)解的之差小于某個(gè)容差，即可停止此次馬爾可夫鏈的迭代。3模擬退火算法的優(yōu)缺點(diǎn) &#

6、160; 優(yōu)點(diǎn)：計(jì)算過程簡(jiǎn)單，通用，魯棒性強(qiáng)，適用于并行處理，可用于求解復(fù)雜的非線性優(yōu)化問題。缺點(diǎn)：收斂速度慢，執(zhí)行時(shí)間長(zhǎng)，算法性能與初始值有關(guān)及參數(shù)敏感等缺點(diǎn)經(jīng)典模擬退火算法的缺點(diǎn)：（1)如果降溫過程足夠緩慢，多得到的解的性能會(huì)比較好，但與此相對(duì)的是收斂速度太慢；(2)如果降溫過程過快，很可能得不到全局最優(yōu)解。 模擬退火算法的改進(jìn)：(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ì)合

7、適的算法終止準(zhǔn)則。也可通過增加某些環(huán)節(jié)而實(shí)現(xiàn)對(duì)模擬退火算法的改進(jìn)。主要的改進(jìn)方式包括：(1) 增加升溫或重升溫過程。在算法進(jìn)程的適當(dāng)時(shí)機(jī)，將溫度適當(dāng)提高，從而可激活各狀態(tài)的接受概率，以調(diào)整搜索進(jìn)程中的當(dāng)前狀態(tài)，避免算法在局部極小解處停滯不前。(2) 增加記憶功能。為避免搜索過程中由于執(zhí)行概率接受環(huán)節(jié)而遺失當(dāng)前遇到的最優(yōu)解，可通過增加存儲(chǔ)環(huán)節(jié)，將一些在這之前好的態(tài)記憶下來。(3) 增加補(bǔ)充搜索過程。即在退火過程結(jié)束后，以搜索到的最優(yōu)解為初始狀態(tài)，再次執(zhí)行模擬退火過程或局部性搜索。(4) 對(duì)每一當(dāng)前狀態(tài)，采用多次搜索策略，以概率接受區(qū)域內(nèi)的最優(yōu)狀態(tài)，而非標(biāo)準(zhǔn)SA的單次比較方式。(5) 結(jié)合其他搜索

8、機(jī)制的算法，如遺傳算法、混沌搜索等。(6)上述各方法的綜合應(yīng)用。4船舶碰撞相關(guān)領(lǐng)域有關(guān)模擬退火算法的應(yīng)用4.1舶碰撞危險(xiǎn)的量化研究基本上經(jīng)歷了四個(gè)階段:第一階段是基于交通流理論，以船舶會(huì)遇率( 或會(huì)遇次數(shù)等)、特定水域歷史碰撞事故等，評(píng)價(jià)特定水域的碰撞危險(xiǎn)度。第二階段是從微觀的角度，根據(jù)人體行為學(xué)及心理學(xué)等，以船舶領(lǐng)域或動(dòng)界評(píng)價(jià)碰撞危險(xiǎn)度。第三階段在確定船舶碰撞危險(xiǎn)度時(shí)，應(yīng)該綜合考慮 DDCPA和TTCPA兩方面的影響。第四階段是實(shí)現(xiàn)TTCPA與DDCPA 確定碰撞危險(xiǎn)度1。船舶會(huì)遇態(tài)勢(shì)的劃分船舶會(huì)遇是海上最常見的船舶交會(huì)態(tài)勢(shì)，其劃分原則是根據(jù)國際海上避碰規(guī)則、航海習(xí)慣和自動(dòng)避碰方法三者綜合分

9、析的結(jié)果。由文獻(xiàn) 1可知，海上互見中的兩船，可劃分為對(duì)遇 (F)、交叉相遇 (A、B、E)和追越 (C、D)幾類會(huì)遇態(tài)勢(shì)，如圖1所示。圖中對(duì)相對(duì)舷角為F、A、B區(qū)域的來船，本船為讓路船。對(duì)來自F、A區(qū)域的船，本船應(yīng)采取向右轉(zhuǎn)向避讓操縱，對(duì)來自B區(qū)域的船，因與本船的相對(duì)舷角較大，可采用向左轉(zhuǎn)向避讓操縱；對(duì)相對(duì)舷角為E、D、C區(qū)域的來船，本船可視為直航船而不采取任何避讓操縱，只有當(dāng)出現(xiàn)緊近局面時(shí)，本船才采取避讓操縱。圖一 互見中的兩船會(huì)遇態(tài)勢(shì)的劃分4.2船舶碰撞危險(xiǎn)度的確定本文將綜合前人的研究成果 ,以來船與本船構(gòu)成的方位 (B)、距離 (D)、船速比 (K)、最近會(huì)遇距離 ( DCPA)和最近會(huì)

10、遇時(shí)間 ( TCPA)為參數(shù) ,給出來船與本船構(gòu)成的碰撞危險(xiǎn)度估計(jì)。設(shè)與本船會(huì)遇的目標(biāo)船數(shù)為n1艘 , UDCPAi 、UTCPAi、UDi、UBi 、UKi為目標(biāo)船i各參數(shù)的危險(xiǎn)隸屬度且屬于 0, 1， i = 1, 2, ,n，則目標(biāo)船i的碰撞危險(xiǎn)度fi可表示18 為： fi (uDCPAi、uTCPAi、uDi、uBi、uKi ) = aDCPA uDCPAi + aTCPAuTCPAi+ aDuDi+aBuBi +aKuKiD1為最晚避讓距離，D2為可采取避讓措施距離；C為碰角 (0C 180°)；W為常數(shù)，取W =2；aDCPA、aTCPA 、aD、aB、aK為目標(biāo)船參數(shù)的

11、權(quán)重，均屬于 0, 1,且aDCPA+aTCPA +aD+aB+aK=1。4.3目標(biāo)函數(shù)模型當(dāng)本船與多個(gè)來船會(huì)遇時(shí) ,如何根據(jù)多個(gè)來船的會(huì)遇態(tài)勢(shì) ,選擇較為合理和最為有效的轉(zhuǎn)讓幅度問題，一直是人們關(guān)注和研究的焦點(diǎn)。 將本船與多船間的轉(zhuǎn)向避碰幅度問題視作一類多目標(biāo)函數(shù)優(yōu)化問題 ,然后應(yīng)用模擬退火算法 ,從可行解空間中求出滿足目標(biāo)函數(shù)和約束條件的最優(yōu)轉(zhuǎn)向避碰幅度解 ,使得轉(zhuǎn)讓后的本船滿足: 與各會(huì)遇目標(biāo)船間的碰撞危險(xiǎn)度盡量減小; 盡量使轉(zhuǎn)讓的角度最??； 航行最少的時(shí)間后，本船恢復(fù)原航向、航速。4.4模擬退火算法的最優(yōu)轉(zhuǎn)向避碰幅度決策模擬退火算法2 是源于對(duì)固體退火過程的直接簡(jiǎn)單模擬而建立起的一種通

12、用隨機(jī)搜索技術(shù)。由于其具有穩(wěn)鍵性、健壯性和高效性等特點(diǎn) ,近年來已在求解許多組合優(yōu)化問題 ,特別是在解 NP完全問題中得到了成功應(yīng)用。 本文將結(jié)合船舶避碰實(shí)際 ,把模擬退火算法引入到船舶避碰決策領(lǐng)域 ,在可行解空間中隨機(jī)搜索 ,從中求出本船滿足多目標(biāo)函數(shù)和約束條件的最優(yōu)轉(zhuǎn)向幅度。 具體實(shí)現(xiàn)步驟為：以均勻概率在可行解空間 30, 180中隨機(jī)產(chǎn)成一個(gè)轉(zhuǎn)向幅度 x ,作為初始狀態(tài)的當(dāng)前最優(yōu)點(diǎn);設(shè)置初始溫度 T0 = Tmax；設(shè)置循環(huán)初值 num = 1；算出本船轉(zhuǎn)向前與各目標(biāo)船構(gòu)成的碰撞危險(xiǎn)度 fi和轉(zhuǎn)向x 后與各目標(biāo)船構(gòu)成的碰撞危險(xiǎn)度 f1i (x) ,i = 1, 2, ,n；計(jì)算殘差和；對(duì)當(dāng)前最優(yōu)點(diǎn)x作一隨機(jī)擾動(dòng) (如加白噪聲 ) ,產(chǎn)生一個(gè)新的最優(yōu)點(diǎn)。重新計(jì)算增量；應(yīng)用 Meteopolis規(guī)則確定是否接受新產(chǎn)生的最優(yōu)點(diǎn)。如果 < 0,則接受該新產(chǎn)生的最優(yōu)點(diǎn)為當(dāng)前最優(yōu)點(diǎn) ,否則以概率接受該新產(chǎn)生的最優(yōu)點(diǎn)為當(dāng)前最優(yōu)點(diǎn)；判斷num ,若num <終止步數(shù),則num = num+ 1 ,轉(zhuǎn)至步驟 ,否則進(jìn)行降溫 ,使 T0 取值為T，這里0<T<1；若連續(xù)若干次降溫后最優(yōu)點(diǎn)沒有改進(jìn)或降溫到給定的閾值 ,或殘差最小 ,則輸出當(dāng)前優(yōu)點(diǎn) ,計(jì)算結(jié)束;否則轉(zhuǎn)至步驟。參考文獻(xiàn)：1