基于混合行為的蟻群算法

陳孟濤，李志華，鄧躍設，楊 雪

（1.江南大學 物聯網工程學院 輕工過程先進控制教育部重點實驗室，江蘇 無錫214122；2.無錫曉山信息產業股份有限公司，江蘇 無錫214122）

0 引 言

群體智能是人工智能研究的一個熱點問題，蟻群算法就是利用群體智能解決組合優化問題的典型算法，由意大利學者M.Dorigo等人［1－2］首先提出的一種新的啟發式算法，主要是模擬了真實螞蟻相互協作找食物的過程。它在解決傳統算法無法解決的組合優化和NP等難題上能夠取得很好的效果，并且具有求解復雜問題的能力，在智能優化領域表現出強大的生命力。目前主要是運用在旅行商問題（TSP）、分配問題、Job－shop調度問題、車輛調度等問題求解，并迅速地推廣到其他應用領域，因此對它的研究不論是在理論上還是在實際應用中都具有十分重要的意義。蟻群算法的魯棒性較強、能進行分布式計算、同其他優化算法結合容易且算法并沒有復雜的數學操作對軟件和硬件要求不高等優點，但也存在搜索時間長且容易陷入局部最優解的問題［3］。Thomas Stutzle等學者提出的 MMAS算法［4］，其主要的基本思想是對路徑上的信息素進行限制，以克服算法早熟早收斂的問題。雖然算法在性能和求解速度有所提高，但仍然存在一些缺陷，比如容易出現停滯和過早陷入局部最優。針對蟻群算法存在的這些缺陷，本文在MMAS算法基礎上，提出了基于混合行為的蟻群（hybrid behavior ant colony，HBAC）算法，該算法具有較好的搜索能力和收斂速度，比較好地克服了上述缺陷。通過在TSP問題上進行測試，實驗結果表明該算法的求解性能有了較大的提高。

1 蟻群算法簡介

1.1 基本蟻群算法及分析

在搜尋食物的過程中，一種稱作信息素的物質會被螞蟻留在它所前行的路徑上，螞蟻不僅能夠準確地感知到信息素濃度的大小，而且能夠通過它指導自我的前行方向。路徑上的信息素濃度越高，該條路徑被螞蟻選擇的概率就會增大。螞蟻個體之所以能夠找到它們要吃的食物，主要是靠它們之間不斷相互協作的結果。

為了便于說明，將以TSP問題［5］說明基本蟻群算法的框架。設N＝｛1，2，3，…，n｝表示N個城市，dij（i，j＝0，1，2，…，N－1）表示城市間的歐式距離，螞蟻的數量用m表示，在t時刻兩個城市間的信息量用τij（t）來表示，可以很好地模擬螞蟻在路徑上的分泌物。用禁忌表tabuk（k＝1，2，…，n）記錄螞蟻k當前所走過的城市。螞蟻k在選擇下一步時，都要針對每條路徑上的信息素強度做一次判定，從而來決定所選擇的城市是否是最好的，在時刻t，螞蟻k所要選擇城市j的轉移概率用pkij表示，其式如下

式中：allowedk——下一步螞蟻k能夠選擇的城市；信息素啟發因子用α表示，其值越大，螞蟻越傾向于選擇其他螞蟻已經走過的路徑，但α值過大會使搜索過早陷于局部最優；β表示期望啟發式因子，值越大，概率選擇越接近于貪婪規則；ηij（t）為啟發函數，其表達式為ηij（t）＝1/dij。每只螞蟻在它所發現的路徑上按照式（2）進行信息素更新

式中：Q——常數，Lk——螞蟻k在本次循環中所走路徑的長度。

1.2 MMAS最大最小螞蟻算法

MMAS算法是從基本蟻群算法演變而來的，算法中最主要的改進是：首先在初始時刻將各個路徑的信息素初始化為τmax；其次在所有螞蟻完成一次周游之后，按照式（5）只對最優解的各路徑的信息素進行更新；最后將各路徑的信息素限制在 ［τmin，τmax］之間

2 目前研究現狀

針對蟻群算法的特點，國內外的許多研究者和研究機構嘗試從許多方面對算法進行研究。蟻群算法已成為國際智能計算領域關注熱點，在布魯塞爾每兩年都召開一次螞蟻優化國際研討會。到目前為止已經有諸多學者對蟻群算法提出了許多改進之處，文獻 ［6］通過種群信息熵動態地調整選擇策略和信息素分布，提出基于信息熵調整的自適應蟻群算法。文獻 ［7］利用信息素記錄搜索過程中獲取的知識和免疫算子修復人工螞蟻構建的候選解以提高候選解的質量，提出基于免疫修復的快速蟻群優化算法。針對蟻群算法存在慢收斂、容易停滯等問題，楊磊等提出一種基于精英策略的逆向蟻群優化盲檢測算法［8］，通過逆向螞蟻加強正反饋作用提高了算法全局尋優能力。彭沛夫提出了基于遺傳因子的自適應蟻群算法最優PID控制［9］，利用現有的信息，通過融入遺傳算法的雜交、變異等方法盡可能地獲取質量較高的最優解。文獻 ［10］根據期望程度和信息素動態調整參數β，同時根據螞蟻走過的路線長度動態調整參數ρ提出了自適應選擇各個參數的算法。同樣，文獻［11－15］也對基本蟻群算法進行了改進，算法的求解速度有所提高，但仍然有一些缺陷。

