加權值多態蟻群算法

鮑文杰　朱信忠　趙建民　徐慧英

摘 要：本文提出加權值多態蟻群算法。在信息素初始化時加入權值，加大各條路徑之間的信息素差異，利于螞蟻快速進行路徑選擇；在概率選擇過程中加入權值，提高螞蟻搜索效率；采用了蟻周模型對信息素進行全局更新，并且設置了信息素最大值，避免算法陷入局部最優解。最后采用均勻分布的方法確定參數值，通過仿真實驗結果表明，該方法在TSP問題中具有良好的穩定性和高效性。

關鍵詞：蟻群算法；權值；均勻分布；信息素

中圖分類號：TP301.6 文獻標識碼：A

Abstract：This paper proposes weighted value polymorphic ant colony algorithm.Added weight when pheromone initialization，increased pheromones differences between the paths，beneficial to the ants select path quickly.Added weight when select probability，improve ants search efficiency.Adopted Ant-Cycle System，updated the pheromones and set up the max pheromones ，avoid the algorithm fall into local optima.Adopted evenly distribution method to determine parameter，simulation results show that the algorithm possesses good stability and efficiency.

Keywords：ants colony algorithm；weight；evenly distributed；pheromone

1 引言（Introduction）

旅行商問題（Traveling Salesman Problem，TSP），是一個經典的路徑問題，它可以描述為：在n個城市的范圍內，一個推銷員要遍歷范圍內所有城市推銷自己的商品。該推銷員從一個城市出發，需要經過所有給定的城市后，最后回到出發地的最小路徑成本，故也常被稱作“推銷員問題”。從圖論的角度看，也就是找出一個最短封閉路線的問題[1]。TSP問題是數學領域中一個非常經典的問題之一。

蟻群算法根據螞蟻的群體行為特性，模仿自然界中的螞蟻尋找食物到蟻巢之間最短路徑的行為，尋找搜索問題的最優解。在自然界中真實螞蟻在尋找食物過程中，能夠在其走過的路徑上釋放一種分泌物，稱之為“信息素”，螞蟻可以根據路徑上的信息素濃度來決定前進的方向[2]。早在1911年，意大利學者Dorigo M受到啟發，在他的博士論文中提出了蟻群算法。

2 蟻群算法的數學模型（Ants colony algorithm）

設m表示蟻群中螞蟻的總數量；n表示城市個數；表示城市i的坐標；表示城市i和城市j之間的距離；表示t時刻路徑（i，j）上的信息素濃度；表示t時刻城市i和城市j之間的啟發程度，通常??；為信息素啟發因子；為期望啟發因子；為信息素揮發因子，表示在時間內衰減的系數；表示t時刻路徑上的信息素增量；表示在t時刻，螞蟻k從城市i轉移到城市j的概率；表示螞蟻k禁忌表；將m只螞蟻放置在n個城市上，每個螞蟻通過感知該城市周圍路徑上的信息素濃度，按照下式選擇下一步即將訪問的城市。

顯然，螞蟻轉移概率與信息素濃度成正比，而與路徑長度成反比，也就是說，信息素濃度越大，路徑越短，螞蟻選擇這條路徑的概率就越大。當螞蟻遍歷了地圖上所有城市后，完成一次循環，記為螞蟻k走過的路徑長度，并保存最短路徑。此時清空禁忌表中的所有元素，并把當前所在城市添加到禁忌表中，準備進入下一次遍歷。路徑上的剩余信息素會隨著時間的流逝慢慢揮發，各條路徑上的信息量按照以下規則更新[3]。

其中，表示信息素殘留系數。Dorigo M給出了三種不同的基本蟻群算法模型，用以針對各類不同的信息素更新機制，分別是蟻周模型、蟻量模型和蟻密模型。

3 加權值多態蟻群算法（Weighted value polymorphic ant colony algorithm）

在加權值多態算法設計中，由于工蟻并不參與到路徑尋優的工作中，故在加權值多態蟻群算法中，我們將蟻群分為偵查蟻和搜索蟻，取消了工蟻。其中，m1表示偵查蟻個數；m2表示搜索蟻個數；n表示城市個數；表示信息素權值；表示概率權值；表示最大信息素值；在初始時刻，為了加大各條路徑之間的初始信息素濃度的差異，在信息素初始化時加入權值，使得距離當前螞蟻所在城市較近的城市的初始信息素濃度明顯大于較遠城市，如此一來，螞蟻一開始就會選擇較短路徑，并且有利于后續螞蟻的快速尋優。具體公式如下：

