第四組蟻群算法應(yīng)用及改進研究

1、第四組 蟻群算法應(yīng)用及改進研究蟻群算法應(yīng)用及改進研究（組長）戴家瑋家指導(dǎo)：教授【摘要】 組合最優(yōu)化問題（COP）即給定的約束條件下，求出使目標(biāo)函數(shù)極?。ɑ驑O大）的變量組合問題，是運籌學(xué)中的一個經(jīng)典且重要的分支，其經(jīng)典難題為旅行商問題（TSP）。本研究以旅行商問題為出發(fā)點，對蟻群算法及其改進方式進行研究，將模擬退火算法與蟻群算法相結(jié)合，并結(jié)合最大最小螞蟻系統(tǒng)思想，最終提出模擬退火蟻群算法，對基本蟻群算法進行改進，提高解的質(zhì)量并蟻群算法收斂速度。且經(jīng)測試該改進算法的確優(yōu)于原始蟻群算法。【】蟻群算法旅行商問題公共自行車調(diào)度模擬退火算法最大最小螞蟻系統(tǒng)1第四組 蟻群算法應(yīng)用及改進研究目錄一、緒論5（一

2、） 研究背景5（二） 研究意義5（三） 技術(shù)路線6二、文獻綜述8蟻群算法8（一）1.蟻群算法相關(guān)應(yīng)用82.國外蟻群算法改進研究83.國內(nèi)蟻群算法改進研究9（二）模擬退火算法101.國外模擬退火算法研究102.國內(nèi)模擬退火算法研究10小結(jié)11（三）三、蟻群算法12（一）蟻群算法產(chǎn)生與發(fā)展121.雙橋?qū)嶒?22.人工螞蟻153.人工螞蟻系統(tǒng)特點17（二）蟻群算法基本模型191.螞蟻系統(tǒng)數(shù)學(xué)模型192.蟻群系統(tǒng)算法的實現(xiàn)21（三）后續(xù)系統(tǒng)221.22蟻2.蟻量系統(tǒng)223.蟻密系統(tǒng)22蟻群算法改進算法23（四）1.精英螞蟻系統(tǒng)232第四組 蟻群算法應(yīng)用及改進研究2.優(yōu)化排列螞蟻系統(tǒng)233.最大最小螞蟻

3、系統(tǒng)244.最優(yōu)螞蟻系統(tǒng)255.蟻群系統(tǒng)25（五）雙（多）蟻群算法261.雙（多）蟻群算法介紹262.多種群蟻群算法以旅行商問題（TSP）為例27四、案例分析公共自行車調(diào)度問題30問題提出30（一）（二）方法選擇30數(shù)學(xué)模型描述30（三）（四）算法設(shè)計32（五）算例分析33五、模擬退火蟻群算法36（一）模擬退火算法361.模擬退火算法概述362.模擬退火算法結(jié)構(gòu)363.模擬退火算法數(shù)學(xué)模型374.模擬退火算法（SA）特點385.模擬退火算法流程396.模擬退火算法解決TSP 問題40（二）模擬退火蟻群算法401.算法結(jié)合思路402.鄰域搜索策略413.改進方式414.改進算法步驟42（三）算法

4、性能測試431.參數(shù)設(shè)置432.對比結(jié)果443第四組 蟻群算法應(yīng)用及改進研究3.算法優(yōu)化性能分析44六、總結(jié)與展望46（一） 本文工作總結(jié)46（二） 存在問題46（三） 研究展望47參考文獻484第四組 蟻群算法應(yīng)用及改進研究一、緒論（一） 研究背景組合最優(yōu)化問題1（Combinatorial Optimization Problem），簡稱為 COP，即給定的約束條件下，求出使目標(biāo)函數(shù)極小（或極大）的變量組合問題。是通過對數(shù)學(xué)方法的研究去尋找離散的最優(yōu)編排、分組、次序或篩選等，是運籌學(xué)中的一個經(jīng)典且重要的分支，所研究的問題涉及管理、信息科學(xué)、工程技術(shù)、交通、通信網(wǎng)絡(luò)等諸多領(lǐng)域。在組合優(yōu)化問題

5、中最有代表性經(jīng)典難題就是 TSP 問題（Traveling Salesman Problem，TSP），即旅行商問題。旅行商問題是目前研究最的組合優(yōu)化問題之一。目前世界上研究旅行商問題最主要遇到的瓶頸問題就是如何避免陷入局部最優(yōu)以及計算效率的問題。為了解決這些難題，20 世紀(jì) 90 年代起，一些更新的思想和算法逐漸形成。由群居性昆蟲行為特性獲得靈感的螞蟻算法（又稱蟻群算法）是目前研究的熱點，蟻群算法就是利用群集智能解決組合優(yōu)化問題的典型例子2；又如由混沌現(xiàn)象受啟發(fā)的一系列新嘗試，將混沌機制和啟發(fā)式搜索方法、人工神經(jīng)網(wǎng)絡(luò)、模擬退火等相交叉結(jié)合，建立優(yōu)質(zhì)高效的算法，來提高算法的計算效率和對全局最優(yōu)

6、點的獲取能力。蟻群算法這一研究熱點，目前對其基本算法的改進大多數(shù)集中于信息素更新機制及參數(shù)選擇。因此，本文以 TSP 問題為出發(fā)點，將模擬退火算法與蟻群算法相結(jié)合，對基本蟻群算法進行改進，并結(jié)合已有的先進改進思想，在提高量的同時蟻群算法收斂速度。（二） 研究意義在組合最優(yōu)化問題中，以 TSP 問題為例，最早也最自然的想法就是采用窮舉法。然而，所謂最優(yōu)解的必然存在性和必能找到的特點是建立在問題的規(guī)模較小的情的。當(dāng)可行解集合中的點個數(shù)較少時，通過最直觀的窮舉法很容易得到最優(yōu)解；但倘若可行合中的有限點數(shù)目逐漸增多，此時如果仍采用完全枚舉、判別、比較、選擇的步驟，則無疑是十分困難和不可取的，所需要的時

