一種基于啟發式演化算法的最優-最差螞蟻系統

李康順 ，徐福梅，張文生，湯銘端

(1. 江西理工大學 信息工程學院，江西 贛州，341000；2. 華南農業大學 信息學院，廣東 廣州，510642；3. 中國科學院 自動化研究所，北京，100190；4. 航天科工集團 第二研究院，北京，100854)

蟻群算法最初是由意大利學者Dorigo等[1-3]提出，它是一種模擬昆蟲王國中螞蟻群體智能行為的仿生優化算法，具有較強的魯棒性、優良的分布式計算機制、易于與其他方法相結合等優點。這種作為一種近年提出的新型優化算法，還沒有像遺傳算法、模擬退火算法等那樣形成系統的分析方法和堅實的數學基礎，許多問題如算法搜索時間較長、在運行過程中容易出現收斂過早或停滯現象、不能擴大解的搜索范圍等[4-8]有待解決。針對這些缺陷，近年來國內外學者對蟻群算法提出大量的改進方法[9-13]，如Dorigo提出的Ant colony system (ACS)[1-2]，由 Stutzle和 Hoos提出的Max-min ant system(MMAS)[3]以及李士勇等[4]提出的最優-最差螞蟻系統Best-worst ant system(BWAS)，這些改進算法對提高螞蟻系統(AS)的計算性能起到一定的促進作用。目前，人們對蟻群算法的研究已經由最初單一的旅行商問題(TSP)領域滲透到了多個應用領域，由解決一維靜態優化問題發展到解決多維動態組合優化問題。對這種算法的研究結果表明，它具有廣闊的發展前景和實用價值[14-15]。在此，本文作者在最優-最差螞蟻系統的基礎上提出一種基于啟發式演化算法的最優-最差螞蟻系統。

1 旅行商問題(TSP)

旅行商問題(TSP)就是指給定 n個城市和兩兩城市之間的距離，要求確定1條經過各城市當且僅當1次的最短路線。其圖論描述為：給定圖G=(V, A)，其中V為頂點集，A為各頂點相互連接組成的邊集，已知各頂點間的邊接距離，要求確定 1條長度最短的Hamilton回路，即遍歷所有頂點當且僅當1次的最短回路。

TSP是典型的易于描述卻難以大規模處理的NP-hard問題，研究如何有效地解決TSP具有重要的理論意義和應用價值。研究TSP的方法有很多，如窮舉搜索法、貪婪法、神經網絡算法和遺傳算法等，它們都存在求解效率低、搜索時間長，不能利用反饋信息等缺點。蟻群算法是最早應用到求解TSP的一種方法，具有分布計算、信息正反饋和啟發式搜索的特征，是進化算法中一種新型的啟發式優化算法。但是，它同樣存在一些缺點，如算法搜索時間較長、運行過程中容易出現收斂過早或停滯現象、不能擴大解的搜索范圍等。受演化算法的啟發，在最優-最差螞蟻系統的基礎上，本文作者提出一種基于啟發式演化算法的最優-最差螞蟻系統(IEABWAS)來求解復雜TSP的算法，一方面，在該算法中加入啟發式演化算子，在每次迭代中將最優螞蟻與次優螞蟻執行啟發式交叉操作，并將這種使用啟發式演化操作產生的更優個體替代系統中的最差螞蟻，以達到快速收斂的目的；另一方面，將最優-最差螞蟻的更新方式進行適應性調整，使搜索更加集中于最優解附近，從而提高算法的全局搜索能力。

2 蟻群算法

設有n個城市組成的集合C[6]，螞蟻數目為m，用di,j(i, j=1, 2, …, n)表示城市i和城市j之間的距離，τij表示在t時刻城市i和城市j之間的路徑上的殘留信息素強度，以此來模擬實際螞蟻的分泌物。螞蟻 k(k=1, 2, …, m)在運動過程中，根據各條路徑上的信息量決定其轉移方向，同時用禁忌表tabuk(k=1, 2, …, n)來記錄螞蟻k當前所走過的城市，集合隨著tabuk進化過程進行動態調整。在搜索過程中，螞蟻根據各條路徑上的信息量及路徑的啟發信息來計算狀態轉移概率。P表示在t時刻螞蟻k由城市i轉移到城市j的狀態轉移概率，其表達式為：

