(上海大學(xué) 機電工程與自動化學(xué)院，上海 201900)

蟻群算法是意大利學(xué)者Dorigo于1992年提出的一種群智能仿生算法[1]。該算法模擬蟻群覓食行為，蟻群會在覓食所經(jīng)過的路徑上留下一種名為信息素的化學(xué)物質(zhì)[2]。螞蟻之間靠感知信息素強度尋找最優(yōu)覓食路徑。蟻群算法具有高魯棒性、分布式計算、正反饋、易與其他算法融合的優(yōu)點[3]。而這些優(yōu)點可用于解決一系列NPC(Non-Deterministic Polynomial Complete)問題。目前，蟻群算法已被廣泛用于解決旅行商問題、指派問題、調(diào)度問題以及圖著色等問題[4]。但蟻群算法也存在著一些問題，如搜索時間較長、易陷入局部最優(yōu)、收斂速度過慢、易產(chǎn)生停滯現(xiàn)象[5]。針對這些不足，很多專家學(xué)者都提出了自己的改進方法。例如安葳鵬[11]通過引入最大代價與最小代價來優(yōu)化蟻群算法的信息素更新機制；方春城[12]將網(wǎng)格地圖模型與蟻群算法相結(jié)合來優(yōu)化機器人行走路徑。

蟻群算法的核心技術(shù)在于其信息素更新方式和狀態(tài)轉(zhuǎn)移概率選擇[6]。其中信息素矩陣的構(gòu)造尤為關(guān)鍵，信息素引導(dǎo)著螞蟻做各種路徑選擇，蟻群的狀態(tài)轉(zhuǎn)移也基于蟻群的信息素矩陣。因此對信息素矩陣的重新構(gòu)造便可提供一種改進的蟻群算法，比如ACS(Ant Colony System)算法[7]、MMAS(Max-Min Ant System)算法[8]、自適應(yīng)蟻群算法[9]、混合行為蟻群算法[10]。

為改善蟻群算法易陷入局部最優(yōu)的情況，本文引入擁擠度算子來增強蟻群之間的信息交流，改善信息素矩陣的分布，避免蟻群因局部信息素過大而過早陷入停滯狀態(tài)。同時通過全局信息素更新和局部信息素更新對信息素矩陣進行自適應(yīng)調(diào)整，提前預(yù)防早熟現(xiàn)象。在路徑調(diào)整過程中結(jié)合一項高效的變異操作，在增強全局搜索能力的同時又提高算法的收斂速度。

對于擁擠度概念，前人也有相關(guān)研究，王劍[13]將魚群算法的擁擠度因子引入蟻群算法，但其僅考慮了整體的擁擠情況，未考慮局部路徑情況，而本文將兩種情況都納入考慮范圍。而對于鄰域搜索概念，段海濱[14]將連續(xù)空間上的相鄰下一節(jié)點定義為鄰域。而本文中是將離散空間中以某一點為圓心的附近若干點劃分為鄰域,著重縮小搜索范圍，提高搜素效率。

1 傳統(tǒng)蟻群算法模型

本文以平面TSP(Traveling Salesman Problem，旅行商問題)為例求解基本蟻群算法模型。該模型采用全局信息素更新和局部信息素更新相結(jié)合的方法，信息素的揮發(fā)和釋放動作只對至今全局最優(yōu)螞蟻所走的路徑更新。螞蟻每選擇一條路徑，都通過局部信息素更新規(guī)則削弱該路徑上的一定量信息素，增加蟻群探索其他路徑的可能性。

1.1 狀態(tài)轉(zhuǎn)移規(guī)則

在蟻群系統(tǒng)中，m只螞蟻在n個城市中并行構(gòu)建TSP路徑。初始時刻，螞蟻被分別置于隨機選出的城市中，各城市之間每條路徑的信息素皆相等。在構(gòu)建路徑的過程中，蟻群采用一種偽隨機比例規(guī)則來確定螞蟻k下一步將要訪問的城市j。其過程為

(1)

(2)

