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

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

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

　　1引言

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

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

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

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

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

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

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

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

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

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

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

　　3.1路徑選擇機(jī)制的改良

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

　　3.2全局信息素更新機(jī)制的改進(jìn)

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

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

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

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

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

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

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

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

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

　　3.4雜交算子的引入

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

　　4結(jié)束語(yǔ)

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

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

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

　　參考文獻(xiàn)

　　[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ì)會(huì)，徐心和.具有變異特征的蟻群算法.計(jì)算機(jī)研究與發(fā)展，1999，36（10）.

　　[5]詹士昌，徐婕，吳俊.蟻群算法中有關(guān)算法參數(shù)的最優(yōu)選擇[J].科技通報(bào)，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)期刊推薦：《微型機(jī)與應(yīng)用》

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

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

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

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

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

---

轉(zhuǎn)載請(qǐng)注明來(lái)自：http://www.jinnzone.com/xinxianqlw/31377.html