7、間和空間是龐大得驚人的。因此，對于 TSP 問題的研究重點應(yīng)在可以接受的時間及空間復(fù)雜度的限制下去尋求最優(yōu)解，從實際效果來看，以算法、模擬退火算法、遺傳算法、人工神經(jīng)網(wǎng)絡(luò)算法為代表的現(xiàn)代智能優(yōu)化算法發(fā)展至今，成果斐然3。蟻群算法基于正反饋機制反復(fù)迭代獲取最優(yōu)解，為保證其解的精確性在尋優(yōu)過由于信息素?fù)]發(fā)機制的存在，且初期信息素匱乏，收斂速度較慢；而模擬退火算法具有大范圍全5第四組 蟻群算法應(yīng)用及改進研究局搜索能力，由于對系統(tǒng)中反饋信息利用不夠，當(dāng)求解到一定范圍時往往做大量無為的冗余迭代。將模擬退火算法與蟻群算法相結(jié)合，可使兩者優(yōu)勢互補，利用模擬退火算法初期生成信息素分布，利用蟻群算法獲得較精確解

8、，另外采用模擬退火的鄰域搜索策略在尋優(yōu)可蟻群算法解的質(zhì)量，且尋優(yōu)過程結(jié)合最大最小螞蟻系統(tǒng)思想進一步提高了解的質(zhì)量且盡可能保障其收斂速度。（三） 技術(shù)路線本文共六章，具體安排如下：第一章：緒論，提出本文研究背景及意義，對全文框架進行梳理。第二章：文獻綜述，對蟻群算法及模擬退火算法國內(nèi)外相關(guān)研究進行綜述，為后續(xù)兩者結(jié)合做鋪墊。第三章：蟻群算法，從蟻群算法產(chǎn)生及發(fā)展切入，研究蟻群算法基本模型，并應(yīng)用旅行商問題（TSP）對其算法模型及實現(xiàn)流程描述，進而對其目前認(rèn)可程度較高的幾種改進方式進行介紹，其中最大最小螞蟻系統(tǒng)將在后續(xù)改進中進一步進行融合。第四章：蟻群算法案例，以“公共自行車系統(tǒng)調(diào)度問題”為實際案

9、例，建立目標(biāo)函數(shù)及其約束條件，利用蟻群算法進行迭代計算，以具體展示蟻群算法如何解決實際問題。第五章：模擬退火蟻群算法，由模擬退火算法入手對對蟻群算法進行改進，即將模擬退火算法與蟻群算法相結(jié)合，并對改進的蟻群算法進試，得出最有效的改進模型。第六章：結(jié)論與展望，總結(jié)本文所做工作及成果，并指出本文不足之處及后續(xù)研究方向。本文技術(shù)路線如圖 1.1 所示：6第四組 蟻群算法應(yīng)用及改進研究蟻群算法 及其改進算法模擬退火算法圖 1.1技術(shù)路線圖7結(jié)論及展望算法性能測試模擬退火蟻群算法 (融合最大最小螞蟻系統(tǒng)改進)改進算法介紹蟻群算法案例分析蟻群算法國內(nèi)外相關(guān)研究模擬退火算法國內(nèi)外相關(guān)研究文獻綜述第四組 蟻群

10、算法應(yīng)用及改進研究二、文獻綜述（一） 蟻群算法1.蟻群算法相關(guān)應(yīng)用受螞蟻行為的啟發(fā)，Colomi 和 Dori 即等人于 1992 年提出 Ant System（AS）的概念，研究成果經(jīng)應(yīng)用于傳統(tǒng)的旅行商問題（TSP）上，取得了很好的效果。2002 年，Daniel Merkle等人基于串行進度生成機制、最晚開始時間優(yōu)先規(guī)則、正向逆向調(diào)度，首次用 ACO 算法解決約束項目排序問題（RCPSP）。國內(nèi)學(xué)者（2005）也將蟻群算法應(yīng)用于和RCPSP，采用串行進度生成機制和最晚結(jié)束時間優(yōu)先規(guī)則，結(jié)果證明該算法解決 RCPSP 有效可行。自從蟻群算法誕生之后，它被陸續(xù)應(yīng)用于路由問題、分配問題、調(diào)度問題

11、、子集問題等許多領(lǐng)域的問題。在調(diào)度問題領(lǐng)域，除了經(jīng)典受限項目調(diào)度問題，它還被應(yīng)用于車間調(diào)度等多個問題，對這些問題的相關(guān)研究列于表 2.14中。表 2.1蟻群算法應(yīng)用于調(diào)度問題列表2.國外蟻群算法改進研究在蟻群算法產(chǎn)生之后，許多學(xué)者對其進行了改進研究，其中大部分改進研究集中于信息素更新機制的改進。精英策略的螞蟻系統(tǒng)（Ant System with elitist strategy）5是最早的改進螞蟻系統(tǒng)。類似于遺傳算法中精英策略保留住一代中最適應(yīng)的，蟻群算法中的精英策略在每次循環(huán)后給最優(yōu)解以額外的信息素量以保持最優(yōu)解的吸引力，從而得到全局最優(yōu)解。Stutzle 等人（1997）提出最大最小螞蟻系

12、統(tǒng)（Max-Min Ant System， MMAS）6，只對找8問題名英文名作者工序車間Job shopColomi，開放車間Open shopPfahringer工作流車間Flow shopStutzle總延遲Total tardinessBauer，總權(quán)重延遲Total weighted tardinessden Besten，Merkle&MiddendorfGagne，項目調(diào)度Project schedulingMerkle，組車間Group schedulingBlum第四組 蟻群算法應(yīng)用及改進研究出當(dāng)前循環(huán)中最優(yōu)解的螞蟻或者找出全局最優(yōu)解的螞蟻走過的路徑進行更新，從而防止早熟收斂

13、現(xiàn)象的發(fā)生。Merkle 等人（2002）7提出了精英遺忘策略，使精英螞蟻忘記一部分已找到的局部最優(yōu)解，從而防止過早收斂，擴大搜索空間，有助于找到全局最優(yōu)解。對蟻群系統(tǒng)改進的另一個方向是多種群蟻群算法研究，而其中大部分研究都基于計算機并行工程，對系統(tǒng)的多種群蟻群算法研究非常少。KAWAMURA 等（2000）8提出的雙蟻群系統(tǒng)，通過蟻群間的互動信息素，在充分利用優(yōu)秀解的同時夸大搜索的解空間，比單蟻群系統(tǒng)取得更好的效果。其中，種群間的效用分為正效用和負(fù)效用，通過參數(shù)可以有效和調(diào)試效用的。為了充分利用學(xué)習(xí)機制，強化最優(yōu)信息的反饋，1995 年 Gambardella 和 Dorigo 提出了Ant

