自適應動態雙種群蟻群算法

摘要:基本蟻群算法容易陷于局部最優解是其較為突出的缺點。針對這一問題，文章提出使用雙種群蟻群同時進行搜索。在迭代過程中，若判斷出算法陷入可能局部最優時，則交換不同種群對應路徑上的信息素，并且同時雙向動態自適應調整信息素揮發系數的改進策略。通過信息素的震蕩變化和揮發系數的自適應調整，擴大搜索空間，提高算法搜索的全局性。通過實驗仿真，證明了此算法改進是可行和有效的。

關鍵詞:蟻群算法;自適應;雙種群;局部最優解;揮發系數

中圖分類號:TP301文獻標識碼:A文章編號:1009-3044(2010)01-181-03

Adaptive Dynamic Dual Population Ant Colony Algorithm

RAO Yue-dong

(Wuhan University of Technology， Wuhan 430070， China)

Abstract: The prominent shortcoming of the basic ant colony algorithm is easily trapped into local optimal solution. Dual population searching at the same time strategy is proposed in this paper in order to solve this problem. In the iterative process， when the algorithm is trapped into a local optimum， then change the pheromone of the corresponding path of different populations. At the same time， bi-directional dynamic adjust adaptively the volatile coefficient of the pheromone. The concussion change of the pheromone and the adaptive adjustments of the volatile coefficient can expand the search space and improve the overall searching performance .It is proved that the algorithm is feasible and effective in the emulation experiments.

Key words: ant colony algorithm; adaptive; dual population; local optimal solution; volatile coefficient

蟻群算法(Ant Colony Optimization algorithm，ACO)是由意大利學者Marco Dorigo等人在20世紀90年代初通過模擬自然界中螞蟻集體覓食的行為而提出的一種基于種群的啟發式仿生類算法[1-2]。它是繼遺傳算法、神經網絡、模擬退火等算法以后的又一種應用于組合優化問題的啟發式搜索算法。蟻群算法最早成功應用于解決TSP問題，經過多年的研究與發展，蟻群算法已經成功運用于許多經典組合優化問題，如網絡路由、機器人路徑規劃、車輛路徑、圖形著色等問題[3-6]。作為一種新興的仿生優化算法，蟻群算法具有分布式并行計算、啟發式搜索、魯棒性強和易于與其他算法結合等優點，但搜索時間較長、收斂速度較慢、易陷于局部最優解等也成為其最為突出的缺點。近年來，眾多學者對蟻群算法嘗試了各種方法的改進，力求提高其收斂速度，擴大搜索空間，從而提高算法的尋優能力，改善算法的全局收斂性，使其能更好的應用于各個領域[7-8]。在分析算法的基本原理和大量的改進方法后發現，對信息素濃度的控制是改善算法性能的關鍵。對此，文章提出采用雙種群蟻群進行同時迭代，在迭代過程中，如若發現算法陷入局部最優，則交換兩種群對應路徑上的信息素，通過信息素的震蕩來擴大算法的搜索空間。同時，對于各個種群的信息素揮發系數，進行雙向動態自適應調整，以提高算法搜索的全局性，使其解盡可能收斂于全局最優。

1 基本蟻群算法數學模型

為了能夠清楚地理解蟻群算法的數學模型，本文借助了經典的對稱TSP問題。設n表示TSP的規模即城市數量，m為蟻群中螞蟻的總數目，dij (i，j=1，2，…n)表示城市i和城市j之間的距離，τij(t)表示在時刻t城市i和城市j之間的路徑上的信息素濃度。在初始時刻各條路徑上的信息素濃度相等，螞蟻k(k=1，2，…m)在運動過程中，根據各條路徑上的信息素濃度決定其轉移方向，同時用禁忌表tabuk (k=1，2…n)來記錄螞蟻k當前己經走過的城市，集合隨著tabuk進化過程作動態調整。在搜索過程中，螞蟻根據各條路徑上的信息量及路徑的啟發信息來計算狀態轉移概率[9]。Pijk(t)表示在t時刻螞蟻k由城市i轉移到城市j的狀態轉移概率，其表達式為:

式中:allowedk ={C-tabuk}表示螞蟻k下一步允許選擇的城市，α為信息啟發式因子，反映了螞蟻在運動過程中所積累的信息量在指導蟻群搜索中的相對重要程度，其值越大螞蟻選擇以前走過路徑的可能性就越大。β為期望啟發式因子，反映了啟發信息在指導蟻群搜索過程中的相對重要程度，其大小反映了蟻群尋優過程中先驗性、確定性因素的作用強度。ηij(t)為啟發函數，表達式為ηij(t)=1/dij。

