基于混合行為的蟻群算法

陳孟濤，李志華，鄧躍設(shè)，楊 雪

（1.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院 輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 無錫214122；2.無錫曉山信息產(chǎn)業(yè)股份有限公司，江蘇 無錫214122）

0 引 言

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

1 蟻群算法簡介

1.1 基本蟻群算法及分析

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

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

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

式中：Q——常數(shù)，Lk——螞蟻k在本次循環(huán)中所走路徑的長度。

1.2 MMAS最大最小螞蟻算法

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

2 目前研究現(xiàn)狀

針對蟻群算法的特點(diǎn)，國內(nèi)外的許多研究者和研究機(jī)構(gòu)嘗試從許多方面對算法進(jìn)行研究。蟻群算法已成為國際智能計(jì)算領(lǐng)域關(guān)注熱點(diǎn)，在布魯塞爾每兩年都召開一次螞蟻優(yōu)化國際研討會(huì)。到目前為止已經(jīng)有諸多學(xué)者對蟻群算法提出了許多改進(jìn)之處，文獻(xiàn) ［6］通過種群信息熵動(dòng)態(tài)地調(diào)整選擇策略和信息素分布，提出基于信息熵調(diào)整的自適應(yīng)蟻群算法。文獻(xiàn) ［7］利用信息素記錄搜索過程中獲取的知識(shí)和免疫算子修復(fù)人工螞蟻構(gòu)建的候選解以提高候選解的質(zhì)量，提出基于免疫修復(fù)的快速蟻群優(yōu)化算法。針對蟻群算法存在慢收斂、容易停滯等問題，楊磊等提出一種基于精英策略的逆向蟻群優(yōu)化盲檢測算法［8］，通過逆向螞蟻加強(qiáng)正反饋?zhàn)饔锰岣吡怂惴ㄈ謱?yōu)能力。彭沛夫提出了基于遺傳因子的自適應(yīng)蟻群算法最優(yōu)PID控制［9］，利用現(xiàn)有的信息，通過融入遺傳算法的雜交、變異等方法盡可能地獲取質(zhì)量較高的最優(yōu)解。文獻(xiàn) ［10］根據(jù)期望程度和信息素動(dòng)態(tài)調(diào)整參數(shù)β，同時(shí)根據(jù)螞蟻?zhàn)哌^的路線長度動(dòng)態(tài)調(diào)整參數(shù)ρ提出了自適應(yīng)選擇各個(gè)參數(shù)的算法。同樣，文獻(xiàn)［11－15］也對基本蟻群算法進(jìn)行了改進(jìn)，算法的求解速度有所提高，但仍然有一些缺陷。

通過研究表明，信息素的濃度不僅對螞蟻選擇下個(gè)城市有導(dǎo)向的作用，而且還將會(huì)影響到算法的效率與運(yùn)行時(shí)間等性能。螞蟻在運(yùn)動(dòng)中信息素較大的路徑常常有更大的導(dǎo)向作用，但是當(dāng)同一條路徑被過多的螞蟻訪問時(shí)，該路徑的信息會(huì)不斷增大，從而使得過多的螞蟻集中到這條路徑，這樣就會(huì)出現(xiàn)阻塞狀態(tài)，蟻群算法就容易早熟和局部收斂。出現(xiàn)這種現(xiàn)象的原因是由于螞蟻的選擇策略造成的，因?yàn)樵诨鞠伻核惴ㄖ邢伻旱霓D(zhuǎn)移主要是依據(jù)信息素濃度和城市之間的距離，其中信息素濃度的多少會(huì)決定螞蟻的轉(zhuǎn)移方向。試假設(shè)，如果螞蟻在一輪循環(huán)中，選擇的下一個(gè)城市不是最優(yōu)的，螞蟻也會(huì)在當(dāng)前路徑上釋放一定數(shù)量的信息素，這樣，當(dāng)前螞蟻就會(huì)產(chǎn)生一條無用的循環(huán)路徑，而路徑上釋放信息素后就會(huì)對后面螞蟻的選擇策略產(chǎn)生影響。正確的選擇機(jī)制對尋找最優(yōu)路徑有重要的指導(dǎo)作用，在螞蟻轉(zhuǎn)移策略方面對算法進(jìn)行改進(jìn)，對信息素進(jìn)行限制，同時(shí)增加了全局調(diào)優(yōu)策略，提升了算法的性能。

3 改進(jìn)的蟻群算法

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

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

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

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

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

HBAC算法的描述如下：

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

（2）循環(huán)次數(shù)NC加1；

（3）將正常螞蟻和停止螞蟻隨機(jī)放在n個(gè)城市上，作為每只螞蟻各自的起點(diǎn)城市；

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

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

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

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

（7）直到螞蟻的個(gè)數(shù)循環(huán)到m時(shí)為止，對搜索到的最優(yōu)解進(jìn)行局部調(diào)整，將調(diào)優(yōu)后得到的最優(yōu)解與當(dāng)前全局最優(yōu)解進(jìn)行比較，若更優(yōu)，則更新當(dāng)前全局最優(yōu)解；

（8）將各個(gè)路徑上的信息量限制在 ［τmin，τmax］之間，自適應(yīng)調(diào)整τmax和τmin的值，按照式（5）對路徑的信息量進(jìn)行全局更新；

