模擬退火算法及其改進(jìn)_劉懷亮.pdf

《模擬退火算法及其改進(jìn)_劉懷亮.pdf》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第4卷第6期廣州大學(xué)學(xué)報(bào)(自然科學(xué)版)Vol.4No.62005年12月JournalofGuangzhouUniversity(NaturalScienceEdition)Dec.2005文章編號:1671-4229(2005)06-0503-04模擬退火算法及其改進(jìn)劉懷亮(廣州大學(xué)信息與機(jī)電工程學(xué)院,廣東廣州510006)摘要:介紹了模擬退火算法的背景、原理和具體實(shí)現(xiàn)方法,分析了它的不足之處,討論了它的改進(jìn)措施,并進(jìn)行了仿真實(shí)驗(yàn)驗(yàn)證.關(guān)鍵詞:模擬退火算法;組合優(yōu)化問題;全局優(yōu)化算法;算法改進(jìn);算法實(shí)現(xiàn)中圖分類號:TP15文獻(xiàn)標(biāo)識碼:A將該思想引入組合優(yōu)化

2、理論,解決了許多諸如VL-0引言SI等大規(guī)模優(yōu)化設(shè)計(jì)問題.近年來該算法引起了巨型計(jì)算機(jī)系統(tǒng)設(shè)計(jì)、大規(guī)模集成電路優(yōu)化、圖像自然科學(xué)、管理科學(xué)和工程技術(shù)領(lǐng)域里存在處理、生物學(xué)、分子物理和化學(xué)、數(shù)值分析、復(fù)雜布大量的組合優(yōu)化問題,其求解時(shí)間隨問題規(guī)模呈局等領(lǐng)域廣泛的重視.指數(shù)級增長,當(dāng)規(guī)模稍大時(shí)就會因時(shí)間限制而失112算法原理去可行性,對這類問題的解決具有重要的理論和模擬退火算法是源于物理中固體物質(zhì)的退火現(xiàn)實(shí)意義.人們提出了許多近似算法,但這些算法過程的原理.在熱力學(xué)中將系統(tǒng)(如處于溶化狀態(tài)或者由于過于注意個(gè)別問題的特征而缺乏通用的合金或晶體)緩慢冷卻的過程稱為/

3、退火0,在這一性,或者因?yàn)樗媒鈴?qiáng)烈地依賴初始解的選取而過程中原子失去熱動力時(shí)有充裕的時(shí)間重新分布缺乏實(shí)用性,而更為主要的是這些算法雖然解決并達(dá)到有序狀態(tài),從而使系統(tǒng)達(dá)到最低能量狀態(tài).了局部搜索的最優(yōu)但卻很難達(dá)到全局最優(yōu).在/退火0過程中系統(tǒng)的能量服從Boltzmann概模擬退火算法(SimulatedAnnealingAlgorithm)率分布,即系統(tǒng)依概率P(E)處于任一能量為E就是對其中的局部搜索算法(LocalSearchAlgo-的熱平衡狀態(tài):rithm)進(jìn)行改進(jìn)而提出的.模擬退火算法將組合優(yōu)P(E)=exp(-E/(HT))(1)化問題與統(tǒng)計(jì)力學(xué)

4、中的熱平衡問題類比,另辟了其中E為能量,T為溫度,H為Boltzmann常一條求解最優(yōu)化問題的新途徑,它可通過模擬退數(shù),該式說明隨著溫度T的降低,系統(tǒng)處于高能E火過程,找到全局或逼近全局的最優(yōu)解.狀態(tài)的概率隨之減小,這就是退火規(guī)律.模擬退火算法首先要確定一個(gè)能量函數(shù)即目1模擬退火算法概述標(biāo)函數(shù),求解最優(yōu)化問題一般通過Metropolis抽樣和/退火0兩個(gè)過程來實(shí)現(xiàn).Metropolis抽樣過程是111算法的提出在某一給定溫度T的情況下,對解的狀態(tài)空間進(jìn)模擬退火算法(SA)又稱為模擬冷卻法、統(tǒng)計(jì)行隨機(jī)抽樣,當(dāng)能量降低即$E<0時(shí),接受當(dāng)前冷卻法、Monte-C

5、arlo退火法、隨機(jī)松弛法和概率狀態(tài),當(dāng)$E>0時(shí),則根據(jù)概率爬山法等.模擬退火算法是一種新的統(tǒng)計(jì)優(yōu)化方P($E)=exp(-$E/T)(2)[1]法,其思想最早是由MetropolisN等人借鑒統(tǒng)計(jì)有條件地接受當(dāng)前狀態(tài).熱力學(xué)中物質(zhì)退火方法而提出的.1983年Kirk-經(jīng)過充分的抽樣之后,類似于熱力學(xué)系統(tǒng)達(dá)[2]patrick等人開展了一些富有成效的工作,成功地到當(dāng)前溫度的平衡狀態(tài),最優(yōu)化過程也將在降低收稿日期:2004-09-23;修回日期:2005-09-13作者簡介:劉懷亮(1976-),男,碩士,主要從事分布式人工智能、數(shù)據(jù)挖掘、數(shù)據(jù)庫等研究.50

6、4廣州大學(xué)學(xué)報(bào)(自然科學(xué)版)第4卷目標(biāo)函數(shù)的過程中跳出誤差曲面的局部極小點(diǎn).C(S.)-C(S(k));退火過程則是使系統(tǒng)的溫度降低,即使(3)若$C<0,則接受S.為下一個(gè)當(dāng)前解;若Tm0,則按概率exp(-$C/T)接受T.為下一個(gè)m為迭代次數(shù).當(dāng)前解.若S.被接受,則S(k+1)=S,否則S(k在新的溫度條件下,繼續(xù)Metropolis抽樣過程.+1)=S(k);重復(fù)進(jìn)行抽樣和退火過程,直到滿足收斂條件.(4)K=K+1,由某個(gè)給定的收斂準(zhǔn)則,判斷算法類似于固體退火必須/徐徐0降溫,才能使固是否應(yīng)該中止.如果是,則轉(zhuǎn)第5步,否則轉(zhuǎn)

7、第2步;體在每一溫度下都達(dá)到熱平衡,最終趨于全局能(5)將當(dāng)前解返回給調(diào)用它的退火過程算法.量最小的基態(tài)而不是位于局部極小點(diǎn).113算法的基本組成3模擬退火算法的不足之處模擬退火算法的基本組成可以分為:(1)產(chǎn)生機(jī)制:以一定的概率選擇一種解,這模擬退火法是在一系列遞減溫度下產(chǎn)生的點(diǎn)個(gè)概率函數(shù)稱為生成函數(shù);列,理論上可以看作是一系列的馬爾可夫鏈(2)接受準(zhǔn)則:以一定的概率接受代價(jià)函數(shù)值(MarkovChains).在某一溫度下多次重復(fù)Metropo-的偶然上升,這個(gè)概率函數(shù)稱為接受函數(shù);lis過程,目標(biāo)函數(shù)值的分布規(guī)律將滿足玻爾茲曼(3)控制參數(shù):以一定的冷卻

8、方式退火,實(shí)際分布規(guī)律.如果系統(tǒng)溫度以足夠慢的速率下