基于可變天氣因素的MMAS改進算法

焦宗浩，高紹姝，李克文

(中國石油大學 計算機與通信工程學院，山東 青島 266580)

0 引 言

隨著人工智能[1]的飛速發展，專家學者逐漸從生活中尋求更先進的思想，如從自然界中模擬生物群體解決生存問題的行為，其中蟻群算法[2]是模擬螞蟻覓食、粒子群算法[3]是模擬鳥群覓食。蟻群算法(ant colony optimization，ACO)是在20世紀90年代由意大利學者M. Dorigo根據蟻群覓食活動提出的，后經德國學者Stützle提出一種改進的蟻群算法——最大最小螞蟻系統(MAX-MIN ant system，MMAS)，該方法廣泛應用于各種領域[4-8]，其工作原理是在每次循環過程中僅選擇一只最優螞蟻進行信息素的更新，該更新方式加快了收斂速度，但同時容易陷入局部最優。針對MMAS存在的問題，現有的文獻一般是通過改進信息素的更新方式[9,10]、調整螞蟻的轉移規則[11]、采用自適應方法[12,13]等，或者是將MMAS與其它算法結合，如鄰域搜索[14]、模擬退火策略[15]，甚至是蟻群算法[16]等。這些算法在一定的程度上提升了螞蟻的全局搜索能力，但精度有待提高。本文通過可變天氣因素對蟻群影響，提出一種基于可變天氣因素的最大最小螞蟻系統(VW-MMAS)，通過隨機的信息素揮發機制，改變信息素的殘留程度，增強其搜索的能力，提高解的精度。

1 相關概念

1.1 基本蟻群算法

我們以求解平面上n城市的旅行商問題(TSP)為例，來說明傳蟻群算法原理。TSP問題是指，給定一組城市坐標，城市數量為n，求得一條遍歷所有城市的最短回路的問題，其中除了出發的城市以外其它城市僅允許走一次。首先初始化蟻群數量m，信息啟發因子α，期望啟發因子β，信息素揮發系數ρ，各路徑上的信息素τij，其中在初始時刻每條路徑的信息素濃度設為相等，即τij=C(C為較小的常數)；然后在每次迭代過程中，每只螞蟻隨機選擇一個城市作為起始城市，再使用輪盤賭的方法，按照式(1)選擇下一個城市

(1)

τij(t)=(1-ρ)τij(t-1)+Δτij(t)

(2)

1.2 最大最小螞蟻系統

最大最小螞蟻系統(MMAS)是在ACO上改進，克服ACO容易陷入局部最優、收斂速度慢、花費時間長等缺點，其主要改進方向是以下3個方面：

(1)將信息素τij限制在τmin與τmax之間，即τmin≤τij≤τmax， 該策略避免最優路徑上的信息素和未訪問路徑的信息素差距過大，導致搜索的停滯；

(2)將初始信息素設置為τmax， 該策略使得算法在初始階段有更多的搜索可能；

(3)在每次迭代之后，只允許路徑最優螞蟻更新信息素，可以是當前迭代最優，也可以是歷史最優。其信息素更新方式按照式(3)進行

(3)

2 改進的最大最小螞蟻系統

雖然群體螞蟻有著明確的分工行為模式，但是其覓食行為仍受著外界環境的影響，如地形、天氣等外在因素。根據螞蟻的生活習性發現，在不同的天氣之后螞蟻的覓食行為有所不同，主要原因是在不同天氣信息素的殘留程度不同，如在雨天之后，雨水沖刷了信息素，導致信息素的整體減少，信息素之間的差距減少，使得螞蟻在雨天過后覓食范圍明顯擴大。因此本文提出的可變天氣因素最大最小螞蟻系統(VW-MMAS)是針對不同天氣情況下，設置不同的信息素揮發系數，從而改進最大最小螞蟻系統，更新全局信息素的殘留程度，擴大其螞蟻的搜索范圍，避免快速陷入局部最優，停止迭代。

2.1 基于可變天氣因素改進MMAS算法

由于實際的天氣是復雜多樣的，為了說明本文所提出的改進方法的有效性，實驗以3種天氣情況為例，分別是雨天、陰天、晴天。通過在不同的天氣情況下設置不同的信息素揮發系數，根據實際情況將信息素揮發系數按照可變天氣因素排序；同時考慮到在不同天氣情況下，外出覓食的螞蟻數量有所不同，本文假設在雨天揮發系數最大且螞蟻不覓食，在陰天揮發系數最小且隨機選擇一定數量螞蟻覓食，在晴天揮發系數中等且全部螞蟻外出覓食。采用上述的改進方式能夠有效增加全局的搜索能力，避免快速陷入局部最優。

