王文國，樊麗娟，劉 洋

（曲阜師范大學 信息科學與工程學院，山東 日照 276826）

改進的蟻群算法與網(wǎng)絡(luò)QoS組播路由研究

王文國，樊麗娟，劉 洋

（曲阜師范大學 信息科學與工程學院，山東 日照 276826）

組播路由和網(wǎng)絡(luò)服務(wù)質(zhì)量（QoS），是當前Internet研究的兩個重要應(yīng)用課題。QoS組播路由是尋找滿足特定QoS約束的一棵最優(yōu)組播樹，是一個典型的NPC完全多目標優(yōu)化問題。針對傳統(tǒng)蟻群算法，首次引入“蟻王”概念，使其能對路徑尋優(yōu)過程進行存儲、排序和指導，從而使群體搜索過程更加協(xié)調(diào)有序。蟻群信息素的變化則采用精英信息素矩陣更新策略，以加快算法的收斂速度。相關(guān)仿真實驗證明，這種改進的算法在解決QoS組播問題時，能夠獲得比基本蟻群算法明顯優(yōu)越的收斂性能。

蟻群算法；QoS組播路由；精英信息素；蟻王

0 引 言

蟻群算法（Ant Colony Optimization，ACO）是通過螞蟻個體在候選解的空間中獨立搜索解，并在搜尋的解上留下一定量的信息素；螞蟻間以信息素為媒介進行間接、異步的信息傳遞。隨著算法的推進，較優(yōu)解路徑上的信息素濃度會不斷增加，同時其他路徑上信息素濃度隨著時間逐漸變?nèi)?；當算法趨于收斂時，在最優(yōu)解路徑上的信息素濃度最大。整個蟻群算法的最優(yōu)解路徑，在螞蟻個體的共同協(xié)作下求得。意大利學者Dorigo等人通過模擬螞蟻尋路覓食的群體行為提出了蟻群算法[1]，具有正反饋、分布式計算和貪婪啟發(fā)式搜索的特點，廣泛用于求解復雜的組合優(yōu)化等問題[2-4]。近年來，也一些學者對該算法提出了若干優(yōu)化方案[5-8]，并在不同應(yīng)用領(lǐng)域進行了有益探索。

1 基本蟻群算法

1.1 路徑選擇公式

假設(shè)有m只螞蟻放入到n個隨機選擇的需求節(jié)點中，每只螞蟻根據(jù)路徑上信息素的濃度選擇下一個未訪問的節(jié)點；每完成一步或者一個循環(huán)后，將更新調(diào)整所有路徑上的信息濃度。設(shè)dij是節(jié)點i到節(jié)點j的距離；ηij是邊(i,j)的能見度，ηij=1/dij，反映由節(jié)點i轉(zhuǎn)移到節(jié)點j的啟發(fā)程度；τij是路徑(i,j)上的信息素軌跡強度；是螞蟻k在路徑(i,j)上留下的單位長度軌跡信息素量；pijk是螞蟻k從節(jié)點i轉(zhuǎn)移到節(jié)點j的狀態(tài)轉(zhuǎn)移概率；j是未訪問的節(jié)點。

螞蟻k在t時刻由節(jié)點i選擇節(jié)點j的狀態(tài)轉(zhuǎn)移概率為

式中，allowedk={0,1,…,n-1}表示螞蟻k下一步允許選擇的路線。α和β為兩個參數(shù)，分別反映螞蟻在運動過程中積累的信息和啟發(fā)信息在螞蟻選擇路徑中的相對重要性。同時，為每只螞蟻設(shè)計一個禁忌表tabuk(k=1,2,…,m)，記錄t時刻螞蟻k已走過的節(jié)點，禁止螞蟻在本次循環(huán)中重復經(jīng)過。循環(huán)結(jié)束后，清空禁忌表。

1.2 信息素更新

所有螞蟻完成一次循環(huán)后，根據(jù)各螞蟻遍歷的適應(yīng)度值，計算信息素增量，更新路徑上的信息素。更新規(guī)則如下：

