卜冠南，劉建華 ，姜 磊，張冬陽

1.福建工程學(xué)院 信息科學(xué)與工程學(xué)院，福州 350118

2.福建省大數(shù)據(jù)挖掘與應(yīng)用技術(shù)重點(diǎn)實(shí)驗(yàn)室，福州 350118

旅行商問題（Traveling Salesman Problem，TSP）是數(shù)學(xué)領(lǐng)域中的著名問題之一。假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑。限制條件是每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是所有路程之中的最小值。TSP是一個(gè)組合優(yōu)化問題，任何能使該問題的求解得以簡化的方法，都將受到高度的評價(jià)和關(guān)注。

20 世紀(jì)90 年代初期科學(xué)家通過實(shí)驗(yàn)發(fā)現(xiàn)，螞蟻在進(jìn)行覓食時(shí)，會在走過的路徑上留下一種對同類有吸引性的化學(xué)物質(zhì)——信息素，螞蟻會根據(jù)信息素濃度的大小來選擇下一條路徑，濃度越高被選中的幾率越大，同時(shí)由于信息素的揮發(fā)特性，較差路徑上的信息素會越來越少，從而最優(yōu)路徑也就能慢慢地被選擇出來。意大利學(xué)者Dorigo等在1996年根據(jù)螞蟻覓食機(jī)制而提出的用來解決旅行商和分布式優(yōu)化問題的一種算法，將其稱為蟻群算法（Ant Colony Optimization，ACO）[1-2]，它應(yīng)用于組合優(yōu)化中具有很強(qiáng)的發(fā)現(xiàn)解的能力，且具有分布式計(jì)算、易于與其他方法相結(jié)合及魯棒性強(qiáng)的優(yōu)點(diǎn)。后來，Dorigo又提出了蟻群系統(tǒng)（Ant Colony System，ACS）[3]，將局部信息素更新與全局信息素更新相結(jié)合，提高算法的收斂速度；2000 年，Stutzle 提出了最大最小蟻群算法（Min-Max Ant System，MMAS）[4]，通過限制信息素的范圍來改善算法中過早停滯的問題；以上是經(jīng)典的螞蟻算法，它們具有高效的搜索能力，但仍存在著容易陷入局部最優(yōu)、收斂速度慢等問題。文獻(xiàn)[5]利用信息素全局更新和局部更新動態(tài)結(jié)合的方法，使當(dāng)前最優(yōu)路徑上的信息素能夠動態(tài)地調(diào)配，幫助算法跳出局部最優(yōu)，避免算法停滯。為了平衡多樣性和收斂速度，文獻(xiàn)[6]定義一種新的方向信息素來刻畫尋優(yōu)過程中的全局信息，從而保證在最優(yōu)路徑的基礎(chǔ)上提高解的全局性，并加快算法的收斂，此外，由于新的探索率因子的提出及全局選擇策略的修正，使得信息素較弱的路徑得以選擇，進(jìn)而擴(kuò)大了搜索的范圍，提高了算法的魯棒性；文獻(xiàn)[7]提出了一種用于求解連續(xù)空間優(yōu)化問題的分組蟻群算法，該算法將連續(xù)空間優(yōu)化問題的定義域劃分成若干個(gè)子區(qū)域，并給每個(gè)子區(qū)域分配一組螞蟻。每組螞蟻在各自的區(qū)域里進(jìn)行搜索，且在搜索過程中采用“精英策略”并利用精英螞蟻更新普通螞蟻的位置信息，以加快算法的收斂速度；文獻(xiàn)[8]設(shè)計(jì)出性能更優(yōu)的分組蟻群算法并應(yīng)用到機(jī)器人路徑規(guī)劃問題中。分組蟻群算法將螞蟻分為兩組，分別放在起點(diǎn)和目標(biāo)點(diǎn)上相向而行搜索路徑，在一定程度上緩解了信息素疊加現(xiàn)象，有助于增加解的多樣性；文獻(xiàn)[9]提出了一種融合貓群算法的動態(tài)分組蟻群算法。借鑒貓群算法中的分工思想，在蟻群系統(tǒng)中引入動態(tài)分組機(jī)制，將螞蟻分為搜索螞蟻和跟蹤螞蟻兩類，其中搜索螞蟻通過路徑構(gòu)建規(guī)劃的改善 使算法在前期多樣性增加，跟蹤螞蟻利用信息素?cái)U(kuò)散機(jī)制對局部信息素進(jìn)行自適應(yīng)更新突出較優(yōu)子路徑的作用，避免算法陷入局部最優(yōu)。以上改進(jìn)的蟻群算法中，在大規(guī)模的旅行商問題中仍然存在容易陷入局部最優(yōu)問題。

