蟻群算法源于1992年一篇博士論文提出的模擬螞蟻尋找食物所選路徑的概率型找尋最優(yōu)解的方案，這種算法本質(zhì)是基于一定規(guī)則的隨機運行來尋找最優(yōu)方案，模仿螞蟻尋找和搬運食物時釋放信息素的機理，不斷優(yōu)化行走路線，在算法實現(xiàn)中執(zhí)行時間越長，所獲得的路徑就越可能接近最優(yōu)路徑。

　　【摘要】對于求解TSP問題，新型的啟發(fā)式算法——蟻群算法，是成功解決此類問題核心的算法之一。本文簡要介紹了幾種啟發(fā)式算法并引出蟻群算法，并對蟻群算法基本原理、常用算法進行了深入的研究，并介紹了一種新的優(yōu)化策略。

　　【關(guān)鍵詞】TSP問題,蟻群算法,優(yōu)化策略

　　1引言

　　蟻群優(yōu)化算法已應(yīng)用于許多組合優(yōu)化問題，例如二次分配問題，還有很多實變量動力學(xué)問題、隨機問題、多目標(biāo)并行的實現(xiàn)等方面，但在實際算法中需要避免的一個問題是過早收斂的問題，算法在執(zhí)行中很快陷入到了局部最優(yōu)解的搜索，難以實現(xiàn)廣度搜索。因此，在標(biāo)準(zhǔn)算法基礎(chǔ)上出現(xiàn)了優(yōu)化算法，這些優(yōu)化算法主體通過對于信息素的調(diào)節(jié)，防止過早收斂問題。在優(yōu)化算法中核心在于平衡廣度搜索與深度搜索，保證算法的執(zhí)行效率、有效性。本文通過對目前常見的蟻群優(yōu)化算法進行綜合分析與比較，較為清晰的梳理出常見優(yōu)化算法的特點，有助于在解決實際問題中選擇合適方法以及算法優(yōu)化。

　　2常見蟻群算法的優(yōu)化算法

　　標(biāo)準(zhǔn)蟻群算法存在收斂慢、易停滯、運算時間長等缺陷，后續(xù)對其做了一系列的改進，以解決該算法存在的問題，產(chǎn)生了許多改進型算法。下面將介紹三種最典型的改進算法：蟻群系統(tǒng)算法（ACS）、最大最小蟻群系統(tǒng)算法（MMAS）、具有變異特征的蟻群算法。

　　2.1蟻群系統(tǒng)算法

　　蟻群系統(tǒng)算法（ACS）是對蟻群算法（AC）的改進，這些改進包括：螞蟻選擇的狀態(tài)轉(zhuǎn)移規(guī)則；全局最優(yōu)更新規(guī)則僅運用于屬于最優(yōu)解路徑上的信息素；對所有的路徑的信息量進行局部更新規(guī)則（LocalUpdatingRule）。在ACS中，全局更新只是運用在每一次循環(huán)中走最優(yōu)解路徑的螞蟻，而不再運用與所有的螞蟻。在所有的螞蟻搜完成了一次循環(huán)后，全局更新才會執(zhí)行。

　　2.2最大最小蟻群系統(tǒng)算法

　　最大最小蟻群系統(tǒng)算法（Max-MinAntSystem，MMAS）是解決TSP、QAP等問題的經(jīng)典蟻群優(yōu)化算法之一，其結(jié)果要優(yōu)于一般的蟻群算法。MMAS與ACS一樣都只允許在每次迭代中表現(xiàn)最好的螞蟻更新其路徑上的信息素，這樣做可以防止算法過早的出現(xiàn)停滯現(xiàn)象。而MMAS與ACS相比不同的地方在于防止這種停滯現(xiàn)象的方法。MMAS的做法為：限定信息素濃度允許值的上下限，并且采用平滑機制。在算法啟動時，MMAS將所有路徑上的信息素濃度初始化為最大值。在每次循環(huán)之后，只有在最佳路線上的螞蟻進行信息素的更新，并將其保持在一個高的水平上，其他之路上的信息素將會按照信息素殘留度降低濃度。

　　2.3與變異結(jié)合的蟻群算法

