一種求解TSP 問題的改進蟻群算法

馮月華

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

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

1 算法改進策略

1.1 蟻群移動規(guī)則

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

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

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

1.2 信息素的更新策略改進

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

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

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

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

1.4 禁忌策略的改進

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

1.5 算法步驟

改進算法求解TSP 問題的步驟如下：

Step1：初始化

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

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

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

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

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

2 實驗仿真

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

?

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

?

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

3 結(jié)論

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

[1] 郭平，鄢文晉.基于TSP 問題的蟻群算法綜述[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