采用這種偽隨機比例規(guī)則產(chǎn)生的城市，既可以保證螞蟻利用路徑的先驗知識選擇當(dāng)前最有可能的最優(yōu)解，又以一定的概率探索新的路徑。通過調(diào)整參數(shù)q0，可以調(diào)節(jié)算法對新路徑的探索概率，達到蟻群算法在探索新路徑和保持較優(yōu)路徑之間的平衡。

1.2 局部信息素更新

在每只螞蟻經(jīng)過一條路徑時，都將會對該路徑上的信息素進行局部更新，即

τij=(1-ζ)·τij+ζ·τ0，τ0∈(0,1)

(3)

式中，ζ為一固定參數(shù);τ0為初始信息素的值，一般取值為1/n·Lnn。其中，Lnn為由最近鄰域啟發(fā)式方法得到的路徑長度。通過局部信息素的更新，達到削弱該條路徑信息素的效果。使該條路徑信息素不會過大增長，從而保證了搜索其他路徑的可能，避免陷入局部最優(yōu)解。

1.3 全局信息素更新

在所有螞蟻都遍歷城市之后，開始進行全局信息素更新。全局信息素更新只對當(dāng)前最優(yōu)螞蟻所走的路徑作用。全局信息素更新公式為

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

(4)

式中，ρ為信息素揮發(fā)因子；Δτij是信息素增量，由螞蟻遍歷一周釋放的信息素與最優(yōu)路徑相除得到。

2 蟻群算法的改進

針對蟻群算法易陷入停滯的缺陷，本文提出一種基于擁擠度的動態(tài)信息素蟻群算法(Dynamic Pheromone Ant Colony System,DPACSC)，在蟻群釋放信息素的過程中實時監(jiān)測當(dāng)前路徑信息素含量和蟻群路徑的情況，為螞蟻提前做好分流準(zhǔn)備，增加螞蟻探索其他路徑的可能，提前做好主動防御工作。

2.1 擁擠度

在路徑選擇過程中，螞蟻會傾向于尋找信息素大的路徑，同時由于蟻群算法的正反饋機制，信息素大的路徑在搜尋過程中信息素的累積會越來越大，進而導(dǎo)致蟻群算法陷入局部最優(yōu)，直至停滯。為了增加蟻群算法路徑選擇的多樣性，提高蟻群算法全局搜索的能力，本文提出靜態(tài)擁擠與動態(tài)擁擠的概念。

定義1 靜態(tài)擁擠。設(shè)Pij是蟻群在某一輪循環(huán)后從i城市到j(luò)城市的路徑轉(zhuǎn)移概率。δ為接近于1的一個常數(shù)。當(dāng)Pij>δ時，則定義路徑i→j發(fā)生全局擁擠。

定義2 動態(tài)擁擠。設(shè)螞蟻的總數(shù)為m,螞蟻在時刻t時位于城市u，且在t+1時刻選擇到達城市v的螞蟻總數(shù)為k，則在時刻t，路徑u→v的動態(tài)擁擠度定義為

(5)

2.2 狀態(tài)轉(zhuǎn)移規(guī)則更新

為防止蟻群算法過早集中于某些路徑，增大蟻群全局搜索能力，結(jié)合擁擠度的概念，改進的狀態(tài)轉(zhuǎn)移規(guī)則算法為

(6)

(7)

在啟發(fā)式信息相對重要性系數(shù)β的基礎(chǔ)上增加擁擠度參數(shù)，由擁擠度參數(shù)來動態(tài)控制啟發(fā)式信息在路徑選擇中的重要性，當(dāng)該條路徑在某一時刻變得擁擠時，則相對降低它在候選路徑中的比例。

2.3 信息素更新方案