在不同的天氣下，設置不同的信息素揮發系數以及蟻群數量。首先設置信息素揮發ρr、ρc、ρs， 其中ρr表示雨天時揮發系數，ρc表示陰天時揮發系數，ρs表示晴天時揮發系數，信息素揮發系數從大到小排序為：ρr>ρc>ρs； 然后設置蟻群數量，晴天時螞蟻數量ms， 陰天時螞蟻數量mc(

2.2 信息素更新的改進

在最大最小螞蟻系統中，只允許最優的螞蟻留下信息素，導致其它路徑的信息素隨著迭代次數的增加而減少，這種方式雖然增強了最優路徑的尋找，但同時增加了螞蟻陷入局部最優的可能性。針對此問題，通過設置閾值，統計最優路徑出現的次數，當時出現的次數大于閾值時，在式(3)更新的基礎上，用式(4)再進行信息素的更新，該方式保持最優路徑上的信息素不變，但增加其它路徑上信息素，使得路徑上信息素濃度差減小

(4)

2.3 VW-MMAS算法流程

步驟1 初始化各參數k,α,β,Q,Iternation，初始信息素設置為τmax， 迭代次數NC=0；

步驟2 按照2.1所述，設置3個隨機揮發系數ρr,ρc,ρs及對應的蟻群數量mr,mc,ms, 在每次循環結束后隨機選擇一個揮發系數及對應的螞蟻數量，作為當前迭代下的揮發系數及螞蟻數量；

步驟3 統計信息素揮發系數ρr連續出現的次數是否大于閾值，若是轉步驟2，否則轉步驟4；

步驟4 將m只螞蟻隨機放入到n座城市中，并將城市放入禁忌表tabu中；

步驟5 每只螞蟻按照概率(式(1))選擇下一次要訪問的城市，并將該城市放入禁忌表中，直到遍歷完所有城市，計算其路徑長度，并將每只螞蟻的路徑長度保存在distance_list中；

步驟6 當每只螞蟻均遍歷完城市之后，保存當前迭代最優路徑bestRoute以及對應最短路徑長度minDistance；

步驟7 按照式(3)將從步驟5中選出來的最優螞蟻更新信息素；

步驟8 判斷最優路徑長度出現的次數是否已經超過設置的閾值，如果已經超出，按照式(4)進行更新信息素；

步驟9 禁忌表tabu清空，迭代次數NC=NC+1。 如果迭代次數沒有達到最大值，則轉向步驟2；否則輸出最優解并退出循環。

流程如圖1所示。

圖1 改進算法VW-MMAS流程

3 仿真實驗結果及討論

為了評估VW-MMAS解決TSP問題的性能，實驗分別使用遺傳算法(GA)、粒子群算法(PSO)、蟻群算法(ACO)、最大最小螞蟻系統(MMAS)以及本文提出的VW-MMAS對TSPLIB數據庫中的TSP問題進行求解比較。其中GA中重要參數取值為：交叉概率pc=0.7， 變異概率pm=0.02， 種群數量m=100； PSO中重要參數取值為：α=1，β=0.9， 種群數量m=1000； ACO中重要參數取值為：α=0.8，β=2，Q=100，ρ=0.05， 種群數量m=2/3*n； MMAS中重要參數取值為：α=0.8，β=2，Q=100，τmin=0.1/n，τmax=1，ρ=0.05， 種群數量m=2/3*n； VW-MMAS中各參數的取值為：α=0.8，β=2，Q=100，τmin=0.1/n，τmax=1，ρr=0.3，ρc=0.2，ρs=0.15， 種群數量mr=0，mc=1/3*n，ms=2/3*n。 針對8個TSP問題，每種算法最大迭代次數MaxIter=1000， 并記錄算法的最優解，結果見表1。

根據表1中的結果可以看到，本文所提出的VW-MMAS算法與GA、PSO、ACO、MMAS算法相比，在大部分的TSP問題上所得解的質量更好，甚至在大規模的TSP問題也有一個很好的解，證明了VW-MMAS算法在求解TSP問題上，所得解的精度有所提升或者保持良好。圖2 展示了VW-MMAS算法在求解每個TSP問題時，最優的解決方案。

表2展示了對于每一個數據集，每種算法獨立運行十次，求得的每個算法的最優解、最差解、平均解以及標準差，其中最優解表示每個算法對TSP問題最好的解決方案，最差解表示每個算法對TSP問題最差的解決方案，平均解以及標準差表示算法的可靠性以及穩定性，而標準差越小，表示該算法越穩定更能找到最優解，反之標準差越大，算法的穩定性越差。

從表2中，可以看出VW-MMAS算法在所有TSP問題上最優解、最差解、標準差上取得了一個較好的性能。同時VW-MMAS算法的標準差小于MMAS算法的標準差，表明其穩定性和可靠性優于MMAS；而相比較GA、PSO、ACO這3種算法，雖然VW-MMAS在少數TSP問題上的標準差偏大，但是在整體上由于其最優解好于其它算法，并且最差解及平均解的精度均有所提高，這意味著VW-MMAS算法在尋找最優解時更穩定可靠，而其它算法更容易陷入局部最優。

表1 不同TSP問題對應算法的實驗結果

圖2 VW-MMAS求解TSP問題最優路徑

上述仿真實驗結果表明，本文提出的VW-MMAS算法在解決TSP問題具有更好的精度，與其它算法相比，提供的最優解最小且標準差較小。

4 結束語

本文提出VW-MMAS算法是在MMAS算法的基礎上，引入以下機制：

(1)結合可變天氣因素，提出隨機信息素揮發系數和蟻群數量機制，使用多個信息素揮發系數和蟻群數量代替原本僅使用單參數求解TSP問題，增加了信息素的變化情況，增強螞蟻的搜索能力；

(2)由于在算法運行后期容易陷入局部最優，通過考慮城市之間的距離對螞蟻路徑搜索的影響，將其作為在陷入局部最優時信息素更新方式，增加了不是最優路徑上信息素的濃度，縮小了信息素之間的差距，從而擴大蟻群的搜索范圍。

通過仿真實驗驗證了VW-MMAS算法的有效性，與其它算法相比，解的精度更好而且標準差最小，表明算法的穩定性和可靠性。

表2 不同TSP問題對應算法比較