基于二次退火機制的改進多態(tài)蟻群算法

杜振鑫，王兆青，王枝楠，秦偉，段云濤

(1. 韓山師范學院 基礎教育師資系，廣東 潮州，521041；2. 浙江理工大學 計算機技術(shù)教研部，浙江 杭州，310018)

TSP(Traveling salesman problem)問題是典型的NP(Non-deterministic polynomial problem)難問題[1]，在車輛調(diào)度、工程控制、VLSI設計等領域具有重要用途[2]，目前不存在多項式復雜度以內(nèi)的全局算法[3]，可以將其簡述為：求1條經(jīng)過n個城市1次且僅1次的閉合回路，使其最短。Dorigo等[4]提出的蟻群算法是目前求解 TSP問題最有效的算法之一[5]。觀察已知的TSP最短路徑可以發(fā)現(xiàn)其應當滿足3個基本原則：(1)空間距離最近的城市應當在TSP最短路徑中盡可能相鄰；(2) 距離最遠的 2個城市中間應盡可能插入其他城市；(3) 最優(yōu)路徑中絕無子路徑交叉現(xiàn)象。徐精明等[6]提出的多態(tài)蟻群算法在螞蟻選路時只從最近的nMAXPC個城市中選擇，在很大程度上減少了計算量，較好地滿足了第1個原則，本文作者在此基礎上加以改進，使之同時滿足3個原則。同時，本文作者提出基于競爭機制更新信息素、新路徑信息素加強和壓縮信息素的機制，使得算法不容易陷入局部最優(yōu)解。

1 多態(tài)蟻群算法

基本蟻群算法有2個主要步驟，即螞蟻構(gòu)建問題的解和信息素更新。τij表示t時刻城市i和j之間的信息素濃度，第k(k=1，2，…，m)只螞蟻在搜索過程中根據(jù)路徑上遺留的信息素濃度決定下一步訪問的城市，表示t時刻螞蟻k由城市i訪問城市j的概率：

式中：η為啟發(fā)信息，一般取η=1/dij；dij為路徑ij的長度；α和β分別表示信息素和啟發(fā)信息的重要程度。tabuk表示螞蟻k已經(jīng)訪問過的城市。

所有螞蟻完成1次循環(huán)以后，各路徑上的信息素更新：

其中：Q為設定的常數(shù)。

基本蟻群算法中的螞蟻只有1種，不能完全反映真實螞蟻群體的復雜性，而且螞蟻由當前城市i訪問下一個城市時要從剩下的所有城市中選擇1個，搜索空間過大，而實際最優(yōu)路徑只可能經(jīng)過城市i最近的nMAXPC個城市之一[7]。據(jù)此，徐精明等[6]提出了多態(tài)蟻群算法(Polymorphic ant colony algorithm，PACA)，主要的改進是將螞蟻分為偵察蟻和搜索蟻。首先將m個偵察蟻分別放置在m個城市中，每個偵察蟻以所在城市為中心，偵查其余m-1個城市，將結(jié)果與先驗知識相結(jié)合記為s[i][j]，標記在路徑ij上：

2 多態(tài)蟻群算法的缺陷及改正

多態(tài)蟻群算法中搜索蟻只從最近的nMAXPC個城市中選擇城市，減輕了選路計算量。但是，若最近的nMAXPC個城市全部訪問完時(如圖1所示)，假設nMAXPC為3，則當螞蟻從1號城市走到4號城市時，因為4號城市鄰近的 nMAXPC=3個城市全部選擇完畢，螞蟻無路可走。實際上，出現(xiàn)圖中所示情況的概率很小，但是，為了使算法不失嚴謹性，仍然應當從理論上予以避免。采用增大nMAXPC的辦法可以避免上述情況。實驗發(fā)現(xiàn)：對于100個城市TSP問題，至少應當滿足：

取40個城市以上才能完全避免上述問題，但是，這又喪失了多態(tài)蟻群算法減少選路計算量的優(yōu)點，而且算法運行中一般只有少數(shù)幾只螞蟻出現(xiàn)無法選路的情況。本文在不增大nMAXPC的情況下將概率選擇公式(6)改為式(7)。根據(jù)式(7)，螞蟻選路時仍然主要從鄰近的nMAXPC個城市中選路，只有無法選路時才會采用上式中s[i][j]=0的情況，兼顧了多態(tài)蟻群算法快速收斂的優(yōu)點，又使得算法不至于停滯。