通過研究表明，信息素的濃度不僅對螞蟻選擇下個城市有導向的作用，而且還將會影響到算法的效率與運行時間等性能。螞蟻在運動中信息素較大的路徑常常有更大的導向作用，但是當同一條路徑被過多的螞蟻訪問時，該路徑的信息會不斷增大，從而使得過多的螞蟻集中到這條路徑，這樣就會出現阻塞狀態，蟻群算法就容易早熟和局部收斂。出現這種現象的原因是由于螞蟻的選擇策略造成的，因為在基本蟻群算法中蟻群的轉移主要是依據信息素濃度和城市之間的距離，其中信息素濃度的多少會決定螞蟻的轉移方向。試假設，如果螞蟻在一輪循環中，選擇的下一個城市不是最優的，螞蟻也會在當前路徑上釋放一定數量的信息素，這樣，當前螞蟻就會產生一條無用的循環路徑，而路徑上釋放信息素后就會對后面螞蟻的選擇策略產生影響。正確的選擇機制對尋找最優路徑有重要的指導作用，在螞蟻轉移策略方面對算法進行改進，對信息素進行限制，同時增加了全局調優策略，提升了算法的性能。

3 改進的蟻群算法

本文在MMAS算法的基礎上，通過引入停止螞蟻，模擬螞蟻多態行為，采用構造局部最優路徑方式避免螞蟻選擇距離較遠的城市，防止產生無用的循環路徑。算法的主要改進思想是把螞蟻分為兩種狀態行為的螞蟻：正常螞蟻和停止螞蟻，正常螞蟻主要是用來尋找最優路徑，停止螞蟻主要是用來構造局部最優路徑，防止產生無用的循環路徑。停止螞蟻不能移動到離當前城市較遠距離的城市，這樣在每輪的循環中停止螞蟻有可能會沒有可以到達的城市，因而它就不能完成一次周游路徑，也就是說不能返回到它原先的出發點。停止螞蟻只可以選擇離當前城市距離最近的候選城市，當沒有候選城市時，停止螞蟻就會處于停止狀態，它就不能完成周游，這樣停止螞蟻就不會在較長的路徑上產生信息素，不會對以后螞蟻的行為產生負面的影響，防止產生無效的信息素。停止螞蟻和正常螞蟻數量的選擇應按照一定的比例，如果正常螞蟻的數量過少，螞蟻的尋優路徑就會減弱，因此停止螞蟻的數量應限定在合適的范圍之內。

在所有的螞蟻完成一次迭代之后所尋找的最好路徑有可能不是最優的，為了提高算法盡快地找到最優解的速度，引入全局調優策略，以保證在改進后的算法找到最優解。具體的方法是在每次迭代之后所找到的最優路徑中，隨機的選取兩條邊進行互換，如果調整后的路徑比當前的路徑好，就更新當前最優路徑，全局調優策略用偽代碼描述如下：

停止螞蟻采用式（6）選擇下一個城市

式（6）中部分參數的含義同式（1）所述。其中，K’表示停止螞蟻，停止螞蟻離當前城市最大訪問距離設為d。信息素更新的規則見式（7），當停止螞蟻不能訪問所有的城市時，信息素就用式（8）的權重q（c）進行度量。為了防止每條路徑的信息量過大或者過小，路徑的信息素限定在［τmin，τmax］之間，在這里根據當前最優路徑動態調整τmax和τmin，在一定程度上能很好避免局部停滯現象的發生，其自適應調整公式如式（10）和式（11）

式中：q（c）——信息素權重函數，m’——停止螞蟻的數量，Lk′——在每次周游中它所旅行的路徑長度，c——停止螞蟻未訪問城市的數量

HBAC算法的描述如下：

（1）參數初始化α，β，ρ，τij（0）＝τmax（常數），螞蟻總數m，m’，NC，NCmax（最大迭代次數）；

（2）循環次數NC加1；

（3）將正常螞蟻和停止螞蟻隨機放在n個城市上，作為每只螞蟻各自的起點城市；

（4）如果是正常螞蟻，以式（1）計算概率選擇

下一個城市j1，其中j1∈ ｛1，2，…，n｝－tabuk，將j1置于tabuk中；