文獻(xiàn)[10]的并行蟻群算法中利用分組和不同的溝通策略來加快算法的收斂速度和多樣性。但是，固定的螞蟻分組仍會面臨算法易陷入局部最優(yōu)解的問題。為此，本文提出了一種自適應(yīng)分組蟻群算法。本文通過實(shí)驗(yàn)發(fā)現(xiàn)，蟻群算法的全局搜索能力隨分組數(shù)增多而增強(qiáng)，故本文將參與實(shí)驗(yàn)的螞蟻在算法迭代周期過程中，分為不同的組，算法前期需要較強(qiáng)的全局搜索能力，因此，算法前期分組多，后期分組減少以加快收斂速度。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法的全局搜索能力和收斂速度均優(yōu)于傳統(tǒng)蟻群算法以及并行蟻群算法。

1 蟻群算法基本原理

目前已經(jīng)出現(xiàn)了各種對蟻群算法的改進(jìn)，例如：對算法參數(shù)進(jìn)行優(yōu)化，對信息素更新規(guī)則或路徑構(gòu)建規(guī)則進(jìn)行改進(jìn)[11]，使用其他智能算法進(jìn)行優(yōu)化蟻群算法[12-13]等等，雖然這些改進(jìn)算法在一定程度上改善了算法的性能，但是仍然存在多樣性不足，收斂速度慢等問題。而本文改進(jìn)算法與其他改進(jìn)算法不同的是，基于并行蟻群算法的分組思想，對參與實(shí)驗(yàn)的螞蟻進(jìn)行自適應(yīng)的分組，加強(qiáng)了螞蟻之間的協(xié)作能力和溝通能力，使算法能更好地平衡多樣性與收斂速度。

1.1 蟻群算法原理

在ACS 算法中，螞蟻k當(dāng)前位置在i處，按照偽隨機(jī)比例規(guī)則來選擇下一個(gè)將要訪問的城市j，其規(guī)則如公式（1）：

其中，q是均勻分布在區(qū)間[0，1]上的一個(gè)隨機(jī)變量；q0是一個(gè)參數(shù)，其范圍是[0，1]；J是根據(jù)公式（2）給出的概率分布產(chǎn)生出來的一個(gè)變量。

其中，α為信息啟發(fā)式因子；β為期望啟發(fā)因子；allowk為螞蟻下一步可以直接到達(dá)并且尚未訪問過的城市的集合；ηij為啟發(fā)函數(shù)，其表達(dá)式為式（3）：

其中，dij為i城市與j城市之間的歐氏距離。

1.2 信息素更新規(guī)則

局部信息素更新規(guī)則：螞蟻在進(jìn)行一次路徑選擇時(shí)，即從當(dāng)前城市i到下一個(gè)城市j后，立即更新信息素，如式（4）：

其中，ρ為局部信息素蒸發(fā)系數(shù)，其范圍為（0，1）；τ0為信息素初始值，經(jīng)實(shí)驗(yàn)發(fā)現(xiàn)τij取(n×Lnn)-1時(shí)，算法能擁有較好的性能；n為城市數(shù)目，Lnn是由最近鄰方法得到的路徑長度。

全局信息素更新規(guī)則：所有螞蟻進(jìn)行一次迭代后更新信息素，且只有在全局最優(yōu)路徑上的螞蟻可以更新，這樣加快了算法的收斂速度，如式（5）：

其中，σ為全局信息素蒸發(fā)系數(shù)，Δτij為全局最優(yōu)路徑上增加的信息素，其計(jì)算式如式（6）計(jì)算：

Lbs為全局最優(yōu)路徑的長度。

1.3 并行蟻群系統(tǒng)

