一、蟻群算法簡介
1 引言
在自然界中各種生物群體顯現出來的智能近幾十年來得到了學者們的廣泛關注，學者們通過對簡單生物體的群體行為進行模拟，進而提出了群智能算法。其中， 模拟蟻群覓食過程的蟻群優化算法(Ant
Colony Optimization， A CO) 和模拟鳥群運動方式的粒子群算法(ParticleS warm Optimization，PSO) 是兩種最主要的群智能算法。
蟻群算法是一種源于大自然生物世界的新的仿生進化算法，由意大利學者M.Dorigo， V.Mani ezzo和A.Color ni等人于20世紀90年代初期通過模拟自然界中螞蟻集體尋徑行為而提出的一種基于種群的啟發式随機搜尋算法[1].螞蟻有能力在沒有任何提示的情形下找到從巢穴到食物源的最短路徑，并且能随環境的變化，适應性地搜尋新的路徑，産生新的選擇。其根本原因是螞蟻在尋找食物時，能在其走過的路徑上釋放一種特殊的分泌物――資訊素2，随着時間的推移該物質會逐漸揮發，後來的螞蟻選擇該路徑的機率與當時這條路徑上資訊素的強度成正比。當一條路徑上通過的螞蟻越來越時，其留下的資訊素也越來越多，後來螞蟻選擇該路徑的機率也就越高，進而更增加了該路徑上的資訊素強度。而強度大的資訊素會吸引更多的螞蟻，進而形成一種正回報機制。通過這種正回報機制，螞蟻最終可以發現最短路徑。
最早的蟻群算法是螞蟻系統(Ant System， AS) ， 研究者們根據不同的改進政策對螞蟻系統進行改進并開發了不同版本的蟻群算法，并成功地應用于優化領域。用該方法求解旅行商(TSP) 問題、配置設定問
題、工廠中的房間作業排程(job-shop) 問題， 取得了較好的試驗結果[3-6] 。蟻群算法具有分布式計算、無中心控制和分布式個體之間間接通信等特征，易于與其他優化算法相結合，它通過簡單個體之間的協作表現出了求解複雜問題的能力，已被廣泛應用于求解優化問題。蟻群算法相對而言易于實作，且算法中并不涉及複雜的數學操作，其處理過程對計算機的軟硬體要求也不高，是以對它的研究在理論和實踐中都具有重要的意義。
目前，國内外的許多研究者和研究機構都開展了對蟻群算法理論和應用的研究，蟻群算法已成為國際計算智能領域關注的熱點課題。雖然目前蟻群算法沒有形成嚴格的理論基礎，但其作為一種新興的進
化算法已在智能優化等領域表現出了強大的生命力。
2 蟻群算法理論
蟻群算法是對自然界螞蟻的尋徑方式進行模拟而得出的一種仿生算法。螞蟻在運動過程中，能夠在它所經過的路徑上留下資訊素進行資訊傳遞，而且螞蟻在運動過程中能夠感覺這種物質，并以此來指導
自己的運動方向。是以，由大量螞蟻組成的蟻群的集體行為便表現出一種資訊正回報現象：某一路徑上走過的螞蟻越多，則後來者選擇該路徑的機率就越大[7]。
2.1真實蟻群的覓食過程
為了說明蟻群算法的原理，先簡要介紹一下螞蟻搜尋食物的具體過程。在自然界中，蟻群在尋找食物時，它們總能找到一條從食物到巢穴之間的最優路徑。這是因為螞蟻在尋找路徑時會在路徑上釋放出
一種特殊的資訊素。蟻群算法的資訊互動主要是通過資訊素來完成的。螞蟻在運動過程中，能夠感覺這種物質的存在和強度。初始階段，環境中沒有資訊素的遺留，螞蟻尋找事物完全是随機選擇路徑，
随後尋找該事物源的過程中就會受到先前螞蟻所殘留的資訊素的影響，其表現為螞蟻在選擇路徑時趨向于選擇資訊素濃度高的路徑。同時，資訊素是一種揮發性化學物，會随着時間的推移而慢慢地消逝。如果每隻螞蟻在機關距離留下的資訊素相同，那對于較短路徑上殘留的資訊素濃度就相對較高，這被後來的螞蟻選擇的機率就大，進而導緻這條短路徑上走的螞蟻就越多。而經過的螞蟻越多，該路徑上殘留的資訊素就将更多，這樣使得整個螞蟻的集體行為構成了資訊素的正回報過程，最終整個蟻群會找出最優路徑。
若螞蟻從A點出發，速度相同，食物在D點，則它可能随機選擇路線ABD或A CD。假設初始時每條路線配置設定一隻螞蟻， 每個時間機關行走一步。圖5.1所示為經過8個時間機關時的情形：走路線ABD的螞蟻到達終點：而走路線A CD的螞蟻剛好走到C點， 為一半路程。
圖5.2表示從開始算起， 經過16個時間機關時的情形：走路線ABD的螞蟻到達終點後得到食物又傳回了起點A，而走路線A CD的螞蟻剛好走到D點.
圖5.2螞蟻出發後經過16個時間機關時的情形
假設螞蟻每經過一處所留下的資訊素為1個機關，則經過32個時間機關後，所有開始一起出發的螞蟻都經過不同路徑從D點取得了食物。此時ABD的路線往返了2趟， 每一處的資訊素為4個機關； 而A CD的路線往返了一趟，每一處的資訊素為2個機關，其比值為2：1。
尋找食物的過程繼續進行， 則按資訊素的指導， 蟻群在ABD路線上增派一隻螞蟻(共2隻) ， 而A CD路線上仍然為一隻螞蟻。再經過32個時間機關後，兩條線路上的資訊素機關積累為12和4，比值為3：1。若按以上規則繼續， 蟻群在ABD路線上再增派一隻螞蟻(共3隻) ， 而A CD路線上仍然為一隻螞蟻。再經過32個時間機關後， 兩條線路上的資訊素機關積累為24和6，比值為4：1.若繼續進行， 則按資訊素的指導， 最終所有的螞蟻都會放棄A CD路線， 而選擇ABD路線。這也就是前面所提到的正回報效應。
2.2人工蟻群的優化過程
基于以上真實蟻群尋找食物時的最優路徑選擇問題，可以構造人工蟻群， 來解決最優化問題， 如TSP問題。人工蟻群中把具有簡單功能的工作單元看作螞蟻。二者的相似之處在于都是優先選擇資訊素濃度大的路徑。較短路徑的資訊素濃度高，是以能夠最終被所有螞蟻選擇，也就是最終的優化結果。兩者的差別在于人工蟻群有一定的記憶能力，能夠記憶已經通路過的節點。同時，人工蟻群再選擇下一條路徑的時候是按一定算法規律有意識地尋找最短路徑，而不是盲目的。例如在TSP問題中， 可以預先知道目前城市到下一個目的地的距離。在TSP問題的人工蟻群算法中， 假設m隻螞蟻在圖的相鄰節點間移動，進而協作異步地得到問題的解。每隻螞蟻的一步轉移機率由圖中的每條邊上的兩類參數決定：一是資訊素值，也稱資訊素痕迹：二是可見度，即先驗值。
資訊素的更新方式有兩種：一是揮發，也就是所有路徑上的資訊素以一定的比率減少，模拟自然蟻群的資訊素随時間揮發的過程；二是增強，給評價值“好”(有螞蟻走過)的邊增加資訊素。螞蟻向下一個目标的運動是通過一個随機原則來實作的，也就是運用目前所在節點存儲的資訊，計算出下一步可達節點的機率，并按此機率實作一步移動，如此往複，越來越接近最優解。螞蟻在尋找過程中，或在找到一個解後，會評估該解或解的一部分的優化程度，并把評價資訊儲存在相關連接配接的資訊素中。
2.3真實螞蟻與人工螞蟻的異同
蟻群算法是一種基于群體的、用于求解複雜優化問題的通用搜尋技術。與真實螞蟻通過外資訊的留存、跟随行為進行間接通信相似，蟻群算法中一群簡單的人工螞蟻通過資訊素進行間接通信，并利用該資訊和與問題相關的啟發式資訊逐漸構造問題的解。
人工螞蟻具有雙重特性：一方面，它們是真實螞蟻的抽象，具有真實螞蟻的特性：另一方面，它們還有一些真實螞蟻沒有的特性，這些新的特性使人工螞蟻在解決實際優化問題時，具有更好地搜尋較優解的能力。
人工螞蟻與真實螞蟻的相同點為：
(1)都是一群互相協作的個體。與真實蟻群一樣，蟻群算法由一群人工螞蟻組成，人工螞蟻之間通過同步/異步協作來尋找問題的最優解。雖然單隻人工螞蟻可以構造出問題的解，但隻有當多隻人工螞蟻
通過互相協作，才能發現問題的最優(次優)解。人工螞蟻個體間通過寫/讀問題的狀态變量來進行協作。
(2)都使用資訊素的迹和蒸發機制。如真實螞蟻一樣，人工螞蟻通過改變所通路過的問題的數字狀态資訊來進行間接的協作。在蟻群算法中，資訊素是人工螞蟻之間進行交流的唯一途徑。這種通信方式在群體知識的利用上起到了至關重要的作用。另外，蟻群算法還用到了蒸發機制，這一點對應于真實螞蟻中資訊素的蒸發現象。蒸發機制使蟻群逐漸忘記過去的曆史，使後來的螞蟻在搜尋中較少受到過去較差解的影響，進而更好地指導螞蟻的搜尋方向。
(3)搜尋最短路徑與局部移動。人工螞蟻和真實螞蟻具有相同的任務，即以局部移動的方式構造出從原點(蟻巢)到目的點(食物源)之間的最短路徑。
(4)随機狀态轉移政策。人工螞蟻和真實螞蟻都按照機率決策規則從一種狀态轉移到另一種相鄰狀态。其中的機率決策規則是與問題相關的資訊和局部環境資訊的函數。在狀态轉移過程中，人工螞蟻和
真實螞蟻都隻用到了局部資訊，沒有使用前瞻政策來預見将來的狀态。
人工螞蟻和真實螞蟻的不同點為：
(1)人工螞蟻生活在離散的時間，從一種離散狀态到另一種離散狀态。
(2)人工螞蟻具有内部狀态，即人工螞蟻具有一定的記憶能力，能記住自己走過的地方。
(3)人工螞蟻釋放資訊素的數量是其生成解的品質的函數。
(4)人工螞蟻更新資訊素的時機依賴于特定的問題。例如，大多數人工螞蟻僅僅在螞蟻找到一個解之後才更新路徑上的資訊素。
2.4蟻群算法的特點
蟻群算法是通過對生物特征的模拟得到的一種優化算法，它本身具有很多優點：
(1)蟻群算法是一種本質上的并行算法。每隻螞蟻搜尋的過程彼此獨立，僅通過資訊激素進行通信。是以蟻群算法可以看作一個分布式的多智能體系統，它在問題空間的多點同時開始獨立的解搜尋，不僅增加了算法的可靠性，也使得算法具有較強的全局搜尋能力。
(2)蟻群算法是一種自組織的算法。所謂自組織，就是組織力或組織指令來自于系統的内部，以差別于其他組織。如果系統在獲得空間、時間或者功能結構的過程中，沒有外界的特定幹預，就可以說系統是自組織的。簡單地說，自組織就是系統從無序到有序的變化過程。
(3)蟻群算法具有較強的魯棒性。相對于其他算法，蟻群算法對初始路線的要求不高，即蟻群算法的求解結果不依賴于初始路線的選擇，而且在搜尋過程中不需要進行人工的調整。此外，蟻群算法的參
數較少，設定簡單，因而該算法易于應用到組合優化問題的求解。
(4)蟻群算法是一種正回報算法。從真實螞蟻的覓食過程中不難看出，螞蟻能夠最終找到最優路徑，直接依賴于其在路徑上資訊素的堆積，而資訊素的堆積是一個正回報的過程。正回報是蟻群算法的重
要特征，它使得算法進化過程得以進行。
3 基本蟻群算法及其流程
4 改進的蟻群算法
針對基本蟻群算法一般需要較長的搜尋時間和容易出現停滞現象等不足，很多學者在此基礎上提出改進算法，提高了算法的性能和效率。
4.1精英螞蟻系統
4.2 最大最小螞蟻系統
為了克服基本蟻群系統中可能出現的停滞現象， Thomas Stutz le等人提出了最大-最小(MAX-MIN) 蟻群系統[10] ， 主要有三方面的不同：
(1)與蟻群系統相似，為了充分利用循環最優解和目前為止找出的最優解，在每次循環之後，隻有一隻螞蟻進行資訊素更新。這隻螞蟻可能是找出目前循環中最優解的螞蟻(疊代最優的螞蟻)，也可能是找出從實驗開始以來最優解的螞蟻(全局最優的螞蟻)；而在螞蟻系統中，對所有螞蟻走過的路徑都進行資訊素更新。
(2) 為避免搜尋的停滞， 在每個解元素(TSP中是每條邊) 上的資訊素軌迹量的值域範圍被限制在[min，Tmax] 區間内； 而在螞蟻系統中資訊素軌迹量不被限制，使得一些路徑上的軌迹量遠高于其他邊，進而螞蟻都沿着同條路徑移動，阻止了進一步搜尋更優解的行為。
(3)為使螞蟻在算法的初始階段能夠更多地搜尋新的解決方案，将資訊素初始化為tmax；而在螞蟻系統中沒有這樣的設定。
4.3基于排序的蟻群算法
基于排序的蟻群算法(Rank-BasedAntSystem)是Bull n heimer、Hartl和Strauss等人提出的[11] 。在該算法中， 每個螞蟻釋放的資訊素按照它們不同的等級進行揮發，另外類似于精英蟻群算法，精英螞蟻在每次循環中釋放更多的資訊素。在修改資訊素路徑前，螞蟻按照它們的旅行長度進行排名(短的靠前)，螞蟻釋放資訊素的量要和螞蟻的排名相乘。在每次循環中，隻有排名前w-1位的螞蟻和精英螞蟻才允許在路徑上釋放資訊素。己知的最優路徑給以最強的回報，和系數w相乘；而排名第r位的螞蟻則乘以系數“w-(≥0)。資訊素如下式所示：
4.4自适應蟻群算法
基本蟻群系統讓資訊量最大的路徑對每次路徑的選擇和資訊量的更新起主要作用，但由于強化了最優資訊回報，就可能導緻“早熟”停滞現象。而最大最小蟻群算法将各個路徑上的資訊量的更新限定在固定的範圍内，這雖然在一定程度上避免了“早熟”停滞現象，但在解分布較分散時會導緻收斂速度變慢。以上方法的共同缺點在于：它們都按一種固定不變的模式去更新資訊量和确定每次路徑的選
擇機率。
為了克服以上算法的不足， L.M.Gambardella和M.Dorigo提出了基于調節資訊素揮發度的自适應蟻群算法[12]。相對基本蟻群算法的改進如下：
(1)在每次循環結束後求出最優解，并将其保留。
(2)自适應地改變p值。當問題規模比較大時，由于資訊量的揮發系數p的存在，使那些從未被搜尋到的資訊量會減小到接近于0，降低了算法的全局搜尋能力；當p過大且解的資訊量增大時，以前搜尋過的解被選擇的可能性過大，也會影響到算法的全局搜尋能力；通過減小p雖然可以提高算法的全局搜尋能力，但又會使算法的收斂速度降低。是以可以自适應地改變p的值。p的初始值p(to)=1；當算法求得的最優值在N次循環内沒有明顯改進時，p減為：
5 關鍵參數說明
在蟻群算法中，不僅資訊素和啟發函數乘積以及螞蟻之間的合作行為會嚴重影響到算法的收斂性，蟻群算法的參數也是影響其求解性能和效率的關鍵因素。資訊素啟發式因子α、期望啟發因子β、資訊
素蒸發系數p、資訊素強度Q、螞蟻數目m等都是非常重要的參數，其選取方法和選取原則直接影響到蟻群算法的全局收斂性和求解效率。
資訊素啟發式因子a
資訊素啟發式因子a代表資訊量對是否選擇目前路徑的影響程度，即反映螞蟻在運動過程中所積累的資訊量在指導蟻群搜尋中的相對重要程度。a的大小反映了蟻群在路徑搜尋中随機性因素作用的強度，其值越大，螞蟻在選擇以前走過的路徑的可能性就越大，搜尋的随機性就會減弱；而當啟發式因子a的值過小時，則易使蟻群的搜尋過早陷于局部最優。根據經驗，資訊素啟發式因子a取值範圍一般為[1，4]時，蟻群算法的綜合求解性能較好。
期望啟發因子β
期望啟發因子β表示在搜尋時路徑上的資訊素在指導螞蟻選擇路徑時的向導性，它的大小反映了蟻群在搜尋最優路徑的過程中的先驗性和确定性因素的作用強度。期望啟發因子β的值越大，螞蟻在某個局部點上選擇局部最短路徑的可能性就越大，雖然這個時候算法的收斂速度得以加快，但蟻群搜尋最優路徑的随機性減弱，而此時搜尋易于陷入局部最優解。根據經驗，期望啟發因子β取值範圍一般為[3，
5]，此時蟻群算法的綜合求解性能較好。實際上，資訊素啟發式因子α和期望啟發因子β是一對關聯性很強的參數：蟻群算法的全局尋優性能，首先要求蟻群的搜尋過程必須要有很強的随機性；而蟻群算法的快速收斂性能，又要求蟻群的搜尋過程必須要有較高的确定性。是以，兩者對蟻群算法性能的影響和作用是互相配合、密切相關的，算法要獲得最優解，就必須在這二者之間選取一個平衡點，隻有正确標明它們之間的搭配關系，才能避免在搜尋過程中出現過早停滞或陷入局部最優等情況的發生。
資訊素蒸發系數p
蟻群算法中的人工螞蟻是具有記憶功能的，随着時間的推移，以前留下的資訊素将會逐漸消逝，蟻群算法與其他各種仿生進化算法一樣，也存在着收斂速度慢、容易陷入局部最優解等缺陷，而資訊素蒸
發系數p大小的選擇将直接影響到整個蟻群算法的收斂速度和全局搜尋性能。在蟻群算法的抽象模型中，p表示資訊素蒸發系數，1-p則表示資訊素持久性系數。是以，p的取值範圍應該是0~1之間的一個
數，表示資訊素的蒸發程度，它實際上反映了螞蟻群體中個體之間互相影響的強弱。p過小時，則表示以前搜尋過的路徑被再次選擇的可能性過大，會影響到算法的随機性能和全局搜尋能力：p過大時，說
明路徑上的資訊素揮發的相對變多，雖然可以提高算法的随機搜尋性能和全局搜尋能力，但過多無用搜尋操作勢必會降低算法的收斂速度。
螞蟻數目m
蟻群算法是一種随機搜尋算法，與其他模拟進化算法一樣，通過多個候選解組成的群體進化過程來尋求最優解，在該過程中不僅需要每個個體的自适應能力，更需要群體之間的互相協作能力。蟻群在搜
索過程中之是以表現出複雜有序的行為，是因為個體之間的資訊交流與互相協作起着至關重要的作用。
對于旅行商問題，單個螞蟻在一次循環中所經過的路徑，表現為問題可行解集中的一個解，m隻螞蟻在一次循環中所經過的路徑，則表現為問題解集中的一個子集。顯然，子集增大(即螞蟻數量增多)，可以提高蟻群算法的全局搜尋能力以及算法的穩定性；但螞蟻數目增大後，會使大量的曾被搜尋過的解(路徑)上的資訊素的變化趨于平均，資訊正回報的作用不明顯，雖然搜尋的随機性得到了加強，但收斂速度減慢；反之，子集較小(螞蟻數量少)，特别是當要處理的問題規模比較大時，會使那些從來未被搜尋到的解(路徑)上的資訊素減小到接近于0，搜尋的随機性減弱，雖然收斂速度加快了，但會使算法的全局性能降低，算法的穩定性差，容易出現過早停滞現象。m一般取10~50.
資訊素強度Q對算法性能的影響
在蟻群算法中，各個參數的作用實際上是緊密聯系的，其中對算法性能起着主要作用的是資訊啟發式因子α、期望啟發式因子β和資訊素揮發因子p這三個參數，總資訊量(對算法性能的影響有賴于上述三個參數的選取， 以及算法模型的選取。例如， 在ant-cycle模型和ant-quantity模型中， 總資訊量4所起的作用顯然是有很大差異的， 即随着問題規模的不同，其影響程度也将不同。相關人員研究結果表
明：總資訊量Q對ant-cycle模型蟻群算法的性能沒有明顯的影響。是以，在算法參數的選擇上，參數Q不必作特别的考慮，可以任意選取。
最大進化代數G
最大進化代數6是表示蟻群算法運作結束條件的一個參數，表示蟻群算法運作到指定的進化代數之後就停止運作，并将目前群體中的最佳個體作為所求問題的最優解輸出。一般6取100~500。
二、部分源代碼
%function [bestroute,routelength]=Ant
clc
clear
tic
% 讀入城市間距離矩陣資料檔案
CooCity = load( 'CooCity.txt' ) ;% 城市網絡圖坐标資料檔案，txt形式給出
NC=length(CooCity); % 城市個數
for i=1:NC % 計算各城市間的距離
for j=1:NC
distance(i,j)=sqrt((CooCity(i,2)-CooCity(j,2))^2+(CooCity(i,3)-CooCity(j,3))^2);
end
end
% distance=xlsread('DistanceCity.xls'); % 城市間距離矩陣資料檔案，excel形式給出
MAXIT=10; % 最大循環次數
Citystart=[]; % 起點城市編号
tau=ones(NC,NC); % 初始時刻各邊上的資訊痕迹為1
rho=0.5; % 揮發系數
alpha=1; % 殘留資訊相對重要度
beta=5; % 預見值的相對重要度
Q=10; % 蟻環常數
NumAnt=20; % 螞蟻數量
%bestroute=zeros(1,48); % 用來記錄最優路徑
routelength=inf; % 用來記錄目前找到的最優路徑長度
for n=1:MAXIT
for k=1:NumAnt %考查第K隻螞蟻
deltatau=zeros(NC,NC); % 第K隻螞蟻移動前各邊上的資訊增量為零
%[routek,lengthk]=path(distance,tau,alpha,beta,[]); % 不靠率起始點
[routek,lengthk]=path(distance,tau,alpha,beta,Citystart); % 指定起始點
if lengthk<routelength % 找到一條更好的路徑
routelength=lengthk;
bestroute=routek;
end
for i=1:NC-1 % 第K隻螞蟻在路徑上釋放的資訊量
deltatau(routek(i),routek(i+1))=deltatau(routek(i),routek(i+1))+Q/lengthk; % 資訊素更新
end
%deltatau(routek(NC),1)=deltatau(routek(NC),1)+Q/lengthk; %
end
length_n(n)=routelength; % 記錄路徑收斂
tau=(1-rho).*tau; % 資訊素揮發
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
costtime=toc;
subplot(1,2,1),plot([CooCity(bestroute,2)],[CooCity(bestroute,3)],'-*')
subplot(1,2,2),plot([1:MAXIT],length_n,'-*')
[routelength,costtime]
三、運作結果
四、matlab版本及參考文獻
1 matlab版本
2014a
2 參考文獻
[1] 包子陽,餘繼周,楊杉.智能優化算法及其MATLAB執行個體（第2版）[M].電子工業出版社，2016.
[2]張岩,吳水根.MATLAB優化算法源代碼[M].清華大學出版社，2017.