圖1 多態(tài)蟻群算法停滯示意圖Fig.1 Phenomenon of PACA’s falling into stagnation

3 基于二次退火機制的改進多態(tài)蟻群算法

本文改進的主要思想是通過退火和局部優(yōu)化使得多態(tài)蟻群算法滿足TSP最短路徑三原則。為了避免算法局部收斂，對信息素更新方式加以改進，采用模擬退火競爭釋放機制，使得信息素更新多樣化。同時，對新發(fā)現(xiàn)最優(yōu)路徑信息素加強和信息素壓縮，減少信息素濃度差。

張曉婧等[8]也提出了基于模擬退火的蟻群算法，但是容易導致早熟收斂，并且退火時僅使用普通的隨機交換城市的方案，效率不夠高。劉波等[9]提出模擬退火和回火策略的蟻群算法，可以有效緩解基本蟻群算法容易早熟、停滯和收斂較慢的問題，但是，螞蟻每次選路在所有路徑中隨機選擇，其效率仍然有待于進一步提高。

3.1 一次退火優(yōu)化路徑

根據(jù)引言中提出的原則(2)，距離越遠的2個城市中間應當以越大的概率插入其他城市，使路徑總長度盡可能地減小。退火過程可分4步完成。

(1) 在當前螞蟻形成的TSP路徑中，以較大的概率選擇2個距離較遠的相鄰城市，其中起點城市記為i，則終點城市為i+1。假設當前螞蟻找到的TSP路徑是C0，以數(shù)組l(k)表示路徑C0中相鄰2個城市之間的距離，那么有：

其中：d表示距離。則選取起點城市i的概率為：

根據(jù)式(9)，空間距離越遠的2個城市越容易被選中，從而在這2個城市中間插入其他城市使得路徑縮短的概率也越大。

(2) 由第一步選擇的城市i，進一步選擇插入i和i+1之間的城市。根據(jù)引言中提出的思想，應當讓距離越近的城市以越大的概率相鄰。設dmax表示距離城市i最遠的城市的距離，即j 為 i的相鄰城市，為了防止下一步選擇的城市是當前城市本身，設置d(i，i)=dmax，則選取插入i和i+1之間的城市j的概率為：

假設根據(jù)式(9)選出的在TSP路徑中相鄰、而空間距離較遠的城市是 i和 i+1，在式(10)中選出的“距離起點城市i較近的”的城市是j，則j被插入在i和i+1之間，形成子路徑i，j和i+1，使得引言部分提出的前2條原則同時得到滿足。

(3) 假設經(jīng)上述2步以后C0變?yōu)镃1，則以模擬退火原則決定保留 C1還是 C0：計算路徑長度 L(C1)和L(C0)的差值ΔL=L(C1)-L(C0)，若ΔL＜0，則用 C1替換C0；否則若 exp(-ΔL/T)＞rand(0，1)，則也用 C1替換C0，否則，就保留 C0而拋棄 C1。退火溫度按照T(t+1)=λT(t)進行迭代(λ為退火系數(shù))。此處的退火溫度T和下面的二次退火溫度為同一個溫度。

(4) 每條路徑Ci在第t次迭代時的退火溫度恒定不變，都為 T(t)。每條路徑的退火次數(shù)：首先對各條路徑長度按照從小到大排序，形成排序隊列qi(1≤i≤m，m為螞蟻的個數(shù))，第 i條路徑的退火次數(shù)為因為較好的路徑釋放信息素的可能性較大，所以，退火次數(shù)較多；較差路徑釋放信息素的可能性較小，所以，退火次數(shù)較少，使得信息素釋放更好地反映路徑的質(zhì)量。

3.2 最優(yōu)路徑3-opt修正

圖2 3-opt修正原理Fig.2 Principle of 3-opt