當螞蟻到達一個城市時，就要進行狀態轉移概率選擇。如果螞蟻附近的MAXPC個城市尚未被訪問過，路徑上的偵查素，則在概率選擇過程中加入權值，使得螞蟻以較大概率選擇這些城市。若螞蟻附近的MAXPC個城市全部已經被訪問過，路徑上的偵查素，螞蟻將會根據普通概率公式選擇其余尚未被搜索過的城市，如下公式：

為了防止在某些路徑上的信息素濃度過高，使得所有螞蟻都選擇該路徑，避免算法陷入局部最優，提高螞蟻尋優效率，算法中還借鑒了Thomas等人提出的最大最小蟻群算法（Max-Min Ant System），在算法中加入了信息素濃度最大值，在每次循環中各條路徑上的信息素更新完畢后，對各條路徑上的信息素濃度進行判斷，若信息素濃度大于，則將信息素濃度強制設為。在同一個問題規模中，的值根據循環次數做出調整，一般來說，會隨著循環次數的增加而變大。

加權值多態蟻群算法步驟如下：

步驟1：初始化各個參數值，偵查蟻個數m1，搜索蟻個數m2，城市個數n，常數Q和C，信息素啟發因子，期望啟發因子，加入權值和，最大循環數值，MAXPC，最大信息素值。

步驟2：把m1只偵查蟻放置于n個城市中，每只偵查蟻偵查其他個城市，釋放偵查素。

步驟3：初始化各路徑上的信息素濃度。

步驟4：初始化循環次數NC=0。

步驟5：把m2只搜索蟻隨機放置在n個城市中，每只搜索蟻將當前所在城市添加到禁忌表tabu。

步驟6：根據概率轉移公式，搜索蟻k選擇下一步即將訪問的城市，并且將該城市添加到tabuk，當m2只搜索蟻全部訪問遍所有城市，記為一次迭代。

步驟7：記錄本次循環中的最短路徑。

步驟8：更新各條路徑上的信息素濃度。

步驟9：判斷各路徑上的信息素濃度是否大于，若是，則將其強制設定為。

步驟10：置，清空禁忌表tabuk，。轉至步驟五。

步驟11：輸出最優解。

4 仿真實驗（Simulation）

在蟻群算法求解各類路徑尋優問題中，參數設置是十分重要的一個環節，若各項參數設置不合理，則算法容易陷入局部最優解，不能很好地求得最優解。那么有沒有簡單的方法，能夠快速方便的從這些實驗組合中找到最優組合呢？于是，我們很自然的想到了均勻設計法。根據ATT48TSP，對加權值多態蟻群算法進行實驗。需要確定的參數的取值范圍為：螞蟻數目；信息素揮發因子；

信息素啟發因子；期望啟發式因子；權值；權值；參數個數s=6，選擇均勻設計表。對每組參數進行300次迭代的實驗，最后實驗結果的最小值并且計算出平均值，如圖1所示。

可見，加權值多態蟻群算法不僅可以求得更好的解，還具有更好的高效性。加權值多態蟻群算法是比基本蟻群算法更好更合理的求解TSP問題的方法。這得益于兩個權值和，有了和的加入，螞蟻在進行路徑選擇時，會優先選擇距離較近的城市，大大提高偵查素在尋優過程中起到的作用，并且在加快收斂速度的同時，有效的避免了搜索陷入局部最優解。即使沒有偵查素的存在，螞蟻也可以選擇其他城市，很好的解決了在多態蟻群算法中，螞蟻在同一個城市重復搜索而某些城市不被搜索的問題，并且通過公式，螞蟻可以在更短的時間內尋找到最短路徑，極大地提高了搜索效率，縮小了搜索范圍。

5 結論（Conclusion）

本文通過在算法中加入權值的方法，對多態蟻群算法進行了優化設計，使螞蟻能夠更快的進行路徑選擇，提高螞蟻搜索效率。對信息素更新機制做了改進，避免算法陷入局部最優解。

本文提出的加權值多態蟻群算法不僅可以解決TSP問題，還可以解決一系列無規則的路徑規劃問題，也可擴展到其他領域應用。在此基礎上，將該算法與基本蟻群算法進行比較，進一步說明其優越性。

參考文獻（References）

[1] 宋志飛.基于蟻群算法的TSP問題研究[D].江西理工大學，2012.

[2] 岳鳳.多態蟻群算法及其應用[D].山東師范大學，2009.

[3] 陳建玲.基于蟻群算法的優化問題研究[D].大慶石油學院，2007.