馮月華

（定西師范高等專科學校,743000）

蟻群算法是一種新型的啟發(fā)式仿生類并行智能進化算法，最早是由意大利學者M.Dorigo 于1991 年首次提出，由于該算法具有分布式計算、正反饋機制以及較強的魯棒性（容易與其他算法結合）等優(yōu)點，在許多領域的組合優(yōu)化問題的求解上得到了巨大的應用和成功。但基本的蟻群算法也存在著許多缺點，其中最關鍵的問題之一就是“探索”和“利用”之間的矛盾：既要以信息素的正反饋機制和啟發(fā)因子引導整個蟻群逐漸向最短路徑靠近，也就是利用先驗信息快速搜尋最優(yōu)解，提高收斂速度；但還要鼓勵“探索”，以免收斂速度過快導致算法陷入局部最優(yōu)解。針對算法缺點，學者們提出了許多改進策略：如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），將各邊的信息素控制在（ ， ）范圍之內，并且只對每次迭代中產生的最短路徑的信息素進行更新，使得搜索有效地控制在最短路徑附近，從而更容易找出最優(yōu)解，有效的防止“早熟”和“停滯”問題；還有將信息素動態(tài)更新的改進算法以及模擬真實螞蟻，將螞蟻設計成有分工、分類的多態(tài)蟻群算法。

1 算法改進策略

1.1 蟻群移動規(guī)則

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

螞蟻K 從城市i 轉移到下一個城市j 的概率為：

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

1.2 信息素的更新策略改進

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

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

1.3 信息素的自適應更新策略

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

1.4 禁忌策略的改進

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

1.5 算法步驟

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

Step1：初始化

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

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

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

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

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

2 實驗仿真

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

?

eil51 算例中包含51 分城市，算法對其運算的結果為表2 所示，通過40 次獨立運行的實驗結果數(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 結論

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

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