資源描述：
《模擬退火算法對(duì)tsp問(wèn)題的求解》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、模擬退火算法對(duì)TSP問(wèn)題的求解柴涌（哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江哈爾濱150001）摘要：模擬退火算法在處理全局優(yōu)化、離散變量?jī)?yōu)化等困難問(wèn)題中具有傳統(tǒng)優(yōu)化算法無(wú)可比擬的優(yōu)勢(shì)。本文描述了模擬退火算法的原理及其基本框架結(jié)構(gòu)，給出了用模擬退火算法求解TSP問(wèn)題的具體實(shí)現(xiàn)方法，并分析說(shuō)明了模擬退火算法的優(yōu)缺點(diǎn)。關(guān)鍵詞：模擬退火；組合優(yōu)化；TSP問(wèn)題中圖分類號(hào)：TP273.1 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1001-005X(2008)01-0094-03SolvingTSPProblembyUs
2、ingSimulatedAnnealingAlgorithmCHAIYong(CollegeofInformationandCommunicationEngineering,HarbinEngineeringUniversity,Harbin150001,China)Abstract:Simulatedannealingalgorithmhasobviouslyunparalleledadvantagesinsolvingsomedifficultproblemsthanthetraditional
3、optimizationalgorithms,suchasglobaloptimizationanddiscretevariablesoptimization.Inthispaper,thebasicframeworkandprincipleofsimulatedannealingalgorithmweredescribed,andthespecificmethodtosolveTSPproblemwasgiven,finallytheadvantagesanddisadvantagesofsimu
4、latedannealingalgorithmwerealsoanalysised.Keywords:simulatedannealingalgorithm;combinatorialoptimization;TSPproblem 在管理科學(xué)、計(jì)算機(jī)科學(xué)、分子物理學(xué)和生物學(xué)以及超大規(guī)模集成電路設(shè)計(jì)、代碼設(shè)計(jì)、圖像處理和電子工程等科技領(lǐng)域中，存在著大量的組合優(yōu)化問(wèn)題，其中的NP完全問(wèn)題，其求解時(shí)間隨著問(wèn)題規(guī)模呈指數(shù)級(jí)增長(zhǎng)，當(dāng)規(guī)模稍大時(shí)就會(huì)因時(shí)間限制而失去可行性。以目前已成熟的數(shù)值計(jì)算理論和算法，或者
5、根本無(wú)法求解，或者其求解的計(jì)算量是爆炸性的，其花費(fèi)的代價(jià)將是人們所不能接受的。旅行商問(wèn)題（TravelingSalesmanProblem，簡(jiǎn)記為TSP）是一個(gè)典型的NP完全問(wèn)題。它可簡(jiǎn)單地描述為：對(duì)于N個(gè)城市，它們之間的距離已知，有一旅行商要從某一城市出發(fā)走遍所有的城市，且每一個(gè)城市只能經(jīng)過(guò)一次，最后回到出發(fā)城市，問(wèn)如何選擇路線可使他所走過(guò)的路程最短。TSP問(wèn)題表面看很簡(jiǎn)單，其實(shí)不然。當(dāng)TSP問(wèn)題的規(guī)模為N個(gè)城市時(shí)，可行解集中的路徑數(shù)為個(gè)，要從個(gè)可行解中找出哪條路徑最短，若以路徑間的比較為基本操作
6、，則需進(jìn)行的基本操作數(shù)為次。當(dāng)N較大時(shí),其數(shù)量是驚人的。若用運(yùn)算速度為1GFLOPS次的CrayⅡ型計(jì)算機(jī)進(jìn)行搜索，當(dāng)時(shí),需要0.000025s；當(dāng)時(shí)需要1.8h；當(dāng)時(shí)則猛增到350a；當(dāng)時(shí)則需要年！顯然，如此求TSP問(wèn)題的方法是不可行的。模擬退火算法（SimulatedAnnealing，簡(jiǎn)稱SA）為求解上述傳統(tǒng)方法難以處理的問(wèn)題提供了一個(gè)有效的途徑和通用框架，并逐漸發(fā)展成一種迭代自適應(yīng)啟發(fā)式概率性搜索算法，用以求解不同的非線性問(wèn)題。對(duì)不可微甚至不連續(xù)的函數(shù)優(yōu)化，SA能以較大概率求得全局優(yōu)化解，具
7、有較強(qiáng)的魯棒性、全局收斂性、隱含并行性及廣泛的適應(yīng)性，并且能處理不同類型的優(yōu)化設(shè)計(jì)變量（離散的、連續(xù)的和混合型的），不需要任何的輔助信息，對(duì)目標(biāo)函數(shù)和約束函數(shù)沒有任何要求。利用Metropolis算法并適當(dāng)?shù)乜刂茰囟认陆颠^(guò)程，在優(yōu)化問(wèn)題中具有很強(qiáng)的競(jìng)爭(zhēng)力，因此研究SA算法在優(yōu)化中的應(yīng)用顯得尤為重要。本文就應(yīng)用SA算法解決TSP優(yōu)化問(wèn)題。１模擬退火算法簡(jiǎn)介模擬退火算法的思想最早是由Metropolis等提出的。其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過(guò)程與一般的組合優(yōu)化問(wèn)題之間的相似性。模擬退火算法是一種通
8、用的優(yōu)化算法，其物理退火過(guò)程由以下三部分組成：1.加溫過(guò)程。其目的是增強(qiáng)粒子的熱運(yùn)動(dòng)，使其偏離平衡位置。當(dāng)溫度足夠高時(shí)，固體將熔為液體，從而消除系統(tǒng)原先存在的非均勻狀態(tài)。2.等溫過(guò)程。對(duì)于與周圍環(huán)境交換熱量而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到平衡狀態(tài)。3.冷卻過(guò)程。使粒子熱運(yùn)動(dòng)減弱，系統(tǒng)能量下降，得到晶體結(jié)構(gòu)。其中，加溫過(guò)程對(duì)應(yīng)算法的設(shè)定初溫，等溫過(guò)程對(duì)應(yīng)算法的Metropolis抽樣過(guò)程，冷卻過(guò)程對(duì)應(yīng)控制參
