基于自適應更新策略的蟻群算法在TSP上的應用

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

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

1 相關工作

1.1 TSP問題描述

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

1.2 蟻群算法求解TSP問題

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

(1)

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

(2)

2 改進算法

2.1 自適應局部信息素更新方式

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

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

(3)

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

ρ=kτij(t)

(4)

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

2.2 改進的全局信息素更新方式

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

(5)

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

2.3 改進的子路徑貢獻度

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

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

(6)

(7)

(8)

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

2.4 AU-ACS算法流程

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

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 仿真實驗與結果分析

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

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

3.1 問題求解及對比

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

圖1 ACS添加不同改進方式的仿真結果

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

3種算法在幾類TPS問題中的結果比較如表2所示。

圖2 AU-ACS和ACS、MMAS算法在幾類TSP問題中的迭代情況

算法TSP已知最優(yōu)值算法最優(yōu)值算法最差值平均值標準差平均誤差/%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所示，對比算法找到的解質量、平均值、標準差、平均誤差(平均值與算法已知最優(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算法找到了問題已知最優(yōu)解，從標準差而言，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問題路徑圖

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

4 結束語

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

圖4 eil51路徑圖

圖5 eil76路徑圖

圖6 kroA100路徑圖

圖7 kroB150路徑圖