3-opt修正的原理可以用圖2表示。圖2中，實線(包含粗實線和細實線)所示是修正前的路徑，城市 j是距離城市i最近的城市，那么將圖中3條粗實線3條路段用3條虛線路段代替，路徑變短的可能性很大，從而原來實線所示路徑以較大概率得到優(yōu)化。通過3-opt優(yōu)化，基本可以滿足引言中的原則(3)：最優(yōu)路徑不含交叉，因為若該路徑含有交叉，則必定不是最優(yōu)路徑，必然可以被3-opt優(yōu)化；反之，經(jīng)過3-opt優(yōu)化的路徑，必定不含交叉。

3.3 二次退火競爭釋放信息素

信息素是蟻群算法中最重要的啟發(fā)因素，因此，其釋放方式十分重要。主要的信息素釋放方式有2種：

一是全局釋放信息素方式。其特點是所有螞蟻都貢獻信息素，優(yōu)點是不容易陷入局部最優(yōu)解，缺點是收斂速度較慢；

二是精英螞蟻系統(tǒng)。其特點是只有當次迭代最優(yōu)的螞蟻才有釋放信息素的權(quán)利，優(yōu)點是只有較優(yōu)路徑才能釋放信息素，所以算法收斂速度較快，缺點是容易使算法陷入局部最優(yōu)解，對初始信息素分布敏感。

Dorigo等[10-11]提出限制路徑上的信息素濃度，減少優(yōu)勢路徑的選擇壓力；Zhu等[12]提出信息素變異和動態(tài)更新的機制，這些改進方案的目的都是為了一方面避免優(yōu)勢路徑上的信息素過度積累，增強算法跳出局部最優(yōu)解的能力，另一方面又要保證算法快速收斂，取得全局和局部尋優(yōu)之間的平衡。本文結(jié)合現(xiàn)有信息素釋放方式的優(yōu)點，提出一種退火競爭釋放信息素的方式。

(1) 變量定義：假設搜索蟻的數(shù)目是m，以Ak(Ck，Lk)表示第k(k=1，2，…，m)只搜索蟻搜索到的路徑，Ck是該只螞蟻生成的TSP路徑，Lk是該路徑的長度。表示m只螞蟻形成的路徑集合。是第t次迭代生成的最優(yōu)路徑，即滿足第 k只(k=1，2，…，m)的螞蟻，Ctmin是其經(jīng)過的 TSP路徑，Ltmin是其 TSP路徑的長度。表示直到第t次迭代時算法找到的最短路徑，Cmin表示其TSP路徑，Lmin表示其路徑長度。T(t)表示模擬退火的第t次迭代溫度，初始溫度為T0。

(2) 各螞蟻競爭獲得釋放信息素的權(quán)利：采用競爭釋放信息素的機制，計算當次迭代中候選集中的每一個路徑Lk，計算

若ΔL=0，則該只螞蟻 k釋放信息素的競爭標記fk=1；若p＞rand(0，1)，則競爭標記fk=1。否則fk=0。

(3) 競爭成功者釋放信息素：

式中：Q為信息素釋放常數(shù)；Δτmin是直到第t次迭代為止，算法找到的全局最優(yōu)路徑在路段(i，j)上釋放的信息素：

(4) 回火機制。當每輪搜索完成，螞蟻釋放信息素以后，對退火控制參數(shù)T(t)降溫：

其中：λ為退火系數(shù)，決定了退火溫度T下降的速度。退火溫度T決定了上一步釋放信息素過程中競爭成功的螞蟻的個數(shù)，若T取值較大，則上一步計算的競爭概率pk就較大，螞蟻競爭成功的個數(shù)就比較多，有利于信息素均勻分布，使得算法側(cè)重于全局搜索，避免過早陷入局部最優(yōu)解；隨著退火溫度T的逐步下降，競爭概率減小，競爭成功的螞蟻越來越少，最后，只有接近本次迭代最優(yōu)解的螞蟻才能獲得釋放信息素的權(quán)利，促進算法加速收斂。本算法使用較小的退火系數(shù)λ促使算法快速收斂，但是，這有可能引起算法陷入局部最優(yōu)。所以，采用多次回火機制，當溫度T從T0下降到Tmin時，將溫度T重新回火為重新開始退火。本文稱這種機制為回火機制。實驗中發(fā)現(xiàn)只要退火系數(shù)λ和最大回火次數(shù)NSmax控制得當，能夠取得比單一退火機制更快的收斂速度，且算法更容易跳出局部最優(yōu)解。

