加權(quán)值多態(tài)蟻群算法

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

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

關(guān)鍵詞：蟻群算法；權(quán)值；均勻分布；信息素

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：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）

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

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

2 蟻群算法的數(shù)學(xué)模型（Ants colony algorithm）

設(shè)m表示蟻群中螞蟻的總數(shù)量；n表示城市個(gè)數(shù)；表示城市i的坐標(biāo)；表示城市i和城市j之間的距離；表示t時(shí)刻路徑（i，j）上的信息素濃度；表示t時(shí)刻城市i和城市j之間的啟發(fā)程度，通常?。粸樾畔⑺貑l(fā)因子；為期望啟發(fā)因子；為信息素?fù)]發(fā)因子，表示在時(shí)間內(nèi)衰減的系數(shù)；表示t時(shí)刻路徑上的信息素增量；表示在t時(shí)刻，螞蟻k從城市i轉(zhuǎn)移到城市j的概率；表示螞蟻k禁忌表；將m只螞蟻放置在n個(gè)城市上，每個(gè)螞蟻通過(guò)感知該城市周圍路徑上的信息素濃度，按照下式選擇下一步即將訪問(wèn)的城市。

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

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

3 加權(quán)值多態(tài)蟻群算法（Weighted value polymorphic ant colony algorithm）

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

當(dāng)螞蟻到達(dá)一個(gè)城市時(shí)，就要進(jìn)行狀態(tài)轉(zhuǎn)移概率選擇。如果螞蟻附近的MAXPC個(gè)城市尚未被訪問(wèn)過(guò)，路徑上的偵查素，則在概率選擇過(guò)程中加入權(quán)值，使得螞蟻以較大概率選擇這些城市。若螞蟻附近的MAXPC個(gè)城市全部已經(jīng)被訪問(wèn)過(guò)，路徑上的偵查素，螞蟻將會(huì)根據(jù)普通概率公式選擇其余尚未被搜索過(guò)的城市，如下公式：

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

加權(quán)值多態(tài)蟻群算法步驟如下：

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

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

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

步驟4：初始化循環(huán)次數(shù)NC=0。

步驟5：把m2只搜索蟻隨機(jī)放置在n個(gè)城市中，每只搜索蟻將當(dāng)前所在城市添加到禁忌表tabu。

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

步驟7：記錄本次循環(huán)中的最短路徑。

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

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

步驟10：置，清空禁忌表tabuk，。轉(zhuǎn)至步驟五。

步驟11：輸出最優(yōu)解。

4 仿真實(shí)驗(yàn)（Simulation）

在蟻群算法求解各類路徑尋優(yōu)問(wèn)題中，參數(shù)設(shè)置是十分重要的一個(gè)環(huán)節(jié)，若各項(xiàng)參數(shù)設(shè)置不合理，則算法容易陷入局部最優(yōu)解，不能很好地求得最優(yōu)解。那么有沒(méi)有簡(jiǎn)單的方法，能夠快速方便的從這些實(shí)驗(yàn)組合中找到最優(yōu)組合呢？于是，我們很自然的想到了均勻設(shè)計(jì)法。根據(jù)ATT48TSP，對(duì)加權(quán)值多態(tài)蟻群算法進(jìn)行實(shí)驗(yàn)。需要確定的參數(shù)的取值范圍為：螞蟻數(shù)目；信息素?fù)]發(fā)因子；

信息素啟發(fā)因子；期望啟發(fā)式因子；權(quán)值；權(quán)值；參數(shù)個(gè)數(shù)s=6，選擇均勻設(shè)計(jì)表。對(duì)每組參數(shù)進(jìn)行300次迭代的實(shí)驗(yàn)，最后實(shí)驗(yàn)結(jié)果的最小值并且計(jì)算出平均值，如圖1所示。

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

5 結(jié)論（Conclusion）

本文通過(guò)在算法中加入權(quán)值的方法，對(duì)多態(tài)蟻群算法進(jìn)行了優(yōu)化設(shè)計(jì)，使螞蟻能夠更快的進(jìn)行路徑選擇，提高螞蟻搜索效率。對(duì)信息素更新機(jī)制做了改進(jìn)，避免算法陷入局部最優(yōu)解。

本文提出的加權(quán)值多態(tài)蟻群算法不僅可以解決TSP問(wèn)題，還可以解決一系列無(wú)規(guī)則的路徑規(guī)劃問(wèn)題，也可擴(kuò)展到其他領(lǐng)域應(yīng)用。在此基礎(chǔ)上，將該算法與基本蟻群算法進(jìn)行比較，進(jìn)一步說(shuō)明其優(yōu)越性。

參考文獻(xiàn)（References）

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

[2] 岳鳳.多態(tài)蟻群算法及其應(yīng)用[D].山東師范大學(xué)，2009.

[3] 陳建玲.基于蟻群算法的優(yōu)化問(wèn)題研究[D].大慶石油學(xué)院，2007.