為了避免殘留信息素過多引起殘留信息淹沒啟發信息，在每只螞蟻走完一步或者完成對所有n個城市的遍歷后，要對殘留信息進行更新處理， t+n時刻在路徑(i，j)上的信息量可按如下規則進行調整:

式中，ρ表示信息素揮發系數，則1-ρ表示信息素殘留因子;Δτij(t)表示本次循環中路徑(i，j)上的信息素增量，Δτijk(t)表示第k只螞蟻在本次循環中留在路徑(i，j)上的信息量。

根據信息素更新策略的不同，Dorigo M提出了三種不同的基本蟻群算法模型，分別稱之為Ant-cycle模型、Ant-quantity模型和Ant-density模型，其差別在于Δτijk(t)的求法不同。

Ant-cycle (3)

Ant-quantity (4)

Ant-density(5)

在蟻周模型中，Q表示信息素強度，它在一定程度上影響算法的收斂速度;Lk表示第k只螞蟻在本次循環中所走路徑的總長度。蟻量和蟻密模型利用的是局部信息，即螞蟻完成一步后更新路徑上的信息素;而蟻周模型利用的是整體信息，即螞蟻完成一個循環后更新所有路徑上的信息素，在求解TSP時性能較好，因此通常采用蟻周模型作為蟻群算法的基本模型。

2 自適應動態雙種群蟻群算法

通過對基本蟻群算法仿真TSP問題結果分析發現，算法很容易陷入局部最優解。即搜索進行到一定程度后，所有的個體發現的解基本完全一致，出現停滯現象，不能再對解空間進一步搜索，導致可能無法找到全局最優解。產生這一現象的根本原因是局部路徑上的信息素過量堆積，當許多螞蟻選中同一條路徑時，該路徑中的信息量就會陡然增大，造成該路徑和其他路徑之間的信息素差異加大，從而使得后續的螞蟻都會集中到這一條路徑上，造成一種堵塞和停滯現象，表現在算法求解結果上就是導致算法早熟和局部收斂。因此，如何控制信息素濃度，在算法收斂速度和收斂空間之間找到平衡點就成為蟻群算法優化的關鍵。

定義:在算法迭代過程中，當求出的最優解出現連續ω(ω為常數)代相同時，則認為算法求解陷入可能局部最優。

2.1 雙種群蟻群搜索

針對單一種群蟻群迭代時，由于信息素正反饋機制容易導致算法早熟這一現象，本文提出在算法運行初始階段即采用雙種群蟻群同時獨立搜索，由于不同種群的初始參數環境設置不同，因此迭代過程中各條路徑上的信息素分布也不會相同。當算法運行過程中，一旦判斷出陷入可能局部最優時，則將兩個種群相對應路徑上的信息素交換。這樣，通過信息素的反復震蕩，擴大算法的搜索空間，在一定程度上改善算法的全局性。

2.2 雙向自適應調整信息素揮發系數

根據公式2分析，信息素揮發系數ρ的大小直接關系各條路徑上信息素的大小分布，從而直接影響到蟻群算法的全局搜索能力及其收斂速度。在基本蟻群算法中，ρ的值是固定的，若ρ的值選取不當，則處理問題規模較大時會使那些從來沒有被搜索到的路徑上的信息量減小接近于O，這不利于尋找更好的解，容易使算法陷入局部最優。對此，本文在雙種群蟻群搜索的基礎上，提出一種雙向動態自適應調整信息素揮發系數的算法改進方法。基本思想是:對于兩個獨立種群的信息素揮發系數值ρ，其取值范圍均設置在(0，1)之間。在算法運行初始階段，將兩個種群的ρ值分別一個設置為較小值(如ρ=0.1)，一個設置為較大值(如ρ=0.9)。在算法迭代過程中，當出現求解陷入可能局部最優時，則分別自適應地動態調整兩個種群的ρ值，調整方法是初始階段ρ值設置較小種群的ρ值逐漸增大，而初始階段ρ值設置較大種群的ρ值逐漸減小。這樣，不同的種群通過ρ值的變化來擴大各自算法的搜索空間，避免搜索過度集中在某些較優的路徑上，以此來尋找更優的路徑。而對于不同種群來說，由于初始階段的ρ值設置存在較大差異，而使得迭代過程中不同種群各自路徑上的信息素存在較大差異，所以當算法陷入局部最優，兩種群對應路徑上的信息素交換的時候，才可能發生較大的震蕩變化，從而進一步拓展算法的搜索空間，使搜索結果收斂于全局最優解。

因此，當算法迭代過程中出現求解陷入可能局部最優時，不同種群的ρ采用以下公式6進行自適應調整，設兩個種群的揮發系數分別為ρA和ρB，并且ρA的初始值設為較小值，ρB的初始值設為較大值，則:

式中k表示迭代的代數，μ1，μ2分別為兩個種群信息素揮發系數的動態改變參數，此時由于已設ρA初始值為較小值，ρB初始值為較大值，因此μ1應大于1，而μ2應小于1。根據實驗結果分析，μ1取值在(1，1.5)，μ2取值在(0.5，1)之間對算法優化較好。

同時，為了防止算法迭代過程中多次陷入可能局部最優，而使得揮發系數ρ值改變過大或過小造成局部路徑上信息素差異過大的情況，可在算法運行初始階段設定路徑上信息素的最大最小值，這樣不僅能提高收斂速度，更有利于搜索結果收斂于全局最優解。

2.3 算法編程步驟

step1 初始化兩個種群參數:αA、βA、ρA、QA、mA、αB、βB、ρB、QB、mB、 NCmax，其中ρA∈(0，1)且取較小值，ρB∈(0，1)且取較大值;

step2 while NC

step3 將兩種群mA、mB只螞蟻分別隨機放置于初始城市位置上，并且分別根據公式1計算選擇概率選擇下一個到達城市，完成各自的周游;

step4 分別記錄A，B兩個種群本次迭代的最佳(最短)路徑;

step5 進入保優函數，比較兩個種群本次迭代的最佳路徑，取其短者為算法在本輪迭代的最佳路徑;

step6 兩種群分別根據公式2更新信息素，同時設定信息素的最大最小值;

step7 當算法陷入可能局部最優時，進入種群通信函數，交換A，B種群對應路徑上的信息素;

step8 當算法陷入可能局部最優時，根據公式6動態改變ρA和ρB的值;

step9 兩個種群的禁忌表TabuA、TabuB分別清零，NC=NC+1;

step10 循環結束;

step11 輸出最優路徑及最短距離。

3 算法仿真分析

本文采用MATLAB作為仿真工具，通過對TSP問題中Oliver30問題進行仿真實驗，驗證改進的自適應動態雙種群蟻群算法比基本的蟻群算法具有更好的全局搜索能力和穩定性。實驗中NC_max設定為200，ω設定為10，即當搜索結果連續出現10代相同時，則認為算法求解陷入可能局部最優。其他各項參數設置如表1所示:

表1 Oliver30問題實驗參數表2 仿真結果對比表

圖1 本文改進算法最優解及其進化曲線圖圖2 基本蟻群算法最優解及其進化曲線圖

實驗分別用本文改進的蟻群算法和基本蟻群算法針對Oliver30問題進行20次求解，得到三組數據(表2):算法運行的最優解(優化結果及進化曲線見圖1和圖2)，運行20次仿真結果的平均解以及平均進化代數。根據實驗結果可以看出，改進的蟻群算法在最優解和平均進化代數上均較基本蟻群算法有所提高，表明經改進的算法能夠搜索到更優的解，全局收斂性得到了增強。并且從平均解上看，本文改進算法也較基本蟻群算法有較大提高，表明改進算法在穩定性上也得到增強。

4 結束語

本文提出雙種群蟻群同時獨立搜索，當算法迭代陷入可能局部最優時交換信息素，并且雙向動態自適應調整信息素揮發系數的改進策略，在算法搜索的全局性和穩定性上都有了顯著提高。在仿真實驗過程中，我們發現不同種群參數的設置對優化結果的穩定性有較大影響，因此，如何合理配比參數，提高收斂結果的穩定性是我們下一步要繼續研究的工作。

參考文獻:

[1] Colorni A，Dorigo M，Maniezzo V，et al.Distributed optimization by ant colonies[A].Proceedings of the 1st European Conference on Artificial Life[C]，1991，134-142.

[2] DorigoM，ManiezzoV，ColoniA.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems，Man，and Cyberneties一PartB，1996:26(1):29-41.

[3] SCHOONDERWOERD R.Ant-based load balancing in telecommunications networks[J].Adaptive Behavior，1996，5(2):169-207.

[4] 金飛虎，洪炳熔，高慶吉.基于蟻群算法的自由飛行空間機器人路徑規劃[J].機器人，2002，24(6):526-529.

[5] 侯立文，蔣馥.一種基于螞蟻算法的交通分配方法及其應用[J].上海交通大學學報，2001，35(6):930-933.

[6] COSTA D， HERTZ A. Ants can colour graphs[J].Journal of the operational Research Society，1997，48(3):295-305.

[7] 郝晉，石立寶，周家啟.求解復雜TSP問題的隨機擾動蟻群算法[J].系統工程理論與實踐，2002，(9):88-91.

[8] 胡勇.動態躍遷轉移蟻群算法[J].計算機工程，2005，31(1):167-168.

[9] 段海濱.蟻群算法原理及應用[M].北京:科學出版社，2005.