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

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

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

引言

蟻群算法是繼模擬退火、禁忌搜索、遺傳算法等之后的一種新型解決組合優(yōu)化問題的啟發(fā)式智能優(yōu)化算法。蟻群算法的優(yōu)點(diǎn)在于：采用正反饋機(jī)制，有發(fā)現(xiàn)較好解的能力，具有很強(qiáng)的并行性和魯棒性等。但是收斂速度慢，計(jì)算時(shí)間較長(zhǎng)，易過早陷入局部最優(yōu)，在求解連續(xù)優(yōu)化問題上沒有優(yōu)勢(shì)。針對(duì)這些問題，目前已有了一些改進(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ì)會(huì)、王穎等提出了自適應(yīng)蟻群算法來提高全局搜索能力和搜索速度[4-5]，丁建立等提出了GAAA（genetic algorithm-ant algorithm）算法融合遺傳算法和蟻群算法的各自優(yōu)點(diǎn)，來取長(zhǎng)補(bǔ)短[6]，尚鮮連等提出了一種智能蟻群優(yōu)化算法[7]，采用最近節(jié)點(diǎn)選擇策略進(jìn)行路徑優(yōu)化，但是未能結(jié)合較大規(guī)模TSP問題實(shí)現(xiàn)驗(yàn)證，未考慮處理實(shí)際使用中出現(xiàn)的特別情況。文章主要采用有限視覺能見度機(jī)制，結(jié)合大規(guī)模TSP實(shí)際應(yīng)用中的特殊情況驗(yàn)證并進(jìn)行完善，避免在大范圍搜索求解，產(chǎn)生較好的初始螞蟻群，極大提高計(jì)算速度，有效解決蟻群算法求解較大規(guī)模問題時(shí)的計(jì)算時(shí)間過長(zhǎng)這一缺陷。

1 TSP問題

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

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

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

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

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

其中pkij（t）表示在t時(shí)刻螞蟻k從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的轉(zhuǎn)移概率；τij（t）表示t時(shí)刻在節(jié)點(diǎn)i和節(jié)點(diǎn)j路徑上的信息素強(qiáng)度；ηij為能見度啟發(fā)因子，表示目標(biāo)城市節(jié)點(diǎn)的能見度，它與距離因子dij成反比，ηij=1/dij；α為信息啟發(fā)因子，表示軌跡重要性；β為期望啟發(fā)因子，表示能見度重要性，不同的數(shù)據(jù)環(huán)境需要根據(jù)情況來設(shè)置調(diào)整相應(yīng)的α和β值。allowedk={1，2，...，n}表示螞蟻k下一步可以選擇的城市，與禁忌表tabuk對(duì)應(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在時(shí)刻（t，t+1）釋放在路徑（i，j）上的信息素，路徑越短，信息素釋放的量就越多；Δτij（t，t+1）表示所有螞蟻在本次循環(huán)中經(jīng)過路徑（i，j）時(shí)信息素的增量之和；信息素的衰減系數(shù)ρ決定蟻群算法的全局搜索能力及算法的收斂速度，設(shè)置系數(shù)ρ<1來避免路徑上軌跡量的無限增加，（1-ρ）反映螞蟻個(gè)體之間相互影響的能力。

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

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

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

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

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

3.2 沖突解決策略

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

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

4 實(shí)驗(yàn)數(shù)據(jù)

結(jié)合Matlab編程實(shí)驗(yàn)環(huán)境，實(shí)現(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)運(yùn)行，得到的平均數(shù)據(jù)結(jié)果如表1所示。

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

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

5 結(jié)束語

針對(duì)傳統(tǒng)蟻群算法產(chǎn)生初始較好解困難，計(jì)算搜索時(shí)間過長(zhǎng)的特點(diǎn)，結(jié)合較大規(guī)模TSP問題，提出了有限視覺范圍的機(jī)制，使得算法時(shí)間復(fù)雜度實(shí)現(xiàn)了質(zhì)的飛躍，從二維變?yōu)榱司€性增長(zhǎng)，由O（mn2）改進(jìn)為O（mn），極大提高計(jì)算速度。對(duì)于較大規(guī)模的問題，這點(diǎn)非常必要也是非常重要的，實(shí)驗(yàn)數(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ì)會(huì)，高齊圣，徐心和.自適應(yīng)蟻群算法[J].控制理論與應(yīng)用， 2000，17（1）：1-3.

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

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

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

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