14、-Q 算法9，該算法建立了螞蟻系統(tǒng)與 Q-learning 的，僅讓每一次循環(huán)中最短路徑上的信息素濃度作更新。學(xué)者 Akihide Hiura 提出了一種比較復(fù)雜的主體的模型以模擬真實的蟻群。其中建立了兩種不同類型的螞蟻模型，并加入了蟻穴模型，堆模型和天地模型。蟻群的通信方式采用信息素，同時也考慮了噪聲。在此模型的基礎(chǔ)上，智能體在動態(tài)環(huán)境中的相互協(xié)作行為。這種完全依賴于模型的研究方式有助于啟發(fā)人們看到很多有趣的現(xiàn)象，但是要解釋這種現(xiàn)象就要對蟻群工作的內(nèi)在機理進行更進一步的了解，根據(jù)實際問題應(yīng)用人工蟻群系統(tǒng)，人工蟻群系統(tǒng)各參數(shù)設(shè)置及算法結(jié)構(gòu)對求解過程的影響。3.國內(nèi)蟻群算法改進研究等人（2004

15、）10提出了最優(yōu)從信息素更新機制的改進角度出發(fā)，螞蟻系統(tǒng)，對最優(yōu)解進行更大限度的增強，而對解進行削弱，使得屬于最優(yōu)路徑的邊與屬于最差路徑的邊之間的信息素量差異進一步增大，從而使螞蟻的搜索行為更集中于最優(yōu)解的附近。（2002）11提出一種自適應(yīng)的蟻群算法，該算法通過自適應(yīng)的改變揮發(fā)度等系數(shù)使解避免陷入局部最優(yōu)，同時還收斂速度。和（2002）12提出一種基于蟻群算法的旅行商問題分段求解方法，將提出的相遇算法與分段算法相結(jié)合，提高了螞蟻覓食的質(zhì)量和解的質(zhì)量。由于遺傳算法具有蟻群算法不具備的一些有點，如前期快速的全局搜索能力等。力等人（2002）13提出了一種動態(tài)自適應(yīng)調(diào)整信息素的蟻群算法，將普通蟻群

16、系統(tǒng)中常數(shù)的改為可變函數(shù)代替，在擴大搜索空間和充分用信息素反饋信息之間取得了較好的平衡。為了充分利用遺傳算法的有點，許多學(xué)者嘗試將遺傳算法和蟻群算法結(jié)合起來，如Tseng9第四組 蟻群算法應(yīng)用及改進研究等人（2005）直接將兩者結(jié)合形成混合算法；Shou（2006）通過采納遺傳算法的部分算子（交叉、變異等）實現(xiàn)兩者的結(jié)合。此外，等（2004）14將蟻群算法與模擬退火算法結(jié)合，利用蟻群算法生成初始解，然后在每個退火溫度上進行抽樣準(zhǔn)則檢驗產(chǎn)生新更新信息素后再進行蟻群搜索，如此讓蟻群算法和模擬退火算法交替進行。這些雜合算法共同點都是利用了蟻群算法獲得初始量較好的這一特點，同時也了蟻群算法在搜索后期質(zhì)

17、量不高、容易陷入過早局部收斂的弱點。在雙（多）種群蟻群算法方面，國內(nèi)的和滕少華（2006）15也提出一種雙種群改進蟻群算法，將兩個螞蟻群體分別進化，并定期交換信息素，緩解了信息素的局部收斂現(xiàn)象。張長春等將粒子群算法與蟻群算法游記地結(jié)合，提出了 PAAA 算法。它利用粒子群算法的較強的全局搜索能力生成信息素分布，再利用蟻群算法的正反饋機制求問題的精確解，汲取各自的優(yōu)勢，以達到優(yōu)勢互補。（二） 模擬退火算法1.國外模擬退火算法研究SA 算法由于具有局部最優(yōu)陷阱的能力，因此被 D.H.Ackley 等人用作 Boltzmann 機的學(xué)習(xí)算法，從而使Boltzmann 機克服了Hopfield 神經(jīng)網(wǎng)

18、模型的缺點（即經(jīng)常收斂到局部最優(yōu)質(zhì)）。在 Boltzmann 機中，即使系統(tǒng)落入了局部最優(yōu)的陷阱，經(jīng)過一段時間后，它還能再跳出來，使系統(tǒng)最終將往全局最優(yōu)質(zhì)的方向收斂。SA 算法可用來進行圖像恢復(fù)等工作16，即把一副被“污染”的圖像重新恢復(fù)的原圖，濾掉其中被畸變的部分。S.Geman 等人的實驗結(jié)果表明，SA 算法不但可以很好地完成圖像恢復(fù)工作，而且它還具有很大的并行性。因此它在圖像處理方面的應(yīng)用前景是廣闊的。2.國內(nèi)模擬退火算法研究從模擬退火算法自身要素改進的角度出發(fā)，2006 年，等提出基于 ingber根、提出的非常快速的模擬退火算法（簡稱 VFSA）改進的 MVFSA 算法，該算法VFS

19、A 算法的兩個基本特點，主要作兩點改動：1，在高溫下，一模型的全局?jǐn)_動方式代替目前的擾動方式；2，在低溫下，對模型擾動進行某種約束，邊擾動邊逐步減小模型擾動空間，以提高新模型被接受的機率。從模擬退火算法與其他搜索算法相結(jié)合的角度出發(fā)，1997 年、和提出模擬10第四組 蟻群算法應(yīng)用及改進研究退火算法與遺傳算法相結(jié)合，主要思想是在傳統(tǒng)GA 的生存策略中引入Bloztman 生存機制，將模擬退火算法融入遺傳算法的新產(chǎn)生中，以求得最優(yōu)解作為遺傳的父本。2003 年提出模擬退火與遺傳算法相結(jié)合，此混合算法是以遺傳算法為主題流程，側(cè)重全局搜索，將模擬退貨機制融入其中，側(cè)重局部搜索，是在對每個實施一定演變