式中：allowedk={C-tabuk}，表示螞蟻k下一步允許選擇的城市；α表示信息啟發式因子，表示軌跡的相對重要性，反映螞蟻在運動過程中所積累的信息在螞蟻運動時所起的作用，其值越大，則該螞蟻越傾向于選擇其他螞蟻經過的路徑，螞蟻之間的協作性越強；β為期望啟發式因子，表示能見度的相對重要性，反映螞蟻在運動過程中啟發信息在螞蟻選擇路徑中的受重視程度，其值越大，則該狀態轉移概率越符合貪心規則；ηij(t )為啟發函數，其表達式為：

為了避免殘留信息素過多導致殘留信息淹沒啟發信息，在每只螞蟻走完1步或者完成對所有n個城市的遍歷后，要對殘留信息進行局部更新處理。由此，在t+n時刻，在城市i和j之間的路徑上的信息量可按如下規則進行調整：

式中：ρ∈(0,1)表示信息素含量τil( t )隨時間的推移而衰減的程度；(t)表示本次循環中城市i和j之間路徑上的信息素增量，初始時刻 Δ τ(0 )=0，(t)是

ij螞蟻k在本次循環中在城市i和城市j之間路徑上留下的信息素。

所有螞蟻走完全部城市以后，僅對最優路徑上的信息素按式(3)進行更新。信息素全局更新公式為：

其中：Lb為本次循環中最優路徑的長度。

根據信息素更新策略的不同，Dorigo等[1-2]給出3種不同的基本蟻群算法模型，分別稱為蟻周系統(Ant-cycle system)、蟻量系統(Ant-quantity system)和蟻密系統(Ant-density system)，計算公式分別見式(4)～(6)。

在蟻周系統(Ant-cycle system)中，

式中：Q為常數，表示每只螞蟻周游1遍留下的信息總量；Lk為螞蟻k在本次循環中所走路徑的長度；

在蟻量系統(Ant-quantity system)中，

在蟻密系統(Ant-density system)中，

蟻密和蟻量系統利用的是局部信息，即螞蟻完成1步更新路徑上的信息素，而蟻周系統用的是整體信息，即螞蟻完成1個循環后更新所有路徑上的信息素，在求解TSP中，蟻周系統的性能較好。因此，通常采用蟻周系統作為蟻群算法的基本模型。

3 傳統的最優-最差螞蟻系統

3.1 最優-最差螞蟻系統概念

最優-最差螞蟻系統[6]在蟻群算法的基礎上進一步增強搜索過程的指導性，使得螞蟻的搜索更集中于到當前循環為止所找出的最優路徑的領域內。蟻群算法的任務就是引導問題的解向著全局最優的方向不斷進化。這種引導機制建立的基礎是解決方案越好，越可能在它的附近找出更優的解。因此，將搜索集中于所找出的最優解附近是合理的。算法的思想就是對最優解進行更大限度的增強，而對最差解進行削弱，使得屬于最優路徑的邊與屬于最差路徑的邊之間的信息素量差異進一步增大，從而使得螞蟻的搜索更集中于最優解附近。該算法主要修改蟻群系統中的全局更新公式。當所有的螞蟻完成1次循環后，增大對最差螞蟻路徑的信息素更新。若(i,j)為最差螞蟻路徑中的 1條邊，且不是最優螞蟻路徑中的邊，則該邊上的信息素按下式更新：

其中：ε為引入的參數；Lworst為當前循環中最差螞蟻中路徑長度；Lbest為當前循環中最優螞蟻的路徑長度；為城市i和城市j之間的信息素軌跡量。

3.2 傳統最優-最差螞蟻系統的不足

