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

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

2、 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 ，

3、 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 ； evenlydistributed ； pheromone1 引言( Introduction )旅行商問題(Traveling Sales

4、man Problem, TSP ,是一個(gè) 經(jīng)典的路徑問題，它可以描述為：在 n 個(gè)城市的范圍內(nèi)，一 個(gè)推銷員要遍歷范圍內(nèi)所有城市推銷自己的商品。該推銷員 從一個(gè)城市出發(fā)，需要經(jīng)過所有給定的城市后，最后回到出 發(fā)地的最小路徑成本，故也常被稱作“推銷員問題”。從圖論的角度看，也就是找出一個(gè)最短封閉路線的問題1。TSP問題是數(shù)學(xué)領(lǐng)域中一個(gè)非常經(jīng)典的問題之一。蟻群算法根據(jù)螞蟻的群體行為特性，模仿自然界中的螞 蟻尋找食物到蟻巢之間最短路徑的行為，尋找搜索問題的最 優(yōu)解。在自然界中真實(shí)螞蟻在尋找食物過程中，能夠在其走 過的路徑上釋放一種分泌物，稱之為“信息素” ，螞蟻可以 根據(jù)路徑上的信息素濃度來決定前

5、進(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ā)程度，通常??；為信息素啟發(fā)因子；為期望啟發(fā)因 子；為信息素?fù)]發(fā)因子，表示在時(shí)間內(nèi)衰減的系數(shù)；表示 t 時(shí)刻路徑上的信息素增量；表示在 t 時(shí)刻，螞蟻 k 從城市 i 轉(zhuǎn)移到城市 j 的概率；表示螞蟻 k 禁忌表；將 m 只螞蟻放置 在 n 個(gè)城市

6、上，每個(gè)螞蟻通過感知該城市周圍路徑上的信息 素濃度，按照下式選擇下一步即將訪問的城市。顯然，螞蟻轉(zhuǎn)移概率與信息素濃度成正比，而與路徑長 度成反比，也就是說，信息素濃度越大，路徑越短，螞蟻選 擇這條路徑的概率就越大。當(dāng)螞蟻遍歷了地圖上所有城市后， 完成一次循環(huán)，記為螞蟻 k 走過的路徑長度，并保存最短路 徑。此時(shí)清空禁忌表中的所有元素，并把當(dāng)前所在城市添加 到禁忌表中，準(zhǔn)備進(jìn)入下一次遍歷。路徑上的剩余信息素會 隨著時(shí)間的流逝慢慢揮發(fā)，各條路徑上的信息量按照以下規(guī) 則更新 3 。其中，表示信息素殘留系數(shù)。 Dorigo M 給出了三種不同 的基本蟻群算法模型，用以針對各類不同的信息素更新機(jī)制， 分

7、別是蟻周模型、蟻量模型和蟻密模型。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)城市，如此一來，螞蟻一開始

8、就會選擇 較短路徑， 并且有利于后續(xù)螞蟻的快速尋優(yōu)。 具體公式如下： 當(dāng)螞蟻到達(dá)一個(gè)城市時(shí)，就要進(jìn)行狀態(tài)轉(zhuǎn)移概率選擇。 如果螞蟻附近的 MAXPC 個(gè)城市尚未被訪問過，路徑上的偵 查素，則在概率選擇過程中加入權(quán)值，使得螞蟻以較大概率 選擇這些城市。若螞蟻附近的 MAXPC 個(gè)城市全部已經(jīng)被訪 問過，路徑上的偵查素，螞蟻將會根據(jù)普通概率公式選擇其 余尚未被搜索過的城市，如下公式： 為了防止在某些路徑上的信息素濃度過高，使得所有螞 蟻都選擇該路徑，避免算法陷入局部最優(yōu)，提高螞蟻尋優(yōu)效 率，算法中還借鑒了 Thomas 等人提出的最大最小蟻群算法 ( Max-Min Ant System )，在算法

9、中加入了信息素濃度最大值， 在每次循環(huán)中各條路徑上的信息素更新完畢后，對各條路徑 上的信息素濃度進(jìn)行判斷，若信息素濃度大于，則將信息素 濃度強(qiáng)制設(shè)為。在同一個(gè)問題規(guī)模中，的值根據(jù)循環(huán)次數(shù)做 出調(diào)整，一般來說，會隨著循環(huán)次數(shù)的增加而變大。 加權(quán)值多態(tài)蟻群算法步驟如下：步驟1 :初始化各個(gè)參數(shù)值，偵查蟻個(gè)數(shù) ml，搜索蟻個(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。

10、步驟 5：把 m2 只搜索蟻隨機(jī)放置在 n 個(gè)城市中，每只 搜索蟻將當(dāng)前所在城市添加到禁忌表 tabu 。步驟 6：根據(jù)概率轉(zhuǎn)移公式，搜索蟻 k 選擇下一步即將 訪問的城市， 并且將該城市添加到 tabuk ，當(dāng) m2 只搜索蟻全 部訪問遍所有城市，記為一次迭代。步驟 7：記錄本次循環(huán)中的最短路徑。步驟 8：更新各條路徑上的信息素濃度。步驟 9：判斷各路徑上的信息素濃度是否大于，若是， 則將其強(qiáng)制設(shè)定為。步驟 10：置，清空禁忌表 tabuk ，。轉(zhuǎn)至步驟五。步驟 11：輸出最優(yōu)解。4 仿真實(shí)驗(yàn)( Simulation ) 在蟻群算法求解各類路徑尋優(yōu)問題中，參數(shù)設(shè)置是十分 重要的一個(gè)環(huán)節(jié)，若各

11、項(xiàng)參數(shù)設(shè)置不合理，則算法容易陷入 局部最優(yōu)解，不能很好地求得最優(yōu)解。那么有沒有簡單的方 法，能夠快速方便的從這些實(shí)驗(yàn)組合中找到最優(yōu)組合呢？于是，我們很自然的想到了均勻設(shè)計(jì)法。根據(jù)ATT48TSP對加權(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ì)表。對每組參數(shù)進(jìn)行300次迭代的實(shí)驗(yàn)，最后實(shí)驗(yàn)結(jié)果的最小值并且計(jì)算出平均值，如圖1 所示。可見，加權(quán)值多態(tài)蟻群算法不僅可以求得更好的解，還 具有更好的高效性。加權(quán)值多態(tài)蟻群算法是比基本蟻群算法 更好更合理的求解 TSP問題的方法。這得益于兩個(gè)權(quán)值

12、和， 有了和的加入，螞蟻在進(jìn)行路徑選擇時(shí)，會優(yōu)先選擇距離較 近的城市，大大提高偵查素在尋優(yōu)過程中起到的作用，并且 在加快收斂速度的同時(shí)，有效的避免了搜索陷入局部最優(yōu)解。 即使沒有偵查素的存在，螞蟻也可以選擇其他城市，很好的 解決了在多態(tài)蟻群算法中，螞蟻在同一個(gè)城市重復(fù)搜索而某 些城市不被搜索的問題，并且通過公式，螞蟻可以在更短的 時(shí)間內(nèi)尋找到最短路徑，極大地提高了搜索效率，縮小了搜 索范圍。5 結(jié)論( Conclusion) 本文通過在算法中加入權(quán)值的方法，對多態(tài)蟻群算法進(jìn) 行了優(yōu)化設(shè)計(jì)，使螞蟻能夠更快的進(jìn)行路徑選擇，提高螞蟻 搜索效率。對信息素更新機(jī)制做了改進(jìn)，避免算法陷入局部最優(yōu)解本文提出的加權(quán)值多態(tài)蟻群算法不僅可以解決TSP問題，