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