傳統最優-最差螞蟻系統對最差螞蟻所執行的全局更新可以改善算法的性能，從而使得最優-最差螞蟻系統的收斂速度比蟻群系統的快，但其存在一定的不足：首先，由于各路徑上的初始信息素相同，螞蟻創建的第1條路徑的引導信息主要是城市間的距離信息，這樣，螞蟻在所經過的路徑上所留下的信息素不一定能反映最優路徑的方向，特別是群體中個體數目較少或者所計算的路徑組合較多時，就更不能保證螞蟻創建的第1條路徑能引導蟻群走向全局最優解；其次，在初始階段，最差路徑中可能存在最優路徑中沒有搜索到較好的若干路段。若在初始階段就對最差螞蟻的路徑信息素進行削弱，將會影響搜索的全局性，阻礙螞蟻搜索到全局最優解。

4 基于啟發式演化算法的最優-最差螞蟻系統(IEABWAS)

為提高算法的全局搜索能力，加快最優解的收斂速度，在文獻[6, 8]的基礎上，針對以上傳統最優-最差螞蟻系統算法的不足，提出以下改進措施。

(1) 采用在每次循環后加入一種啟發式交叉算子的方式[8]。這種方式不只是單純地進行隨機交叉，而是綜合父代基因，再根據各個城市之間的連接關系的一種啟發式交叉方式。將最優路徑和次優路徑進行交叉，通過這種交叉得到的子代有效地繼承父代較好的基因，從而有利于發現最優解，加快算法的收斂速度。

(2) 在螞蟻運行的初始階段，不對最差螞蟻信息素進行削弱，而是在螞蟻運行若干代以及大致確定進化方向之后，再對最差螞蟻的信息素進行更新，從而削弱最差路徑上的信息量。

將以上2種措施相結合，對最差螞蟻信息素實施調整，使得搜索更集中于最優解附近，并通過加入啟發式演化交叉算子得到可行解，有效地繼承父代優秀的基因，更進一步加強在最優解附近的搜索能力，達到最終加快收斂速度、盡快找到全局最優解的目的。

在最優-最差螞蟻系統的基礎上，對最差螞蟻實施的信息素更新方式作適應性調整，并且在算法中加入一種啟發式交叉算子。這種改進后的新算法不但加快算法的收斂速度，而且增強尋找全局最優解的能力。

4.1 IEABWAS信息素更新

在算法的初始階段執行蟻群算法，對每次循環后的最差螞蟻不更新信息素。當算法運行到一定代時，方向已基本確定(取最大循環代數的 1/4，此時進化方向已經大致確定)，路徑圖中各條邊上的信息素基本與距離成正比。將最差螞蟻按公式(7)進行信息素更新，削弱最差路徑中的信息量，使得螞蟻更傾向于選擇最優路徑附近的邊，從而快速地搜索到最優解。

4.2 IEABWAS啟發式交叉算子

在演化計算中，常見的交叉算子有部分匹配交叉算子PMX、順序交叉算子OX、循環交叉算子CX等。這些交叉算子帶有很大的隨機性，不能很好地利用父個體的優良性能，最終不能提高尋優的速度。因此，本文作者采用一種啟發式交叉算子。該交叉算子考慮城市之間的連接關系并很好地繼承父代的優秀基因，從而提高尋優的速度，加快收斂到全局最優解[8]。交叉方式如下：

隨機選擇2個父代個體X=( x1, x2, …, xn)，Y=(y1,y2, …, yn)，將編碼串看作一個環行回路[12]。通過啟發式交叉算子產生子代child的過程為：

(1) 隨機選定1個城市xi作為交叉的起點，將xi加入到子代child中。

(2) 記當前城市c為xi，分別找到X和Y中城市xi的下1個城市 xi+1和 yj+1，如果 xi+1和 yj+1均不在子代中，并且有d(xi, xi+1)≤d(yi, yi+1)，就將xi+1加入到child中，記當前城市c為xi+1，否則，將yi+1加入到child中，并記當前城市c為yi+1。

(3) 若xi+1已經在子代中，而yj+1不在子代中，則將yj+1作為當前城市并加入到子代中；若yi+1已經在子代中，而xj+1不在子代中，則將xj+1作為當前城市并加入到子代中；若xi+1和yj+1均在子代中，則比較d(xi, xi+2)和 d(yi, yi+2)。

(4) 重復執行步驟(2)，直到完整地生成子代為止。

