求解較大規(guī)模TSP問題的改進(jìn)蟻群算法

摘 要：為了優(yōu)化并提高傳統(tǒng)蟻群算法求解較大規(guī)模TSP問題的計算速度，提出了一種基于有限視覺能見度機(jī)制的改進(jìn)蟻群優(yōu)化算法。采用初始解優(yōu)化路徑中節(jié)點間鄰接特征，縮小可選范圍搜索求解，算法時間復(fù)雜度由O（mn2）改進(jìn)為O（mn），最后對可能的沖突問題給出變異解決方案。結(jié)合大規(guī)模TSP問題驗證并加以完善，實驗結(jié)果證明，新算法提高計算速度效果顯著。

關(guān)鍵詞：蟻群算法ACS；TSP；有限視覺能見度

引言

蟻群算法是繼模擬退火、禁忌搜索、遺傳算法等之后的一種新型解決組合優(yōu)化問題的啟發(fā)式智能優(yōu)化算法。蟻群算法的優(yōu)點在于：采用正反饋機(jī)制，有發(fā)現(xiàn)較好解的能力，具有很強(qiáng)的并行性和魯棒性等。但是收斂速度慢，計算時間較長，易過早陷入局部最優(yōu)，在求解連續(xù)優(yōu)化問題上沒有優(yōu)勢。針對這些問題，目前已有了一些改進(jìn)的蟻群算法：

White T等提出了ASGA（ant system with genetic algorithm）算法加入了控制參數(shù)的調(diào)整，更加優(yōu)化[2]，Stüzle T等提出了MMAS（max-min ant system）算法避免算法過早收斂于非全局最優(yōu)解[3]，張紀(jì)會、王穎等提出了自適應(yīng)蟻群算法來提高全局搜索能力和搜索速度[4-5]，丁建立等提出了GAAA（genetic algorithm-ant algorithm）算法融合遺傳算法和蟻群算法的各自優(yōu)點，來取長補(bǔ)短[6]，尚鮮連等提出了一種智能蟻群優(yōu)化算法[7]，采用最近節(jié)點選擇策略進(jìn)行路徑優(yōu)化，但是未能結(jié)合較大規(guī)模TSP問題實現(xiàn)驗證，未考慮處理實際使用中出現(xiàn)的特別情況。文章主要采用有限視覺能見度機(jī)制，結(jié)合大規(guī)模TSP實際應(yīng)用中的特殊情況驗證并進(jìn)行完善，避免在大范圍搜索求解，產(chǎn)生較好的初始螞蟻群，極大提高計算速度，有效解決蟻群算法求解較大規(guī)模問題時的計算時間過長這一缺陷。

1 TSP問題

已知n個城市V={v1，v2，…，vn}和各城市之間的距離dij，尋找一條經(jīng)過各個城市一次且僅一次的最短路徑。

文章選取對稱TSP為基礎(chǔ)，即具備dij=dji特征的對稱矩陣信息來探討TSP問題，特別針對于較大n規(guī)模的TSP問題分析探討。

2 傳統(tǒng)蟻群算法

初始隨機(jī)將m只螞蟻放置在n個城市上，設(shè)置兩兩城市間鄰接邊上初始信息素τs（0）=const（const為一個常量）；禁忌表tabuk記憶螞蟻k已經(jīng)遍歷的城市節(jié)點，初始時刻是起始第一個城市節(jié)點，隨著螞蟻運(yùn)動軌跡的變化動態(tài)調(diào)整，凡是已經(jīng)遍歷過的城市節(jié)點，螞蟻不允許再遍歷該城市節(jié)點。當(dāng)n個城市節(jié)點全部都寫入禁忌表tabuk中，得到一條優(yōu)化路徑。一次循環(huán)完成后，禁忌表tabuk置空，螞蟻又可重新開始選擇，重復(fù)上述過程得到不同路徑。

在生成路徑的過程中，螞蟻根據(jù)當(dāng)前所在位置城市i所對應(yīng)鄰接城市節(jié)點路徑上各信息素及能見度啟發(fā)信息來計算選取下一個節(jié)點的轉(zhuǎn)移概率。規(guī)則如下：若pkij（t）

