一種求解TSP 問題的改進(jìn)蟻群算法

馮月華

（定西師范高等專科學(xué)校,743000）

蟻群算法是一種新型的啟發(fā)式仿生類并行智能進(jìn)化算法，最早是由意大利學(xué)者M(jìn).Dorigo 于1991 年首次提出，由于該算法具有分布式計(jì)算、正反饋機(jī)制以及較強(qiáng)的魯棒性（容易與其他算法結(jié)合）等優(yōu)點(diǎn)，在許多領(lǐng)域的組合優(yōu)化問題的求解上得到了巨大的應(yīng)用和成功。但基本的蟻群算法也存在著許多缺點(diǎn)，其中最關(guān)鍵的問題之一就是“探索”和“利用”之間的矛盾：既要以信息素的正反饋機(jī)制和啟發(fā)因子引導(dǎo)整個(gè)蟻群逐漸向最短路徑靠近，也就是利用先驗(yàn)信息快速搜尋最優(yōu)解，提高收斂速度；但還要鼓勵(lì)“探索”，以免收斂速度過快導(dǎo)致算法陷入局部最優(yōu)解。針對算法缺點(diǎn)，學(xué)者們提出了許多改進(jìn)策略：如M.Dorigo 提出的無論全局搜索能力還是收斂速度都有明顯提高的蟻群系統(tǒng)（Ant Colony System，ACS）；額外強(qiáng)化每次迭代的中找到的最優(yōu)解的信息素濃度以提高收斂速度的帶精英的蟻群算法（Ant System with Elitist Strategy，ASelit），但是該算法陷入局部最優(yōu)解時(shí)很難跳出來；針對該問題，Stutsle T. 提出了最大最小蟻群算法（Max-Min Ant System，MMAS），將各邊的信息素控制在（ ， ）范圍之內(nèi)，并且只對每次迭代中產(chǎn)生的最短路徑的信息素進(jìn)行更新，使得搜索有效地控制在最短路徑附近，從而更容易找出最優(yōu)解，有效的防止“早熟”和“停滯”問題；還有將信息素動(dòng)態(tài)更新的改進(jìn)算法以及模擬真實(shí)螞蟻，將螞蟻設(shè)計(jì)成有分工、分類的多態(tài)蟻群算法。

1 算法改進(jìn)策略

1.1 蟻群移動(dòng)規(guī)則

在基本的蟻群算法中，如果到幾個(gè)城市的信息量相差無幾，讓螞蟻根據(jù)概率公式選取下一次要搜索的較優(yōu)城市是十分困難的。因此對概率公式做了如下改進(jìn)：

螞蟻K 從城市i 轉(zhuǎn)移到下一個(gè)城市j 的概率為：

其中，q0先給定的（0,1）之間的參數(shù)，q 是在0～1 之間的隨機(jī)數(shù)，當(dāng)q> q0采用隨機(jī)性搜索，按照公式（2）計(jì)算概率，從中選擇其值最大的一條路徑；當(dāng)q<=q0時(shí)，螞蟻采用確定性搜索，按公式（1）選擇距離短且信息量多的路徑，這種利用先驗(yàn)信息指導(dǎo)路徑選擇的策略提高了算法的收斂速度。q0調(diào)節(jié)了“利用”和“探索”之間的平衡，因此它的取值十分重要： q0的取值過大，大多數(shù)螞蟻就會(huì)選擇同一條路徑（不一定是全局最優(yōu)解），算法容易陷入局部最優(yōu)解；如果取值過小，搜索就會(huì)變得很盲目，這樣算法的收斂速度就會(huì)受到影響。因此，通常情況下， q0的前期取值為0.5，后期取值為0.9。

1.2 信息素的更新策略改進(jìn)

為了不使啟發(fā)因子被殘留信息量淹沒，在每次搜索結(jié)束后，要將殘留信息素進(jìn)行更新。帶精英策略的蟻群算法的信息素的更新方法為：

在搜索后期，蟻群已經(jīng)接近全局最優(yōu)解的時(shí)候， 的值已經(jīng)足夠大，該路徑上的信息素的總和也已經(jīng)足夠多，并且算法的收斂速度也夠快，再繼續(xù)增加信息量的意義不是太大了，而且這個(gè)時(shí)候收斂速度過快反而降低了蟻群在已知最優(yōu)解周圍探索的能力，因此將（6）式中的 的值修改為：

1.3 信息素的自適應(yīng)更新策略

