蟻群算法的改進(jìn)及其在TSP 問(wèn)題中的 應(yīng)用

蟻群算法的改進(jìn)及其在TSP問(wèn)題中的應(yīng)用雷德明吳智銘上海交通大學(xué)自動(dòng)化研究所200030上海摘要：在過(guò)去的10多年，蟻群算法（ACO）的研究和應(yīng)用取得了很大的進(jìn)展，大量結(jié)果證明了算法的有效性和在某些領(lǐng)域的優(yōu)勢(shì)。算法的基本缺陷：搜索時(shí)間過(guò)長(zhǎng)和容易陷入局部解也得到了一定程度的解決，提出了一些有效的方法。但問(wèn)題并未完全消除。本文首先分析了ACO中產(chǎn)生停滯現(xiàn)象的原因，然后給出了一種解決方案，通過(guò)直接交換部分邊上的信息素和合理設(shè)定每條邊的信息素?fù)]發(fā)率，來(lái)克服算法停滯現(xiàn)象。仿真結(jié)果表明上述方法是可行和有效的。關(guān)鍵詞：蟻群算法信息素旅行商問(wèn)題TheImprovementofAntColonyOptimizationAlgorithmanditsApplicationtoTSPproblemLeiDemingWuZhiming(ShanghaiJiaotongUniversity,InstituteofAutomation,20030,Shanghai)Abstract:TheresearchesandapplicationsonACOalgorithmhavemadegreatprogressesinthepastmorethantenyears.Anumberofresultsprovethevalidityofthealgorithmanditsadvantagesinsomefields.Itsbasicshortcomings,whicharelongsearchingtimeandeasilyjumpingintolocaloptimalsolution,alsohavebeenovercomepartiallyandsomeeffectivemethodsareintroduced.However,theproblemsaren’tcompletelysolved.Thispaperfirstanalyzesthegroundsproducingstagnationandthenintroducesanewsolutionforexcludingstagnation,whichincludesthedirectexchangeofpheromoneonsomeedgesanddynamicallysettingevaporationrateforeachedge.Thesimulationresultsdemonstratethattheaboveapproachisreasonableandefficient.Keyword:AntColonyOptimizationalgorithmpheromoneTSPproblem1．引論蟻群算法（ACO）是受自然界中螞蟻搜索食物行為啟發(fā)而提出的一種智能優(yōu)化算法。單個(gè)螞蟻是脆弱的，但整個(gè)蟻群的群居生活卻能完成許多單個(gè)個(gè)體無(wú)法承擔(dān)的工作，螞蟻間借助于信息素這種化學(xué)物質(zhì)進(jìn)行信息的交流和傳遞，并表現(xiàn)出正反饋現(xiàn)象：某段路徑上經(jīng)過(guò)的螞蟻越多，該路徑被重復(fù)選擇的概率就越高。正反饋機(jī)制和通訊機(jī)制是蟻群算法的兩個(gè)重要基礎(chǔ)。正反饋?zhàn)饔媚芗涌焖惴ǖ乃阉鳎矔?huì)導(dǎo)致算法出現(xiàn)停滯現(xiàn)象，而通訊機(jī)制能使個(gè)體相互協(xié)作，有利于算法搜索到更優(yōu)解。目前，該算法在組合優(yōu)化包括TSP,QAP等、車輛路徑問(wèn)題、電力系統(tǒng)中故障點(diǎn)的估計(jì)以及通訊網(wǎng)絡(luò)等諸多領(lǐng)域得到應(yīng)用。蟻群算法是一種本質(zhì)并行的算法，和其它智能算法不同，其搜索時(shí)間比較長(zhǎng)，新解的產(chǎn)生不是直接在已有解的基礎(chǔ)上通過(guò)變換如GA的交叉算子而得到的，和其他算法一樣，該算法也容易陷于局部最優(yōu)解，使搜索停滯。本文給出了一種改進(jìn)方案，通過(guò)直接交換部分邊上的信息素和合理設(shè)定每條邊的信息素?fù)]發(fā)速度，來(lái)避免算法出現(xiàn)停滯現(xiàn)象。仿真結(jié)果表明新方法是可行和有效的。2．蟻群算法基本原理和遺傳算法不同，關(guān)于蟻群算法的介紹往往要結(jié)合具體問(wèn)題進(jìn)行，通常選擇的問(wèn)題是TSP問(wèn)題。該問(wèn)題可以描述如下：設(shè)有個(gè)城市集，任意兩個(gè)城市之間的距離為，求一條經(jīng)過(guò)每個(gè)城市僅一次的路徑，使得最小表示t時(shí)刻位于城市的螞蟻的個(gè)數(shù)，為螞蟻的總數(shù)。表示t時(shí)刻邊上的信息素量，＝(為常數(shù))。隨著時(shí)間的推移，新的信息素加進(jìn)來(lái)，舊的信息素要揮發(fā)，表示信息素的揮發(fā)快慢。當(dāng)所有螞蟻完成一次周游后，各條邊上的信息素按下式調(diào)整：（1）(2)表示本次周游中路徑上的信息素增量，初始時(shí)刻，＝0。表示第只螞蟻在周游過(guò)程中釋放在邊上的信息素。（3）為常數(shù)，表示本次周游第只螞蟻所形成的回路的長(zhǎng)度。螞蟻在周游時(shí)，向那個(gè)城市轉(zhuǎn)移由轉(zhuǎn)移概率決定。（4）其中＝表示螞蟻當(dāng)前能選擇的城市集合，為禁忌表，它記錄螞蟻已路過(guò)的城市，用來(lái)說(shuō)明人工螞蟻的記憶性。是某種啟發(fā)信息。在TSP問(wèn)題中，。體現(xiàn)了信息素和啟發(fā)信息對(duì)螞蟻決策的影響。蟻群算法基本的運(yùn)行過(guò)程是這樣的：只螞蟻同時(shí)從某個(gè)城市出發(fā)，根據(jù)（4）選擇下一次旅行的城市，已去過(guò)的城市放入中，一次循環(huán)完成后，由公式（1），（2），（3）更新每條邊上的信息素，反復(fù)重復(fù)上述過(guò)程，直到終止條件成立。蟻群算法研究包括算法的應(yīng)用和算法的改進(jìn)，利用蟻群算法解決實(shí)際優(yōu)化問(wèn)題是整個(gè)研究的主流，每年都要發(fā)表許多這類論文。關(guān)于算法的改進(jìn)。可以從以下3個(gè)方面對(duì)算法進(jìn)行。1.將算法和其它搜索方法結(jié)合，提高算法的搜索效率，例如：在算法中引入逆轉(zhuǎn)變異方式，通過(guò)隨機(jī)變異，增大搜索所需的信息量，克服了搜索慢的缺點(diǎn)。2－opt和ACO的混合也明顯地改進(jìn)了算法的計(jì)算效率。2.自適應(yīng)調(diào)整參數(shù)等。FabioAbbattista等提出由GA優(yōu)化AS的參數(shù)，將兩種算法的優(yōu)勢(shì)結(jié)合在一起。而在文獻(xiàn)[3]中，不再保持固定，而是隨著搜索的進(jìn)行動(dòng)態(tài)地調(diào)整。文獻(xiàn)[4]提出了自適應(yīng)改變值的方法。3．設(shè)計(jì)，和等新的計(jì)算公式。SeungGwanLee等給出了一種信息素全局更新規(guī)則，根據(jù)該規(guī)則，高級(jí)個(gè)體經(jīng)過(guò)的邊要增加信息素，而低級(jí)個(gè)體路過(guò)的邊要減少信息素。所謂高級(jí)個(gè)體是那些獲得較優(yōu)解的個(gè)體，兩類個(gè)體各占一半。的公式也很多。和GA相比，蟻群算法相對(duì)簡(jiǎn)單，能加以改進(jìn)的地方比較少，但現(xiàn)有的改進(jìn)還不盡如人意，需進(jìn)一步研究新方法和措施。3．蟻群算法的改進(jìn)對(duì)ACO來(lái)說(shuō)，之間的相對(duì)大小會(huì)直接影響城市到城市的轉(zhuǎn)移概率，從而直接影響可行解的質(zhì)量。在搜索早期，信息素的分布是分散的，隨著搜索進(jìn)行，信息素慢慢地集中到部分邊上，搜索方向也隨之基本確定。當(dāng)某些邊上地信息素強(qiáng)度明顯高于其它邊，導(dǎo)致在構(gòu)造可行解時(shí)，總是使用少數(shù)幾條邊，就會(huì)使解的結(jié)構(gòu)過(guò)于相似，搜索也會(huì)停頓下來(lái)，算法陷入局部最優(yōu)解。雖然不同的智能算法出現(xiàn)停滯現(xiàn)象的原因各不相同，但結(jié)果是相同的，即所求的解越來(lái)越相似，避免這種現(xiàn)象的方法也是一致的，那就是增加解的多樣性。并且有些增加多樣性的手段也是通用的。例如：結(jié)合智能算法和局部搜索方法，就是一種常見(jiàn)的方法。當(dāng)分別用GA和ACO求解TSP問(wèn)題時(shí)，2－opt，3－opt等就曾分別和兩種算法結(jié)合，并且效果明顯。如何在ACO中增加解的多樣性呢？關(guān)鍵是形成和保持一個(gè)合理的信息素分布，讓較多的邊能以較高概率用于構(gòu)造可行解，也就是在“探索”和“利用”之間建立一個(gè)平衡點(diǎn)，既充分利用正反饋機(jī)制加快搜索，又盡可能地?cái)U(kuò)大算法的搜索區(qū)域，使用更多的邊形成新解。通過(guò)加入新搜索方式，根據(jù)新解改變之間的相對(duì)大小和信息素分布，可以讓算法逃離局部最優(yōu)解。本文引入另一種通過(guò)直接交換部分邊上的信息素避免搜索停滯的方法。其具體過(guò)程如下：對(duì)于個(gè)城市的TSP問(wèn)題，每個(gè)城市設(shè)定交換概率，產(chǎn)生（0，1）上均勻分布隨機(jī)數(shù)，如果，則在城市（起點(diǎn)）與其它城市可以形成的條邊中，隨機(jī)選出一定數(shù)量的邊，然后兩兩互換相應(yīng)邊上的信息素。若，則不作上述處理。交換概率（<0.15）不能過(guò)大，過(guò)大會(huì)抑止正反饋?zhàn)饔?。通過(guò)直接互換部分邊上的信息素，改變了的分布，從而使人工螞蟻在確定轉(zhuǎn)移城市時(shí)有較多的選擇，避免算法過(guò)早地陷入局部解。信息素的揮發(fā)率也會(huì)影響信息素分布。如何確定的大小，是應(yīng)用ACO的關(guān)鍵。通常，被設(shè)置成常數(shù)，由經(jīng)驗(yàn)或?qū)嶒?yàn)而定，且每條邊的揮發(fā)率相同。實(shí)際上，在以城市為起點(diǎn)與其它城市形成的條邊中，不一定每次每條邊上的信息素都要揮發(fā)，例如：在搜索開(kāi)始后很長(zhǎng)一段時(shí)間內(nèi)，讓所有邊上的信息素都不減少，能加快搜索。各個(gè)邊之間也要有差別。一般情況下，較大的邊用于構(gòu)造可行解的概率較高，為了防止部分邊上的信息素濃度過(guò)大，相應(yīng)地，這些邊上的信息素應(yīng)揮發(fā)快一些。而為了避免最優(yōu)路徑上的某些邊由于信息素強(qiáng)度過(guò)低而失去選擇機(jī)會(huì)，這些邊的值應(yīng)該較大。的計(jì)算公式如下：（5）（6）表示t時(shí)刻邊上信息素?fù)]發(fā)率。是早期搜索時(shí)間，，但兩者的差別不能太大。介于個(gè)的平均值與最大值之間。當(dāng)所有螞蟻完成一次周游后，先根據(jù)對(duì)各邊的信息素強(qiáng)度進(jìn)行調(diào)整，然后互換部分邊上的信息素，改變現(xiàn)有的信息素分布。算法的具體步驟如下Begin初始化，，，，＝0，對(duì)任意邊。while(){只螞蟻從初始城市出發(fā)，根據(jù)（4）將所有城市周游一次。計(jì)算可行解，若新解優(yōu)于舊解，則替換，否則，保留舊解2-opt等局部?jī)?yōu)化（option）利用包括最優(yōu)回路在內(nèi)的少量解更新，，根據(jù)交換概率選擇城市，對(duì)選中的城市，在以該城市為起點(diǎn)的條邊隨機(jī)確定部分邊，兩兩互換這些邊上的信息素。,＝0,對(duì)任意邊.}輸出最終結(jié)果End4．仿真實(shí)驗(yàn)本文選用文獻(xiàn)[7]中列出的兩個(gè)TSP問(wèn)題：50－city和75－city問(wèn)題。這兩個(gè)問(wèn)題目前已知的最優(yōu)長(zhǎng)度為426.14和542.3。分別用基本蟻群算法BACO、沒(méi)有信息素交換的ImprovedACO1和有信息素交換的ImprovedACO2對(duì)兩問(wèn)題進(jìn)行求解，每個(gè)程序各運(yùn)行20次，計(jì)算結(jié)果如表一所示。ImprovedACO2所獲得的最優(yōu)回路如圖一、圖二所示。表一：三種算法的計(jì)算結(jié)果算法50-city問(wèn)題75-city問(wèn)題平均值最好結(jié)果最差結(jié)果平均值最好結(jié)果最差結(jié)果BACOImprovedACO1ImprovedACO2434.2430.4442.8552.3549.9556.8428.7427.3429.9546.8545.3547.83427.5427.3427.8544.6543.0547.0圖一50-cityTSP問(wèn)題的最優(yōu)回路(長(zhǎng)度為427.3)圖275-cityTSP問(wèn)題的最優(yōu)回路(長(zhǎng)度為543.0)從表一可以發(fā)現(xiàn)，改進(jìn)后ACO明顯優(yōu)于改進(jìn)前的蟻群算法，而信息素的直接交換也改善了算法的求解質(zhì)量，使解的平均值與最優(yōu)結(jié)果之間的誤差都在0.5%之內(nèi)。驗(yàn)證了改進(jìn)措施的有效性。5．結(jié)論如何抑止搜索停滯現(xiàn)象是設(shè)計(jì)大多數(shù)智能優(yōu)化算法必須解決的問(wèn)題，一些通用的方法可用來(lái)解決該問(wèn)題，也應(yīng)該存在專門解決某類算法停滯問(wèn)題的途徑。本文提出了避免ACO算法陷入局部最優(yōu)解的專門方法：直接交換部分邊上的信息素和動(dòng)態(tài)地給每條邊設(shè)置揮發(fā)率，這兩種措施改善了算法搜索性能，提高了算法的計(jì)算效率。參考文獻(xiàn)1．SeungGwanLee,TaeUngJungandTaechoongChungAneffectivedynamicalweightedruleforAntColonysystemalgorithmProceedingsofIEEEconferenceonEvolutionaryComputation2001v2:1393-13962．FabioAbbattista,NicolaAbbattistaandLauraCaponettiAnEvolutionaryandCooperativeagentsforoptimizationProceedingsofIEEEconferenceonEvolutionaryComputation1995v2:668-6713．覃剛力楊家