式中，ρ為信息素軌跡衰減系數(shù)，Δτijk(t,t+1)表示第k只螞蟻在(t,t+1)時刻留在(i,j)路徑上的信息素量，表示路徑(i,j)的信息素增量。

其中，Q表示初始信息素，為常量，其值由實驗確定；Lk表示第k只螞蟻在本次循環(huán)中所走路線的費用值（可以表示為長度）。

2 引入蟻王概念的改進蟻群算法

在構(gòu)造解的過程中，蟻群算法因為采用隨機選擇策略使得算法的進化速度變慢，而正反饋原理旨在強化性能較好的解，因此失去了隨機性，大量螞蟻會選擇同一條路徑，從而使搜索到的路徑失去了多樣性，此時算法容易出現(xiàn)停滯現(xiàn)象并陷入局部最優(yōu)解。

為了對傳統(tǒng)蟻群算法進行改進，在蟻群中引入“蟻王”（或叫蟻后）概念。假設(shè)蟻王能夠保存搜索到的所有候選解，并對路徑進行比較排序，進而迅速發(fā)現(xiàn)全局最優(yōu)解。目的是對群體搜索過程有整體記憶并加以指導，從而提高全局搜索效率。

2.1 算法思想

引入蟻王的蟻群算法要實現(xiàn)的目標是，假設(shè)不同的螞蟻從起點出發(fā)，分別經(jīng)過若干條不同路徑最后到達終點，盡量讓螞蟻在初始階段選擇較多的不同路徑，以獲得最終的多樣化解。每一只螞蟻完成了自己的行程后，就將信息素傳遞給蟻王（全局信息）。每次迭代完成后，蟻王將收集到的路徑按從小到大的順序排列，并將較大路徑舍棄，保存較小路徑，以供蟻群下一次尋優(yōu)時加以利用。每次迭代完成后，對前一輪全局最優(yōu)解進一步優(yōu)化，動態(tài)更新路徑信息。如此反復比較，找到最短路徑，然后使用信息素全局更新規(guī)則對螞蟻所選各路徑上的信息素進行更新，即螞蟻完成一個循環(huán)后更新所有路徑上的信息素，只有那些屬于最短路徑的邊信息素才被增強，最終形成一個新的最短路徑。

蟻群算法的任務(wù)就是引導問題的解向著全局最優(yōu)方向不斷進化。蟻王的引進能夠?qū)ψ顑?yōu)解進行快速增強，同時對最差解進行削弱，使屬于最優(yōu)路徑的邊與屬于最差路徑的邊之間的信息量差異進一步增大，逼使螞蟻的搜索行為更集中于最優(yōu)解附近。

假設(shè)蟻王能夠保存搜索到的最優(yōu)值。螞蟻將在接下來的路徑選擇中，根據(jù)蟻王的指導決定路徑的選擇，從而緩解蟻群算法的停滯現(xiàn)象及局部最優(yōu)問題。具體的算法流程，如圖1所示。

圖1 改進的蟻群算法流程

3 改進的蟻群算法

3.1 蟻群的路徑選擇規(guī)則

蟻王可存儲搜索到當前為止前g個較優(yōu)解。改進蟻群算法將設(shè)置一個精英解信息素矩陣。設(shè)蟻群中有m(t)個螞蟻按照精英信息素矩陣選擇轉(zhuǎn)移節(jié)點，n(t)個螞蟻按照基本蟻群算法中邊上的信息素進行選擇轉(zhuǎn)移節(jié)點，w(t)個螞蟻將隨機選取蟻群存儲的g個較優(yōu)解中的一個解，進行變異操作。

設(shè)精英信息素矩陣時刻t邊(i,j)上的信息素量為則按照精英信息素矩陣選擇轉(zhuǎn)移節(jié)點的公式為：

按照基本蟻群算法邊上信息素進行轉(zhuǎn)移節(jié)點的螞蟻選擇邊的公式為：

3.2 信息素的獎勵促進機制

螞蟻每完成一次搜索會找到一條最優(yōu)路徑，蟻王將最優(yōu)路徑與之前搜索到的全局最優(yōu)路徑作比較，如果新搜索到的全局最優(yōu)解最優(yōu)，則以其取代之前的全局最優(yōu)路徑。

