基于蟻群算法的廣義擴展雙橋問題的最優解*

?

基于蟻群算法的廣義擴展雙橋問題的最優解*

孫婷1，孫曄1，向新1，許蘊山1，張遠貴2

(1.空軍工程大學,陜西 西安710038； 2.中國人民解放軍95810部隊氣象臺,北京100076)

摘要：在擴展雙橋實驗的基礎上，提出了同時考慮路徑長度和多項邊成本的廣義擴展雙橋問題，該模型是多準則決策問題的基礎模型。提出了一種基于蟻群算法的多準則尋優方法，該方法采用了邊成本矩陣和相應的目標函數描述問題，并將信息素與其相關聯。仿真結果證明，通過合理的參數設置，蟻群算法能有效得出廣義擴展雙橋問題的最優解。同時，退化為擴展雙橋問題時，該算法同樣適用。該實驗有效證明了蟻群算法對于多準則決策問題的解決具有很好的指導意義。

關鍵詞：多準則決策；擴展雙橋實驗；蟻群算法

0引言

雙橋實驗是研究螞蟻通過信息素濃度選擇路徑行為的經典實驗。Marco Dorigo等人在簡單雙橋模型的基礎上，提出了一種擴展雙橋模型[1]。擴展雙橋模型的特點在于，圖的上部是一條不帶環路但并非最短的路徑，圖的下部是一系列路徑的集合，包括2條最短路徑，也包括有限數目的更長的不帶環路的路徑，以及無窮多的更長的帶環路的路徑。擴展雙橋問題是蟻群算法的經典實驗，由于其路徑選擇可能性增大，而且存在環路問題，該問題的求解對于深刻揭示蟻群算法具有重要意義。常規講，擴展雙橋實驗就是以路徑長度最短為準則的決策問題。

但是在實際工作中，可能很難遇見根據單一準則進行決策的情況[2-3]。一般都會從對最優解產生影響的各個方面進行全面的考慮和分析，最終得出全局的最優方案，這類問題就稱為多準則決策問題[4-5]。針對這樣的問題，也有一些研究從其他方面進行考慮，比如Satish Talreja提出了一種新的觀念，針對多準則決策問題，采用了層次分析法進行決策，并利用簡單雙橋問題為背景進行了說明[6]，但是方法具有明顯局限性。遺傳算法[7-8]、粒子群算法[9]等算法也已被運用于該類問題。蟻群算法已被證明能出色地應用于各類組合優化問題[10-11]，是一種并行的高效的元啟發式算法。本文中，以擴展雙橋問題為基礎，討論出現邊成本的情況下如何求解擴展雙橋問題。為了明確起見，在本文中具有邊成本的擴展雙橋問題稱為廣義擴展雙橋問題。該模型即為多準則決策問題的基礎模型，并使用蟻群算法求解，最終證明蟻群算法對于求解多準則決策問題的有效性。

1廣義擴展雙橋模型

廣義擴展雙橋模型如圖1所示。即在擴展雙橋問題中同時考慮路徑長度和多個路徑成本，由尋最短路徑轉化為尋兼顧全局的最優路徑。假設每條邊都有n類不同的路徑成本(圖中標注了第k類成本)，螞蟻經過不同的邊所花費的代價不同。選擇次短路徑成本小但距離較長，而選最短路徑距離短但成本大，如果基于成本考慮則最短距離的選擇不是最優的。在本文中，針對最優策略討論廣義的擴展雙橋問題的解，而原本的擴展雙橋問題是最優策略為最短距離的特殊情況。

圖1　第k類成本時帶邊成本的擴展雙橋的圖示Fig.1　Generalized extended double bridge with cost k

為了討論方便起見，這里設定目標函數為路徑距離和路徑成本的函數，

F=f(Length,Cost1,…，Costi,…，Costn)，

(1)

式中：Length為路徑長度；Costi為其他n項路徑成本。對于最簡單的情況，目標函數可以選取為路徑長度和成本的線性和，ak為加權值，則

(2)

關于路徑成本的建模，考慮到螞蟻是逐點移動的，成本是在逐點移動過程中產生的，為此，本文提出邊成本矩陣C來描述廣義擴展雙橋問題的各邊成本，針對邊成本Costk，有邊成本矩陣如下：

(3)

式中：k表示成本標示，在本文模型中由于選用n類邊成本，應該采用n個邊成本矩陣，且

(4)

采用蟻群算法求解，首先對螞蟻行為進行界定。

(1) 螞蟻從源節點起逐點決策前往目的節點，此過程稱為前向模式，在此過程中，為了防止螞蟻直接返回，前一點排除在下一個擬前往點之外。第k只螞蟻由節點i到節點j的概率為

(5)

式中：Ni為當前節點i的鄰點的集合(不包含該節點的上一點)；τij為節點i和節點j連接邊上累積的信息素值；α為信息素指數。