蟻群算法在構(gòu)建解的過程中，會產(chǎn)生很多無用解，具體表現(xiàn)為：① 產(chǎn)生許多重復(fù)解，一直在進行無用迭代；② 構(gòu)建許多明顯不是最優(yōu)解的路徑，例如將兩個相距很遠的城市作為螞蟻路徑上的相鄰解。針對問題①，引入擁擠度的概念，擴大螞蟻選擇路徑的可能性來降低蟻群的重復(fù)解。同時加入下文的變異操作尋找更優(yōu)異的解。針對問題②，提出“搜索域”概念，優(yōu)先將最靠近當(dāng)前城市的nk個城市置于“搜索域”中。但由于環(huán)境復(fù)雜性以及某些情況下最優(yōu)解不在當(dāng)前nk個城市中產(chǎn)生，造成漏解。因此設(shè)定如下“搜索域”方法。

假定在城市i處尋找下一城市j，首先尋找距離城市i最近的一處城市x，i→x的距離為dix，在此基礎(chǔ)上疊加一項Δd的參數(shù)，以(dix+Δd)為半徑，在此半徑范圍內(nèi)的城市則為允許搜索的城市，其余歸入禁忌表之中。

(8)

式中,allow為可搜索的城市集合；tabu為蟻群的禁忌表集合。在可選取的城市中采用偽隨機概率選擇公式和擁擠度結(jié)合的方法進行下一個城市選擇。

2.4 變異操作

蟻群算法搜索路徑的大部分操作都是對重復(fù)路徑的查找。為避免這種重復(fù)操作，當(dāng)路徑重復(fù)次數(shù)達到S次時，則表明當(dāng)前查找路徑陷入局部最優(yōu)解，開始進行兩元素優(yōu)化(2-opt)的變異操作[15]。在當(dāng)前最優(yōu)路徑的城市訪問順序中選取兩個城市進行互換。當(dāng)互換的城市并非相鄰順序的城市時，則將兩個城市之間的順序完全顛倒。例如，TSP城市集C={c1,c2,c3,…,cn}，假設(shè)其中有兩個城市節(jié)點i,j。交換節(jié)點i在j的前面，即順序T=v1→v2…vi-1→vi→vi+1…vj-1→vj→vj+1…vn→v1,當(dāng)進行交換順序時，將vi到vj之間的順序完全交換，即新的順序為T=v1→v2…vi-1→vj→vj-1…vi+1→vi→vj+1…vn→v1。這時檢驗交換后的路徑長度，若優(yōu)于原路徑長度，則替換原搜索順序。在搜索時從前往后依次進行檢驗。本文在此基礎(chǔ)上再次進行改良，針對2-opt算法的盲目實驗替換，結(jié)合本文“搜索域”方案，使交換的兩元素限定在一定區(qū)域內(nèi)，減少了實驗的操作步驟。經(jīng)過試驗，本方法可一定程度上加快實驗收斂速度，基本可保證在100次迭代左右便搜索到較好的路徑。

3 算法框架

基于擁擠度的動態(tài)信息素蟻群算法的步驟表述如下。

① 初始化參數(shù)α,β,q0,ζ,ρ,δ，螞蟻變量t=1,城市變量m=1,循環(huán)次數(shù)NC。

② 查看是否達到最大的循環(huán)次數(shù)NC，若是，則直接退出算法，若不是，則更新各條路徑信息素的值，保留各次最優(yōu)路徑。

③ 查看搜索相同路徑次數(shù)是否超過S，若是,則進行局部2-opt的路徑優(yōu)化，如發(fā)現(xiàn)更優(yōu)路徑，則用該路徑來替換搜索路徑。

④ 隨機分配螞蟻至各個城市，并將該城市計入禁忌表之中。

⑤ 判斷是否所有的螞蟻均已完成搜索，若是，則返回步驟②，否則從第t+1只螞蟻開始搜索路徑。

⑥ 判斷是否螞蟻已完成所有城市的訪問，若是，則返回步驟⑤，否則從第m+1個城市開始搜素路徑，并檢查搜索路徑概率是否大于δ。

⑦ 按“搜索域”大小搜索可訪問城市，并計算各條路徑上的擁擠度大小。

⑧ 按上述的狀態(tài)轉(zhuǎn)移規(guī)則選擇下一個城市的選取點，并將該點置入禁忌表中，返回步驟⑥。