這種交叉方式得到的子代是可行的，雖然不能保證得到的子代一定比父代優，但在很大程度上繼承了父代優秀的基因，達到交叉的目地。實驗表明：此交叉方式對小規模的TSP求得最優解的效果最明顯，而且能顯著提高收斂速度。對于大規模的TSP，此交叉算子也能很快地找到近似最優解，并且解的質量較好。該交叉方式同樣適用于其他演化算法。

4.3 IEABWAS算法的實現步驟

根據以上分析，改進的基于啟發式演化交叉算子的最優-最差螞蟻系統算法的實現步驟如下。

(1) 參數初始化。令時間t=0和循環次數Nc=0，設置最大循環次數Nmax，將m只螞蟻置于n個城市上，令每條邊上的初始信息量τil(t)=const(其中，const為常數)，且初始時刻

(2) 對每只螞蟻隨機選擇1個初始位置；

(3) 按式(1)計算尚未走過的城市轉移概率，采用輪盤賭方式選擇策略為每只螞蟻選擇下1個要轉移的位置，按式(2)執行局部信息素更新；

(4) 重復步驟(2)，直到所有螞蟻都完成1次遍歷為止；

(5) 計算每只螞蟻的路徑長度并排序，分別找到最優、次優和最差螞蟻并記錄；

(6) 對最優螞蟻按式(3)執行全局信息素更新規則，若算法運行到最大循環代數的1/4，則對最差螞蟻按式(7)執行信息素更新規則，否則，不執行信息素更新；

(7) 將最優螞蟻和次優螞蟻路徑執行啟發式演化交叉得到另一條新路徑，并對所有螞蟻重新排序，將最差螞蟻排除；

(8) 記錄到目前為止最短的路徑，若 Nc＜Nmax，則清空禁忌表繼續下1輪循環，否則，輸出最優路徑。

表1 不同算法的實驗結果對比Table 1 Comparison results of different algorithms

5 數據仿真實驗

為驗證改進的IEABWAS算法對全局最優解的搜索能力和收斂速度，選用國際通用的 TSP測試庫TSPLIB中的Oliver30，Att48，Eil51和Eil75這4個實例，用 VC++對不同的算法進行編程實現，分別進行測試比較。

實驗中設置的參數分別為：螞蟻數目與城市數目相同，最大循環代數為3 000次，啟發因子α=1，期望因子β=5，信息素揮發度ρ=0.7，最差螞蟻更新參數ε=10，總信息量 Q=100。對各個實例分別運行 20次，測試結果如表1所示，其中ACS算法實驗數據來源于文獻[2]，BWAS算法實驗數據來源于文獻[4]。運用 IEABWAS算法，得到 Oliver30，Att48，Eil51和Eil75這4個實例的最優路徑分別如圖1～4所示。

從表1可以看出，IEABWAS算法無論是在解的質量上還是在求解的速度上，都明顯優于傳統蟻群(ACS)算法和最優-最差螞蟻系統(BWAS)算法，表明改進算法具有更強的全局搜索最優解的能力，而且在收斂速度上也有較大的提高，算法的性能得到提高。

圖1 Olive30的最優路徑示意圖Fig.1 Optimal path sketch map of Olive 30

圖2 Att48的最優路徑示意圖Fig.2 Optimal path sketch map of Att48

圖3 Eil51的最優路徑示意圖Fig.3 Optimal path sketch map of Eil51

圖4 Eil75的最優路徑示意圖Fig.4 Optimal path sketch map of Eil75

6 結論

(1) 提出一種基于啟發式演化算法的最優-最差螞蟻系統(IEABWAS)算法。與傳統的最優-最差螞蟻系統算法相比，IEABWAS算法的性能得到明顯改善，并具有更強的全局搜索能力和較快的收斂速度。

(2) 算法自適應地對最差螞蟻實施信息素調整，以削弱最差解，使搜索更集中于較優解附近，從而有效地引導了螞蟻的路徑，提高了算法的全局搜索能力。

(3) 算法在迭代過程中加入啟發式演化交叉算子，將這種交叉算子得到的較優解來替代較差解，從而進一步加強了對最優解附近的搜索能力。

