基于信息素更新和揮發因子調整的改進蟻群算法

孟曉琳，黃天民，陳尚云

(西南交通大學 數學學院，四川 成都 611756)

0 引 言

20 世紀90年代，學者Macro Dorigo 首先提出了蟻群算法，其迅速成為啟發式算法研究的熱點，它在解決傳統算法無法解決的組合優化和NP 等難題上能夠取得很好的效果，并且具有解決復雜問題的能力.同時，蟻群算法的魯棒性較強，能進行分布式計算，同其他優化算法結合容易，而且算法沒有復雜的數學操作，對軟硬件要求不高，但是該算法搜索時間較長，很容易陷入局部最優解［1－2］.為了克服蟻群算法的缺點，許多學者對其進行了研究，并提出了相應的改進算法［3－6］.在此基礎上，本研究提出一種將信息素局部更新和全局更新相結合，并對揮發因子ρ進行分段設置，以此來增強蟻群算法的全局搜索能力，并采用TSP 實例對算法進行驗證，證明了本改進算法的有效性.

1 蟻群算法的基本原理

設m 表示螞蟻的數量，dij(i，j = 1，2，…，n)表示城市i、j 之間的距離，bi(t)表示t 時刻位于城市i的螞蟻個數，則，表示t 時刻在i和j 連線上殘留的信息素，初始時刻，各路徑上的信息素濃度相等，設τij(0)= C，C 為常數.

在搜索過程中，每只螞蟻根據狀態轉移概率來判斷路徑的選擇，t 時刻螞蟻k 由城市i 到j 的狀態轉移概率用來表示，

每只螞蟻對路徑做出選擇后將移動至下一城市，并且將當前螞蟻所在城市放入禁忌表tab uk中，當禁忌表包含所有城市時，表示已經完成一次迭代，計算每只螞蟻所走的路徑并保留最短路徑.

路徑上的信息素會隨著時間的推移而漸漸減弱，經過n 個時刻，路徑ij 的信息素將按照式(2)進行更新，式中，ρ 表示信息素揮發因子，Δτij(t)表示本次迭代中路徑ij 上的信息素增量，表示第k 只螞蟻在本次迭代中留在路徑ij 上的信息素，其表達式為，

式中，Q 表示常數，Lk表示第k 只螞蟻在本次迭代中走過的路徑長度［4］.

2 蟻群算法的改進

本研究對基本蟻群算法做了2 點改進:其一，針對基本蟻群算法容易出現早熟和停滯現象，進行了信息素更新的改進;其二，為了使算法的全局搜索能力和收斂速度均得到提高，進行了信息素揮發因子的改進.

2.1 信息素的局部更新與全局更新

在基本蟻群算法中，信息素的更新方式有可能導致這樣的現象:新的最優路徑尚未出現時，當前最優路徑上的信息素就會按照信息素更新公式不斷增多.這使得當前最優路徑上的信息素可能會因為過度增多而大于新的最優路徑上信息素，最終導致算法停滯.對此，本研究提出一種局部更新和全局更新信息素結合的方法，其思路是:

對于第k 只螞蟻，它每經過一條路徑ij，設經過該路徑的時間為n，則在時刻t + n，該路徑上的信息素會用式(4)進行更新.

式中，ρ 為信息素揮發因子;τij(0)為信息素初始值.當螞蟻k 經過(i，j)時，式(4)就會減小該路徑上的信息素，降低其他螞蟻選中該路徑的概率，增加探索其他邊的機會.相較于基本蟻群算法，此改進可以避免因某一路徑信息素累計量過大而導致算法停滯.

同時，每次迭代結束以后，對于當前最優路徑上的信息素用式(5)進行全局動態更新，

中華民族五千年的發展和奮斗史使我們清楚的明白，一個民族的物質財富只是民族財富的外在形式，而真正起決定作用、內在的財富是這個民族的文化，它發揮著巨大的精神作用。文化強則國強，精神富則國富。引進劇是外來文化中獨樹一幟的新生力量，是我們接收外來文化的一種新的發展趨勢，我們應該認真對待，使引進劇在馬克思主義哲學的事業下符合21世紀的東方與西方文化建設的方向，在物質生活飛速發展的形勢下增強人民精神世界的獲得感、幸福感和滿足感。

式中，Δτij(t)為全局更新信息素增量，LNC為當前迭代即第NC 次迭代的最優路徑長度，Lbest為當前最優路徑長度.

此改進有利于螞蟻根據當前最優路徑動態地調整信息素，隨著迭代進行，有更優路徑出現后，LNC和Lbest的差值會逐漸減小.相應地，信息素增量減小直至0，此時，當前最優路徑上只進行信息素蒸發.與基本蟻群算法相比，這樣能使當前最優路徑上的信息素濃度更為突出，但又不至于造成算法停滯，使當前最優路徑的變化更快地反映在信息素分布上.

2.2 分段調整信息素揮發因子