20、而產(chǎn)生解的設(shè)計了遺傳算法中的變異和倒位的思想。此算法策略是從全局最優(yōu)解的搜索角度和算法的進化速度上來提高模擬退火遺傳算法的性能。此混合算法比基本遺傳算法在進化速度上有很大提高，且在局部搜索能力方面也有非常明顯的改進，此算法還在從當(dāng)前局部最優(yōu)狀態(tài)向其他未被搜索空間轉(zhuǎn)移的能力上有了較大的實質(zhì)性。2004 年17提出將模擬退火與免疫算法混合。該混合算法是從一組隨機，初始解開始，先通過選擇、交叉、變異等免疫操作來產(chǎn)生一組的新抗體，然后再對各新抗體進行模擬退火求最優(yōu)解。免疫算法的全局搜索能力好，可以快速在解空間的全體解搜索出來，陷入局部最優(yōu)級解，其局部搜索能力較差。模擬退火算法的 Metropolis

21、準(zhǔn)則可以有限度地接受解，并可以使其接受概率趨向于零，使得算法局部搜索能力強。兩種算法合理融合，使算法的在全局和局部搜索能力均有提高。2007 年等18提出適應(yīng)的模擬遺傳算法，提出自適應(yīng)變異概率的概念與理論遺傳算法的收斂速度，以解決遺傳算法中變異概率取值較小且在整個搜固定不變，易陷入局部最小值的不足，雜交母體選擇是以整體退火選擇的方式，可克服種群早熟化，避免過早收斂。（三） 小結(jié)模擬退火算法是目前來說最的啟發(fā)式鄰域搜索算法，雖然具有較大分為快速全局搜索能力，但是由于對系統(tǒng)中的反饋信息利用不夠，當(dāng)求解到一定范圍時往往做大量無為的冗余迭代，使解的質(zhì)量不高。蟻群算法基于信息素正反饋機制，為求得質(zhì)量較高

22、的解，由于初期信息素匱乏，導(dǎo)致收斂速度較慢。為了解決蟻群算法存在的不可避免的缺陷，本文將模擬退火算法的鄰域搜索思想應(yīng)用于蟻群算法的尋優(yōu)中，完美解決了各自算法的問題和缺陷。另外融合了目前解決 TSP 問題最好的改進思想最大最小螞蟻系統(tǒng)，在尋優(yōu)過進一步提高解的質(zhì)量并盡可能保障其收斂速度。11第四組 蟻群算法應(yīng)用及改進研究三、蟻群算法（一） 蟻群算法產(chǎn)生與發(fā)展1.雙橋?qū)嶒灷ハx學(xué)家發(fā)現(xiàn)，在覓食過，螞蟻在它所經(jīng)過的路徑上留下濃度與源質(zhì)量成比例的信息素，并能夠感知信息素的存在及其濃度，以此指導(dǎo)朝著信息素濃度高的地方移動。于是，蟻群的集體行動便表現(xiàn)出一種信息正反饋現(xiàn)象。螞蟻群體就是通過這種間接交流機制達到在

23、覓食過沿著最短路徑前進的目的。為了研究螞蟻群體覓食行為的特征，Deneubourg 及他的同事們設(shè)計了一種雙橋?qū)嶒?9。雙橋的首尾分別連接了蟻穴和源。他們在試驗中測試了不同長度的雙橋（分別稱為雙橋?qū)嶒灒?）和雙橋?qū)嶒灒?），得到了十分重要的結(jié)論。在 Deneubourg 等人的實驗中，兩個橋的長度是一樣的，如圖 3.1（a）所示。實驗的結(jié)果顯示（如果 3.1（b）所示），螞蟻群體只有很小的概率會均勻選擇兩橋，大多數(shù)情，螞蟻群體會漸漸只選擇其中某一橋，而兩橋被選擇的概率幾乎是相等的。造成這種現(xiàn)象的是：在覓食的最初期，螞蟻們對任何一橋都沒有偏好，于是隨意選擇一座橋，并在經(jīng)過的路徑上留下信息素。在初

24、期，兩橋上的信息素濃度大致相等，然而由于隨機波動，雙橋中的一個也許會擁有的信息素，于是螞蟻群體更加傾向于走這一路徑，并留下的信息素。于是，這種正反饋效應(yīng)隨著時間慢慢放大。如果時間足夠長，這種現(xiàn)象會導(dǎo)致所有螞蟻最終都選擇某一條路徑。這種自身催化或者正反饋的過程，實際就是螞蟻群體實現(xiàn)自組織行為的一個例子，這種宏觀模式（螞蟻群體傾向于選擇某一條路徑）的出現(xiàn)來自于微觀層面的過程與交互作用。在這個實驗中，螞蟻的微觀行為可以解釋螞蟻群體集中于一條路徑的宏觀現(xiàn)象。螞蟻在覓食過，感知周圍環(huán)境的變化并進行信息傳遞，從而調(diào)整自身的群體行為。12第四組 蟻群算法應(yīng)用及改進研究圖 3.1 雙橋?qū)嶒灒?）及其實驗結(jié)果在

25、 Gross 等人（1989）的實驗中20，兩橋的長度不一樣，較長的一條為較短的一條長度的兩倍，也就是說兩橋的長度比設(shè)定為 2:1（如圖 3.2（a）所示）。這個實驗的結(jié)果顯示，經(jīng)過一定的時間以后，大部分的螞蟻會選擇較短的一橋進行覓食，小部分的螞蟻會選擇較長的一橋進行覓食。其可以解釋為：在覓食的最初期，螞蟻隨機選擇覓食途徑，因此較長一橋和較短一橋選擇概率相等，然而當(dāng)螞蟻發(fā)現(xiàn)兩橋的長度差別后，便更傾向于走更短的路徑，從而迅速的在較短路徑上留下濃度很高的信息素，強化了蟻群的正反饋行為。由于較短路徑上信息素濃度積累得比較長路徑要快得多，因此大多數(shù)螞蟻在選擇路徑會選擇較短路徑，形成了如圖 3.2（b）