并行蟻群系統(tǒng)（Parallel Ant Colony System，PACS）是由臺灣學(xué)者Chu等人在2004年提出的一種新型蟻群算法。后來有很多對于并行蟻群算法的改進(jìn)和應(yīng)用[14-15]。并行蟻群系統(tǒng)中將螞蟻分成若干組，每組螞蟻相互獨(dú)立，每組螞蟻中每只螞蟻即對應(yīng)問題的一個(gè)解。每組螞蟻中的每只螞蟻按照ACS去搜索可行解。每組螞蟻在搜索過程中，每過一定的周期通過七種不同的溝通交流規(guī)則更新信息素濃度，最后直至算法滿足結(jié)束條件使得螞蟻找到一個(gè)最優(yōu)解，并行蟻群系統(tǒng)基本步驟如下：

步驟1初始化分組和螞蟻系統(tǒng)參數(shù)。

步驟2搜索。每組螞蟻按照公式（1）、（2）獨(dú)立進(jìn)行路徑規(guī)劃。

步驟3局部信息素濃度更新。每組螞蟻按照公式（4）更新信息素濃度。

步驟4評價(jià)。計(jì)算每組螞蟻中每只螞蟻所走路徑長度。

步驟5全局信息素濃度更新。每組螞蟻按照公式（7）、（8）更新信息素濃度：

Lg是第g組中螞蟻的最短路徑，σ是一個(gè)信息素衰減常數(shù)。

步驟6通過溝通交流更新信息素。如圖1所示，算法迭代過程中，每過R迭代次數(shù)時(shí)，每組螞蟻溝通交流一次，計(jì)算所有組螞蟻的最短路徑，把求得的最短路徑代入公式（9）、（10）更新信息素：

ε是一個(gè)信息素衰減常數(shù)，Lgb是所有組中螞蟻的最短路徑，即Lgb≤Lg,g=1,2,…,G。

圖1 根據(jù)各組最佳路徑更新信息素水平

步驟7終止。增加循環(huán)計(jì)數(shù)器。移動螞蟻到最初選擇城市，并繼續(xù)步驟2～6，直到停滯或達(dá)到當(dāng)前最大迭代次數(shù)，所有螞蟻?zhàn)呦嗤穆肪€即表示停滯。

2 PACS算法分組大小的分析

PACS對于TSP的搜索效率相較于ACS、AS對TSP的搜索效率是增強(qiáng)的。但是PACS是基于基本的蟻群算法改進(jìn)的算法，故基本蟻群算法面臨的問題對于PACS也是存在的?；镜南伻核惴ㄊ歉鱾€(gè)螞蟻單獨(dú)行動且每只螞蟻都執(zhí)行相同的操作，螞蟻之間的協(xié)作不足，可能會導(dǎo)致滯后、算法陷入局部最優(yōu)以及減少找到最優(yōu)解的可能性等問題。

Chu等學(xué)者的文章中分組數(shù)是固定的，但分組大小對算法的搜索性能影響并未可知。這里通過實(shí)驗(yàn)對不同分組大小的PACS進(jìn)行了分析。這里選用了4個(gè)普遍可用的典型 TSP 數(shù)據(jù)集 st70、gr96、eil101 和 ch130 對蟻群算法和并行蟻群算法在旅行商問題上進(jìn)行性能測試。根據(jù)文獻(xiàn)[16]可知，蟻群算法中螞蟻數(shù)量一般是城市數(shù)量的1～1.5 倍，故選擇80 只螞蟻對4 個(gè)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。把螞蟻分為2 組（每組40 只螞蟻）、4 組（每組20 只螞蟻）、5組（每組16只螞蟻）、8組（每組10只螞蟻）、10組（每組8 只螞蟻）、16 組（每組5 只螞蟻）、20 組（每組4 只螞蟻）。實(shí)驗(yàn)過程中的其他參數(shù)，如啟發(fā)因子，信息素衰減參數(shù)，算法最大迭代次數(shù)等參數(shù)保持一致。信息啟發(fā)因子α=1，期望啟發(fā)因子β=5，常數(shù)q0=0.9，信息素衰減因子ρ=σ=ε=0.1，算法最大迭代次數(shù)tmax=200。每個(gè)數(shù)據(jù)實(shí)驗(yàn)10 次，最后取最短路徑平均值。實(shí)驗(yàn)結(jié)果如表1～4所示。