蟻群算法研究的一個(gè)核心問題就是在“探索”和“利用”之間尋找一個(gè)平衡點(diǎn)。為信息素的揮發(fā)因子，當(dāng)過小時(shí)，路徑上的信息素過高，導(dǎo)致全局搜索能力過低；當(dāng)過大時(shí)，路徑上的殘留信息素過低，算法的收斂速度就會(huì)變慢。改進(jìn)算法用下式的自適應(yīng)策略調(diào)節(jié)：

1.4 禁忌策略的改進(jìn)

在許多改進(jìn)的蟻群算法中很容易出現(xiàn)停滯狀態(tài)：算法在當(dāng)前的最短路徑附近搜索了很多次，但最優(yōu)解并沒有更新，在這種情況下可以說明全局最優(yōu)解并不在附近，然而算法卻不能及時(shí)跳出。再建立一個(gè)禁忌表禁忌掉搜尋了很多次而最短路徑?jīng)]有更新的路徑及附近路徑，然后轉(zhuǎn)到其他路徑上繼續(xù)搜索。在沒有禁忌掉的其他所有路徑中，找出最短路徑繼續(xù)搜索，如果新的最短路徑比剛才禁忌掉的路徑更優(yōu)，為了充分利用先驗(yàn)知識(shí)、加快收斂速度，再將新的最短路徑的信息素作為全局最短路徑來更新。

1.5 算法步驟

改進(jìn)算法求解TSP 問題的步驟如下：

Step1：初始化

設(shè)NC=0、MaxNc=5000，計(jì)算任意兩個(gè)城市之間的距離，得到啟發(fā)因子的初始矩陣；對所有邊Lij 上的信息素賦初值；將m 只螞蟻放置在n 個(gè)城市上，并更新對應(yīng)的禁忌表；

Step3：判斷螞蟻是否訪問完所有城市，計(jì)算每只螞蟻的路徑長度；否則轉(zhuǎn)到step2 繼續(xù)搜索；

Step4：選出最短路徑，按照公式對信息素進(jìn)行更新，并對路徑上的信息素進(jìn)行調(diào)整；

Step5：如果N 次循環(huán)中最短路徑?jīng)]有改進(jìn)，將此路徑和其附近路徑置入禁忌表；

Step6：判斷是否滿足條件，滿足條件輸出；如果不滿足條件，轉(zhuǎn)到step2。

2 實(shí)驗(yàn)仿真

為了證明算法的有效性，采用TSPLIB 庫中的eil51 問題進(jìn)行測試，通過Matlab 編程，并在Intel 2.0G 的CPU、1G 內(nèi)存的計(jì)算機(jī)上運(yùn)行，試驗(yàn)參數(shù)為表1 所示。

?

eil51 算例中包含51 分城市，算法對其運(yùn)算的結(jié)果為表2 所示，通過40 次獨(dú)立運(yùn)行的實(shí)驗(yàn)結(jié)果數(shù)據(jù)與ACS 以及帶精英的MMAS 算法相比較，表明本文改進(jìn)算法得到的解更優(yōu)，算法更穩(wěn)定。圖1 為改進(jìn)算法得到的最優(yōu)解的搜索圖。

?

圖2 是改進(jìn)算法和帶精英的最大最小算法收斂性能的比較，改進(jìn)算法在30 次后基本收斂，最差收斂到456，最好收斂到428。在求解過程中兩種算法都能朝全局最優(yōu)解能不斷收斂，但改進(jìn)算法的收斂速度更快一些，得到的最優(yōu)解更優(yōu)，因此，與帶精英的MMAS 相比，改進(jìn)的蟻群算法更優(yōu)。

3 結(jié)論

本文在帶精英的MMAS 的基礎(chǔ)上對蟻群算法從信息素動(dòng)態(tài)調(diào)整策略、禁忌策略上做了進(jìn)一步改進(jìn)，實(shí)驗(yàn)證明改進(jìn)算法更優(yōu)，更穩(wěn)定。但是改進(jìn)算法在大規(guī)模的TSP 問題中尋優(yōu)能力就會(huì)有所減弱，如何改進(jìn)該問題以及對算法中采用怎樣的參數(shù)自適應(yīng)調(diào)整策略能進(jìn)一步提高算法性能，還有待于進(jìn)一步研究。

[1] 郭平，鄢文晉.基于TSP 問題的蟻群算法綜述[J].計(jì)算機(jī)科學(xué)，2007.35（10）：181～184

[2] BULLNHEIMER B,HARTL R F,STRAUSS C.A new rank based verion of the ant system:a computational study[R].Vienna.University of Vienna,1997

[3] STUTZLE T，HO0S H H.MAX-MIN ant system[J]. Future Generation Computer System，2000.16(8): 889-914