26、所表現(xiàn)的現(xiàn)象。與雙橋?qū)嶒灒?）相比，雙橋?qū)嶒灒?）覓食初期隨意波動的影響大大減小，起作用的主要是媒介質(zhì)、自身催化和差異路徑長度等機制。值得注意的是，雖然較長路徑遠(yuǎn)長于較短路徑，但仍有一部分螞蟻會選擇較長路徑，螞蟻這種不依據(jù)信息素濃度進行路徑選擇的行為稱為路徑探索，對蟻群優(yōu)化模型的建立有著不容忽視的作用。圖 3.2 雙橋?qū)嶒灒?）及其實驗結(jié)果在幾年后，Dorigo 和Stutzle（2004）21考慮到另一種情況：如果在螞蟻集中于某一條13第四組 蟻群算法應(yīng)用及改進研究覓食路徑后在添加一條新的路徑，那么蟻群的行為會發(fā)生怎樣的變化？他們在雙橋的基礎(chǔ)上，進行了附加實驗。他們在實驗初期只提供一條較長的

27、覓食路徑，在 30 分鐘以后再添加一條較短路徑（如圖 3.3（a）所示。有趣的是，在出現(xiàn)新的較短路徑后，螞蟻群體并沒有選擇較短路徑，而是仍然選擇原來的較長路徑，如圖 3.3（b）所示。實驗者對此的解釋為：由于長路徑上信息素濃度過高，而信息素蒸發(fā)又太慢，即使有螞蟻進行路徑探索，但較短路徑的信息素濃度仍遠(yuǎn)遠(yuǎn)低于較長路徑，從而使大部分螞蟻個人仍然選擇較長分支而不選擇較短分支。圖 3.3 雙橋?qū)嶒灥母郊訉嶒灱捌浣Y(jié)果在雙橋?qū)嶒灪螅珼eneuborug 和他同事嘗試用數(shù)學(xué)方法解釋在實驗中觀察到的蟻群現(xiàn)象，提出了一個簡單的隨機模型，形成了螞蟻系統(tǒng)和蟻群系統(tǒng)的雛形。假設(shè)信息素?fù)]發(fā)（實驗進行的時間很短，故可不考

28、慮信息素?fù)]發(fā)的情況）。設(shè)和是第只螞蟻經(jīng)過某一橋后在A 橋和 B 橋上已經(jīng)經(jīng)過的螞蟻數(shù)，那么第 + 1只螞蟻選擇分支A 的概率為( + ) = ( + ) + ( + )( 1.1)同時，這只螞蟻選擇分支B 的概率為：( + ) = ( + ) + ( + )( 1.2)顯然，有 + = 1，也就是說這只螞蟻必然需要在兩個分支中選擇一個。這兩個公式要表達的現(xiàn)象很簡單：以往走分支 A 的螞蟻越多，正在選擇路徑的這種螞蟻選擇分支 A的概率就越大。而螞蟻數(shù)量對螞蟻路徑選擇的影響，是通過信息素濃度來實現(xiàn)的。在模型中，信息素的濃度的影響又是通過參數(shù)和來的。表示公式的非線性程度，值越大，信息素濃度差別的影響

29、就越大。當(dāng)值很大時，兩分支上信息素濃度些微的差距就會導(dǎo)致選擇高信息素濃度路徑的螞蟻數(shù)量遠(yuǎn)大于低濃度路徑。表示進行隨機選擇程度，值越大，螞蟻越忽略信息素對選擇的作用。當(dāng)值相對于螞蟻數(shù)量達到無限大時，所有螞蟻都以 1/214第四組 蟻群算法應(yīng)用及改進研究的概率選擇兩條分支。Liu 采用蒙特卡羅方法對此系統(tǒng)進行了模擬，證實了模型對實驗描述的有效性。值得注意的是，在這個模型中，螞蟻在前往覓食和返回巢穴的過都會信息素。Deneubourg進行的實驗也證明了，這是蟻群集中到較短路徑的必須方式，如果螞蟻僅僅在前往覓食或返回巢穴的過信息素，那蟻群是無法找到巢穴與的最短路徑的。2.人工螞蟻雙橋?qū)嶒炏蛉藗冋故玖宋?/p>

30、蟻群內(nèi)在的搜尋最短路徑的能力，于是人們嘗試去設(shè)計一種人工螞蟻，使之在類似雙橋系統(tǒng)的圖上移動并尋找最短路徑。例如，考慮一個靜態(tài)連接圖 = (，)，如圖 3.4 所示，其中表示節(jié)點集合，它的絕對值為節(jié)點數(shù)量，表示連接中節(jié)點的邊的集合。引入蟻群使之在這個連接圖中進行路徑搜索，尋找從源節(jié)點（蟻巢）到目的節(jié)點（源）目的的最短距離。在這個例子中，粗線表示的路徑即為螞蟻找到的最短路徑。圖 3.4 螞蟻在靜態(tài)連接圖中找到的最短路徑解在螞蟻路徑搜索能力的基礎(chǔ)上，人們開始試圖開發(fā)人工螞蟻。然而人們發(fā)現(xiàn)，僅僅對自然界中的螞蟻進行模仿存在很大的缺陷：由于螞蟻在進行路徑選擇時依據(jù)的是信息素，螞蟻本身對路徑的長短并沒有直

31、觀預(yù)見。因此，如果在搜索初期的隨機選擇中螞蟻選擇了較差的路徑解（如形成環(huán)路）而這個被強化，那么由于正反饋作用，這個較差解的路徑上會積累越來越多的信息素從而使得螞蟻群體集中于這個較差路徑解。究其根本，這個問題是由螞蟻群體信息素的正反饋作用即信息素的正向更新引起的。然而，如果只是去掉信息素的正向更新而只保留信息素的逆向更新（信息素的揮發(fā)），螞蟻群體將15第四組 蟻群算法應(yīng)用及改進研究只遵循隨機搜索而無法獲得最短路徑。因此，解決這個問題的關(guān)鍵是賦予人工螞蟻一些不同于自然螞蟻的能力，建立一個有效的信息素更新機制。人工螞蟻的這種智能首先表現(xiàn)為一種記憶力，它們可以把所有已經(jīng)被搜的路徑的長度都記住，然后使人