（5）如果是停止螞蟻，將螞蟻所能到達離當前城市的最遠距離設為d，則按照式（6）計算的概率選擇下一個城市j2，其中j2∈ ｛1，2，…，n｝－tabuk，將j2置于tabuk中，按照式（7）更新路徑的信息素；

（6）禁忌表未滿則轉至（4），禁忌表滿時，得出螞蟻此次的一次遍歷距離，并把禁忌表tabuk清空；

（7）直到螞蟻的個數循環到m時為止，對搜索到的最優解進行局部調整，將調優后得到的最優解與當前全局最優解進行比較，若更優，則更新當前全局最優解；

（8）將各個路徑上的信息量限制在 ［τmin，τmax］之間，自適應調整τmax和τmin的值，按照式（5）對路徑的信息量進行全局更新；

（9）若NC＜ NCmax，轉至（2）繼續；

（10）輸出到目前為止發現的最優解和最優路徑。

由于在HBAC算法中正常螞蟻和停止螞蟻是分布式計算，它們的螞蟻數之和為m，在算法中同樣是m只螞蟻遍歷n個城市，而經過的循環次數為NC，所以HBAC算法與基本蟻群算法具有相同的時間復雜度O（m＊n2＊NC）。

4 仿真實驗及分析

為了驗證本文算法的有效性，將其應用到TSP問題上，測試用例選用測試庫TSPLIB中Ulysses22，Oliver30和Eil51這3個典型的問題，在matlab7.0上分別進行仿真實驗，并用HBAC算法與基本的蟻群算法，MMAS算法的實驗結果進行對比。

實驗參數的設置：α＝1.0，β＝2.0，揮發系數ρ＝0.98，最大迭代次數NCmax＝2000，m’＝5，初始化信息素τmax＝1，正常螞蟻的數量和停止螞蟻的數量的總和等于整個城市的數目n，停止螞蟻距離d的取值為0.25＊Dmax，其中Dmax表示兩個城市之間的最大距離。按上述參數的配置，在規定的迭代次數內進行30次實驗，實驗結果取平均值。圖1是HBAC算法在解決Eil51問題所獲得的最優解。

圖1 Eil51取得最優解的圖形

表1在Eil51問題上各種算法的結果對照表，可以看出HBAC要明顯優于ACS和MMAS蟻群算法，其主要表現在收斂的速度和最優解路徑上。表1中HBAC算法的最優值代數和最優值要好于蟻群算法。

表1 Eil51問題結果的對比

改進后算法在搜索能力和運行的速度方面都有所改善，并且能夠同時兼顧二者。多次試驗后發現，HBAC算法所取得最差解也要比MMAS算法的平均最優解好，是因為算法通過構造局部最優路線，避免產生無用路徑的結果，說明HBAC算法具有搜索最優路徑的功能。另外，HBAC算法尋找最優路徑的迭代次數也要比基本蟻群算法的迭代次數小，說明改進后的算法在收斂速度上有了很大的提高。

圖2表示HBAC算法求解Eil51問題時解的平均值和最優值的收斂進化曲線，從圖中可以明顯地看出，在每次迭代中的最優路徑的波動范圍都較小，一直處于較平穩的狀態，并且能夠在相對最短的時間內找到最優值，平均值與最優值的差異也很小。說明改進后的算法不僅在求解能力上具有優勢，而且在算法執行的效率上也有所提高。

表2是3個典型TSP問題平均最優路徑對比結果，從表中可以看出，在解決Oliver30和Eil51的問題上，HBAC算法的平均路徑長度要比ACS算法和MMAS算法要短，主要是因為在改進后的算法中引入了停止螞蟻，防止在周游的路徑上產生沒有用的信息素，對于后面螞蟻的行為產生誤導，同時螞蟻的信息素的范圍根據當前最優路徑動態調整，避免信息素過大或者過小。但在較小規模Ulysses22的問題上，HBAC算法得到的平均路徑長度與經典算法相差較小。是因為當問題規模較小時，螞蟻對路徑的誤判概率相對較小，停止螞蟻的作用相對較弱的緣故。

仿真實驗表明，相對于其它參與比較的算法，HBAC算法的性能在多方面得到了較好地改進。

圖2 Eil51問題平均值和最優值的收斂曲線

表2 3個典型TSP問題實驗結果的對比（表中顯示結果為平均路徑長度）

5 結束語

本文在分析現有的基本蟻群算法的基礎上，引入停止螞蟻概念和局部調優策略，提出了一種基于混合行為的蟻群算法，通過構造局部路線，防止無用路徑的產生，充分發揮信息素的作用，同時還根據最優路徑動態調整信息素范圍，避免了蟻群算法過早地陷于局部最優的現象。在TSP問題的測試與實驗結果證明了該算法的有效性和可行性。但實驗中并未考慮規模較大的問題，這將是下一步的研究重點。