（9）若NC＜ NCmax，轉(zhuǎn)至（2）繼續(xù)；

（10）輸出到目前為止發(fā)現(xiàn)的最優(yōu)解和最優(yōu)路徑。

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

4 仿真實(shí)驗(yàn)及分析

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

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

圖1 Eil51取得最優(yōu)解的圖形

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

表1 Eil51問題結(jié)果的對比

改進(jìn)后算法在搜索能力和運(yùn)行的速度方面都有所改善，并且能夠同時(shí)兼顧二者。多次試驗(yàn)后發(fā)現(xiàn)，HBAC算法所取得最差解也要比MMAS算法的平均最優(yōu)解好，是因?yàn)樗惴ㄍㄟ^構(gòu)造局部最優(yōu)路線，避免產(chǎn)生無用路徑的結(jié)果，說明HBAC算法具有搜索最優(yōu)路徑的功能。另外，HBAC算法尋找最優(yōu)路徑的迭代次數(shù)也要比基本蟻群算法的迭代次數(shù)小，說明改進(jìn)后的算法在收斂速度上有了很大的提高。

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

表2是3個(gè)典型TSP問題平均最優(yōu)路徑對比結(jié)果，從表中可以看出，在解決Oliver30和Eil51的問題上，HBAC算法的平均路徑長度要比ACS算法和MMAS算法要短，主要是因?yàn)樵诟倪M(jìn)后的算法中引入了停止螞蟻，防止在周游的路徑上產(chǎn)生沒有用的信息素，對于后面螞蟻的行為產(chǎn)生誤導(dǎo)，同時(shí)螞蟻的信息素的范圍根據(jù)當(dāng)前最優(yōu)路徑動(dòng)態(tài)調(diào)整，避免信息素過大或者過小。但在較小規(guī)模Ulysses22的問題上，HBAC算法得到的平均路徑長度與經(jīng)典算法相差較小。是因?yàn)楫?dāng)問題規(guī)模較小時(shí)，螞蟻對路徑的誤判概率相對較小，停止螞蟻的作用相對較弱的緣故。

仿真實(shí)驗(yàn)表明，相對于其它參與比較的算法，HBAC算法的性能在多方面得到了較好地改進(jìn)。

圖2 Eil51問題平均值和最優(yōu)值的收斂曲線

表2 3個(gè)典型TSP問題實(shí)驗(yàn)結(jié)果的對比（表中顯示結(jié)果為平均路徑長度）

5 結(jié)束語

本文在分析現(xiàn)有的基本蟻群算法的基礎(chǔ)上，引入停止螞蟻概念和局部調(diào)優(yōu)策略，提出了一種基于混合行為的蟻群算法，通過構(gòu)造局部路線，防止無用路徑的產(chǎn)生，充分發(fā)揮信息素的作用，同時(shí)還根據(jù)最優(yōu)路徑動(dòng)態(tài)調(diào)整信息素范圍，避免了蟻群算法過早地陷于局部最優(yōu)的現(xiàn)象。在TSP問題的測試與實(shí)驗(yàn)結(jié)果證明了該算法的有效性和可行性。但實(shí)驗(yàn)中并未考慮規(guī)模較大的問題，這將是下一步的研究重點(diǎn)。

［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）.［倪慶劍，邢漢承，張志政，等.蟻群算法及其應(yīng)用研究進(jìn)展 ［J］.計(jì)算機(jī)應(yīng)用與軟件，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）.［段海濱，張祥銀，徐春芳.仿生智能計(jì)算 ［M］.北京：科學(xué)出版社，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）.［肖菁，李亮平.基于信息熵調(diào)整的自適應(yīng)蟻群算法 ［J］.計(jì)算機(jī)工程與設(shè)計(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）. ［閉應(yīng)洲，丁立新，陸建波.基于免疫修復(fù)的快速蟻群優(yōu)化算法 ［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）. ［楊磊，于舒娟.基于精英策略的逆向蟻群優(yōu)化盲檢測算法 ［J］.計(jì)算機(jī)技術(shù)與發(fā)展，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）.［彭沛夫，林亞平，胡斌，等.基于遺傳因子的自適應(yīng)蟻群算法最優(yōu)PID控制 ［J］.電子學(xué)報(bào)，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）.［羅中良，易明珠，劉小勇.最優(yōu)化問題的蟻群混合差分進(jìn)化算法研究 ［J］.中山大學(xué)學(xué)報(bào)，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）.［張志民，張小娟，李明華，等.一種引入獎(jiǎng)勵(lì)與懲罰機(jī)制的蟻群算法 ［J］.計(jì)算機(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）.［徐精明，曹先彬，王煦法.多態(tài)蟻群算法 ［J］.中國科學(xué)技術(shù)大學(xué)學(xué)報(bào)，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）.［李躍光，趙俊生，張遠(yuǎn)平.求解TSP的改進(jìn)量子蟻群算法 ［J］.計(jì)算機(jī)工程與設(shè)計(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）. ［鄭松，侯迪波，周澤魁.動(dòng)態(tài)調(diào)整選擇策略的改進(jìn)蟻群算法 ［J］.控制與決策，2008，23（2）：225－228.］