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

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

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

1 相關工作

1.1 TSP問題描述

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

1.2 蟻群算法求解TSP問題

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

(1)

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

(2)

2 改進算法

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

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

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

(3)

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

ρ=kτij(t)

(4)

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

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

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

(5)

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

2.3 改進的子路徑貢獻度

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

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

(6)

(7)

(8)

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

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算法的改進效果。本文算法的基本參數設置如表1所示。

表1 AU-ACS算法的基本參數配置

3.1 問題求解及對比

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

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

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

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

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

算法TSP已知最優值算法最優值算法最差值平均值標準差平均誤差/%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所示，對比算法找到的解質量、平均值、標準差、平均誤差(平均值與算法已知最優值的差值除以算法已知最優值)，AU-ACS算法都更加優越、穩定。以kroA100為例，3種算法雖然都找到了案例已知最優解，但是就平均值而言，AU-ACS算法更接近已知最優解值，從平均誤差而言，AU-ACS算法比ACS算法低了0.6639%，比MMAS算法低了1.053%；如圖2所示，AU-ACS算法在490次迭代收斂，比ACS算法快了269，比MMAS算法快了408。可以看出，AU-ACS算法不管是收斂精度還是收斂速度都更具備優越性。以kroB150為例，只有AU-ACS算法找到了問題已知最優解，從標準差而言，AU-ACS算法比ACS算法小167.6024，比MMAS算法小35.6166；從平均誤差而言，AU-ACS算法比ACS算法低了2.605%，比MMAS算法低了3.4941%。所以AU-ACS算法具有更好的穩定性。

3.2 AU-ACS算法找到的TSP問題路徑圖

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

4 結束語

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

圖4 eil51路徑圖

圖5 eil76路徑圖

圖6 kroA100路徑圖

圖7 kroB150路徑圖