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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(3) 假設(shè)經(jīng)上述2步以后C0變?yōu)镃1，則以模擬退火原則決定保留 C1還是 C0：計(jì)算路徑長度 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)進(jìn)行迭代(λ為退火系數(shù))。此處的退火溫度T和下面的二次退火溫度為同一個(gè)溫度。

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

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

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

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

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

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

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

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

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

(1) 變量定義：假設(shè)搜索蟻的數(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次迭代時(shí)算法找到的最短路徑，Cmin表示其TSP路徑，Lmin表示其路徑長度。T(t)表示模擬退火的第t次迭代溫度，初始溫度為T0。

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

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

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

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

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

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

3.4 新路徑信息素加強(qiáng)和信息素壓縮

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

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

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

3.5 算法流程

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)與分析

DSAPACA 算法參數(shù)設(shè)置為：α=1，β=3，m=城市規(guī)模，ρ=0.15，Q=20，=0.5，R=30，ω=2。對(duì)于城市規(guī)模小于100的TSP問題，MAXPC=10，退火參數(shù)設(shè)置為：初始溫度 T0=105，退火系數(shù) λ=0.95，最大回火次數(shù)NSmax=4。對(duì)于城市規(guī)模大于等于100的TSP問題，MAXPC=15，退火參數(shù)設(shè)置為：T0=106，退火系數(shù)最大回火次數(shù)=6。MAX-MIN算法的參數(shù)設(shè)置參照文獻(xiàn)[13]。表1所示為2種算法對(duì) 5個(gè) TSP問題的測試結(jié)果。從表 2可以看出：DSAPACA算法在5個(gè)不同規(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)蟻群存在的選路方面的缺陷，在此基礎(chǔ)上加以改進(jìn)，使其滿足最短路徑三原則。

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

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

[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] 段海濱. 蟻群算法原理及其應(yīng)用[M]. 北京: 科學(xué)出版社,2006: 45-96.DUAN Hai-bin. Ant colony algorithms: Theory and applications[M]. Beijing: Science Press, 2006: 45-96.

[6] 徐精明, 曹先彬, 王煦法. 多態(tài)蟻群算法[J]. 中國科學(xué)技術(shù)大學(xué)學(xué)報(bào), 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] 全惠云, 文高進(jìn). 求解 TSP子空間的遺傳算法[J]. 數(shù)學(xué)理論與應(yīng)用, 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]. 計(jì)算機(jī)應(yīng)用與軟件, 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]. 華中科技大學(xué)學(xué)報(bào): 自然科學(xué)版, 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]. 計(jì)算機(jī)工程與設(shè)計(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.