表1 st70數(shù)據(jù)的實(shí)驗(yàn)結(jié)果

表2 gr96數(shù)據(jù)的實(shí)驗(yàn)結(jié)果

表3 eil101數(shù)據(jù)的實(shí)驗(yàn)結(jié)果

表4 ch130數(shù)據(jù)的實(shí)驗(yàn)結(jié)果

從表1～4 分別是4 組城市數(shù)據(jù)采用PACS 不同分組數(shù)求解最短規(guī)則路徑結(jié)果，圖2演示各組數(shù)據(jù)求解最短路徑值與分組數(shù)的關(guān)系圖?？梢钥闯?，前期隨著分組數(shù)變多，并行蟻群算法得到的最優(yōu)解越好，但是分組數(shù)大約超過8 組后，算法得到的最優(yōu)解慢慢趨于穩(wěn)定，即最優(yōu)解不再隨分組數(shù)增多而變化。從表1～4 中的實(shí)驗(yàn)結(jié)果中發(fā)現(xiàn)，并行蟻群算法分組數(shù)在10 組之后的最優(yōu)解基本不變，還會慢慢變差。由文獻(xiàn)[13]知，分組蟻群算法對螞蟻進(jìn)行均勻分組，每組螞蟻在各自的子區(qū)域內(nèi)采用不同的方法進(jìn)行搜索，每次搜索完后產(chǎn)生新的全局最優(yōu)解。分組這一策略使搜索不易陷入局部最優(yōu)解，也使搜索空間大幅度減??；而且每輪迭代過程中采用了大步長和小步長搜索，使得螞蟻位置的更新更具效率和準(zhǔn)確性。通過這些策略使得算法尋優(yōu)精度和速度都得到了顯著的提高。但是通過圖2分析可知，螞蟻分組并不是越多越好，因?yàn)椴⑿邢伻核惴ㄊ窃谝话阆伻核惴ǖ幕A(chǔ)上提出的，每組螞蟻的實(shí)驗(yàn)運(yùn)行原理還是按照一般蟻群算法的思想在運(yùn)行，故分組多了的話，因螞蟻總數(shù)是固定的，這樣就會導(dǎo)致每組中的螞蟻過少，那么每組螞蟻在算法步驟2中的相對獨(dú)立尋優(yōu)階段就會受到影響，使算法收斂速度降低，全局搜索能力下降，易陷入局部最優(yōu)中。一般并行蟻群算法把螞蟻分到8組以下。

圖2 最短路徑與分組數(shù)的變化關(guān)系

3 一種自適應(yīng)分組的蟻群算法

3.1 自適應(yīng)分析方法

動態(tài)分組機(jī)制將螞蟻分為搜索螞蟻和跟蹤螞蟻，使算法提高了多樣性，即增強(qiáng)了全局搜索能力，也在一定程度上加快了收斂速度。文獻(xiàn)[16]提出了一種分組并行混沌粒子群優(yōu)化算法，通過將種群劃分為若干個(gè)組，每組單獨(dú)計(jì)算，大大提高了收斂速度，且避免早熟和局部最優(yōu)，縮短了迭代時(shí)間。因此，可以知道，通過分組策略可以增強(qiáng)算法的全局搜索能力。由圖2 可以發(fā)現(xiàn)，PACS算法對TSP問題的尋優(yōu)能力隨著分組的不同會發(fā)生一定的變化，分組少時(shí)，尋優(yōu)能力較弱，分組很多時(shí)尋優(yōu)能力也較弱，在分組為8 組左右時(shí)，算法尋優(yōu)能力較強(qiáng)。分組少時(shí)，螞蟻在組與組之間的溝通就會變少，算法趨于全局搜索的機(jī)會就會變少，每組螞蟻過多，趨于局部搜索。螞蟻分組增多時(shí)，螞蟻之間的溝通機(jī)會就會變多，每組螞蟻可以與更多其他組的螞蟻溝通，進(jìn)而搜索到更優(yōu)質(zhì)的路徑，即算法趨于全局搜索。故PACS算法隨著分組增多，全局搜索能力變強(qiáng)，局部搜索能力減弱，且算法的收斂速度明顯加快。