[1] Dorigo M, Maniezzo V, Colorni A. The ant system: Optimization by a colony of cooperating agents[J]. IEEE Transaction on Systems, Man, and Cybernetic-Part B, 1996, 26(1): 29-41.

[2] Dorigo M, Gambardella L M. Ant colonies for the traveling salesman problem[J]. BioSystems, 1997, 43(2): 73-81.

[3] Stutzle T, Hoos H. Max-min ant systems[J]. Future Generation Computer Systems, 2000, 16(8): 889-914.

[4] 李士勇, 陳永強, 李研. 蟻群算法及其應用[M]. 哈爾濱: 哈爾濱工業大學出版社, 2004.LI Shi-yong, CHEN Yong-qiang, LI Yan. Ant colony algorithm and its application[M]. Harbin: Harbin Industry University Press,2004.

[5] 吳啟迪. 智能蟻群算法及應用[M]. 上海: 上海科技教育出版社, 2004.WU Qi-di. Intelligent ant colony algorithms with applications[M]. Shanghai: Shanghai Technical Education Press, 2004.

[6] 段海濱. 蟻群算法原理及應用[M]. 北京: 北京科學出版社,2005.DUAN Hai-bin. Ant colony algorithms principle and applications[M]. Beijing: Beijing Science Press, 2005.

[7] 潘正君, 康立山, 陳毓屏. 演化計算[M]. 北京: 清華大學出版社, 1998.PAN Zheng-jun, KANG Li-shan, CHEN Yu-ping. Evolutionary computation[M]. Beijing: Tsinghua University Press, 1998.

[8] 劉海, 郝志峰. 改進遺傳交叉算子求解 TSP問題[J]. 華南理工大學學報, 2002, 30(12): 71-73.LIU Hai, HAO Zhi-feng. Improving genetic cross operator to solve TSP problem[J]. Journal of Huanan University of Science and Technology, 2002, 30(12): 71-73.

[9] 劉立東, 蔡淮. 融入遺傳算法的混和蟻群算法[J]. 計算機工程與設計, 2008, 29(5): 1248-1250.LIU Li-dong, CAI Huai. Novel hybrid algorithm of combination of genetic algorithm and ant colony algorithm[J]. Computer Engineering and Design, 2008, 29(5): 1248-1250.

[10] 陳燁. 帶雜交算子的蟻群算法[J]. 計算機工程, 2001, 27(12):74-76.CHEN Ye. An ant colony algorithm with crossover operator[J].Computer Engineering, 2001, 27(12): 74-76.

[11] 吳慶洪, 張紀會, 徐心和. 具有變異特征的蟻群算法[J]. 計算機研究與發展, 1999, 36(10): 1240-1245.WU Qing-hong, ZHANG Ji-hui, XU Xin-he. An ant colony algorithm with mutate on features[J]. Journal of Computer Research and Development, 1999, 36(10): 1240-1245.

[12] 龔本燦, 李臘元. 基于信息素適量更新與變異的高效蟻群算法[J]. 計算機工程與應用, 2008, 44(1): 45-48.GONG Ben-can, LI La-yuan. Efficient ant colony algorithm based on right pheromone updating and mutation[J]. Computer Engineering and Technology, 2008, 44(1): 45-48.

[13] 孫力娟, 王良俊, 王汝傳. 改進的蟻群算法及其在 TSP中的應用研究[J]. 通信學報, 2004, 25(10): 111-116.SUN Li-juan, WANG Liang-jun, WANG Ru-chuan. Research of using an improved ant colony algorithm to solve TSP[J]. Journal of China Institute of Communication, 2004, 25(10): 111-116.

[14] 譚冠政, 李文斌. 基于蟻群算法的智能人工腿最優 PID 控制器設計[J]. 中南大學學報: 自然科學版, 2004, 35(1): 91-96.TAN Guan-zheng, LI Wen-bin. Design of ant algorithm based optimal PID controller and it s application to intelligent artificial leg[J]. Journal of Central South University: Science and Technology, 2004, 35(1): 91-96.

[15] TAN Guan-zheng, DOU Hong-quan. ACS algorithm-based adaptive fuzzy PID controller and its application to CIP-I intelligent leg[J]. Journal of Central South University of Technology, 2007, 14(4): 584-588.