蟻群算法中，信息素揮發因子ρ 的大小直接關系到算法的全局搜索能力和收斂速度，基本蟻群算法中的ρ 是(0，1)區間的某個固定值.當ρ 過小時，已經被搜索過的路徑被再次選擇的可能性過大，容易出現局部收斂;反之，當ρ 過大時，雖然可以提高算法的隨機性能和全局搜索能力，但又會使算法的收斂速度降低［6］.對此，本研究提出一種分段調整信息素揮發因子的方法，即隨著迭代次數的增加，將算法分為初期、中期和后期.在算法初期，將ρ 設置為較大的值，這樣可以使算法的全局搜索能力增強，在中期和后期適當減小ρ 的值，使得算法可以較快地收斂到最優解.這樣既增加了算法的全局搜索能力，又可以在一定程度上加快算法的收斂.具體規則為，

其中，NC 表示算法的迭代次數，NC－max 表示最大迭代次數.

在整個迭代過程的前四分之一，將ρ 取值為最接近1 的值0.9，可以在初始階段提高算法的全局搜索能力;然后，將ρ 設置為中間數值0.5，使算法既不至于陷入局部收斂，又能加快收斂速度;到了迭代過程的后四分之一，將ρ 值取為0.1，因為此時的搜索結果已經基本確定，適時可以加快算法的收斂速度.

2.3 算法實現

根據以上的改進思路，改進后的算法實現的具體步驟為:

1)參數初始化α，β，Q，NC－max，m，令迭代計數器NC = 1.

2)隨機選擇每只螞蟻的初始位置，初始化禁忌表tk，按照式(6)設置ρ 的值.

3)按照式(1)選擇路徑，將所選城市添加到tk中，并按照式(4)更新局部信息素.

4)若tk未滿則轉至步驟3)，若已滿，得出螞蟻此次的最優路徑長度LNC，并更新Lbest的值.

5)對當前的最優路徑按照式(5)更新全局信息素，清空tk.

6)若NC ＜NC－max，則NC = NC +1，并轉至步驟2)，開始新一次的迭代，否則算法結束，輸出最優路徑長度Lbest.

3 仿真實驗及結果分析

在仿真實驗中，選用TSP LIB 中的Oliver 30 和att 48 作為仿真算例，以驗證本研究提出的改進算法性能，并與基本蟻群算法求解Oliver30 TSP 和att48 TSP 進行比較.

基本蟻群算法采用的參數為:α = 1，β = 2，ρ =0.5，Q = 100，NC－max = 200，m = 30［7］;本研究提出的改進算法的參數為:α = 1，β = 2，Q = 100，NCmax = 200，m = 30.對2 種算法分別測試20 次，其結果如表1、2 所示.

表1 對Oliver30 TSP 測試20 次的結果

表2 對att48 TSP 測試20 次的結果

從表1、2 可以看出，經過20 次的測試，采用本基本蟻群算法改進的算法求解Oliver 30 和att 48 所得最優值、最差值和平均值與基本蟻群算法相比均有所改善.

另外，在收斂速度上，本研究算法在150 代以內幾乎可收斂到最優值，但基本蟻群算法在180 代到200 代依然存在多次尚未收斂的情況.2 種算法的最短距離及收斂情況如圖1、2、3、4 所示.圖1 和圖2分別是基本蟻群算法測試att48 TSP 問題的某一次最短距離和收斂情況.

圖1 基本蟻群算法測試att48 TSP 問題的最短距離

圖2 基本蟻群算法測試att48 TSP 問題的收斂情況

圖3 和圖4 分別是改進算法測試att48 TSP 問題的某一次最短距離和收斂情況.

圖3 改進算法測試att48 TSP 問題的最短距離

圖4 改進算法測試att48 TSP 問題的收斂情況

由實驗結果可見，隨機選擇的某一次實驗結果中，基本蟻群算法測試att 48 的最短距離是35 701.8073 km，收斂速度較慢，在迭代180 次之后仍未收斂;改進算法測試att 48 的最短距離是34 751.3419 km，收斂速度明顯提升，在迭代150 次左右達到最優.此表明，在求解Oliver 30 和att 48 問題上，本改進算法在求最優解和收斂速度上有明顯優勢.

4 結 語

本研究通過引入信息素局部更新和全局更新相結合，以及分段式更新信息素揮發因子的方法，對基本蟻群算法進行了改進，達到了擴大解的搜索空間、兼顧搜索速度和搜索能力的目的.改進算法的性能在Oliver 30 和att48 問題上已經得到驗證，但對于更大規模的數據，改進的算法是否能夠使用還有待于進一步的研究.

［1］王運濤，姚礪，毛力.基于混合行為的自適應蟻群算法［J］.計算機仿真，2009，26(12):151－153.

［2］段海濱，王道波，于秀芬.蟻群算法的研究現狀及其展望［J］.中國工程科學，2007，9(2):98－102.

［3］方霞，席金菊.基于變異和啟發式選擇的蟻群優化算法［J］.計算機工程與應用，2013，49(24):24－27.

［4］李成兵，郭瑞雪，李敏.改進蟻群算法在旅行商問題中的應用［J］.計算機應用，2014，34(S1):131－132，165.

［5］王沛棟.改進蟻群算法及在路徑規劃問題的應用研究［D］.青島:中國海洋大學，2012.

［6］趙偉，蔡興盛，曲慧雁.一種基于懲罰函數和新信息素更新方式的蟻群算法［J］.計算機工程與科學，2013，35(3):103－107.

［7］葉仕通，萬智萍.一種基于改進全局信息素更新效率的蟻群算法及仿真［J］.計算機應用與軟件，2014，31(1):176－179.