　　吳慶洪等人提出了一種優(yōu)化蟻群算法——具有變異特征的蟻群算法。其核心思想為采用逆轉(zhuǎn)變異方式，隨機地進行變異，以增大進化時所需的信息量，從而克服傳統(tǒng)蟻群算法收斂較慢的問題。這種變異機制之所以會具有較快的收斂速度，是因為它充分利用了2-OPT交換法簡潔高效的特點。

　　3蟻群算法優(yōu)化的新策略

　　對蟻群算法所作的優(yōu)化是在已有的改進型算法——ACS算法的基礎(chǔ)上進行的，下文即將描述的優(yōu)化途徑也都是在前人所做改良（即ACS已有的改良途徑）的基礎(chǔ)上作的更進一步的改進。

　　3.1路徑選擇機制的改良

　　在ACS的路徑選擇策略中，我們需要對ij邊上已有的信息進行有效的利用，而對于變量q的設(shè)定，存在著很大的偶然性使得我們不能很有效地利用已有信息。對此，為了進一步對已有知識加以充分利用，新變量（∑ijk）/m被引入用以替代變量q，其中∑ijk表示上一次循環(huán)中選擇路徑ij的螞蟻個體的總數(shù)。在q0確定的情況下，∑ijk將伴隨著算法的運行而隨之增大，從而使螞蟻個體能在下一次路徑選擇中優(yōu)先利用已有的信息來選擇將要前往的城市，進一步地提高了算法的搜索性能。

　　3.2全局信息素更新機制的改進

　　對于信息素的全局更新，我們不僅僅要運用在每一次循環(huán)中走最優(yōu)解路徑的螞蟻，還要運用與每一次循環(huán)中最差的螞蟻使用。但是對于最差螞蟻的全局更新規(guī)則與走最優(yōu)解路徑螞蟻的規(guī)則不同，其更新規(guī)則采用如下的公式：？子ij（t）←（1-？著）×？子ij（t）+？著×△？子ij（t）；

　　其中，？著為區(qū)間（0，1）上的參數(shù)；而△？子ij（t）則用如下的公式計算：

　　△？子ij（t）=Q/L-Q/L’若ij路徑是算法已求出的最差路徑的一部分

　　或=0若ij路徑不是已求出的最差路徑的一部分；

　　在ACS算法的基礎(chǔ)上，增加對最差的螞蟻采用以上的更新機制，能更有效地模擬螞蟻在自然界的覓食過程中分泌的信息素，能準(zhǔn)確得出路徑長度與時間之間的關(guān)系，可使得更多的已有知識被利用，同時在后續(xù)的循環(huán)中能夠增加好的路徑被選擇的概率并減少差的路徑被選擇的概率，這樣算法的性能可以大大提高。

　　3.3增加最小信息素濃度設(shè)置

　　MMAS給每一條支路都設(shè)置了一個最小信息素濃度，在算法運行過程中，各個支路的信息素濃度不會降到？子min以下。這樣保證了即使沒有任何一只螞蟻選擇走某條路徑，在再一次的循環(huán)中這條路徑依然有一定的概率被選中，從而避免了一些可能存在的好的路徑被過載地拋棄，同時也避免了算法過早地收斂。設(shè)置了一個最小信息素濃度？子min，它的計算公式為：

　　？子min=1/[2n？（1-？籽）？L]；

　　n表示當(dāng)前問題的城市節(jié)點數(shù)，？籽為信息素殘留度，L為算法運算到當(dāng)前為止，已求出的最優(yōu)路徑的長度；為了保證所有路徑上的信息素濃度不低于？子min，每當(dāng)一次循環(huán)中的信息素局部及全局更新完成后，就需要比較？子ij和？子min，如果？子ij<？子min，則將？子ij強行設(shè)置為？子min。

　　3.4雜交算子的引入

　　遺傳算法具有良好的搜索能力，引入了雜交算子來對現(xiàn)有的所有解進行重組，這樣可以發(fā)現(xiàn)潛在的更好的解。我們現(xiàn)在嘗試一種新的增強解的方法：雜交算子被引入到ACS算法中，以對在算法運行過程中產(chǎn)生的新的解進行雜交，并充分利用當(dāng)前所知的所有路徑信息，兩者結(jié)合可以發(fā)現(xiàn)更好的解，從而對最終我們希望得到的結(jié)起了增強作用。