3.4 新路徑信息素加強和信息素壓縮

蟻群算法在迭代中偶爾發(fā)現(xiàn)更優(yōu)的路徑，由于信息素濃度得不到及時增大，會因為揮發(fā)機制很快被遺忘，使得算法探測功能逐漸減弱。因此，提出對新路徑上不屬于老路徑的路段的信息素加強方法：

蟻群算法容易局部收斂的另一個原因是迭代后期路徑上的信息素濃度相差過大，使得螞蟻搜索空間越來越小，最后陷入局部最優(yōu)解。特別對于大規(guī)模TSP問題，由于算法迭代次數(shù)較多，使得路徑上的信息素濃度相差更大，很容易使算法陷入局部最優(yōu)解。為了解決這個問題，Stutzle等[11]提出了最大-最小螞蟻系統(tǒng)，通過在算法中設置信息素濃度上限 τmax和下限τmin，抑制信息素濃度相差過大的情況，算法性能有了較大改進。但是，如果 τmax設置過大或者 τmin設置過小，仍然會導致信息素濃度相差過大；如果τmax設置過小或者 τmin設置過大，會使得優(yōu)勢路徑上的信息素濃度都等于 τmax，較差路徑上的信息素濃度都等于τmin，從而失去了信息素的區(qū)分作用，算法趨近于隨機算法，不利于算法收斂，所以，很難準確地設置 τmax和 τmin。為了彌補這一缺陷，付治政等[13]提出一種壓縮信息素濃度的方法，但其算法需要對信息素濃度分段考慮，并且采用的分段參數(shù)不容易控制，且不能保證壓縮后信息素的順序。本文提出一種信息素壓縮方法，既能保持信息素濃度的小順序，又能避免濃度相差過大。算法中只設置一個信息素濃度下限 τmin，不設置信息素濃度上限 τmax。當路徑上的最大信息素濃度 max(τ)和最小信息素濃度 min(τ)的比值大于固定值R時，所有路徑上的信息素執(zhí)行以下壓縮操作：

經(jīng)過壓縮以后，各路徑上的信息素濃度順序仍保持不變，但是比值被大幅度減小，有利于為下一次迭代提供均等的機會。

3.5 算法流程

以上描述的基于二次退火機制的改進多態(tài)蟻群算法(Double simulated annealing based PACA，DSAPACA)算法具體步驟如下。

Step 1：初始化各參數(shù)，按式(5)初始化各路徑信息素；

Step 2：迭代計數(shù)器NC=0。

Step 3：將m只搜索蟻隨機放入n個城市中，并將該城市放入每只搜索蟻的禁忌表tabu中；

Step 4：按照改正的概率轉(zhuǎn)移式(7)選擇每只螞蟻下一步前進的城市，并將該城市放入每只螞蟻的禁忌表中，直到所有螞蟻都完成1次遍歷，生成候選路徑集合{Ak(Ck，Lk)|1≤k≤m}。

Step 5：對于{Ak(Ck，Lk)|1≤k≤m}集合中的每一條路徑，按式(9)和(10)進行1次退火過程，生成新的候選解集合{A′k(C′k，L′k)|1≤k≤m}，并在該集合中確定本輪迭代最優(yōu)解

Step 8：對各條路徑上的信息素按照式(14)對新的全局最優(yōu)路徑上的信息素加強，按照式(15)信息素進行壓縮。

Step 10：輸出全局最優(yōu)解并退出循環(huán)。

4 實驗與分析

DSAPACA 算法參數(shù)設置為：α=1，β=3，m=城市規(guī)模，ρ=0.15，Q=20，=0.5，R=30，ω=2。對于城市規(guī)模小于100的TSP問題，MAXPC=10，退火參數(shù)設置為：初始溫度 T0=105，退火系數(shù) λ=0.95，最大回火次數(shù)NSmax=4。對于城市規(guī)模大于等于100的TSP問題，MAXPC=15，退火參數(shù)設置為：T0=106，退火系數(shù)最大回火次數(shù)=6。MAX-MIN算法的參數(shù)設置參照文獻[13]。表1所示為2種算法對 5個 TSP問題的測試結(jié)果。從表 2可以看出：DSAPACA算法在5個不同規(guī)模的TSP問題中收斂精度和速度都比 MMAS算法的高，且問題規(guī)模越大其優(yōu)勢越明顯，DSAPACA的最優(yōu)值也與TSPLIB庫中的最優(yōu)值非常接近。