在前向過程中，螞蟻將按式(1)計算并記錄經過路徑和相應路徑成本。

(2) 螞蟻到達目的節點后按原路徑返回，此過程稱為反向模式，在此過程中，螞蟻將在每邊釋放信息素：

(6)

式中：Q為信息素強度；Fk為第k只螞蟻所走路徑的目標函數值。

則每邊信息素為原有信息素加上一次迭代過程中該邊螞蟻釋放的信息素之和，如下：

τij←τij+∑Δτk.

(7)

考慮到信息素的揮發因素，式(7)可以修正為

τij←(1-ρ)τij+∑Δτk，

(8)

式中：ρ為信息素蒸發系數，蒸發系數的取值關系到算法的收斂行為[12]。

(3) 螞蟻回到原點的時刻不同，先到的螞蟻不受其他螞蟻影響，繼續開始尋找新的路徑。在本文中，每邊的路徑長度相同，并默認單位時間完成一個邊的移動，該單位時間就是算法迭代的一個周期。

蟻群算法的流程圖如圖2所示。

2仿真實驗

在仿真試驗中，為簡單起見本文僅考慮只有一種邊成本的簡單模型。如圖3所示，各點的邊上標注的為路徑成本。

由圖3得到的邊成本矩陣：

圖2　蟻群算法流程圖Fig.2　Flow chart of ACO

圖3　只有一種邊成本的廣義擴展雙橋實驗的圖示Fig.3　Generalized extended double bridge　　　with one kind of edge cost

此時的目標函數簡化為

F=a0·Length+a1·Cost.

(9)

設定a0=1，a1=0.5，取參數α=1，信息素強度Q=1，螞蟻只數m=128，同時設定迭代次數為5 000次。在該問題的求解過程中，考慮了不同信息素蒸發系數(ρ∈{0,0.01,0.1})對實驗結果的影響，結果如圖4所示。

圖4　考慮邊成本時螞蟻路徑生成結果Fig.4　Ant path considering edge cost

圖4中，路徑長度和成本目標函數的平均值是指使用螞蟻最近找到的4m條路徑求得的目標函數值計算得出的。由圖4可得，ρ=0時，即不存在信息素的蒸發時，結果不收斂，目標函數平均值在15附近浮動，螞蟻無法尋找到最優路徑。當信息素蒸發存在(ρ=0.01和ρ=0.1)時，最后結果都達到了收斂。但當蒸發系數過大(ρ=0.1)時，信息素蒸發過快，無法給以后的螞蟻起很好的引導作用，最后都收斂到了次優路徑中。當蒸發系數為一適當的取值(ρ=0.01)時，在信息素的正反饋作用下，螞蟻都收斂到了最優路徑。此時的最優路徑為：1-2-11-14-15-18-19。實驗證明，通過合理地設置參數，蟻群算法能有效地解決廣義擴展雙橋問題。

在特殊情況下，不考慮邊成本時，廣義擴展雙橋問題就退化成了擴展雙橋問題。模型圖與圖3相似，但邊上成本均為0，矩陣C為零矩陣。此時的目標函數為

F=Length=n-1，

(10)

式中：n為螞蟻經過的點數，問題退化為經典的求最短路徑問題。在這種情況下同樣設置了不同的蒸發系數ρ∈{0,0.01,0.1}，觀察了螞蟻找到的路徑的生成情況，結果如圖5所示。由圖可知，不存在信息素的蒸發(ρ=0)時，結果不收斂，平均移動值在7.5附近浮動。當信息素蒸發存在(ρ=0.01和ρ=0.1)時，最后結果都達到了收斂。但ρ=0.1時，結果收斂到了長度為6的次短路徑；ρ=0.01時，所有螞蟻都尋找到了長度為5的最短路徑，即1-2-10-16-18-19。實驗結果與Marco Dorigo給出的結果相符，表明擴展雙橋問題確為廣義雙橋問題的特例。

圖5　不考慮邊成本時螞蟻路徑生成結果Fig.5　Ant path without edge cost

3結束語

由單準則決策問題擴展成多準則決策問題，廣義擴展雙橋模型比擴展雙橋模型具有更強的實用性。本文提出了邊成本矩陣來描述邊成本并給出了求解的目標函數,并使用蟻群算法求得了廣義擴展雙橋問題的最優解。仿真結果證明，通過不同蒸發系數的設置，證明了蟻群算法對于廣義擴展雙橋問題求解的有效性。當不考慮邊成本時，廣義擴展雙橋就退化為擴展雙橋問題。仿真實驗得出了與理論相一致的結果。實驗結果表明，蟻群算法能有效應用于多準則決策問題，對于其他應用也有很好的指導意義。

參考文獻：

[1]DORIGO M ,STUTZLE T. Ant Colony Optimization[M].London: The MIT Press, 2004: 15-20.