其中pkij（t）表示在t時刻螞蟻k從節(jié)點i轉(zhuǎn)移到節(jié)點j的轉(zhuǎn)移概率；τij（t）表示t時刻在節(jié)點i和節(jié)點j路徑上的信息素強(qiáng)度；ηij為能見度啟發(fā)因子，表示目標(biāo)城市節(jié)點的能見度，它與距離因子dij成反比，ηij=1/dij；α為信息啟發(fā)因子，表示軌跡重要性；β為期望啟發(fā)因子，表示能見度重要性，不同的數(shù)據(jù)環(huán)境需要根據(jù)情況來設(shè)置調(diào)整相應(yīng)的α和β值。allowedk={1，2，...，n}表示螞蟻k下一步可以選擇的城市，與禁忌表tabuk對應(yīng)。轉(zhuǎn)移概率pkij（t）與ταij（t）ηβij（t）成正比。

當(dāng)螞蟻完成一次循環(huán)，得到相應(yīng)的優(yōu)化解之后，所有路徑段上信息素需要根據(jù)公式（2）調(diào)整：

其中，Δτkij（t，t+1）表示螞蟻k在時刻（t，t+1）釋放在路徑（i，j）上的信息素，路徑越短，信息素釋放的量就越多；Δτij（t，t+1）表示所有螞蟻在本次循環(huán)中經(jīng)過路徑（i，j）時信息素的增量之和；信息素的衰減系數(shù)ρ決定蟻群算法的全局搜索能力及算法的收斂速度，設(shè)置系數(shù)ρ<1來避免路徑上軌跡量的無限增加，（1-ρ）反映螞蟻個體之間相互影響的能力。

3 改進(jìn)蟻群算法

傳統(tǒng)ACS中螞蟻k從當(dāng)前節(jié)點i選擇下一個節(jié)點j時，需要將n-1個節(jié)點與禁忌表比較，時間復(fù)雜度為O（mn）2，再計算n-1個節(jié)點的轉(zhuǎn)移概率，螞蟻在選擇下一節(jié)點之前需要考慮所有可能的節(jié)點集合，時間量也相應(yīng)增大，對于較大規(guī)模的實際問題，搜索時間很長。

3.1 有限視覺能見度機(jī)制

無數(shù)實例表明，在最優(yōu)解對應(yīng)的優(yōu)化回路中城市節(jié)點i的鄰接點僅是離城市i較近的幾個有限城市。為了優(yōu)化選擇，采用有限視覺能見度策略：以螞蟻k所在當(dāng)前節(jié)點i為中心，將螞蟻k的所有可選鄰接點優(yōu)先順序按距離路徑非遞減排列，設(shè)置w個節(jié)點作為有限可選范圍，其中w=n/r，r=1，2，…，20（r的值根據(jù)問題規(guī)模n的大小進(jìn)行適當(dāng)調(diào)整）[8]。

算法設(shè)計一個n×w維有序矩陣，用來記錄每一個節(jié)點對應(yīng)的w個優(yōu)先鄰接城市節(jié)點編號信息矩陣。采用有限視覺能見度，t時刻螞蟻k在節(jié)點i，僅需檢測其所在編號信息矩陣中w個節(jié)點，并與禁忌表tabuk中節(jié)點信息進(jìn)行比較，大大降低可行節(jié)點數(shù)目，同時轉(zhuǎn)移概率計算量也隨之下降，不計算總的迭代次數(shù)NC_max在內(nèi)，時間復(fù)雜度由O（mn2）變?yōu)镺（wmn），其中w是一個常數(shù)，不隨問題規(guī)模n的變化而變化，所以亦可記為O（mn），改進(jìn)蟻群算法計算速度極大提高，由于這種策略得到的螞蟻群初始解較好，避免了過早收斂，出現(xiàn)較差解的可能。

3.2 沖突解決策略

螞蟻k在選擇下一個鄰接點時，往往是選擇幾個距離最近的節(jié)點，即從allowedk所列表中，僅選擇符合dij較小的幾個城市。這種情況下采用ACS在求解大規(guī)模TSP時存在一個很大問題：在求解路徑的后期，第i只螞蟻走完大多數(shù)城市后，搜索到回路中最末尾幾個城市時，剩下可選城市范圍越來越窄，螞蟻i已經(jīng)無法進(jìn)行更多的選擇，這幾個城市間距很遠(yuǎn)，極有可能出現(xiàn)路徑交叉，從一個邊界區(qū)域跳躍至另一個邊界區(qū)域，產(chǎn)生較差的解，影響整個蟻群算法的搜索效率。從ACS的大量實例求解中，可以看到螞蟻優(yōu)化解，這個問題是一個突出矛盾，目前為止尚無好的解決方案。這種現(xiàn)象出現(xiàn)的主要原因是，ACS中螞蟻選擇路徑時沒有考慮剩下城市的整體布局，從而出現(xiàn)了這樣的選擇沖突。