32、工螞蟻具備對路徑的評估比較能力，從而排除較差的解（如距離較長的路徑或包含了較好路徑的環(huán)路路徑），而在較好的信息素。此外，由于人工螞蟻具備了評估比較能力，因為可以根據(jù)解的質(zhì)量決定在路徑上的信息素的量。另一個問題是如何利用螞蟻的路徑探索能力，使螞蟻在一定程度上搜索“較差”的路徑，避免過分重復(fù)搜索已有的路徑和解的過早收斂。為此，可以引入現(xiàn)實中自然蟻群也具有的信息素?fù)]發(fā)現(xiàn)象，使得所有路徑上的信息素以一定的速度揮發(fā)，降低被搜多的路徑上的信息素，從而讓其他路徑有更大的概率被螞蟻選擇。在解決了這兩個問題后，便可以根據(jù)以下幾個關(guān)鍵模塊建立人工螞蟻系統(tǒng)：螞蟻的路徑搜索行為：在靜態(tài)連接圖中，螞蟻在節(jié)點以一定的概率

33、選擇下一個節(jié)點，建立一個局部解。選擇概率的大小取決于可選擇的節(jié)點間信息素濃度的大小。螞蟻完成多次節(jié)點選擇后一個完整搜索和行進的過，螞蟻不信息素，即沒有直接的信息素正向更新。在搜索的初期，每條邊都被賦予一定數(shù)量的信息素，螞蟻開始搜索路徑。此時第只螞蟻處于第個節(jié)點選擇作為下一個節(jié)點的概率為： = (3.3) 0其中，為螞蟻在節(jié)點上可以選擇的相鄰節(jié)點的集合。螞蟻依據(jù)這個概率在每一個節(jié)點做出路徑選擇，直至形成從蟻穴到源的完整路徑。然后，螞蟻會憑借人工賦予的智能對解的性能進行評估，如果當(dāng)前經(jīng)過的路徑的解較好，則在回蟻穴的途中信息素，這也使蟻群表現(xiàn)為信息素反向更新。信息素更新機制：螞蟻在到達源后，會沿原路

34、返回蟻穴，并根據(jù)路徑解的性能一定量的信息素。設(shè)更新的信息素的量為，則信息素的更新機制可以簡單描述為： + (3.4)從式（3.4）可以看出，一旦有螞蟻經(jīng)過某條路徑，那么該路徑上必然會增加一定量的信息素。的選擇通常設(shè)定為所經(jīng)過路徑長度的函數(shù)，所經(jīng)過的路徑越短，更新的信息素越多。信息素?fù)]發(fā)機制：自然蟻群系統(tǒng)也有信息素?fù)]發(fā)現(xiàn)象，但是對于蟻群路徑探索行為的促16第四組 蟻群算法應(yīng)用及改進研究進作用并不明顯。與此不同，人工蟻群的信息素?fù)]發(fā)強度可以進行人工，因此信息素?fù)]發(fā)強度可以進行人工，因此信息素的揮發(fā)機制在人工蟻群系統(tǒng)中有著重要的作用。人工蟻群系統(tǒng)中，信息素的揮發(fā)和信息素的是交互進行的。與信息素的不同

35、，在所有路徑山信息素的揮發(fā)量是一樣的。信息素的這個揮發(fā)機制可以描述為： (1 ) (，) (3.5)其中 (0，1，表示揮發(fā)系數(shù)。每個周期（例如一只螞蟻完成一次搜索）每條邊都會揮發(fā)相同量的信息素。3.人工螞蟻系統(tǒng)特點人工螞蟻系統(tǒng)的建立，一方面參照并借鑒了真實螞蟻系統(tǒng)的特性，是在觀察和實驗的基礎(chǔ)上對真實螞蟻覓食行為的一種抽象。人工螞蟻和真實螞蟻有以下的一些共同點：（1） 人工螞蟻和真是螞蟻一樣，通過互相合作完成任務(wù)人工螞蟻和真實螞蟻的能力都很不出色，但是卻能夠通過群體的相互合作完成無法完成的工作，如覓食等。它們的行為受群體內(nèi)其他行為的影響，同時影響著其他的行為，而它們這種相互影響、相互合作的行為

36、的目的，是完成群體的共同的任務(wù)，如覓食。（2） 人工螞蟻和真實螞蟻一樣，以信息素作為媒介人工螞蟻和真實螞蟻一樣，在選擇路徑的時候可以感知別的螞蟻遺留在道路上的信息素濃度，同經(jīng)過的道路上一定量的信息素，新的信息素起到了道路上信息素更新的作用。這種信息素更新的機制是螞蟻系統(tǒng)的關(guān)鍵，形成了信息素的正反饋效應(yīng)，使螞蟻漸漸集中于某些路徑，也使蟻群算法具有收斂性。（3） 人工螞蟻系統(tǒng)和真實螞蟻系統(tǒng)一樣，都存在信息素?fù)]發(fā)現(xiàn)象真實螞蟻系統(tǒng)中，信息素會隨著時間自然揮發(fā)，這種現(xiàn)象造成了螞蟻的路徑探索行為。由于這種行為有利于搜索不同路徑，防止過早收斂，因此在人工螞蟻系統(tǒng)中人為建立了信息素?fù)]發(fā)機制，定期在所有路徑上揮

37、發(fā)相同量的信息素。（4） 人工螞蟻和真實螞蟻一樣，都通過基于概率決策的局部行為完成任務(wù)人工螞蟻和真實螞蟻一樣，在進行路徑選擇是根據(jù)路徑上的信息素濃度進行概率型決策，某一段路徑上的信息素濃度越大，被螞蟻選中的概率就越大。所有分支路徑又組成了螞蟻的整個路徑，即通過局部路徑搜索完成整個路徑的搜索。（5） 人工螞蟻系統(tǒng)和真實螞蟻系統(tǒng)一樣，都具有自組織特性17第四組 蟻群算法應(yīng)用及改進研究人工螞蟻群體和真實螞蟻群體都沒有者，每個螞蟻單獨行動就能夠使群體完成復(fù)雜的任務(wù)，并且保證群體有序運轉(zhuǎn)。螞蟻系統(tǒng)的這種自組織性使蟻群算法具有易于等特點。另一方面，為了便于算法模型的建立、增加算法的柔性、增強算法的性能，人

