嵌入小生境技術的自適應并行蟻群算法

摘要：針對原始蟻群算法搜索能力不強、易陷入局部最優的問題，提出了一種自適應并行蟻群算法。通過引入“聚度”的概念，使新算法能充分利用學習機制、強化最優信息的反饋，而當算法處于停滯狀態時，引入小生境技術重新初始化其它螞蟻狀態，用共享函數來阻止這部分螞蟻向局部最優移動。通過仿真實驗，驗證了該算法的有效性和實用性。

關鍵詞：蟻群算法；并行蟻群算法；小生境技術

中圖分類號：TP18文獻標識碼：A文章編號：1009-3044(2008)34-1817-03

An Adaptive Parallel Ant Colony Method Based on the Niche Method

LI Xiang-li1， ZHOU Lin-cheng2

(1.Jiangsu College of Information Technology， Wuxi 214153， China;2.Wuxi Machinery and Electron Higher Professional and Technical School， Wuxi， 214028， China)

Abstract: A self-adaptive parallel ant colony algorithm based on the niche method is proposed to solve the local optimum problem of the original ant colony algorithm. This proposed algorithm makes full use of learning mechanism and intensifies the feedback of the optimal information. When the ant is stagnated， the niche method is applied to make some ants move to local optimum and others jump out from the local optimum by re-initialized status and by the effect of the sharing functions. An example is given to show the validity of the proposed algorithm.

Key words: ant colony algorithm; parallel ant colony system; niche method

1 引言

蟻群優化算法[1]是一種全局性鄰域搜索算法，具有分布式計算、信息正反饋和啟發式搜索的特征，易于與其它方法相結合。該算法得到了具有NP難度的旅行商問題(TSP) [2]的最優解，并應用到連續空間[3]和數據挖掘[4]中。但是蟻群算法也存在著一些缺陷。尋找“精解”和“快速收斂” 兩者的平衡點成為蟻群算法發展和應用的關鍵。

并行蟻群算法[5]是最近提出的一種優化結果較好的算法，該算法將所有螞蟻分為幾個子種群，并進行種群間的信息交流。但是其子種群的規模的預先確定有很大的難度：若規模過大，則種群多樣性容易被破壞，搜索能力下降；若過小，則使得搜索時間增加。因此，本文中引入“螞蟻聚度”的概念[6]，通過設定“聚度閾值”來自動調整子種群的規模，提出了自適應的并行蟻群算法。傳統的蟻群算法以及改進的Ant-Q System[7]和MAX-MIN[8]模型都存在著全局尋優能力不強的缺點，小生境技術[9]的引入正是為了解決這一問題。當自適應并行蟻群系統進入停滯階段時，除了保留部分螞蟻對局部最優點繼續進行搜索外，其它的螞蟻重新劃分種群，并重新初始化信息素，然后對整個空間進行重新搜索。這樣，在減少螞蟻數量的時候也可以在信息量的“探索”和“利用”之間得到很好的平衡。通過對TSP問題進行計算，證明了該方法的有效性和可行性。

2 并行蟻群算法和小生境技術基本原理

2.1 并行蟻群系統(PACS：Parallel Ant Colony System)

在并行蟻群系統[5]中螞蟻被分為幾個不同的種群，并在一些合適的周期內，通過種群之間的信息交流策略來更新信息素。PACS與基本蟻群算法的主要不同在于：1）將所有螞蟻分成若干個不同的種群；2）通過局部調整準則、全局調整準則和信息交流調整準則對信息素進行調整。

以n個城市的TSP問題為例說明PACS模型。首先作如下定義:G表示總的種群數目，Nk(K=1，2，…G)表示第k個種群中螞蟻的個數，且滿足螞蟻總數m=■Nk；dij(i，j=1，2，...，n)表示城市i和城市j之間的距離，τij(t)表示t時刻在城市i，j連線上殘留的信息量。隨著時間的推移，以前留下的信息逐漸消逝，用參數ρ、α、λ表示信息的揮發因子。所有螞蟻完成一次迭代以后，各路徑上的信息量根據下列準則作調整:

準則1（局部調整準則）：局部調整是每只螞蟻在建立一個解的過程中進行的。 隨著時間的推移，種群j中兩個元素(城市)r和s之間的局部信息素數量要根據下式作調整：

■（1）

