(1.上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院， 上海 201620； 2.上海工程技術(shù)大學(xué) 管理學(xué)院， 上海 201620)

TSP屬于NP難問(wèn)題[1]，仿生進(jìn)化思想的發(fā)展為NP難問(wèn)題提供了新的思路，這其中以蟻群算法的貢獻(xiàn)最為顯著。蟻群算法的提出[2]，是源于Marco Dorigo的博士論文，它是一種具有進(jìn)化思想的啟發(fā)式算法，根據(jù)正反饋機(jī)制實(shí)現(xiàn)種群間的信息交流。蟻群算法從1992年提出至今，針對(duì)該算法的不足，研究學(xué)者一直進(jìn)行著改進(jìn)工作。Dorigo[3]和T.Stützle[4]分別提出了蟻群系統(tǒng)、最大-最小蟻群算法，對(duì)傳統(tǒng)蟻群算法的信息素更新方式以及界限進(jìn)行了改進(jìn)；文獻(xiàn)[5]提出適當(dāng)刺激螞蟻嘗試那些很少經(jīng)過(guò)的路徑，從而增加螞蟻的全局搜索能力；文獻(xiàn)[6]提出信息素二次更新，即在全局信息素更新規(guī)則中引入子路徑長(zhǎng)度的貢獻(xiàn)度決策，對(duì)下一迭代的τij(t)更新，使那些可能構(gòu)成全局最優(yōu)路徑的子路徑被選擇的概率增加，增加算法全局搜索的多樣性；文獻(xiàn)[5]與文獻(xiàn)[6]中算法的收斂速度會(huì)隨著迭代運(yùn)行的推進(jìn)不斷變慢；文獻(xiàn)[7]引入自適應(yīng)動(dòng)態(tài)因子σ實(shí)時(shí)更新全局信息素濃度，自適應(yīng)動(dòng)態(tài)因子由雙曲正切函數(shù)f(x)決定，當(dāng)搜索路徑越長(zhǎng)，σ越趨近于零，反之亦然，通過(guò)f(x)有效區(qū)分每次迭代的最優(yōu)解上的信息素加成影響，加強(qiáng)了較短子路徑上的信息素濃度，從而加快算法收斂到全局最優(yōu)的速度；文獻(xiàn)[8]基于精英策略的最大-最小螞蟻系統(tǒng)，提出加強(qiáng)螞蟻對(duì)已知最短路徑的敏感度，讓螞蟻在一個(gè)高起點(diǎn)上進(jìn)行解的優(yōu)化，該算法前期加快了算法的收斂速度；文獻(xiàn)[7]和文獻(xiàn)[8]中的算法限制了種群多樣性的擴(kuò)展，算法后期易陷入局部最優(yōu)；文獻(xiàn)[9]保留全局更新中的最短(最長(zhǎng))總路徑長(zhǎng)度，然后根據(jù)約束條件進(jìn)行增減全局信息素，該算法在處理大規(guī)模TSP問(wèn)題時(shí)獲得的解精度不高；文獻(xiàn)[10]將信息素蒸發(fā)參數(shù)ρ和信息素值τ相互抑制平衡，這種改進(jìn)算法增加了全局搜索的多樣性，針對(duì)大規(guī)模的TSP問(wèn)題，可以獲得更好的解質(zhì)量，但是算法后期的收斂速度還有待提高。

1 相關(guān)工作

1.1 TSP問(wèn)題描述

旅行商問(wèn)題是旅行者要走遍給定數(shù)量的城市，前提這些給定的城市只允許旅行者拜訪一次，要求找出旅行者走遍每個(gè)城市后的最短路徑。一般求解TSP問(wèn)題的算法分為兩大類(lèi)：精確算法和啟發(fā)式算法。精確算法主要有定界法、規(guī)劃法等。啟發(fā)式算法有遺傳算法、模擬退火、粒子群優(yōu)化算法、蟻群優(yōu)化算法等。其中蟻群算法由于具備進(jìn)化思想，為解決旅行商問(wèn)題提供了新的思路。

1.2 蟻群算法求解TSP問(wèn)題

在標(biāo)準(zhǔn)的蟻群算法中，螞蟻根據(jù)式(1)[3]狀態(tài)轉(zhuǎn)移概率規(guī)則，判斷螞蟻下一個(gè)去往的城市。

(1)