從第1章的分組實(shí)驗(yàn)分析結(jié)果可以看到，螞蟻分組是一個(gè)增加算法全局搜索能力的算法但是又可以看到螞蟻并不是分組越多越好。為了平衡這一點(diǎn)，又由于PACS算法螞蟻間協(xié)作不足，存在陷入局部最優(yōu)的缺陷，故這里提出一種自適應(yīng)分組策略來加強(qiáng)螞蟻間的協(xié)作，稱作自適應(yīng)并行蟻群算法（Adaptive Parallel Ant Colony System，APACS）。在算法前半程分組數(shù)多，增強(qiáng)全局搜索能力，算法后半程分組少，加快算法收斂速度且增強(qiáng)局部搜索能力。因此本文算法迭代分為若干段，分組規(guī)則如下：

μ表示自適應(yīng)分組算子，G表示算法最大分組數(shù)，t表示算法當(dāng)前迭代數(shù)，g(t)表示算法迭代次數(shù)為t時(shí)，算法的分組數(shù)，tmax表示算法最大迭代數(shù)。

3.2 組間信息素融合規(guī)則

由公式（11）可知，自適應(yīng)分組策略是在算法前期分組多，算法后期分組少。因此，算法迭代過程中，每組螞蟻的城市之間的信息素濃度矩陣是相對獨(dú)立的。蟻群算法是啟發(fā)式算法，信息素是隨著算法迭代一直在增加的。根據(jù)自適應(yīng)分組策略組數(shù)減少時(shí)，算法迭代過程中，分組螞蟻需要合并為一組，城市之間信息素濃度矩陣也是要合并。因此，自適應(yīng)分組方法，在兩組合并時(shí)，需要提出一種兩組信息素融合規(guī)則。

一種方式是信息素融合時(shí)，兩組信息素相加，另一種方式是信息素融合時(shí)，取兩組信息素之和的一半。通過分析可知，前者融合方式，會使得信息素在分組變化時(shí)，信息素濃度急劇增加，會導(dǎo)致算法的局部搜索能力過強(qiáng)，進(jìn)而導(dǎo)致算法陷入局部最優(yōu)；后者融合方式，取信息素融合的一半，防止了信息素濃度急劇增多的問題，故選擇后者融合方式。螞蟻分組減少時(shí)，當(dāng)前的信息素濃度矩陣轉(zhuǎn)換為兩組螞蟻信息素之和的1/2。舉例說明，算法前期螞蟻分成8 組，中期分成4 組，后期分成2組，那么在分組減少階段，例如8 組減少為4 組時(shí)，用算法前期的第一組信息素與第五組信息素之和的1/2作為算法中期的第一組；算法前期的第二組信息素與第六組信息素之和的1/2作為算法中期的第二組；以此類推，就能在螞蟻分組減少時(shí)，把信息素融合起來繼續(xù)進(jìn)行算法迭代。如公式（12）所示：

τg(i,j)表示第g組信息素濃度矩陣中第i個(gè)城市到第j個(gè)城市之間信息素。

3.3 算法描述

步驟1參數(shù)初始化。

步驟2將m只螞蟻分成G組，每組螞蟻中的每只螞蟻隨機(jī)放置在不同的初始城市。

步驟3搜索：每組螞蟻按照公式（1）和（2）獨(dú)立進(jìn)行路徑規(guī)劃。

步驟4局部信息素濃度更新：每組螞蟻按照公式（4）更新信息素濃度。

步驟5評價(jià)：計(jì)算每組螞蟻中每只螞蟻所走路徑長度。

步驟6全局信息素濃度更新：每組螞蟻按照公式（7）和（8）更新信息素濃度。

步驟7通過溝通交流更新信息素：如圖1 所示，算法迭代過程中，每迭代R次數(shù)時(shí)，每組螞蟻溝通交流一次，計(jì)算所有組螞蟻的最短路徑，把求得的最短路徑代入公式（9）和（10）更新信息素。R是溝通頻率，是一個(gè)常數(shù)，根據(jù)最大迭代次數(shù)選取。

