資源描述：
《一種改進(jìn)的自適應(yīng)蟻群算法求解tsp問題》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、總第244期計(jì)算機(jī)與數(shù)字工程Vo1．38No．22010年第2期Computer＆DigitalEngineering11一種改進(jìn)的自適應(yīng)蟻群算法求解TSP問題占志剛張求明張盛意王康(中國地質(zhì)大學(xué)(武漢)計(jì)算機(jī)學(xué)院武漢430074)摘要文章提出了一種改進(jìn)的蟻群算法，其核心是限制單步路徑上的螞蟻數(shù)目，當(dāng)該路徑上的信息素達(dá)到一定濃度時，人為的迫使螞蟻改換路徑，從而更好的全局尋優(yōu)，避免算法陷入局部極優(yōu)，并使用2-Opt方法對路徑進(jìn)行優(yōu)化。對旅行商問題(TSP)的實(shí)驗(yàn)結(jié)果表明：新算法的優(yōu)化結(jié)果和效率都優(yōu)于基本蟻群算法。關(guān)鍵
2、詞蟻群算法；信息素；2-Opt；旅行商問題中圖分類號TP18；TP301AnImprovedAdaptiveAntColonyAlgorithmforSolvingTSPZhanZhigangZhangQiumingZhangShengyiWangKang(SchoolofComputer，ChinaUniversityofGeosciences，Wuhan430074)AbstractAnimprovedantcolonyalgorithmisproposed，whosecoreistolimitthenumbe
3、rofantsonthesingle-steppath，whenthepheromoneonthepathreachesacertainconcentration，weforcetOchangepathsofants，SOthenewalgo—rithmhavegoodcapabilityinglobalsearch，avoidfallinginlocalbest，andtheroutesareoptimizedby2-Optmethodwhenallantshavefoundeffectiveroute．Thet
4、estsforTSPproblemshowthatthenewalgorithmissuperiortoconventionalACAinqualityandefficiency．KeyWordsantcolonyalgorithm，pheromone，2-Optmethod，TSPClassNIImberTP18：TP301人要在，z個城市販賣自己的物品，TSP問題就是尋1引言找該商人通過個城市各一次并回到出發(fā)城市的蟻群算法同其它生物仿生算法一樣，受自然界最短回路。中真實(shí)生物(螞蟻)的集體行為(覓食)的啟發(fā)而發(fā)該
5、文在基本蟻群算法的基礎(chǔ)上，采用螞蟻信息展起來的一種基于群體智能的模擬進(jìn)化算法，它是素的最優(yōu)路徑更新機(jī)制，限制單步路徑上的信息素由意大利學(xué)者DorigoM．等人[2]在1992年最先提濃度與全局環(huán)路上信息素濃度的比例，較好地回避出來的。他們充分利用蟻群搜索食物的過程與旅算法陷入局部極優(yōu)。行商問題(TSP)的相似性，解決了TsP問題，取得2基本蟻群算法(ACA)了很好的結(jié)果L1]。十幾年來，人們對蟻群算法進(jìn)行了廣泛深入的研究[7瑚]，并將其成功應(yīng)用于多種實(shí)用于尋找最短路徑的蟻群算法來源于螞蟻覓際問題[]。食的群體行為。
6、單個的螞蟻沒有智能，只能簡單的經(jīng)典TSP(Travellingsa】e5manproblem)問題隨機(jī)游蕩，一旦單只螞蟻找到食物，它就會返回巢在通信領(lǐng)域和交通領(lǐng)域等的網(wǎng)絡(luò)設(shè)計(jì)中有著重要中通知同伴，并且在沿途路徑上釋放“信息素”(外的意義。TSP問題是經(jīng)典的NP難問題，假設(shè)某商激素pheromone)作為蟻群前往食物所在地的標(biāo)收稿日期：2009年1O月24日，修回日期：2009年l1月21日作者簡介：占志剛，男，碩士研究生，研究方向：智能計(jì)算。張求明，男，博士，副教授，研究方向：智能計(jì)算，智能信息處理。張盛意，男，研
7、究方向：數(shù)據(jù)挖掘。l2占志剛等：一種改進(jìn)的自適應(yīng)蟻群算法求解TSP問題第38卷記。如果兩只螞蟻同時找到食物，并且采取不同的．i，螞蟻k在此次循環(huán)中經(jīng)過城市i和城市J路線回巢，那么比較長的路線上的信息素味道會比△一l0，否則較淡，蟻群會沿著另一條更近的路線前往食物所在地。蟻群算法設(shè)計(jì)虛擬的螞蟻，模擬螞蟻的覓食行(5)其中：Q為表示信息素強(qiáng)度的常數(shù)，表示螞蟻k為，讓他們摸索不同的路線，并留下隨著時間逐漸在本次循環(huán)中所經(jīng)過路徑的總長度。消失的虛擬“信息素”，根據(jù)“信息素”較濃的路徑較算法初始進(jìn)化次數(shù)NC一0，螞蟻隨機(jī)初始
8、起短的原則，尋找最短路徑。始城市，依據(jù)狀態(tài)轉(zhuǎn)移概率選擇下一城市，當(dāng)所有在基本蟻群算法[3]中，以TSP問題為例，設(shè)有螞蟻依次經(jīng)過所有城市后回到起始城市為一次進(jìn)n個城市，m只螞蟻，采用d(，J一1，2，?，，z)表示化，評價每只螞蟻通過的路徑長度，并記錄最短路城市i到城市J之間的距離，(f)表示在時刻t城徑，更新所有路徑上的信息素，轉(zhuǎn)入下次循環(huán)：NC市i和城市