式中，τij(t)為t迭代過(guò)程中，城市i與j連接路徑上的信息素值;ηij為城市i與j連接路徑長(zhǎng)度的倒數(shù)值，是一種啟發(fā)式信息，如果城市i與j連接路徑長(zhǎng)度越短，那么螞蟻選擇的下一個(gè)城市越可能是j;Allowedk為螞蟻k未走過(guò)的城市;α和β分別決定了信息素和啟發(fā)因子的重要性。當(dāng)所有螞蟻完成了一次完整的路徑構(gòu)建，即完成一次迭代，此時(shí)信息素的更新將會(huì)按照式(2)[3]進(jìn)行。

(2)

2 改進(jìn)算法

2.1 自適應(yīng)局部信息素更新方式

文獻(xiàn)[2]～文獻(xiàn)[4]的局部信息素更新都是根據(jù)式(3)[3]進(jìn)行的。

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

(3)

式中，ρ為信息素?fù)]發(fā)參數(shù)[3]，取值范圍在[0,1]。這些傳統(tǒng)算法一直把ρ設(shè)置為定值，但是隨著TSP問(wèn)題規(guī)模的改變，就需要不停地通過(guò)實(shí)驗(yàn)去尋找合適的定值，無(wú)疑增加了解決TSP問(wèn)題的時(shí)間，解質(zhì)量也沒(méi)有太大的改善。所以提出式(4)以自適應(yīng)地改變信息素?fù)]發(fā)值。

ρ=kτij(t)

(4)

式中，k為一個(gè)比例因子，在這里設(shè)置為0.5。這樣信息素?fù)]發(fā)值ρ就會(huì)自適應(yīng)地在[0,0.5]間取值，一開(kāi)始路徑上的信息素值很小，這樣ρ的取值也會(huì)取較小值，使得路徑上的信息素?fù)]發(fā)量很少，從而螞蟻釋放在路徑上的信息素保存量就會(huì)增加，加快算法收斂到最優(yōu)路徑上，隨著算法不斷的迭代運(yùn)行，此時(shí)路徑上的信息素就會(huì)不斷增加，這樣ρ的取值也會(huì)相應(yīng)增大，使得路徑上的信息素?fù)]發(fā)量增加，上一代螞蟻釋放在路徑上的信息素量就會(huì)減少，這有助于算法跳出局部最優(yōu)，增加了路徑選取的多樣性，避免了算法過(guò)早地收斂或停滯，從而很好地平衡螞蟻探尋新的路徑和強(qiáng)化已找到的算法最優(yōu)路徑。

2.2 改進(jìn)的全局信息素更新方式

在計(jì)算經(jīng)過(guò)一次迭代過(guò)程所有螞蟻構(gòu)建的總旅行長(zhǎng)度時(shí)，求出本次迭代里的最短總旅行長(zhǎng)度和最長(zhǎng)總旅行長(zhǎng)度，然后對(duì)螞蟻尋找到的最短和最長(zhǎng)總旅行路徑上的全局信息素根據(jù)式(5)進(jìn)行更新。

(5)

式中，Lshorlest(llongest)為螞蟻找到的全局最短(長(zhǎng))總旅行路徑長(zhǎng)度；n為城市總個(gè)數(shù)，引入城市個(gè)數(shù)，阻止因TSP規(guī)模增大使c值趨于零，獎(jiǎng)懲機(jī)制作用力下降。這里改進(jìn)的全局信息素更新策略是通過(guò)獎(jiǎng)勵(lì)(懲罰)當(dāng)前最好(最差)總旅行路徑上的信息素，在強(qiáng)化當(dāng)前迭代找到的全局最優(yōu)解的同時(shí)又削弱最差解對(duì)螞蟻路徑選擇的影響來(lái)實(shí)現(xiàn)的。因?yàn)槭褂玫氖且灾笖?shù)函數(shù)的形式進(jìn)行增減全局信息素的方法，較反比例函數(shù)增減幅度更小一些，這樣TSP問(wèn)題中各路徑上的信息素值差距就不會(huì)很大，某種程度上給予螞蟻更多路徑選擇權(quán)，在加快算法收斂到最優(yōu)解的同時(shí)有效預(yù)防了算法過(guò)早收斂停滯。

2.3 改進(jìn)的子路徑貢獻(xiàn)度

基本的蟻群算法在全局信息素更新中，螞蟻會(huì)增加找到的最優(yōu)路徑的信息素值，然而在最優(yōu)路徑里某些子路徑過(guò)長(zhǎng)時(shí)，螞蟻就會(huì)去增強(qiáng)子路徑較短的路徑，而這些路徑可能不屬于全局最優(yōu)解，這樣會(huì)造成局部最優(yōu)的困境。為了改善這種情況，根據(jù)式(6)、式(7)提出改進(jìn)的子路徑貢獻(xiàn)度的概念，在當(dāng)前迭代最優(yōu)解中，找出子路徑對(duì)全局最優(yōu)路徑貢獻(xiàn)值大于路徑本身貢獻(xiàn)度值的所有子路徑，然后對(duì)這些子路徑一一進(jìn)行信息素再?gòu)?qiáng)化處理，更新公式如下：

