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

王文國(guó)，樊麗娟，劉 洋

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

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

王文國(guó)，樊麗娟，劉 洋

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

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

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

0 引 言

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

1 基本蟻群算法

1.1 路徑選擇公式

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

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

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

1.2 信息素更新

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

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

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

2 引入蟻王概念的改進(jìn)蟻群算法

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

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

2.1 算法思想

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

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

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

圖1 改進(jìn)的蟻群算法流程

3 改進(jìn)的蟻群算法

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

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

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

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

3.2 信息素的獎(jiǎng)勵(lì)促進(jìn)機(jī)制

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

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

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

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

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

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

設(shè)當(dāng)所有螞蟻第t次迭代搜索路徑后，當(dāng)前迭代得到的最優(yōu)解為L(zhǎng)iterbest(t)，此時(shí)全局最優(yōu)解為L(zhǎng)gbest。

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

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

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

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

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

組播QoS多約束路由是符合時(shí)延、延時(shí)抖動(dòng)、帶寬、丟包率屬性的要求下，使組播樹(shù)的代價(jià)最小。描述如下：

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

進(jìn)行變異操作的螞蟻進(jìn)行如下操作：

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

此時(shí)，螞蟻的路徑選擇公式為：

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

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

5 仿真實(shí)驗(yàn)結(jié)果與分析

仿真實(shí)驗(yàn)環(huán)境：采用matlab 7.8，應(yīng)用Salam拓?fù)渌惴S機(jī)生成網(wǎng)絡(luò)拓?fù)鋱D，如圖2所示。

圖2 網(wǎng)絡(luò)拓?fù)?/p>

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

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

假設(shè)仿真實(shí)驗(yàn)各參數(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]。

兩種算法每次路由請(qǐng)求實(shí)驗(yàn)進(jìn)行100次，則實(shí)驗(yàn)結(jié)果見(jiàn)表2。

表2 基本蟻群算法和改進(jìn)蟻群算法的實(shí)驗(yàn)結(jié)果

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

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

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

圖3 25,(13,18,43,50)路由請(qǐng)求組播樹(shù)平均最優(yōu)代價(jià)進(jìn)化曲線

圖4 38,(5,42,11,20.33)路由請(qǐng)求組播樹(shù)平均最優(yōu)代價(jià)進(jìn)化曲線

圖5 兩種算法的組播樹(shù)代價(jià)

6 結(jié) 語(yǔ)

本文在基本蟻群算法的基礎(chǔ)上，提出了一種新的改進(jìn)思路。具體的，引進(jìn)蟻王概念的蟻群算法，借鑒自然螞蟻無(wú)法感知距離的行為，讓“蟻王”對(duì)蟻群路徑的選擇策略和過(guò)程加以指導(dǎo)和改善。仿真實(shí)驗(yàn)結(jié)果表明，在蟻群中引入蟻王概念，可使群體搜索過(guò)程更加協(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] 劉洋,王文國(guó).差異化密集蟻群算法與網(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].西安:西安科技大學(xué),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].軟件學(xué)報(bào),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] 鄧可,林杰,張鵬.基于信息熵的異類(lèi)多種群蟻群算法[J].計(jì)算機(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].計(jì)算機(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].上海:同濟(jì)大學(xué),2008. JIANG Qiu-xia.Research on Hybrid Ant Colony Algorithm and Its Application[D].Shanghai:Tongji University,2008.

王文國(guó)（1960—），男，博士，教授，主要研究方向?yàn)榫W(wǎng)絡(luò)與信息安全；

樊麗娟（1988—），女，碩士研究生，主要研究方向?yàn)橛?jì)算機(jī)網(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

國(guó)家人事部高層次留學(xué)人員回國(guó)工作資助項(xiàng)目（No.200461）

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