表1 TSP問題測試結(jié)果Table 1 Search results of TSP

5 結(jié)論

(1) 改正了基本多態(tài)蟻群存在的選路方面的缺陷，在此基礎上加以改進，使其滿足最短路徑三原則。

(2) 通過一次退火，以較大概率使得“空間距離越近的城市在 TSP路徑中以越大的概率相鄰”，并且改進算法充分利用原有多態(tài)蟻群算法中的“偵查素”,無需額外計算。通過二次退火，使得信息素釋放大體圍繞最優(yōu)路徑呈正態(tài)分布，既保證了優(yōu)勢路徑釋放較多的信息素，又增加了較差路徑的釋放機會，避免信息素單一釋放機制引起的局部最優(yōu)現(xiàn)象。

(3) 改進算法收斂速度較快，精度較高。

[1] Garey M R, Johnson D S. Computer and intractability: A guide to the theory of NP-completeness[M]. New York: Freeman,1979: 18-19.

[2] Michalewicz Z, Fogel D B. How to solve it: Modern heuristick[M]. Berlin Heidelberg: Spring-Verlag, 2000: 37-38.

[3] Salman A, Ahmad I, Al-Madani S. Particle swarm optimization for task assignment problem[J]. Microprocessors and Microsystems, 2002, 26: 363-371.

[4] Dorigo M, Socha K. An introduction to ant colony optimization[R]. Belgium: Universite Libre de Bruxelles, 2006:7-9.

[5] 段海濱. 蟻群算法原理及其應用[M]. 北京: 科學出版社,2006: 45-96.DUAN Hai-bin. Ant colony algorithms: Theory and applications[M]. Beijing: Science Press, 2006: 45-96.

[6] 徐精明, 曹先彬, 王煦法. 多態(tài)蟻群算法[J]. 中國科學技術(shù)大學學報, 2005, 35(1): 59-65.XU Jing-ming, CAO Xian-bin, WANG Xu-fa. Polymorphic ant colony algorithm[J]. Journal oF University of Science and Technology of China, 2005, 35(1): 59-654.

[7] 全惠云, 文高進. 求解 TSP子空間的遺傳算法[J]. 數(shù)學理論與應用, 2002, 22(1): 36-39.QUAN Hui-yun, WEN Gao-jin. Subspace genetic algorithm for TSP[J]. Mathematical Theory and Applications, 2002, 22(1):36-39.

[8] 張曉婧, 高慧敏. 基于模擬退火的蟻群算法求解 Job-Shop問題[J]. 計算機應用與軟件, 2008, 25(5): 77-79.ZHANG Xiao-jing, GAO Hui-min. Application of ant colony optimization based on simulated annealing to job-shop problem.[J]. Computer Applications and Software, 2008, 25(5):77-79.

[9] 劉波, 蒙培生. 采用基于模擬退火的蟻群算法求解旅行商問題[J]. 華中科技大學學報: 自然科學版, 2009, 37(11): 26-30.LIU Bo, MENG Pei-sheng. Simulated annealing-based ant colony algorithm for traveling salesman problems[J]. Huazhong University of Science and Technology: Natural Science Edition,2009, 37(11): 26-30.

[10] Dorigo M, Stutzle T. Ant colony optimization[M]. London: MIT Press, 2004: 153-172.

[11] St Stutzle T, Hoos H. Max-Min ant system[J]. Future Generation Computer System, 2000, 16(9): 889-914.

[12] Zhu Q B, Yang Z J. An ant colony optimization algorithm based on mutation and dynamic pheromone updating[J]. Journal of Software, 2004, 15(2): 185-192.

[13] 付治政, 肖菁, 張軍. 基于信息素調(diào)整的蟻群算法求解JSP問題[J]. 計算機工程與設計, 2010, 31(2): 378-381.FU Zhi-zheng, XIAO Jing, ZHANG Jun. Implementation of ant colony system algorithm with changing pheromones for job shop scheduling problem[J]. Computer Engineering and Design, 2010,31(2): 378-381.