lij=d(i,j)/[Lbest(t)-d(i,j)]

(6)

(7)

(8)

在對(duì)當(dāng)前迭代最優(yōu)路徑上的信息素更新后，再根據(jù)式(6)計(jì)算構(gòu)成當(dāng)前迭代最優(yōu)路徑的子路徑貢獻(xiàn)值，q0是一個(gè)閾值，這里設(shè)置為0.3。式(7)表示滿足判別條件的子路徑上信息素強(qiáng)化增量，然后根據(jù)式(8)調(diào)節(jié)子路徑上的信息素終值。

2.4 AU-ACS算法流程

采用AU-ACS算法求解旅行商問(wèn)題的基本步驟如下。

1:INPUT:none

2:OUTPUT:length_best % best solution at any time

3:t=0 % iteration count

4:kib% iteration best ant

5:τ0% initial pheromone trail

6:Nmax% maximum number of iterations

7:parameter initialization

8:while (termination condition not satisfied) do

9:ConstructSolutions

10:length_best←The current iteration finds the best length

11:Local pheromone updates %using Eq.(4)

12:Global pheromone update % using Eq.(5)

13:Path quadratic optimization % using Eq.(6)-(8)

14:Local search optimization % using the 3-Opt algorithm

15:t←t+1

16:if (t≥Nmax) then

17:Terminate program run

18:end while

19:if (the solution didn’t improve very long) then

20:initializes the parameters and rerun the program

21 end

3 仿真實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證提出的AU-ACS算法的理論有效性，選取了TSPLIB(http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/STSP.html)里的典型問(wèn)題集，在CPU為i5-4200M、RAM為8 GB的PC上用Matlab仿真測(cè)試，將AU-ACS算法和ACS算法、MMAS算法(均加入了3-Opt算法)的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比，直觀地得到AU-ACS算法的改進(jìn)效果。本文算法的基本參數(shù)設(shè)置如表1所示。

表1 AU-ACS算法的基本參數(shù)配置

3.1 問(wèn)題求解及對(duì)比

如圖1所示，以eil51為實(shí)驗(yàn)對(duì)象，對(duì)ACS算法添加各類(lèi)改進(jìn)方式進(jìn)行仿真，ACSL、ACSQ、ACSZ、AU-ACS分別是ACS算法添加了自適應(yīng)局部信息素更新方式、改進(jìn)的全局信息素更新方式、改進(jìn)的子路徑更新方式、3種改進(jìn)方式+3Opt[11]算法。如圖1所示，可以看出ACS算法只添加自適應(yīng)局部信息素更新方式，提高了算法搜索的多樣性，但是算法迭代收斂到最優(yōu)解的速度緩慢；只添加改進(jìn)的全局信息素更新方式，提高了算法收斂到最優(yōu)解速度，但是種群多樣性不高，進(jìn)而解精度較差；只添加改進(jìn)的子路徑更新方式，隨著算法的迭代運(yùn)行，提升了解的精度；最后把3種改進(jìn)方式與3Opt算法結(jié)合到ACS算法中進(jìn)行仿真，可以看出既增加了種群多樣性，又加快了算法的收斂到最優(yōu)解的速度。

圖1 ACS添加不同改進(jìn)方式的仿真結(jié)果

選取eil51、eil76、kroA100、kroB150，用AU-ACS、ACS、MMAS這3種算法進(jìn)行實(shí)驗(yàn)，各自實(shí)驗(yàn)20次。對(duì)3種算法的仿真結(jié)果進(jìn)行對(duì)比，如圖2所示，在設(shè)置的3個(gè)TSP問(wèn)題案例中，AU-ACS算法都可以找到問(wèn)題已知最優(yōu)解，分別是：426、538、21282、26130。基于eil51案例中，在前200次的迭代過(guò)程里，相對(duì)于ACS、MMAS算法，AU-ACS算法收斂的速度更快，并且收斂的精確度也更高，在經(jīng)過(guò)500次迭代后，AU-ACS已經(jīng)收斂到了已知最優(yōu)解；基于kroA100案例中，相對(duì)于ACS、MMAS算法，AU-ACS算法收斂速度超快，大約在經(jīng)過(guò)70次迭代后，AU-ACS就已經(jīng)收斂到了已知最優(yōu)解；基于kroB150案例中，相對(duì)于ACS、MMAS算法，在前400次的迭代過(guò)程，AU-ACS的收斂速度更快，雖然ACS算法經(jīng)過(guò)400次迭代后收斂速度略快于AU-ACS算法，但是ACS算法最終卻沒(méi)有找到案例已知最優(yōu)解，MMAS算法雖然在早期迭代過(guò)程中不斷向已知最優(yōu)解收斂，但是在經(jīng)過(guò)600次迭代后，算法陷入了局部最優(yōu)解，削弱了算法尋找更優(yōu)解的能力，算法的多樣性由此降低，AU-ACS算法在1500次迭代后快速收斂于已知最優(yōu)解，從而凸顯了AU-ACS的優(yōu)越性。