［1］Colorni A，Dorigo M，Maniezzo V.Distributed optimization by ant colonies ［C］.Prceeding of the First European Conference on Artificial Life.Paris France：Elsevier Publishing，1991：134－142.

［2］Dorigo M，Maniezzo V，Colorni A.The ant system：Optimization by a colony of cooperating agents ［J］.IEEE Transaction on Systems Man and Cybernatic，1996，26（1）：29－41.

［3］NI Qinjian，XING Hancheng，ZHANG Zhizheng，et al.Ant colony algorithm and its applications：Review and PRoGRESS ［J］.Computer Applications and Software，2008，25（8）：12－16（in Chinese）.［倪慶劍，邢漢承，張志政，等.蟻群算法及其應用研究進展 ［J］.計算機應用與軟件，2008，25（8）：12－16.］

［4］Stutzle T，Hoos H.Max－min ant systems ［J］.Future Generation Computer Systems，2000，16（19）：889－914.

［5］DUAN Haibin，ZHANG Xiangyin，XU Chunfang.Bio－inspired computing ［M］.Beijing：Science Press，2011（in Chinese）.［段海濱，張祥銀，徐春芳.仿生智能計算 ［M］.北京：科學出版社，2011.］

［6］XIAO Jing，LI Liangping.Adaptive ant colony algorithm based on information entropy ［J］.Computer Engineering and Design，2010，31（22）：4873－4876（in Chinese）.［肖菁，李亮平.基于信息熵調整的自適應蟻群算法 ［J］.計算機工程與設計，2010，31（22）：4873－4876.］

［7］BI Yingzhou，DING Lixin，LU Jianbo.Fast ant colony optimization algorithm with immunity repairing ［J］.Control and Decision，2010，24（10）：1509－1512（in Chinese）. ［閉應洲，丁立新，陸建波.基于免疫修復的快速蟻群優化算法 ［J］.控制與決策.2010，24（10）：1509－1512.］

［8］YANG Lei，YU Shujuan.Blind detection based on a converse ant algorithm using elitist strategy ［J］.Computer Technology and Development，2010，20（12）：90－93（in Chinese）. ［楊磊，于舒娟.基于精英策略的逆向蟻群優化盲檢測算法 ［J］.計算機技術與發展，2010，20（12）：90－93.］

［9］PENG Peifu，LIN Yapin，HU Bin，et al.Optimal PID control of self－adapted ant colony algorithm based on genetic gene ［J］.Acta Electronica Sinica，2006，34（6）：1109－1113（in Chinese）.［彭沛夫，林亞平，胡斌，等.基于遺傳因子的自適應蟻群算法最優PID控制 ［J］.電子學報，2006，34（6）：1109－1113.］

［10］CAI Zhaoquan，HUANG Han.Ant colony optimization algorithm based on adaptive weight and volatility parameters ［C］.Shanghai：IEEE Press，2008：75－79.

［11］LUO Zhongliang，YI Mingzhu，LIU Xiaoyong.On ant colony hybird differential evolution for optimization problems ［J］.Acta Scientiarum Naturalium Universitatis Sumyatseni，2008，47（3）：33－35（in Chinese）.［羅中良，易明珠，劉小勇.最優化問題的蟻群混合差分進化算法研究 ［J］.中山大學學報，2008，47（3）：33－35.］

［12］ZHANG Zhimin，ZHANG Xiaojuan，LI Minghua，et al.Ant colony algorithm with strategy of award and penalty ［J］.Computer Simulation，2006，23（7）：161－163（in Chinese）.［張志民，張小娟，李明華，等.一種引入獎勵與懲罰機制的蟻群算法 ［J］.計算機仿真，2006，23（7）：161－163.］

［13］XU Jingming，CAO Xianbin，WANG Xufa.Polymorphic ant colony algorith ［J］.Journal of University of Science And Technology of China，2005，35（1）：59－65（in Chinese）.［徐精明，曹先彬，王煦法.多態蟻群算法 ［J］.中國科學技術大學學報，2005，35（1）：59－65.］

［14］LI Yueguang，ZHAO Junsheng，ZHANG Yuanping.Improved quantum ant colony algorithm for TSP ［J］.Computer Engineering and Design，2009，30（16）：3843－3845（in Chinese）.［李躍光，趙俊生，張遠平.求解TSP的改進量子蟻群算法 ［J］.計算機工程與設計，2009，30（16）：3843－3845.］

［15］ZHENG Song，HOU Dibo，ZHOU Zekui.Ant colony algorithm with dynamic transition probability ［J］.Control and Decision，2008，23（2）：225－228（in Chinese）. ［鄭松，侯迪波，周澤魁.動態調整選擇策略的改進蟻群算法 ［J］.控制與決策，2008，23（2）：225－228.］