　　4結(jié)束語

　　蟻群算法作為組合優(yōu)化的經(jīng)典算法，在實際問題的應(yīng)用中仍然存在一些問題，這些問題需要進一步研究。

　　（1）正反饋機制的建立，啟發(fā)函數(shù)的定義，求解問題遞增式的進行，以及最優(yōu)解與問題定義中的現(xiàn)實世界的情況相對應(yīng)等問題需要考慮。

　�。�2）在開始運行蟻群算法求解問題時，需要對大量的變量進行初始化，這些變量的初始值會對算法的性能產(chǎn)生較大的影響。然而這些變量初始值的選取方法和原則在目前還沒有一個理論上的依據(jù)，只能在多次實驗中積累經(jīng)驗從而選擇比較好的值。因此在初始化變量的最佳值設(shè)置問題上還有待進一步的研究。

　　參考文獻

　　[1]Dorigo，M.Optimization，LearningandNaturalAlgorithms.PhDthesis，DipartimentodiElettronica，PolitecnicodiMilano，page140，1992.

　　[2]Dorigo，M.，Maniezzo，V.，Colorni，A.TheAntSystem：optimizationbyacolonyofcoorperatingagents.IEEETransactionsonSMC，1996，26（1）：28～41.

　　[3]Stuetzle，T.，Hoos，H.TheMAX-MINAntSystemandLocalSearchfortheTravelingSalesmanProblem.ProceedingsofICE’97-1997IEEE4thInternationalConferenceonEvolutionaryComputation.IEEEPress，1997：308～313.

　　[4]吳慶洪，張紀(jì)會，徐心和.具有變異特征的蟻群算法.計算機研究與發(fā)展，1999，36（10）.

　　[5]詹士昌，徐婕，吳俊.蟻群算法中有關(guān)算法參數(shù)的最優(yōu)選擇[J].科技通報，2003，19（5）：381～386.

　　[6]Michalewicz，Z.GeneticAlgorithms+DataStructure=EvolutionPrograms.Berlin：Springer-Verlag，1996.

　　[7]elib.zib.de/pub/Packages/mp-testdata/tsp/tsplib/tsplib.html.

　　[8]Dorigo，M.，Gambardella，L.M.AntColoniesFortheTravelingSalesmanProblem.BioSystems（43）：73～81，1997.

相關(guān)期刊推薦：《微型機與應(yīng)用》

　　《微型機與應(yīng)用》是一本具有28年歷史的計算機專業(yè)技術(shù)期刊，由華北計算機系統(tǒng)工程研究所（原信息產(chǎn)業(yè)部電子第六研究所）主辦。該刊緊密結(jié)合我國計算機發(fā)展與應(yīng)用的需要，及時報道國家相關(guān)的技術(shù)經(jīng)濟政策、國內(nèi)外信息技術(shù)最新成果、在各行業(yè)及生活、娛樂中的應(yīng)用技術(shù)。該刊尤以其技術(shù)性、實用性強而深受廣大工程技術(shù)人員、科技工作者、大專院校師生、企事業(yè)管理人員以及電腦愛好者的歡迎。本刊曾用刊名：信息化縱橫。

　　《微型機與應(yīng)用》欄目設(shè)置

　　本刊主要欄目：綜述與評論、軟件天地、硬件縱橫、網(wǎng)絡(luò)與通信、應(yīng)用奇葩、技術(shù)與方法、圖形與圖像。

　　《微型機與應(yīng)用》期刊數(shù)據(jù)庫收錄情況/影響因子

　　《微型機與應(yīng)用》為全國優(yōu)秀科技期刊，被“萬方數(shù)據(jù)—數(shù)字化期刊群”、“中國知網(wǎng)-中國期刊全文數(shù)據(jù)庫”、“中國知網(wǎng)-中國科技期刊精品數(shù)據(jù)庫”等重要數(shù)據(jù)庫收錄，并為《中國學(xué)術(shù)期刊綜合評價數(shù)據(jù)庫》來源期刊，歷年被《中國無線電電子學(xué)文摘》、《中國電子科技文摘》等收錄。

---

轉(zhuǎn)載請注明來自：http://www.jinnzone.com/xinxianqlw/31377.html