步驟8增加循環(huán)計(jì)數(shù)器：移動螞蟻到最初選擇城市，并繼續(xù)步驟2～6，直到循環(huán)計(jì)數(shù)器增加到tmax/μ后，算法分組數(shù)目g改變?yōu)樵瓉淼?/2，每組的信息素濃度矩陣按照公式（12）進(jìn)行更新。

步驟9增加循環(huán)計(jì)數(shù)器：繼續(xù)步驟2～8，直到達(dá)到最大迭代數(shù)，結(jié)束。

3.4 時(shí)間復(fù)雜度分析

APACS算法程序

1.開始

2.初始化信息素和參數(shù)

3.計(jì)算城市之間距離

4.For 分組1 →G #螞蟻分為G組

5.For 迭代次數(shù) 1 →tmax

6.For 每組螞蟻i:1 →m #m是每組螞蟻數(shù)量

7.For 城市j:2 →n #n是每組螞蟻數(shù)量

8.構(gòu)建螞蟻的解空間

9.局部信息素更新

10.評價(jià)

11.全局信息素更新

12.通過溝通交流更新信息素

13.End

14.End

15.End

16.End

從以上的算法流程中可以看出，各組螞蟻是獨(dú)立運(yùn)行的，所以APACS的時(shí)間復(fù)雜度是O(tmax×m(1)×(n-1)+tmax×m(2)×(n-1))+…+tmax×m(G)×(n-1)) ，其中m(1)為第一組螞蟻數(shù)量，m(2)為第二組螞蟻數(shù)量，…，m(G)為第G組螞蟻數(shù)量，設(shè)總螞蟻數(shù)為m，則APACS 最大時(shí)間復(fù)雜度為O(tmax×m×n) ，PACS 的最大時(shí)間復(fù)雜度也為O(tmax×m×n) ，ACS 的最大時(shí)間復(fù)雜度也為O(tmax×m×n)。由此，本文的改進(jìn)算法并沒有增加時(shí)間復(fù)雜度。

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

為驗(yàn)證改進(jìn)后的算法性能，本文實(shí)驗(yàn)測試環(huán)境為：Windows10 系統(tǒng)，利用 Matlab2018a 對 TSP 標(biāo)準(zhǔn)數(shù)據(jù)庫中的6 組不同規(guī)模的城市進(jìn)行仿真。在ACS 的實(shí)驗(yàn)基礎(chǔ)上，經(jīng)過實(shí)驗(yàn)參數(shù)的調(diào)節(jié)與數(shù)據(jù)統(tǒng)計(jì)發(fā)現(xiàn)[8]，實(shí)驗(yàn)所使用參數(shù)如表5時(shí)，實(shí)驗(yàn)效果最好。

表5 參數(shù)設(shè)置

實(shí)驗(yàn)內(nèi)容是從TSPLIB 測試案例集中選擇6 組TSP實(shí)例，分別使用ACS、PACS、APACS 三種算法對6 個(gè)不同規(guī)模的城市進(jìn)行求解，求解旅行商問題的最短路徑。每個(gè)算法對每組城市數(shù)據(jù)分別做10 次實(shí)驗(yàn)，求10 次最短路徑的平均最優(yōu)值。本文中最大迭代次數(shù)tmax取為1 000，溝通頻率R與文獻(xiàn)[10]中R取值相同，取為30。

實(shí)驗(yàn)過程中，螞蟻總數(shù)選擇80只，其他參數(shù)設(shè)置如表5 所示。根據(jù)文獻(xiàn)[10]知，對于PACS 算法，選擇將螞蟻分為8 組，每組10 只螞蟻。對于本文提出的APACS算法，算法迭代前期將螞蟻分為8 組較為合適，每組10只螞蟻；算法迭代的中期將螞蟻分為4 組，每組20 只螞蟻；算法迭代后期將螞蟻分為2組，每組40只螞蟻；最后將80只螞蟻放在一組中進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如表6，圖3給出三種算法的實(shí)驗(yàn)結(jié)果對比，圖4 給出參與實(shí)驗(yàn)的6個(gè)不同規(guī)模城市的最優(yōu)解的路徑圖。