⑨ 展示各條最優(yōu)路徑。

4 仿真實驗

為使算法更具說服力，選用國際上經(jīng)典的TSPLIB庫中的12個案例(Eil51、Berlin52、St70、KroA100等)作為標(biāo)準(zhǔn)實驗數(shù)據(jù)進行試驗。對參數(shù)的初始化固定如表1所示。其中，螞蟻數(shù)量設(shè)為城市數(shù)量的2/3， “搜索域”間距Δd設(shè)為初始間距dix的1/3。

利用Eclipse編寫程序驗證算法。表2為各TSP的官方數(shù)據(jù)。各問題求解結(jié)果如表3所示。圖1～圖8為所得路徑結(jié)果。

表1 各參數(shù)設(shè)置

表2 各TSP官方最好記錄

表3 典型TSP問題求解對比實例

SD:standard deviation

圖1 KroA100

圖2 St70

圖3 Berlin52

圖4 ch130

圖5 Eil101

圖6 KroA150

圖7 KroB150

圖8 TSP225

從表3可以看出，經(jīng)過改進的蟻群算法在驗證各個TSPLIB問題時，都可得到接近最優(yōu)解的路徑。從各算法性能比較(表5)中可以看出，有些結(jié)果要優(yōu)于文獻中的研究結(jié)果。標(biāo)準(zhǔn)偏差也在理想范圍之內(nèi)，說明在各個循環(huán)過程中，改進的蟻群算法可以得到較優(yōu)解。對比文獻中的結(jié)果，所提出的方法產(chǎn)生了較為理想的結(jié)果。其中，對比WFA with 2-opt可以看出，在城市數(shù)目較小的情況下，WFA with 2-opt可以得到較好的路徑解，但隨著城市數(shù)目增大，解質(zhì)量開始下降。反觀本算法，雖然在城市數(shù)目較小的情況下并未取得最優(yōu)解，但與最優(yōu)解的偏差都在可接受范圍內(nèi)。即使城市數(shù)目開始增多，但解質(zhì)量并未隨之變差，依舊在最優(yōu)解附近。如KroA200問題中，WFA with 2-opt和PSO-ACO-3opt問題的標(biāo)準(zhǔn)偏差都已經(jīng)很大，說明解已經(jīng)開始不穩(wěn)定。其中在和PSO-ACO-3opt算法的對比中，增加了兩者算法的運行時間比較，如表4所示。

表4 算法的運行時間對比

通過表4可以看出，對于同一個TSPLIB問題，在相同的搜索次數(shù)內(nèi)，PSO-ACO-3otp在求解時，將會花費較多時間，即使是最基本的Eil51問題，PSO-ACO-3opt將花費140.50 s的時間，而本算法只需6.737 s便可完成任務(wù)，在效率方面本算法更加優(yōu)異。

表5 各算法性能比較

5 結(jié)束語

針對蟻群算法易陷入局部最優(yōu)解的問題，提出了一種基于擁擠度的蟻群優(yōu)化算法。通過引入靜態(tài)擁擠度算子和動態(tài)擁擠度算子，蟻群算法參數(shù)可跟隨信息素濃度變化而動態(tài)更新，增強了蟻群之間的信息交流，達到了改善信息素矩陣的目的。改進的蟻群算法能夠提前主動預(yù)防早熟和停滯現(xiàn)象，提高了蟻群算法的全局搜索能力。同時加入的“搜索域”規(guī)則在求解過程中首先淘汰大部分劣質(zhì)解，使算法在很少的步驟內(nèi)就得到一組全局次優(yōu)解，而引入的變異算子能對次優(yōu)解進一步優(yōu)化，增強蟻群算法的局部搜索能力。

蟻群算法作為一種新興的仿生優(yōu)化算法，還有許多值得研究的地方，很多理論問題也有待進一步探討。但是隨著研究的深入，蟻群算法也將和其他模擬進化算法一樣，能夠獲得越來越多的應(yīng)用。