[2]張洪波, 湯國建. 彈道導彈防御中多目標攔截的策略[J]. 現代防御技術, 2007, 35(2): 23-26.

ZHANG Hong-bo, TANG Guo-jian. The Tacises of Multitarget Interception in Ballistic Missile Defense[J]. Modern Defense Technology, 2007, 35(2): 23-26.

[3]魏唯, 歐陽丹彤, 呂帥, 等. 動態不確定環境下多目標路徑規劃方法[J]. 計算機學報, 2011, 34(5): 836-847.

WEI Wei, OUYANG Dan-tong, Lü Shuai, et al. Multiobjective Path Planning Under Dynamic Uncertain Environment[J]. Chinese Journal of Computer,2011, 34(5): 836-847.

[4]魏唯, 歐陽丹彤, 呂帥. 一種實時多目標路徑規劃方法[J]. 計算機科學, 2010, 37(7): 236-241.

WEI Wei, OUYANG Dan-tong, Lü Shuai. Real-Time Multiobjective Path Planning[J]. Computer Science,2010, 37(7): 236-241.

[5]郭季, 高博. 多目標路徑規劃方法的研究[J]. 自動化儀表, 2010, 31(7): 8-12.

GUO Ji, GAO Bo. Research on the Method of Path Planning for Multi-Targets[J]. Process Automation Instrumentation, 2010, 31(7): 8-12.

[6]TALREJA S. Transforming the Concept of Double Bridge Experiment[J]. International Journal of Scientific Engineering and Technology(S2277-1581), 2012, 1(4): 107-110.

[7]蔣里強, 高建軍. 裝備維修保障的多目標優化模型研究[J]. 現代防御技術, 2012, 40(1): 150-153.

JIANG Li-qiang, GAO Jian-jun. Research on Multi-Objective Optimization Model of Equipment Maintenance Support[J]. Modern Defense Technology, 2012, 40(1): 150-153.

[8]肖天國,符卓.基于遺傳算法的聯合路徑優化[J].中國科技論文在線,2008, 3(10): 720-724.

XIAO Tian-guo, FU Zhuo. Optimizing Route of Muti-Modal Transportaion Based on Genetic Algotithm[J]. Sciencepaper Online, 2008, 3(10): 720-724.

[9]姚躍亭, 趙建軍, 楊利斌, 等. 發射與制導分離的編隊協同防空目標分配決策[J]. 現代防御技術, 2013, 41(1): 75-81.

YAO Yue-ting, ZHAO Jian-jun, YANG Li-bin, et al. Decision Making on Weapon Target Assignment with Separated Guidance and Fire in Coordinated Air Defense[J]. Modern Defense Technology, 2013, 41(1): 75-81.

[10]DORIGO M, MANIEZZO V, COLORNI A. Ant System: Optimization by a Colony of Cooperating Agents[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 1996, 26(1): 29-41.

[11]SHWETA K. An Experimental Study of Ant System for Solving Traveling Salesman Problem[J]. International Journal of Emerging Technology and Advanced Engineering, 2013, 3(7): 648-650.

[12]RAGHAVENDRA G S, KUMAR P. A Note on the Parameter of Evaporation in the Ant Colony Optimization Algorithm[J]. International Mathematical Forum, 2011, 6(34): 1655-1659.

Ant Colony Optimization Based Solution for Generalized Extended Double Bridge Experiment

SUN Ting1,SUN Ye1, XIANG Xin1, XU Yun-shan1, ZHANG Yuan-gui2

(1.Air Force Engineering University,Shaanxi Xi’an 710038, China;2.PLA,No.95810 Troop,Meteorological Observatory, Beijing 100076, China)

Abstract:On the basis of extended double bridge experiment, a generalized extended double bridge problem, which considers path length and several kinds of edge cost are proposed. And it is a basic model of multiple criterion decision. An ant colony optimization based method for multiple criterion decision is proposed. This method models this problem with edge cost matrix and objective function and associate them with pheromone. The simulation results show that this method can solve generalized extended double bridge problem effectively through a reasonable set of parameters, and can also apply to extended double bridge experiment. This experiment proves that ant colony optimization has a good guidance for multiple criterion decision.

Key words:multiple criterion decision; extended double bridge experiment; ant colony optimization

中圖分類號：TP391.9

文獻標志碼：A

文章編號：1009-086X(2015)-05-0242-05

doi:10.3969/j.issn.1009-086x.2015.05.039

通信地址：038399山西省朔州市懷仁縣親和鄉清水河村付1號E-mail：344578382@qq.com

作者簡介：孫婷(1989-)，女，浙江湖州人。碩士生，主要研究方向為認知無線電、智能算法。

基金項目：國家自然科學基金(61372167)

*收稿日期：2014-05-24；修回日期：2014-08-22