其中Lnn表示用最近鄰域啟發式（nearest neighbour heuristic）得到的所有城市之間的最小距離。

準則2（全局調整準則）：只有生成了全局最優解的螞蟻才有機會進行全局調整，全局調整規則為：

■ （2）

其中Q是信息素強度，它影響算法的收斂速度。Lj表示第j個群體中螞蟻找到的最短路徑。

準則3（信息交流調整準則）：信息交流準則是并行蟻群算法與ACS算法的主要不同點。每經過R1次循環，通過種群間的信息交流對信息素值進行調整。在本文中采用環形結構的種群間信息交流策略。

■ （3）

其中 “neighbour”定義為在環形結構中的種群。Lng表示鄰域(\"neighbour\")種群中的最短路徑。

2.2 小生境技術原理

小生境技術的提出為搜索空間的擴展提供了可能性。共享機制由Goldberg[10]提出，它通過共享函數調整群體中各個個體的適應度，以維護群體的多樣性。共享函數是表示兩個個體之間密切關系程度的函數，記為sh(dij)，dij表示個體i與個體j之間的某種關系。

3 嵌入小生境技術的自適應并行蟻群算法

并行蟻群算法的子種群規模是固定的，使算法存在著搜索能力不強的缺陷。本文引入“聚度” [6]的概念，通過“聚度值”與閾值的比較自適應地調整各個子種群地規模。設從城市i共有r條路徑到達另外r個城市i1，i2…ir，另設上一次迭代中，經過這r條路徑上的螞蟻數分別為a1，a2…ar，如圖1所示。則定義城市i的聚度為：■。當m只螞蟻均勻分布在r條路徑上時，城市的聚度為：■ ；而當m只螞蟻都集中在r條路徑中的某一條上時，城市i的聚度值為最大：■。

用K代表子種群規模，則自適應的子種群規模可以通過如下公式確定：

■（4）

其中σ是“聚度閾值”一般取常數。若聚度值較大，說明螞蟻上一次從這個城市到達另外城市的路徑相對集，在以后的搜索最優過程中，過度強化正反饋信息引起停滯現象的可能性就越大。所以當sta大于閾值σ時，子種群規模就降低到最低限度2，以刺激種群多樣性的提高。相反，當城市聚度越小時，這個城市的信息量分布相對比較分散，導致收斂速度較慢。所以當sta較小時種群的多樣性較好，子種群由下式確定：

■（5）

在確定子種群的規模后就按照上述并行蟻群算法的調整準則對信息量進行調整。

在自適應并行蟻群算法進入停滯后采用共享機制重新確定城市之間的信息量，對群體中信息素值較大（認為與局部最優點的相似度較高）的個體通過施加共享函數進行懲罰，阻止新螞蟻種群再次陷入同一局部最優點。施加共享函數后城市間的共享信息素為：

■（6）

共享函數sh(x)采用典型的三角共享函數：

■（7）

式中τshare為共享信息量；τmax為自適應并行蟻群模型中的信息素最大值。

根據圖2討論共享函數對信息量的影響。不失一般性的認為距離局部最優點xi越近的點對應的信息量就越大（雖然會有個別點不滿足這個條件，但在螞蟻數量較多的情況下對結果的影響不會太大）。本文選取τshare=1/2τmax，假設共享前τi1=0.2τshare，τi2=0.4τshare，由式（7）可得x1、x2的共享度都為0，則共享信息素分別為τi1和τi2；同理如果τi3=1.6τshare，x3的共享度為0.6，共享信息量為0.4τi3。由此可見當螞蟻距離局部最優點較遠時共享信息量與原信息量相等；當螞蟻距離局部最優點較近時共享信息量相應減小。由于螞蟻在搜索過程中是通過感知信息素的數量進行路徑選擇的，所以這樣的的處理達到了局部最優點對新初始化螞蟻的排斥作用，能夠有效避免蟻群再次陷入同一局部最優。

■

圖1源自城市i的各條路徑上螞蟻的分布情況 圖2共享函數對初始化信息素的影響

3.1 算法描述

1) 初始化：將m只螞蟻隨機分為G個種群，第k個種群中螞蟻的個數用Nk(k=1，2，…，G)表示。

2) 重復運行直到禁忌表添滿為止（這一過程將運行(n-1)次）

