資源描述：
《基于受限制候選表的反應(yīng)蟻群算法求解TSP問題.pdf》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。
1、第32卷第4期蘭州理工大學學報Vol.32No.42006年8月JournalofLanzhouUniverityofTechnologyAug.2006文章編號1673-5196200604-0083-04基于受限制候選表的反應(yīng)蟻群算法求解TSP問題趙玲1929劉三陽21.集美大學理學院福建廈門3610212.西安電子科技大學理學院陜西西安710071摘要2針對蟻群算法求解大規(guī)模旅行商問題(TSP)時會出現(xiàn)計算時間長等問題9將反應(yīng)貪婪隨機適應(yīng)搜索機制引入蟻群算法中9提出了一種基于受限制候選表(RCL)的反應(yīng)蟻群算法9
2、其中的候選表大小可以隨機選取.將螞蟻要選擇的下一點的范圍控制在RCL中9避開了許多局部極小點9克服了最近鄰居候選表的不足9提高了搜索效率.對大規(guī)模TSP問題進行仿真實驗的結(jié)果表明該算法具有良好的性能.關(guān)鍵詞2蟻群算法3受限制候選表3組合優(yōu)化問題3旅行商問題中圖分類號TP301.6文獻標識碼ASolutionofTSPproblembyusingalgorithmofreactiveantcolonywithrestrictedcandidatelist12LiUSan-yang2Z~AOLing1.SchoolofSc
3、ienceJimeiUniverityXiamen361021China2.SchoolofScienceXianUniverityofelectronicTechnologyXian710071ChinaAbstractAimedatthetime-conumingproblemthatWouldhappenedWiththeolutionofmaivetrave-lingalemanproblemTSPbyuingalgorithmofreactiveantcolonyakindofreactiveantcolon
4、yalgo-rithmbaedonretrictedcandidatelitRCLWapropoedbymeanofintroducingamechanimofgreedtochaticadaptiveearchingintoantcolonyalgorithm.inthealgorithmpropoedthedimenionofcandi-datelitcouldbeelectedtochatically.WhenthenextpointthattheantWouldelectWacontrolledtobeWith
5、inthecopeofRCLalotoflocalminimumpointcouldbeavoidedtheinufficiencyofmotnea-retneighborcandidatelitWouldbeovercomedandtheearchingefficiencyWouldbeimproved.itWahoWnbyaimulationtetonmaiveTSPthatthialgorithmpropoedpoeedfineperformance.Keywordsantcolonyalgorithmretri
6、ctedcandidatelitcombinatorialoptimizationproblemtravelingalemanproblem旅行商問題travelingalemanproblem部極小點隨著問題規(guī)模的擴大算法會出現(xiàn)運算效TSP是典型的NP-hard組合優(yōu)化問題能保證此類率低等問題.問題找到最優(yōu)解的確定性算法其運行時間呈指數(shù)為了提高蟻群算法的搜索效率特別是對大規(guī)復(fù)雜度尤其對于大規(guī)模問題要在多項式時間內(nèi)結(jié)模的問題常采用候選集策略.通常的方法是構(gòu)造一束只能用近似算法得到可以接受的解.人們曾先后個最近鄰居表ne
7、aretneighborlitNNL即對每用禁忌搜索算法模擬退火算法和遺傳算法等啟發(fā)個城市選擇離它最近的幾個城市作為候選集.這種式搜索算法求解NP-hard問題.20世紀90年代意方法可以指導(dǎo)螞蟻找到一些較短路徑減少搜索時大利學者Dorigo等人受自然界螞蟻集體尋徑的啟間但由于這種候選表的大小是固定的如果候選表發(fā)提出了蟻群算法1成功地解決了TSP問題和的大小選取不合適就會阻止最優(yōu)解的生成出現(xiàn)解其他許多組合優(yōu)化問題.但是蟻群算法容易陷入局的退化.2本文將反應(yīng)貪婪隨機適應(yīng)搜索機制reactive收稿日期2005-07-11
8、greedyrandomizedadaptiveearchprocedureRe-基金項目陜西省自然科學基金2004A02activeGRASP引入蟻群算法中提出了一種基于作者簡介趙玲1980-女甘肅蘭州人碩士.84蘭州理工大學學報第32卷受限制候選表retrictedcandidatelit9RCL的反一個邊以后9按下式更新該邊
