基于擁擠度的改進(jìn)蟻群算法

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

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

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

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

對于擁擠度概念，前人也有相關(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路徑。初始時刻，螞蟻被分別置于隨機(jī)選出的城市中，各城市之間每條路徑的信息素皆相等。在構(gòu)建路徑的過程中，蟻群采用一種偽隨機(jī)比例規(guī)則來確定螞蟻k下一步將要訪問的城市j。其過程為

(1)

(2)

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

1.2 局部信息素更新

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

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

(3)

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

1.3 全局信息素更新

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

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

(4)

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

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

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

2.1 擁擠度

在路徑選擇過程中，螞蟻會傾向于尋找信息素大的路徑，同時由于蟻群算法的正反饋機(jī)制，信息素大的路徑在搜尋過程中信息素的累積會越來越大，進(jìn)而導(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時刻選擇到達(dá)城市v的螞蟻總數(shù)為k，則在時刻t，路徑u→v的動態(tài)擁擠度定義為

(5)

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

為防止蟻群算法過早集中于某些路徑，增大蟻群全局搜索能力，結(jié)合擁擠度的概念，改進(jìn)的狀態(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ù)解，一直在進(jìn)行無用迭代；② 構(gòu)建許多明顯不是最優(yōu)解的路徑，例如將兩個相距很遠(yuǎn)的城市作為螞蟻路徑上的相鄰解。針對問題①，引入擁擠度的概念，擴(kuò)大螞蟻選擇路徑的可能性來降低蟻群的重復(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為蟻群的禁忌表集合。在可選取的城市中采用偽隨機(jī)概率選擇公式和擁擠度結(jié)合的方法進(jìn)行下一個城市選擇。

2.4 變異操作

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

3 算法框架

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

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

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

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

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

⑤ 判斷是否所有的螞蟻均已完成搜索，若是，則返回步驟②，否則從第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ù)進(jìn)行試驗。對參數(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)過改進(jìn)的蟻群算法在驗證各個TSPLIB問題時，都可得到接近最優(yōu)解的路徑。從各算法性能比較(表5)中可以看出，有些結(jié)果要優(yōu)于文獻(xiàn)中的研究結(jié)果。標(biāo)準(zhǔn)偏差也在理想范圍之內(nèi)，說明在各個循環(huán)過程中，改進(jìn)的蟻群算法可以得到較優(yōu)解。對比文獻(xiàn)中的結(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)更新，增強(qiáng)了蟻群之間的信息交流，達(dá)到了改善信息素矩陣的目的。改進(jìn)的蟻群算法能夠提前主動預(yù)防早熟和停滯現(xiàn)象，提高了蟻群算法的全局搜索能力。同時加入的“搜索域”規(guī)則在求解過程中首先淘汰大部分劣質(zhì)解，使算法在很少的步驟內(nèi)就得到一組全局次優(yōu)解，而引入的變異算子能對次優(yōu)解進(jìn)一步優(yōu)化，增強(qiáng)蟻群算法的局部搜索能力。

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