基于并行模擬退火算法的tsp問題求解

《基于并行模擬退火算法的tsp問題求解》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、第27卷第5期唐山師范學(xué)院學(xué)報(bào)2005年9月Vol.27No.5JournalofTangshanTeachersCollegeSep.2005基于并行模擬退火算法的TSP問題求解郟宣耀（浙江大學(xué)寧波理工學(xué)院信息科學(xué)與工程分院，浙江寧波315100）摘要：針對(duì)標(biāo)準(zhǔn)模擬退火算法串行優(yōu)化單個(gè)解，優(yōu)化過程較長(zhǎng)、效率較低的弱點(diǎn)，提出一種基于多種群群體優(yōu)化的并行機(jī)制。該機(jī)制通過將單個(gè)解的串行優(yōu)化轉(zhuǎn)化為許多個(gè)解同時(shí)進(jìn)行的并行優(yōu)化來提高算法的整體優(yōu)化效率。利用該算法求解TSP問題能夠顯著提高優(yōu)化效率，仿真結(jié)果表明

2、該算法是有效的。關(guān)鍵詞：并行優(yōu)化；多種群；模擬退火；旅行商問題；組合優(yōu)化中圖分類號(hào)：TP301.6文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-9115（2005）05-0050-041引言[1]模擬退火算法是20世紀(jì)80年代初提出的一種基于蒙特卡羅（MenteCarlo）迭代求解策略的啟發(fā)式隨機(jī)優(yōu)化算法。它通過Metropolis接受準(zhǔn)則概率接受劣化解并以此跳出局部最優(yōu)，通過溫度更新函數(shù)的退溫過程進(jìn)行趨化式搜索并最終進(jìn)入全局最優(yōu)解集。但模擬退火算法在某一溫度下為了達(dá)到解的平穩(wěn)必須使采樣次數(shù)盡可能的大，即盡量增

3、大對(duì)應(yīng)Markov鏈長(zhǎng)，且為了優(yōu)化過程的平滑必須使退溫速度盡量緩慢，這使得模擬退火算法的優(yōu)化效率很難提高。為此，許多學(xué)者提出了各種改[2][3][4][5][6][7]進(jìn)方法，如改進(jìn)狀態(tài)產(chǎn)生函數(shù)、改進(jìn)固定的退溫策略和狀態(tài)接受函數(shù)，將算法的尋優(yōu)過程由串行轉(zhuǎn)化為并行等。其中，并行機(jī)制的引入能從根本上提高算法尋優(yōu)和收斂速度，改善優(yōu)化效率?；诙嗵幚砥鞯牟⑿袡C(jī)制研究和應(yīng)用的較為普[5][6]遍，該方法通過若干臺(tái)主從式或?qū)ΨQ式處理器協(xié)同計(jì)算來提高算法執(zhí)行效率。本文則基于多種群群體優(yōu)化，實(shí)現(xiàn)算法本身的并行性。T

4、SP是組合優(yōu)化問題中最為典型的NP難題之一，精確解算法的時(shí)間是關(guān)于問題規(guī)模的指數(shù)函數(shù)，存在指數(shù)爆炸的問題，實(shí)際求解一般使用近似解算法。傳統(tǒng)的算法有動(dòng)態(tài)規(guī)劃法、分支定界法、最近鄰法、最近插入法、雙極小樹生成法等。但這些算法的時(shí)間性能仍不理想（如動(dòng)態(tài)規(guī)劃、分支定界等）或?qū)?yōu)性能不佳，易于求得局部最優(yōu)解（如最近鄰法等）。模擬退火算法等現(xiàn)代啟發(fā)式隨機(jī)優(yōu)化算法是求解此類問題的有效方法。這里僅討論對(duì)稱TSP，即di,j?dj,i。應(yīng)用本文的并行模擬退火算法對(duì)TSP問題的仿真實(shí)驗(yàn)結(jié)果表明了該算法的有效性。2模擬退