所有螞蟻進行一次搜索路徑后，各邊上信息素的更新公式依式（2）、式（3）和式（4）計算。

本文采用最大最小螞蟻系統(tǒng)將路徑上的信息素設(shè)置在一定范圍內(nèi)。設(shè)信息素的量控制在[tmin,tmax]范圍內(nèi)。當路徑上的信息素更新完畢后，按以下公式進行調(diào)整：

螞蟻每完成一次迭代循環(huán)搜索后，就將路徑存儲到蟻王中；蟻王將此次搜索到的路徑值與之前搜索到的存儲路徑值作比較，如果新搜索到的路徑解優(yōu)于之前搜索到的最優(yōu)解，則以這條代替之前的全局最優(yōu)路徑。螞蟻在進行循環(huán)狀態(tài)轉(zhuǎn)移時，為了使其他螞蟻在尋路時更好地選擇此路徑，需要將這條路徑上的信息素濃度增大，以進一步增強蟻王搜索過程的指導性，使螞蟻的搜索更集中于當前所找出的全局最優(yōu)路徑上，進而加快收斂速度。

設(shè)當所有螞蟻進行搜索巡游后，只對當前搜索到的前e(t)個較優(yōu)解路徑進行精英信息素矩陣對應(yīng)邊上進行更新。精英信息素矩陣邊上信息素更新公式為：

當所有的螞蟻完成一次搜索后，進行信息素的更新。信息素的更新采用較優(yōu)路徑更新策略。較優(yōu)路徑包括兩部分：（1）當前迭代最優(yōu)解的路徑；（2）螞蟻在當前迭代搜索到解的路徑比自己最優(yōu)解更優(yōu)的路徑。路徑（1）信息素的更新，能夠使局部最優(yōu)路徑信息素保留，促使以后螞蟻的搜索方向集中于較優(yōu)方向。路徑（2）信息素的更新，能夠使本次搜索成績較好的螞蟻的經(jīng)驗在群體間進行交流，有利于在下一次迭代搜索中發(fā)現(xiàn)更好的解。

設(shè)當所有螞蟻第t次迭代搜索路徑后，當前迭代得到的最優(yōu)解為Literbest(t)，此時全局最優(yōu)解為Lgbest。

若Literbest(t)＜Lgbest，則m(t)=m(t)+θ1，e(t)=e(t)+θ2，w(t)=w(t)+θ3；

若Literbest(t)≥Lgbest，則m(t)=m(t)-θ1，e(t)=e(t)-θ2，w(t)=w(t)-θ3。

其中，θ1、θ2、θ3均為大于零的參數(shù)。

該算法關(guān)鍵在于蟻王對螞蟻的調(diào)配。當一次迭代搜索完成后，判斷當前迭代得到的迭代最優(yōu)解與全局最優(yōu)解之間的關(guān)系。若迭代最優(yōu)解優(yōu)于全局最優(yōu)解，則加大e(t)的數(shù)量，即加大精英信息素矩陣中優(yōu)質(zhì)解路徑更新的數(shù)量，那么精英信息素矩陣中信息素的分布表示當前較優(yōu)質(zhì)解的分布。同時，要加大m(t)的數(shù)量，表示下一次搜索將加大在精英信息素矩陣進行搜索螞蟻的數(shù)量，有利于螞蟻能夠在表示較優(yōu)解的矩陣發(fā)現(xiàn)更好的解。此外，需增加進行變異操作螞蟻的數(shù)量w(t)，以加大對當前算法搜索到的優(yōu)質(zhì)解的變異操作，從而對優(yōu)質(zhì)解進行變動，以獲得更優(yōu)的解。

若迭代最優(yōu)解優(yōu)于全局最優(yōu)解，即全局最優(yōu)解不變，則減少e(t)、m(t)、w(t)的數(shù)量，以防止劣質(zhì)解對算法搜索造成干擾。

蟻群中有一部分螞蟻按照路徑上的信息素進行搜索，且該路徑上的信息素量置于一定的范圍內(nèi)，以防止由于精英信息素螞蟻進行搜索而造成的停滯現(xiàn)象。

