資源描述：
《一種求解TSP問題的改進蟻群算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第8第期計算機技術(shù)與發(fā)展Vo1．18NO．122008年12月O0ⅣUTERTE(O10(YANDDFⅦLoPMENTDec．2008一種求解TSP問題的改進蟻群算法王娟，王建(中國工程物理研究院計算機應(yīng)用研究所，四川綿陽621900)摘要：針對基本蟻群算法存在收斂速度慢，易陷于局部最優(yōu)解等缺點，提出了一種求解旅行商(P)問題的改進蟻群算法。通過在基本蟻群算法中提出保留最優(yōu)解和引入個體差異策略的改進方法，有效地抑制了算法收斂過程中的停滯現(xiàn)象，提高了全局搜索能力和解的質(zhì)量。TSPLIB的實例驗證了該改進算法的有效性。關(guān)
2、鍵詞：蟻群算法；旅行商問題；最優(yōu)解；個體差異策略中圖分類號：TP301．6文獻標(biāo)識碼：A文章編號：1673—629x(20o8)12—0050一o3AnImprovedAntColonyAlgorithmforSolvingTSPProblemWANGJuan，WANGJian(ComputerApplicationInstitute，ChinaAcademyofEngineeringPhysics，Mianyang621900，China)Abstract：Introducesanimprovedantcolony
3、algorithmtosolvethetravelingsalesamnproblem(TSP)forreducingthedeficiencyoftradi*tionalantalgorithmforslowconvergenceandlocaloptimalsolution．Theimpmvedantcolonyalgorithmwhichintroducesreservingoptimalsolutionandindividualvariationtotraditionalantalgorithmcanconq
4、uerstagnationandoptimizesolution．ThesimulationexperimentshowsthevalidityforthisimprovedalgorithminTSPLIB．Keywords：antcolonyalgorithm；travelingsalemaanprobl~n；optimalsolution；individualvariationO引言文中在研究基本蟻群算法的基礎(chǔ)上，提出了保留旅行商問題(Travelingsalesmanproblem，TSP)是最優(yōu)解和引入個體
5、差異策略的兩點改進方法，有效抑一個典型的組合優(yōu)化問題，是一個NP難問題，其可能制了收斂過程中的停滯現(xiàn)象，提高了算法的搜索能力。的路徑數(shù)目與城市數(shù)目成指數(shù)型增長，所以一般很難TSPLIB中Att48、St70和Ei176問題的實例求解結(jié)果精確地求出其最優(yōu)解。目前，人們在如何解決這個問表明改進的蟻群算法具有良好的性能。題方面已經(jīng)做出了大量的研究，包括：遺傳算法、禁忌搜索算法、模擬退火算法等，且都取得了一定的成果。1基本蟻群算法求解TSP問題20世紀90年代，意大利學(xué)者M．Dorigo，V．Maniezzo和TSP問題是指
6、對于給定的個城市集合(1，2，?，A．Colomi等人從生物進化的機理中受到啟發(fā)，通過Tt)，找到一條經(jīng)過每一個城市一次且回到起點的最小模擬自然界螞蟻尋徑的行為，提出了一種全新的模擬花費的封閉環(huán)路。其目標(biāo)函數(shù)是：進化——蟻群算法。該算法具有較強的魯棒性、較好minD=d(i，i+1)+d(：r／，1)的全局優(yōu)化能力和分布式計算能力，同時還易于與其他方法相結(jié)合，特別適合于求解困難的組合優(yōu)化問題。其中，(i，J)(i，J=1，2，?，)表示城市i和之間但基本蟻群算法也存在一些缺陷，如：搜索時間長、易的距離。陷入局部最優(yōu)和
7、出現(xiàn)停滯現(xiàn)象。針對這些缺點，人們基本蟻群算法求解TSP問題[]可以簡單地表述對基本蟻群算法做了各種改進研究，比較典型的有蟻如下：假設(shè)將只螞蟻隨機地放置在T／個城市上，初始群系統(tǒng)(AntColonySystem，ACS)和MAX～MIN螞蟻時刻城市間每一條邊的信息素r(0)相等，每只螞蟻系統(tǒng)。禁忌表tabu中的第一個元素設(shè)為其初始城市，在搜索過程中，螞蟻將根據(jù)城市間的距離di，=1，2，?，收稿日期：2008—03—18T1)和城市間邊上信息素強度決定下一個要訪問的城基金項目：中國工程物理研究院面上基金資助項目(200
8、60324)作者簡介：王娟(1974一)，女，陜西渭南人，碩士，工程師，研究方市，磚為t時刻螞蟻k(k：1，2，?，D1)由城市i到城向為人工智能、軟件工程。市J的轉(zhuǎn)換概率：第l2期王娟等：一種求解TSP問題的改進蟻群算法·5l·得了很大的進展，大量結(jié)果證明了算法的有效性和在某些領(lǐng)域的優(yōu)勢。但是，蟻群算旦法也有一些缺陷。例_{0，[!·]￡：)