38、工螞蟻又被賦予了一些特殊的智能使以完成一些真實螞蟻難以做到的行為：（1） 搜索行為的差別真實螞蟻是在現(xiàn)實的三維世界中進行連續(xù)的爬行；人工螞蟻是在抽象畫的二維地圖中進行搜索，而人工螞蟻的行為是在節(jié)點間的離散的躍遷。（2） 信息素更新機制的差別真實螞蟻在行進的同時不斷著信息素，并且在前進和返回的途中都在信息素；人工螞蟻在前進過程不信息素，只在返回的途中信息素，并且信息素的是在瞬間完成的。此外，人工螞蟻得到了可以解的質(zhì)量的人工智能，所以信息素的大小與解的質(zhì)量有關(guān)；真實螞蟻無法解的質(zhì)量，對所有路徑都信息素。在人工螞蟻系統(tǒng)的基礎(chǔ)上，Dorigo 提出了蟻群算法。概括起來，蟻群算法具有以下特點：（1） 全

39、局搜索能力強使用相互作用的螞蟻群體進行搜索，使獲得最優(yōu)解的概率增加。螞蟻搜索時基于概率決策而不是確定型決策，使得解空間較大，所有路徑都有可能被找到。（2） 算法適應(yīng)性強蟻群算法對搜索空間沒有特殊要求，可以應(yīng)用于非常多種類型的問題。此外，由于任務(wù)是由群體完成的，所以單個螞蟻不工作對群體行為造成影響。（3） 易與其他算法相結(jié)合蟻群算法的搜索時逐步完成的，因此可以方便的在每一步或每完成一次搜索后與其他算法或其他優(yōu)化策略組合，如與正向逆向調(diào)度結(jié)合。此外，由于存在啟發(fā)式信息，蟻群算法獲得初始解的能力較隨機生成初始解的算法更強，與其他算法結(jié)合可以獲得較好的結(jié)果，例如使用蟻群算法迭代若干次后作為遺傳算法的初

40、始解進行交叉，變異等操作。（4） 容易出現(xiàn)過早收斂現(xiàn)象蟻群系統(tǒng)中信息素的正反饋現(xiàn)象有著正反兩面性，一方面使螞蟻可以集中于某路徑即保證算法的收斂性，另一方面，容易使蟻群過早陷入某些較差解或次優(yōu)解。信息素?fù)]發(fā)可以在18第四組 蟻群算法應(yīng)用及改進研究一定程度上彌補這個缺點，此外也可以在算法中引入改進措施進行彌補。而在引入改進措施后，蟻群算法往往得到了較高質(zhì)量的解，但犧牲了其收斂速度，最終另一，即收斂速度過慢。（二） 蟻群算法基本模型在人工螞蟻系統(tǒng)的基礎(chǔ)上，Dorigo 提出了最早的蟻群算法螞蟻系統(tǒng)，大部分蟻群算法都是以螞蟻系統(tǒng)為原型的。蟻群系統(tǒng)可以應(yīng)用于許多問題，對應(yīng)不同的問題，蟻群算法的數(shù)學(xué)模型的

41、表現(xiàn)形式并非完全相同。旅行商問題作為一個組合優(yōu)化難題是螞蟻系統(tǒng)最早應(yīng)用的問題，而且他是一個最短路徑問題，與蟻群的覓食行為非常相似，因此，為了解釋蟻群首先借由旅行商問題（TSP）給出螞蟻系統(tǒng)的數(shù)學(xué)模型。然后介紹算法的基本模型，螞蟻系統(tǒng)解決旅行商問題的實現(xiàn)方法。1.螞蟻系統(tǒng)數(shù)學(xué)模型旅行商問題可以描述為：在 = (，)的途中，為節(jié)點即城市的集合，為連接節(jié)點的無向連接弧即連接兩兩城市的道路，已知 = 個城市兩兩之間的距離，求一條路徑使得旅行商依次經(jīng)過每個城市一次且總路程最短。首先定義符號：表 3.1 TSP 蟻群算法符號表值得注意的是，啟發(fā)信息是人工螞蟻智能的又一體現(xiàn)。自然螞蟻在搜索初期對途徑?jīng)]有任何

42、偏好，只是純粹的依靠概率進行搜索。為了提高人工螞蟻的效率，螞蟻系統(tǒng)引入了啟發(fā)信息即從城市移動到城市的啟發(fā)程度，事實證明這對算法效率的提高特別是初始量的提高有非常重要的作用，nij通常依據(jù)問題性質(zhì)而認(rèn)為決定，不隨著蟻群的移動而改變。例如，在TSP 問題中，一般設(shè)定 = 1 ，路徑的長度越短，初期擁有的信息越多。螞蟻系統(tǒng)的數(shù)學(xué)模型的建立與最初的人工螞蟻相似，也是通過螞蟻的路徑搜索行為、信19符號說明m蟻群中螞蟻的總數(shù)()時刻位于城市的螞蟻的個數(shù)城市和城市之間的距離路徑(，)的能見度，即為啟發(fā)信息路徑(，)上的信息素強度，即信息素信息螞蟻在路徑(，)上的信息素量螞蟻從城市移動到城市的概率第四組 蟻群

43、算法應(yīng)用及改進研究息素更新機制和信息素?fù)]發(fā)機制等幾個關(guān)鍵模板構(gòu)建。螞蟻的路徑搜索行為：在網(wǎng)絡(luò)圖 = (，)中，螞蟻在節(jié)點以一定的概率選擇下一個節(jié)點，建立一個局部解，多個局部解一個完整解。選擇概率的大小取決于可選擇的節(jié)點間信息素濃度的大小。當(dāng)?shù)? = 1，2， ，)只螞蟻處于節(jié)點時，它選擇節(jié)點作為下一個目的節(jié)點的概率為： () () () ()() =(3.6)0其他情況其中，為螞蟻在節(jié)點上可以選擇的相鄰節(jié)點的集合。從式（3.6）可以看出，螞蟻選擇下一個節(jié)點的概率同時受啟發(fā)信息和信息素信息影響，而這個影響的大小則受參數(shù)和。和分別反映了啟發(fā)信息和信息素信息在螞蟻選擇中的相對重要性。此外，為了達到旅