4 改進蟻群算法在QoS組播中的應(yīng)用

Qos組播數(shù)學模型：計算機網(wǎng)絡(luò)表示為一個帶權(quán)圖G=(V,E)，其中V代表節(jié)點集合，E代表節(jié)點間的鏈路集合，|V|、|E|分別為節(jié)點個數(shù)與鏈路個數(shù)。假設(shè)組播的發(fā)送節(jié)點s∈V，接收節(jié)點集M?V-{s}；組播樹T是G的子圖，VT?V，TEE?。T中存在由發(fā)送點到任意接收的點di的一條路徑可表示為p(s,di)，則對于p(s,di)的任意一條鏈路e∈p(s,di)、頂點n∈p(s,di)，該路由的代價、時延、延時抖動、丟包率各度量函數(shù)分別為：延時：

組播QoS多約束路由是符合時延、延時抖動、帶寬、丟包率屬性的要求下，使組播樹的代價最小。描述如下：

其中，D、Dj、B、Pl分別為約束條件屬性值。此時，各螞蟻選擇路徑公式中ηij(t)為1/Cost(i,j)。

進行變異操作的螞蟻進行如下操作：

從蟻王保存的當前較優(yōu)的g個組播樹隨機選取一個組播樹T。隨機選擇這個組播樹的一個目的節(jié)點di，則變異操作的螞蟻將從源節(jié)點s到目的節(jié)點di進行移動。

此時，螞蟻的路徑選擇公式為：

其中，q∈(0,1)為隨機數(shù)，q0為概率，為一個參數(shù)。

此時，螞蟻操作的螞蟻將按一定的概率在精英解信息素矩陣表示的信息素量或按邊上的信息素量進行選擇路徑。

5 仿真實驗結(jié)果與分析

仿真實驗環(huán)境：采用matlab 7.8，應(yīng)用Salam拓撲算法隨機生成網(wǎng)絡(luò)拓撲圖，如圖2所示。

圖2 網(wǎng)絡(luò)拓撲

其中，網(wǎng)絡(luò)各邊的參數(shù)見表1。

表1 網(wǎng)絡(luò)參數(shù)取值范圍

假設(shè)仿真實驗各參數(shù)：螞蟻數(shù)量M=40，α=1，β=2，ρ=0.1，tmin=0.01，tmax=3，θ1=2，θ2=1，θ3=1，q0=0.7，g=3，m(0)=10，w(0)=4，e(0)=3，M1=5，迭代最大次數(shù)Nc=300。網(wǎng)絡(luò)服務(wù)質(zhì)量各參數(shù)[B,D,Dj.Pl]要求為[40,150,60,10e-3]。

兩種算法每次路由請求實驗進行100次，則實驗結(jié)果見表2。

表2 基本蟻群算法和改進蟻群算法的實驗結(jié)果

設(shè)第k次試驗中第t輪迭代搜索后，得到的全局最優(yōu)解為總共n次實驗，第t輪迭代搜索后，得到的全局最優(yōu)解的平均值為：

以路由請求{25,(13,18,43,50)}{38,(5,42,11,20,33)}為例，比較基本與改進的蟻群算法。當實驗次數(shù)n=100時，兩種路由請求下，所求組播樹代價全局最優(yōu)解的平均值(t)進化曲線分別如圖3、圖4所示。

由圖3、圖4中的平均最優(yōu)代價曲線可以看出，改進蟻群算法在全局最優(yōu)的進化過程中，搜索到組播樹的代價明顯優(yōu)于基本蟻群算法。例如，設(shè)源節(jié)點s=18，當目的節(jié)點數(shù)量不斷增加時，比較兩種算法多次實驗所求組播樹代價，結(jié)果如圖5所示。這里的代價值是多次實驗的平均值，實驗次數(shù)為100次。

圖3 25,(13,18,43,50)路由請求組播樹平均最優(yōu)代價進化曲線

圖4 38,(5,42,11,20.33)路由請求組播樹平均最優(yōu)代價進化曲線

圖5 兩種算法的組播樹代價

6 結(jié) 語