新算法用于解決沖突解決策略采用變異機(jī)制：尋找路徑后期，當(dāng)w個鄰接節(jié)點和禁忌表tabuk相沖突或者路徑長度不能達(dá)到預(yù)期優(yōu)化數(shù)據(jù)時，則轉(zhuǎn)向全局節(jié)點數(shù)據(jù)檢測，突破w個視覺范疇，找到合理的節(jié)點作為下一節(jié)點。同時為了保證尋找的解的優(yōu)越性，采用一定的概率進(jìn)行變異，比較變異前后可行解的差異，選擇兩者中較優(yōu)解為調(diào)整后的結(jié)果。

4 實驗數(shù)據(jù)

結(jié)合Matlab編程實驗環(huán)境，實現(xiàn)了用傳統(tǒng)蟻群算法ACS和改進(jìn)蟻群算法解決較大規(guī)模TSP問題并仿真，以TSPLIB提供的a280和pr1002問題為例。設(shè)置參數(shù)α=2，β=3，在a280問題中螞蟻數(shù)量m=50，近距離城市數(shù)量w=20，pr1002問題中設(shè)置螞蟻數(shù)量m=300，近距離城市w=30。每種情況進(jìn)行運(yùn)行10次以上的試驗運(yùn)行，得到的平均數(shù)據(jù)結(jié)果如表1所示。

基于有限視覺范圍和變異機(jī)制的改進(jìn)蟻群算法在時間復(fù)雜度上有明顯優(yōu)勢，大大提高了算法的計算能力，而且能夠產(chǎn)生良好的蟻群初始解，問題規(guī)模越大，效果越顯著。

圖1為實驗選取a280問題的改進(jìn)算法運(yùn)行結(jié)果仿真之一，在多次求解得到較好解的優(yōu)化路徑曲線和迭代進(jìn)化曲線（平均路徑長度和最短路徑長度）。雖然與圖2中目前已求得的a280問題次優(yōu)路徑曲線有一定差距，但是求解速度已不在同一級別上[8]。

5 結(jié)束語

針對傳統(tǒng)蟻群算法產(chǎn)生初始較好解困難，計算搜索時間過長的特點，結(jié)合較大規(guī)模TSP問題，提出了有限視覺范圍的機(jī)制，使得算法時間復(fù)雜度實現(xiàn)了質(zhì)的飛躍，從二維變?yōu)榱司€性增長，由O（mn2）改進(jìn)為O（mn），極大提高計算速度。對于較大規(guī)模的問題，這點非常必要也是非常重要的，實驗數(shù)據(jù)表明，改進(jìn)算法效率顯著，可行有效。

基于有限視覺能見度的改進(jìn)算法經(jīng)過變異機(jī)制完善，求解得到的較優(yōu)解也并不遜色于傳統(tǒng)ACS算法，雖然離TSPLIB提供的最優(yōu)解還有一定差距，這也正是該算法的魅力所在，需要我們思考和不斷探索更多更先進(jìn)的方法來輔助完善。

參考文獻(xiàn)

[1]Dorigo M， Maniezzo V， Colorni A. The ant system： optimization by a colony of cooperating agents[J].IEEE Trans. on Systems， Man and Cybernetics，1996，1（26）：29-41.

[2]White T，Pagurek B，Oppacher F.ASGA：Improving the ant system by integration with genetic algorithms[R].Canada：Systems and Computer Engineering，Carleton University，1998.

[3]Stützle T，Hoos H.Max-min ant system[J].Future Generation System，2000，16：889-914.

[4]張紀(jì)會，高齊圣，徐心和.自適應(yīng)蟻群算法[J].控制理論與應(yīng)用， 2000，17（1）：1-3.

[5]王穎，謝劍英.一種自適應(yīng)蟻群算法及仿真研究[J].系統(tǒng)仿真學(xué)報， 2002，14（1）：31-33.

[6]丁建立，陳增強(qiáng)，袁著祉.遺傳算法與蟻群算法的融合[J].計算機(jī)研究與發(fā)展，2003，40（9）：1351-1356.

[7]尚鮮連，陳靜，姒茂新.改進(jìn)的智能蟻群算法在TSP問題中的應(yīng)用[J].計算機(jī)仿真，2009，26（12）：160-163.

[8]方霞，席金菊.基于變異和啟發(fā)式選擇的蟻群優(yōu)化算法[J].計算機(jī)工程與應(yīng)用，2013，49（24）：24-27.