44、行商問題的每個城市只能經(jīng)過一次的要求，螞蟻們還會建立一個已經(jīng)達到過的城市的集合，這個類似表的集合使得螞蟻選擇到達過的城市，它在選擇中的作用通過來體現(xiàn)，即表中的城市會自動從中排除。信息素更新機制：與真實螞蟻在行進的同時信息素不同，人工螞蟻只在完成完整的路徑搜索后，根據(jù)這個路徑的質(zhì)量決定的信息素的量，并在返回途中沿原路。在算法模型中，信息素的是瞬間完成的。螞蟻系統(tǒng)信息素的更新機制可以通過下式表現(xiàn)：( + ) = () + (， + )(3.7)=1其中， (， + )表示第只螞蟻在完成從到的路徑后在路徑(，)上的信息素，它的大小根據(jù)完整路徑的質(zhì)量而定，路徑越短，的信息素越多，可以表示為： 0如果(

45、，)在路徑上否則(3.8) (， + ) = 其中，為一正常數(shù)，表示第 k 只螞蟻完成的完整路徑的長度，即中所有邊的長度之和。顯然，螞蟻在路徑(，)上的長度。的信息素大小取決于(，)所在的完整路徑信息素?fù)]發(fā)機制：在信息素更新的同時，人工蟻群同樣有類似自然蟻群信息素?fù)]發(fā)現(xiàn)象，他的作用是平衡信息素的累計，擴大螞蟻的搜索范圍，避免螞蟻過早的集中于某些路徑，有助于獲得最優(yōu)解。螞蟻系統(tǒng)的信息素?fù)]發(fā)機制可以通過下式表現(xiàn)：20第四組 蟻群算法應(yīng)用及改進研究( + 1) = (1 )()(3.9)其中，為信息素的揮發(fā)率，與信息素更新需要在完成整個路徑的搜索之后進行不同，信息素的揮發(fā)與螞蟻的行為無關(guān)，僅僅根據(jù)揮

46、發(fā)率隨時間揮發(fā)。2.蟻群系統(tǒng)算法的實現(xiàn)以旅行商問題，順序構(gòu)建為例，即只有在一只螞蟻獲得一條完整路徑并完成信息素更新后，下一只螞蟻才開始搜索，螞蟻系統(tǒng)算法的實現(xiàn)步驟可以表示為：（1）初始化相關(guān)參數(shù)，如螞蟻數(shù)目、算法終止條件及和的值等；（2）將螞蟻隨機或均勻分布到各個城市；（3）螞蟻通過概率選擇進行路徑搜索，并將每一步的城市列入列表中；（4）當(dāng)某只螞蟻完成了一次完整的路徑搜索后，更新信息素；（5）當(dāng)所有螞蟻完成了搜索，是否滿足算法終止條件；（6）重復(fù) 2-5 的過程直至滿足算法終止條件，終止算法。根據(jù)以上步驟，TSP 問題的 AS 算法流程圖可以表示為：是圖 3.5 螞蟻系統(tǒng)算法流程圖21終止算法

47、滿足算法終止條件？否是所有螞蟻完成了搜索？否更新信息素第k只螞蟻完成搜索分配螞蟻初始化參數(shù)第四組 蟻群算法應(yīng)用及改進研究（三） 后續(xù)系統(tǒng)在螞蟻系統(tǒng)（AS）算法出現(xiàn)之后，Dorigo22根據(jù)的不同，發(fā)展出了三種不同的模型，分別稱為蟻（antcycle system）、蟻量系統(tǒng)（ant-quantity system）和蟻密系統(tǒng)（ant-density system）。這三種算法是螞蟻系統(tǒng)的直接后續(xù)算法，可以說是基本螞蟻系統(tǒng)的不同表現(xiàn)形式，但也存在一些差別。1. 蟻蟻基于順序構(gòu)建的方法構(gòu)建解，即一只螞蟻完成一次完整的路徑搜索后才根據(jù)該解的質(zhì)量對該路徑進行信息素更新。蟻的信息素更新機制如下所示：/，

48、如果(，)在路徑上0，否則 (， + ) = (5.1)其中，為一正常數(shù)，表示第只螞蟻完成的完整路徑的長度，即是中所有邊的長度之和。顯然，螞蟻在路徑(，)上的信息素大小取決于(，)所在的完整路徑的長度。2. 蟻量系統(tǒng)蟻量系統(tǒng)與蟻的差別在于信息素更新的方式，它的更新方式如下所示：/，如果螞蟻經(jīng)過(，) (， + 1) = (5.2)0，否則其中，為一正常數(shù)，為路徑(，)的長度。從該式可以看出，蟻量系統(tǒng)的信息素更新方式是隨著螞蟻的行進不斷逐步進行的。螞蟻每完成一次節(jié)點的選擇，即螞蟻完成一段的行進，就根據(jù)這段路徑的質(zhì)量（路徑的長度）息素就越多。信息素，路徑的長度越短，獲得的信3. 蟻密系統(tǒng)蟻密系統(tǒng)與

49、蟻周和蟻量系統(tǒng)的差別也在于信息素的更新方式，它的更新方式如下所示：，如果螞蟻經(jīng)過(，) (， + 1) = (5.3)0，否則其中，為一正常數(shù)。從式中可以看出，蟻密系統(tǒng)信息素的與螞蟻經(jīng)過的路程長度無關(guān)，也就是說，螞蟻在它經(jīng)過的每段路徑都相同量的信息素。三種螞蟻系統(tǒng)算法的最主要區(qū)別在于信息素的更新方式。后兩種系統(tǒng)中，螞蟻每完成一中，螞蟻只有在走完個城市22段路徑都會更新信息素濃度，利用的是局部信息；而蟻第四組 蟻群算法應(yīng)用及改進研究后信息素濃度，利用的是整體信息。1996 年，Dorigo5等對這三種算法進行了比較，結(jié)果是蟻比其他兩種算法有更好的性能。此后的研究主要基于蟻而進行，而蟻也通常被直接叫做螞蟻系統(tǒng)，其他兩種算法基本已被遺棄。（四） 蟻群算法改進算法螞蟻系統(tǒng)在解決一些小規(guī)模的 TSP 問題時的表現(xiàn)尚可令人滿意。但隨著問題規(guī)模的擴大，螞蟻系統(tǒng)很難在可接受的循環(huán)次