本文在基本蟻群算法的基礎(chǔ)上，提出了一種新的改進思路。具體的，引進蟻王概念的蟻群算法，借鑒自然螞蟻無法感知距離的行為，讓“蟻王”對蟻群路徑的選擇策略和過程加以指導和改善。仿真實驗結(jié)果表明，在蟻群中引入蟻王概念，可使群體搜索過程更加協(xié)調(diào)有序，且算法能夠獲得比基本蟻群算法更加優(yōu)越的性能，提高了全局搜索效率。

[1] 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(01):29-41.

[2] Wang Z,Crowcroft J.Quality-of-Service for Routing Supporting Multimedia Applications[J].IEEE Journal of Selected Areas in Communications,1996,14(07):1228-1234.

[3] 劉洋,王文國.差異化密集蟻群算法與網(wǎng)絡(luò)QoS路由選擇[J].通信技術(shù),2015,48(08):949-953. LIU Yang,WANG Wen-guo.Differentiated Dense Ant Colony Algorithm and Network QoS Routing Selection[J]. Communications Technology,2015,48(08):949-953.

[4] 楊原.基于群智能優(yōu)化算法的QoS組播路由算法研究[D].西安:西安科技大學,2014. YANG Yuan.Research on QoS Multicast Routing Algorithm based on Swarm Intelligence Optimization Algorithm[D]. Xi’an:Xi’an University of Science and Technology,2014.

[5] 陳峻,沈潔,秦玲等.基于分布均勻度的自適應(yīng)蟻群算法[J].軟件學報,2003,14(08):1379-1387. CHEN Jun,SHEN Jie,QIN Ling,et al.An Adaptive Ant Colony Algorithm based on Equilibrium of Distribution[J]. Journal of Software,2003,14(08):1379-1387.

[6] 鄧可,林杰,張鵬.基于信息熵的異類多種群蟻群算法[J].計算機工程與應(yīng)用,2008,44(36):16-19. DENG Ke,LIN Jie,ZHANG Peng.Multiple Heterogeneous ant Colonies Algorithm based on Information Entropy[J].Computer Engineering and Applications,2008,44(36):16-19.

[7] 張鵬,林杰,鄧可.一種基于路徑相似度的蟻群算法[J].計算機工程與應(yīng)用,2007,43(32):28-33. ZHANG Peng,LIN Jie,DENG Ke.Ant Colony Algorithm based on Similarity of Paths[J].Computer Engineering and Application,2007,43(32):28-33.

[8] 姜秋霞.混合蟻群算法及其應(yīng)用研究[D].上海:同濟大學,2008. JIANG Qiu-xia.Research on Hybrid Ant Colony Algorithm and Its Application[D].Shanghai:Tongji University,2008.

王文國（1960—），男，博士，教授，主要研究方向為網(wǎng)絡(luò)與信息安全；

樊麗娟（1988—），女，碩士研究生，主要研究方向為計算機網(wǎng)絡(luò)。

Modified Ant-Colony Algorithm and Its Application in QoS Multicast Routing

WANG Wen-guo, FAN Li-juan, LIU Yang
(Dept. of Info. Science & Engineering, Qufu Normal University, Rizhao Shandong 276826, China)

Multicast routing and QoS(Quality of Service) are two important topics of present Internet research. QoS multicast routing, focused to select an optimized multicast routing tree with sufficient resources to meet the requirement of customers, is a typical NPC complete multi-objective optimization problem. The traditional ant-colony algorithm is modified with the introduction of a “queen” concept, thus to help in storage, sorting, and selecting of paths. Meanwhile, the elitist pheromone matrix is used as a strategy to update related pheromone, so as to speed up convergence of the algorithm. Simulation with Matlab indicates that, this new method could achieve much better performance than the basic ant-colony algorithm.

ant-colony algorithm; QoS multicast routing; elitist pheromone; queen

TP311

A

1002-0802(2016)-12-1642-06

10.3969/j.issn.1002-0802.2016.12.013

2016-08-22

2016-11-16 Received date:2016-08-22;Revised date:2016-11-16

國家人事部高層次留學人員回國工作資助項目（No.200461）

Foundation Item:National High Level Talents Attracting Program of China(No.200461)