5、火算法原理及要素2.1設(shè)計(jì)思想及原理模擬退火算法的思想來源于統(tǒng)計(jì)熱力學(xué)中固體物質(zhì)的退火過程。初始時(shí)系統(tǒng)溫度較高，高溫液態(tài)物質(zhì)存在非均勻狀態(tài)，熱運(yùn)動(dòng)較激烈。為了使系統(tǒng)在每一溫度下均達(dá)到平衡狀態(tài)，最終達(dá)到固體的基態(tài)，退溫過程必須緩慢進(jìn)行。當(dāng)溫度降至較低時(shí)，粒子僅圍繞晶體格點(diǎn)做微弱運(yùn)動(dòng)，逐漸凝固成固態(tài)。組合優(yōu)化問題和物理退火過程有其相似性。組合優(yōu)化問題中的目標(biāo)函數(shù)類似于物理退火過程中系統(tǒng)的能量，其解集相當(dāng)于粒子狀態(tài)，最優(yōu)解則對(duì)應(yīng)于能量最低態(tài)。結(jié)合物理退火過程的抽樣過程、接受準(zhǔn)則、退火控制等，就構(gòu)成適用于組

6、合優(yōu)化問題的模擬退火算法。模擬退火算法由某一較高初溫開始，采用具有概率突跳特性的Metropolis接受準(zhǔn)則在解空間進(jìn)行隨機(jī)搜索，隨著溫度的下降重復(fù)抽樣過程，直到各溫度下的抽樣穩(wěn)定，最終得到問題的全局最優(yōu)解。2.2關(guān)鍵組成部分模擬退火算法的實(shí)質(zhì)結(jié)構(gòu)為內(nèi)外兩層循環(huán)。外循環(huán)控制溫度的下降，內(nèi)循環(huán)則在當(dāng)前溫度下重復(fù)抽樣過程，直到抽樣穩(wěn)定為止。算法中的關(guān)鍵組成因素為初始溫度、溫度更新函數(shù)、狀態(tài)產(chǎn)生函數(shù)、狀態(tài)接受函數(shù)、內(nèi)循環(huán)終止準(zhǔn)則和外循環(huán)終止──────────基金項(xiàng)目：浙江大學(xué)寧波理工學(xué)院青年創(chuàng)新基金（2

7、004-11）收稿日期：2005-03-09作者簡(jiǎn)介：郟宣耀（1982-），男，浙江舟山人，浙江大學(xué)寧波理工學(xué)院信息科學(xué)與工程分院教師，研究方向?yàn)橛?jì)算智能，優(yōu)化理論與算法。-50-郟宣耀：基于并行模擬退火算法的TSP問題求解準(zhǔn)則六部分。從理論上分析，為了使算法最終得到全局最優(yōu)，應(yīng)把初始溫度設(shè)置盡量大，溫度下降盡量緩慢。但這導(dǎo)致算法收斂速度過慢，優(yōu)化效率降低。實(shí)際應(yīng)用中，通常隨機(jī)產(chǎn)生一組解，計(jì)算其目標(biāo)函數(shù)值的方差作為初始溫度。鑒于計(jì)算的方便，溫度更新函數(shù)一般取指數(shù)退溫，即Ti?1??Ti,??(0,1

8、)。為使溫度下降不至過快，λ取值一般接近于1。狀態(tài)產(chǎn)生函數(shù)的功能是產(chǎn)生一新解，它應(yīng)盡可能使產(chǎn)生的候選解遍布整個(gè)解空間。候選解通常在當(dāng)前狀態(tài)的鄰域結(jié)構(gòu)內(nèi)以一定概率方式產(chǎn)生。其中領(lǐng)域函數(shù)與概率方式由問題的性質(zhì)決定。候選解產(chǎn)生之后若優(yōu)于當(dāng)前解則接受其并取代當(dāng)前解，若劣于當(dāng)前解，則由狀態(tài)接受函數(shù)決定是否接受。通常采用min[1,exp(??C/t)]作為狀態(tài)接受函數(shù)?？梢姡S著溫度的降低，接受劣解的概率也隨之降低以使算法最終收斂到全局最優(yōu)。內(nèi)循環(huán)終止準(zhǔn)則亦即Metropoli