對每個螞蟻，根據傳統的選擇概率，選擇下一個要轉移去的數據j；

將第k只螞蟻轉移到第j個數據；

進行局部搜索，根據公式(1)更新每只螞蟻的信息素；

將數據j插入到禁忌表tabuk(s)。

3) 計算種群中每只螞蟻所走路徑的總長度，找出此次搜尋中的最短路徑lt 。

4) 全局信息素更新：在每一種群中按照公式(2)進行全局信息素的更新。

5) 種群間信息交流：每經過R1次循環就根據公式(3)進行螞蟻種群間的信息素交流。

6) 自動劃分種群規模：按照公式(4)自動地進行種群規模的劃分。

7) 如果（NC

8) 種群重新初始化：當||lt-lt-1||<ε成立，認為自適應并行蟻群算法進入停滯階段，引入小生境技術。

按照公式(6)計算共享信息素值；

9) 當NC=NCMAX，或者出現停滯時，輸出最優解，結束。

4 實例運算及性能分析

從通用的TSPLIB中選用TSP問題，用上述算法、MMAS算法和文獻[6]提出的基于分布均勻度的蟻群算法進行了比較測試。根據多次實驗所得結論，本文選擇α=1，β=2，ρ=0.4，ε=0.5， “聚度閾值”σ根據城市個數的不同選擇不同的數值（本文實驗中選取為0.8×max sta）。更改螞蟻的數目，每次迭代的NCMAX取1500次，分別運行50次取平均值列于表1中。

從表1可以看出當螞蟻數目減少的時候，本文提出的方法較之基于分布均勻度的蟻群算法能夠得到效果更好的解。這是因為小生境技術可以使得大部分螞蟻的搜索具有較強的“爬坡”能力，使得解具有較好的多樣性、全局性，避免了早熟現象。雖然在時間消耗上較之基于分布均勻度的蟻群算法要多，但綜合考慮搜索結果和收斂時間，本文提出的方法在螞蟻數量減少的情況下，保證了收斂速度和防止早熟之間的平衡。

5 結論

本文提出了自適應的并行蟻群算法，通過設定“聚度閾值”來自動調整子種群的規模。并行蟻群算法同樣存在著搜索多樣性的不足、易陷入局部最優的問題，小生境技術的引入正是為了解決這一問題。當自適應并行蟻群系統進入停滯階段時，除了保留部分螞蟻對局部最優點繼續進行搜索外，其它的螞蟻重新初始化信息素，然后對整個空間進行重新搜索。通過共享函數來阻止螞蟻向局部最優移動，這種方法既有效地擺脫了停滯的狀態又保留了原有的較優解。

參考文獻：

[1] Dorigo M， Maniezzo V， Colorni A. Ant system: Optimization by a colony cooperating Agents[C]. IEEE Transactions on Systems， Man， and Cybernetics-Part B: Cybernetics， 1996，26(1): 29-41.

[2] Dorigo M， Gambardella L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[C]. IEEE Transactions on Evolutionary Computation， 1997，1(l):53-66.

[3] 李向麗，楊慧中，魏麗霞.基于退火的蟻群算法在連續空間優化中的應用[J].計算機工程與應用，2007，43(23):74-76.

[4] LI X L， YANG H Z. Application of a Novel Algorithm on Clustering Analysis[C]. Proceedings of the International Conference on Complex Systems and Applications，2006:836-840.

[5] Chu S C， Roddick J F， Pan J S. Ant colony system with communication strategies[J].Information Systems，2004，167(1-4):63-76

[6] 陳崚，沈潔，秦玲，等. 基于分布均勻度的自適應蟻群算法[J].軟件學報，2003，14(8):1379-1387.

[7] Machado L， Schirru R. The ant-Q algorithm applied to the nuclear reload problem[J].Annals of Nuclear Energy，2002，29(12):1455-1470.

[8] Stützle T， Hoos H. MAX-MIN ant system[J].Future Generation Computer Systems，2000，16(8):889-914.

[9] 郟宣耀，王芳.一種改進的小生境遺傳算法[J].重慶郵電學院學報:自然科學版，2005，17(6):721-744.

[10] Goldberg D， Richardson J. Genetic algorithms with sharing for multimodal function optimization[C].Proceedings of the 2nd International Conference of Genetic Algorithms，1987:41-49.