3種算法在幾類(lèi)TPS問(wèn)題中的結(jié)果比較如表2所示。

圖2 AU-ACS和ACS、MMAS算法在幾類(lèi)TSP問(wèn)題中的迭代情況

算法TSP已知最優(yōu)值算法最優(yōu)值算法最差值平均值標(biāo)準(zhǔn)差平均誤差/%ACSeil51426426445432.11.34861.4319eil76538540561548.55.64291.9516kroA10021282212822170721498.7262.61391.0182kroB15026130262442766427019.7367.65033.4048MMASeil51426427440432.53.87051.5180eil76538547556549.82.85972.1933kroA10021282212822198121581.5247.35121.4073kroB15026130267952779327252235.66454.2939AU-ACSeil51426426428426.70.94870.1643eil76538538544541.22.65830.5947kroA10021282212822157721357.493.50250.3543kroB15026130261302659626339.0200.04790.7998

如表2所示，對(duì)比算法找到的解質(zhì)量、平均值、標(biāo)準(zhǔn)差、平均誤差(平均值與算法已知最優(yōu)值的差值除以算法已知最優(yōu)值)，AU-ACS算法都更加優(yōu)越、穩(wěn)定。以kroA100為例，3種算法雖然都找到了案例已知最優(yōu)解，但是就平均值而言，AU-ACS算法更接近已知最優(yōu)解值，從平均誤差而言，AU-ACS算法比ACS算法低了0.6639%，比MMAS算法低了1.053%；如圖2所示，AU-ACS算法在490次迭代收斂，比ACS算法快了269，比MMAS算法快了408?？梢钥闯?，AU-ACS算法不管是收斂精度還是收斂速度都更具備優(yōu)越性。以kroB150為例，只有AU-ACS算法找到了問(wèn)題已知最優(yōu)解，從標(biāo)準(zhǔn)差而言，AU-ACS算法比ACS算法小167.6024，比MMAS算法小35.6166；從平均誤差而言，AU-ACS算法比ACS算法低了2.605%，比MMAS算法低了3.4941%。所以AU-ACS算法具有更好的穩(wěn)定性。

3.2 AU-ACS算法找到的TSP問(wèn)題路徑圖

AU-ACS算法找到的幾類(lèi)TPS問(wèn)題路徑圖如圖4～圖7所示。采用AU-ACS算法優(yōu)化路徑，eil51、eil76、kroA100和kroB150這4種TPS的最短距離分別為426，538，21282，26130。

4 結(jié)束語(yǔ)

針對(duì)蟻群算法存在的過(guò)早收斂、搜索時(shí)間長(zhǎng)的問(wèn)題[12-15]，提出了具有自適應(yīng)信息素更新策略的蟻群算法，改進(jìn)的自適應(yīng)策略包括：自適應(yīng)局部信息素更新方式、改進(jìn)的全局信息素更新方式、改進(jìn)的子路徑貢獻(xiàn)度等，這些改進(jìn)策略相互作用共同提高本文算法的性能。實(shí)驗(yàn)結(jié)果表明，AU-ACS算法的最優(yōu)解精度和算法收斂速度都比ACS算法和MMAS算法更優(yōu)越，并且，隨著選擇的TSP案例的城市規(guī)模越大，顯示出的優(yōu)勢(shì)越發(fā)明顯。在接下來(lái)的研究過(guò)程中，將進(jìn)一步研究自適應(yīng)信息素更新策略，從而進(jìn)一步改進(jìn)蟻群算法在TSP問(wèn)題上的應(yīng)用。

圖4 eil51路徑圖

圖5 eil76路徑圖

圖6 kroA100路徑圖

圖7 kroB150路徑圖