?

基于蟻群算法的廣義擴展雙橋問題的最優(yōu)解*

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

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

摘要：在擴展雙橋?qū)嶒灥幕A(chǔ)上，提出了同時考慮路徑長度和多項邊成本的廣義擴展雙橋問題，該模型是多準(zhǔn)則決策問題的基礎(chǔ)模型。提出了一種基于蟻群算法的多準(zhǔn)則尋優(yōu)方法，該方法采用了邊成本矩陣和相應(yīng)的目標(biāo)函數(shù)描述問題，并將信息素與其相關(guān)聯(lián)。仿真結(jié)果證明，通過合理的參數(shù)設(shè)置，蟻群算法能有效得出廣義擴展雙橋問題的最優(yōu)解。同時，退化為擴展雙橋問題時，該算法同樣適用。該實驗有效證明了蟻群算法對于多準(zhǔn)則決策問題的解決具有很好的指導(dǎo)意義。

關(guān)鍵詞：多準(zhǔn)則決策；擴展雙橋?qū)嶒?；蟻群算?/p>

0引言

雙橋?qū)嶒炇茄芯课浵佂ㄟ^信息素濃度選擇路徑行為的經(jīng)典實驗。Marco Dorigo等人在簡單雙橋模型的基礎(chǔ)上，提出了一種擴展雙橋模型[1]。擴展雙橋模型的特點在于，圖的上部是一條不帶環(huán)路但并非最短的路徑，圖的下部是一系列路徑的集合，包括2條最短路徑，也包括有限數(shù)目的更長的不帶環(huán)路的路徑，以及無窮多的更長的帶環(huán)路的路徑。擴展雙橋問題是蟻群算法的經(jīng)典實驗，由于其路徑選擇可能性增大，而且存在環(huán)路問題，該問題的求解對于深刻揭示蟻群算法具有重要意義。常規(guī)講，擴展雙橋?qū)嶒灳褪且月窂介L度最短為準(zhǔn)則的決策問題。

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

1廣義擴展雙橋模型

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

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

為了討論方便起見，這里設(shè)定目標(biāo)函數(shù)為路徑距離和路徑成本的函數(shù)，

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

(1)

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

(2)

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

(3)

式中：k表示成本標(biāo)示，在本文模型中由于選用n類邊成本，應(yīng)該采用n個邊成本矩陣，且

(4)

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

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

(5)

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

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

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

(6)

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

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

τij←τij+∑Δτk.

(7)

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

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

(8)

式中：ρ為信息素蒸發(fā)系數(shù)，蒸發(fā)系數(shù)的取值關(guān)系到算法的收斂行為[12]。

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

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

2仿真實驗

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

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

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

圖3　只有一種邊成本的廣義擴展雙橋?qū)嶒灥膱D示Fig.3　Generalized extended double bridge　　　with one kind of edge cost

此時的目標(biāo)函數(shù)簡化為

F=a0·Length+a1·Cost.

(9)

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

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

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

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

F=Length=n-1，

(10)

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

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

3結(jié)束語

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

參考文獻：

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

[2]張洪波, 湯國建. 彈道導(dǎo)彈防御中多目標(biāo)攔截的策略[J]. 現(xiàn)代防御技術(shù), 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]魏唯, 歐陽丹彤, 呂帥, 等. 動態(tài)不確定環(huán)境下多目標(biāo)路徑規(guī)劃方法[J]. 計算機學(xué)報, 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]魏唯, 歐陽丹彤, 呂帥. 一種實時多目標(biāo)路徑規(guī)劃方法[J]. 計算機科學(xué), 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]郭季, 高博. 多目標(biāo)路徑規(guī)劃方法的研究[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]蔣里強, 高建軍. 裝備維修保障的多目標(biāo)優(yōu)化模型研究[J]. 現(xiàn)代防御技術(shù), 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]肖天國,符卓.基于遺傳算法的聯(lián)合路徑優(yōu)化[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]姚躍亭, 趙建軍, 楊利斌, 等. 發(fā)射與制導(dǎo)分離的編隊協(xié)同防空目標(biāo)分配決策[J]. 現(xiàn)代防御技術(shù), 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

文獻標(biāo)志碼：A

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

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

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

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

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

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