表6 ACS、PACS、APACS在不同測試集的性能對比

圖3 ACS，PACS，APACS算法實(shí)驗(yàn)結(jié)果對比

圖4 最優(yōu)路徑

從表6 中數(shù)據(jù)可以發(fā)現(xiàn)，在 oliver30、berlin52 等小規(guī)模的城市實(shí)驗(yàn)結(jié)果，三種算法都可以找到相同的最優(yōu)解，APACS 的平均解優(yōu)于ACS 和PACS，在找到最優(yōu)解的同時(shí)，APACS所需要的迭代次數(shù)最少，APACS能夠快速地找到最優(yōu)解，且最差解均優(yōu)于ACS 和PACS；對于st70、rat99、ch130 以及 rat195 的等中規(guī)模實(shí)驗(yàn)結(jié)果中，APACS 找到的最優(yōu)解，最差解及平均解均優(yōu)于ACS 和PACS算法求得的解。對于中規(guī)模實(shí)驗(yàn)，可以發(fā)現(xiàn)，ACS算法找到的最優(yōu)解較差，且算法迭代前期就停滯了，算法陷入了局部最優(yōu)，無法跑出局部陷阱；PACS 和APACS 算法求得的最優(yōu)解相差不大，APACS 算法較優(yōu)一點(diǎn)，且從最優(yōu)迭代次數(shù)來看，APACS 算法也是優(yōu)于PACS算法的。

分析最佳迭代次數(shù)可以發(fā)現(xiàn)，在小規(guī)模測試集oliver30、Berlin52 和 st70 中發(fā)現(xiàn)，ACS 算法的迭代次數(shù)高于PACS 算法和APACS 算法，在大規(guī)模的測試集rat99、ch130 和 rat195 中，ACS 的算法迭代次數(shù)低于PACS和APACS算法。這是因?yàn)樵谛∫?guī)模測試集中，傳統(tǒng)ACS 算法已陷入局部最優(yōu)的缺陷不明顯，而在大規(guī)模測試集中，傳統(tǒng)ACS 算法易陷入局部最優(yōu)的缺陷明顯加劇，導(dǎo)致在算法迭代過程中，早早陷入了局部最優(yōu)陷阱。而APACS 算法有更強(qiáng)全局搜索能力，易跳出局部最優(yōu)，表現(xiàn)得更好，且能找到更優(yōu)的解。綜合以上，可以發(fā)現(xiàn)本文提出的APACS算法是一個(gè)求解旅行商問題的更好的算法。

從圖3 可以看出，三種算法的收斂性，APACS 算法和PACS 算法明顯優(yōu)于ACS 算法，收斂速度更快，降低了基本蟻群算法前期搜索慢的缺陷。本文提出的APACS 算法相比于PACS 算法能得到更好的最優(yōu)解并且不容易陷入局部最優(yōu)，算法搜索能力更強(qiáng)，搜索速度更快。故通過自適應(yīng)地分組調(diào)節(jié)并行蟻群算法，相較于PACS 算法和ACS 算法得到了更優(yōu)質(zhì)的最短路徑結(jié)果。在相同情況下，改進(jìn)的算法性能更優(yōu)于PACS和一般蟻群算法，從而進(jìn)一步驗(yàn)證了算法的有效性。

5 結(jié)語

本文算法基于Chu等人提出的PACS基礎(chǔ)上加以分析改進(jìn)，發(fā)現(xiàn)分組對螞蟻算法在TSP問題上的尋優(yōu)上有一定的降低算法陷入局部最優(yōu)能力，螞蟻分組多，算法不易陷入局部最優(yōu)好，算法收斂快；螞蟻分組少，算法易陷入局部最優(yōu)，算法收斂慢。故提出了一種自適應(yīng)分組的策略。通過這樣的操作，使得PACS的尋求最優(yōu)解的能力增強(qiáng)，加快了算法尋求最優(yōu)解效率。并通過實(shí)驗(yàn)驗(yàn)證，改進(jìn)的算法優(yōu)于PACS和基本蟻群算法，較好地適用于求解TSP 問題。下一步的研究方向是研究算法迭代前期，怎樣確定最合適的分組數(shù)目。