具有個(gè)體記憶的蟻群算法與網(wǎng)絡(luò)QoS路由研究* 1

王文國，劉　洋

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

?

具有個(gè)體記憶的蟻群算法與網(wǎng)絡(luò)QoS路由研究* 1

王文國，劉洋

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

摘要：QoS路由算法的目的是在網(wǎng)絡(luò)中找到滿足一定帶寬、延時(shí)、延時(shí)抖動(dòng)和丟包率等約束要求的路由，該問題是NPC問題。受自然螞蟻啟發(fā)，假設(shè)人工螞蟻具有短期記憶能力，使其選擇路徑時(shí)可把最近迭代搜索到的解與自己過去搜索的最優(yōu)最差解進(jìn)行比較，動(dòng)態(tài)調(diào)整其路徑選擇過程。蟻群信息素的變化則采用較優(yōu)解路徑更新策略，以加快算法的收斂。螞蟻將根據(jù)搜索到解的情況，判斷是否陷入局部最優(yōu)，若是則改變路徑信息素量上下限的大小，使算法跳出局部最優(yōu)。仿真實(shí)驗(yàn)證明，改進(jìn)的蟻群算法在解決QoS路由選擇問題時(shí)，能夠獲得比基本蟻群算法與最大-最小螞蟻系統(tǒng)更優(yōu)搜索性能。

關(guān)鍵詞：蟻群算法;QoS路由選擇;螞蟻個(gè)體記憶;動(dòng)態(tài)選擇

0引言

隨著計(jì)算機(jī)網(wǎng)絡(luò)的發(fā)展，傳統(tǒng)盡力而為的服務(wù)已不能滿足各種網(wǎng)絡(luò)業(yè)務(wù)的需求。特別是網(wǎng)絡(luò)中多媒體的應(yīng)用對(duì)帶寬、延時(shí)、延時(shí)抖動(dòng)、丟包率等參數(shù)提出了嚴(yán)格要求[1]。網(wǎng)絡(luò)服務(wù)質(zhì)量(QoS)就是提供用戶能夠滿足業(yè)務(wù)需求的、一致的、可預(yù)計(jì)的數(shù)據(jù)交付服務(wù)。網(wǎng)絡(luò)服務(wù)質(zhì)量路由(QoSR)算法目的是在網(wǎng)絡(luò)中搜索最佳路由，該路由滿足帶寬、延時(shí)、延時(shí)抖動(dòng)、丟包率等條件。由于包含兩個(gè)或兩個(gè)以上不相關(guān)可加或可乘性參數(shù)的路由選擇問題是NPC問題[2]，傳統(tǒng)路由算法無法在有效時(shí)間內(nèi)找到最優(yōu)解，因而啟發(fā)式搜索算法成為解決多約束QoS路由問題的有效途徑[2-5]。

作為解決NPC問題的有效方法之一，人工蟻群算法可以用于優(yōu)化QoS路由選擇問題[3]。作為一種分布式算法，該算法通過螞蟻之間的相互協(xié)作來尋求最優(yōu)解，并通過螞蟻釋放的信息素作為螞蟻之間交流的媒介。螞蟻釋放信息素的量與它搜索到解的質(zhì)量有關(guān)：搜索到解的質(zhì)量優(yōu)，則釋放的信息素量多；反之則少。蟻群算法還具有并行性、魯棒性，易與其他算法相結(jié)合等優(yōu)點(diǎn)，但也存在收斂速度慢，易停滯于局部最優(yōu)解的缺點(diǎn)。該算法具有正反饋性，搜索到較優(yōu)解螞蟻釋放的信息素量多，這對(duì)后來的螞蟻搜索起到了導(dǎo)向作用。蟻群算法初期之所以收斂慢是由于在迭代初期，各路徑信息素量少并且信息素的分布不能體現(xiàn)解的優(yōu)劣程度，此時(shí)算法的正反饋較弱，需要經(jīng)過一段時(shí)間的迭代搜索，各路徑信息素的差別才能體現(xiàn)出來。易收斂于局部最優(yōu)也是由于蟻群算法的正反饋性，導(dǎo)致某些路徑上信息素的量過大，螞蟻在以后的路徑選擇中失去了多樣性。目前已有多種人工蟻群算法的改進(jìn)版本：如文獻(xiàn)[4]采用遺傳算法初期收斂快的特點(diǎn)，用收斂初期形成的較優(yōu)解來初始化算法初期路徑上信息素的量，算法后期利用蟻群算法的正反饋性來求解最優(yōu)，加快算法的收斂速度。文獻(xiàn)[5]通過路上經(jīng)過的螞蟻數(shù)量的聚度來動(dòng)態(tài)調(diào)整路徑選擇的概率范圍，調(diào)和算法的收斂速度與搜索的廣度。文獻(xiàn)[6]采用多個(gè)種群的螞蟻同時(shí)運(yùn)行，采用路徑信息素的熵作為種群中蟻群算法進(jìn)行程度的量，對(duì)不同進(jìn)化程度的種群進(jìn)行交流來克服單一蟻群算法出現(xiàn)的進(jìn)化停滯現(xiàn)象。文獻(xiàn)[7]將兩個(gè)路徑的相似度作為一種參數(shù)，算法的運(yùn)行過程中，使算法朝著與全局最優(yōu)解路徑相似度高的方向進(jìn)化，提高了搜索到解的質(zhì)量。文獻(xiàn)[8]采用粒子群算法來確定蟻群算法的參數(shù)，從而使蟻群算法獲得較好的性能。

在本文改進(jìn)的蟻群算法中，螞蟻的狀態(tài)轉(zhuǎn)移規(guī)則不僅依賴于路徑信息素量的外部環(huán)境，而且與螞蟻?zhàn)陨淼乃阉鳡顟B(tài)有關(guān)。每只螞蟻能夠保存自己搜索到的最優(yōu)解與最差解。螞蟻在接下來的路徑選擇中，將根據(jù)自己的搜索狀態(tài)與外界信息素的因素自主決定邊的選擇策略，克服螞蟻因面對(duì)同一環(huán)境信息而造成的選擇性單一，從而緩解蟻群算法的停滯現(xiàn)象。在信息素更新方面，只更新本輪迭代中較佳狀態(tài)的螞蟻搜索到解的各條邊上的信息素量與本輪循環(huán)最優(yōu)解的各條邊上的信息素量。

1基本蟻群算法模型

蟻群算法利用螞蟻之間的交流來尋找最優(yōu)解。蟻群算法中單個(gè)螞蟻并不具有智能性，而通過螞蟻釋放的信息素作為螞蟻之間交流的媒介，促進(jìn)螞蟻之間的協(xié)作，使螞蟻朝著最優(yōu)解的方向進(jìn)行搜索。算法本身主要包括路徑選擇部分與信息素的更新部分。

1.1路徑選擇公式

螞蟻k在t時(shí)刻由i節(jié)點(diǎn)選擇j節(jié)點(diǎn)的概率公式為：

(1)

(2)

式中，ηij(t)為期望值啟發(fā)函數(shù)，其值為路徑(i,j)距離的倒數(shù)。τij(t)為t時(shí)刻路徑(i,j)上信息素的量，allowk為螞蟻待選路徑的集合，α為信息素啟發(fā)因子，表示信息素在路徑選擇中所占的重要程度，β為期望值啟發(fā)因子，表示期望值在路徑選擇中的重要程度。

1.2信息素更新公式

τij(t+1)=(1-ρ)*τij(t)+Δτij(t)

(3)

(4)

(5)

式中，ρ為信息素?fù)]發(fā)系數(shù)，Δτij(t)為路徑(i,j)信息素的增量，Q為信息素總量，Lk為螞蟻k搜索解的適應(yīng)度值。本文信息素的更新方式為螞蟻進(jìn)行遍歷完成后進(jìn)行更新，更新信息素量的大小反映了全局解的優(yōu)劣。

路徑選擇公式表示解的構(gòu)造過程，信息素更新公式體現(xiàn)了解的反饋信息。信息素更新公式?jīng)Q定了螞蟻在此后的搜索過程中選擇路徑的情況，而路徑選擇公式?jīng)Q定了信息素需要更新的路徑。這兩個(gè)公式相互作用，形成了蟻群算法搜索解的過程。

2改進(jìn)的蟻群算法模型

基本蟻群算法在構(gòu)造解的過程中，更多的依賴于路徑上信息素的量與期望啟發(fā)函數(shù)。這些因素都是外部因素，任何一只螞蟻在選擇路徑時(shí)，面對(duì)的外部環(huán)境都是一樣的。由于蟻群算法的正反饋性，當(dāng)路徑上的信息素量越來越大時(shí)，螞蟻在此后的選擇過程中，失去了隨機(jī)性，大量的螞蟻會(huì)選擇同一條路徑，于是搜索到的路徑解失去了多樣性。此時(shí)算法容易陷入局部最優(yōu)解。

本文假設(shè)每只螞蟻能夠保存自己搜索到的最優(yōu)解與最差解。螞蟻在接下來的路徑選擇中，將根據(jù)自己的搜索狀態(tài)以及外界信息素分布情況綜合決定路徑的選擇，從而克服螞蟻因面對(duì)同一環(huán)境信息而造成的選擇單一性，進(jìn)一步緩解蟻群算法的停滯現(xiàn)象。

2.1路徑選擇公式

螞蟻k在t+1輪搜索中，路徑選擇公式為：

(6)

(7)

μ1>10<μ2≤1λ≥1

(8)

(9)

(10)

2.2信息素更新公式

(12)

(13)

(14)

當(dāng)螞蟻?zhàn)咄晁械穆窂綍r(shí)，進(jìn)行信息素的更新，Lk為螞蟻k構(gòu)造解路徑的適應(yīng)度值，本文中Lk越小越優(yōu)。

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

(15)

螞蟻k解的構(gòu)造過程中，根據(jù)上輪迭代循環(huán)搜索到的解的適應(yīng)度值與自己搜索到存儲(chǔ)的值相對(duì)比。當(dāng)上輪循環(huán)搜索到解優(yōu)于自己搜索到的最優(yōu)解，螞蟻在本次循環(huán)狀態(tài)轉(zhuǎn)移時(shí)，只考慮邊上信息素量的因素，即所有螞蟻搜索的經(jīng)驗(yàn)。若候選的節(jié)點(diǎn)屬于自己搜索到最優(yōu)路徑的一部分，則加大選擇此節(jié)點(diǎn)的概率；其他節(jié)點(diǎn)將減少被選擇的概率。此時(shí)，每只螞蟻搜索的范圍將集中到自身搜索到的最優(yōu)解附近。這樣將搜索區(qū)域集中到某一區(qū)域，避免搜索區(qū)域過大而造成的無效搜索。

若螞蟻上輪搜索到解差于螞蟻?zhàn)陨砑核阉鞯降淖畈罱猓诒敬窝h(huán)螞蟻進(jìn)行狀態(tài)轉(zhuǎn)移時(shí)，若候選邊屬于自己搜索到最差路徑的一部分，將不選擇該邊；其他邊按照信息素量與期望啟發(fā)值乘積所占的比例進(jìn)行概率搜索。

若螞蟻上輪搜索到解處于自己搜索到最優(yōu)解與最差解之間，螞蟻狀態(tài)轉(zhuǎn)移公式按照基本蟻群算法的狀態(tài)轉(zhuǎn)移策略，此時(shí)螞蟻會(huì)依靠信息素作為螞蟻之間交流的中間橋梁進(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īng)驗(yàn)在群體之間進(jìn)行交流，有利于在下一次的迭代搜索中發(fā)現(xiàn)更好的解。

設(shè)第t輪迭代搜索后得到的當(dāng)前迭代最優(yōu)解為Literbest(t)，第t輪迭代搜索完成時(shí)，算法已搜索到的最優(yōu)解為Lgbest。若Literbest(t)

τmin=τmin*(1+θ1)

(16)

τmax=τmax*(1-θ2)

(17)

0<θ1<1 , 0<θ2<1

按照上述改進(jìn)后的蟻群算法，螞蟻在構(gòu)造解的過程中，首先通過縱向比較，與自己的搜索到的最優(yōu)最差解進(jìn)行對(duì)比，動(dòng)態(tài)地選擇路徑計(jì)算公式，以加強(qiáng)或減弱蟻群算法的正反饋性；然后通過與其它螞蟻之間的橫向交流，加強(qiáng)螞蟻之間相互協(xié)作，使算法向著最優(yōu)解方向進(jìn)化。

3改進(jìn)蟻群算法在QoS路由選擇中的應(yīng)用

3.1多約束QoS路由數(shù)學(xué)模型

計(jì)算機(jī)網(wǎng)絡(luò)可以抽象成帶權(quán)圖G(V,E), 其中V為網(wǎng)絡(luò)中節(jié)點(diǎn)(路由器，交換機(jī))的集合，E為網(wǎng)絡(luò)中鏈路的集合。不失一般性，設(shè)該圖為無向圖。圖中的每個(gè)節(jié)點(diǎn)的屬性為：代價(jià)，延時(shí)，延時(shí)抖動(dòng)，丟包率；鏈路的屬性為：代價(jià)，帶寬，延時(shí)，延時(shí)抖動(dòng)。設(shè)網(wǎng)絡(luò)中的源節(jié)點(diǎn)為s, 目的節(jié)點(diǎn)為d，s∈V，d∈V。定義源節(jié)點(diǎn)s到目的節(jié)點(diǎn)d的代價(jià)、延時(shí)、延時(shí)抖動(dòng)、丟包率，帶寬屬性如下：

代價(jià)：

延時(shí)：

延時(shí)抖動(dòng)：

帶寬：

BandWidth(R(s,d))=min{BandWidth(e),e∈R(s,d)}

其中n為節(jié)點(diǎn)，e為鏈路。

QoS路由選擇問題如下：以s為源節(jié)點(diǎn)，d為目的節(jié)點(diǎn)。在網(wǎng)絡(luò)中找到一條路由R(s,d)，使之滿足以下條件：

其中D，Dj，Pl，B為保障服務(wù)質(zhì)量所需的延時(shí)，延時(shí)抖動(dòng)，丟包率，帶寬要求。QoS路徑選擇問題即在保障服務(wù)質(zhì)量要求下，所求路由的代價(jià)最小。

3.2改進(jìn)蟻群算法在QoS路由選擇中的應(yīng)用

將m只螞蟻放于網(wǎng)絡(luò)中的源節(jié)點(diǎn)s，各只螞蟻按照各自的尋路公式進(jìn)行選擇路徑，直到找到目的節(jié)點(diǎn)d。設(shè)螞蟻k找到的一條路由為Routek，該路由的使用度函數(shù)值為Lk，Lk定義如下：

Lk=Cost(Routek)*{φD(Delay(Routek))*

φDj(Delay_jitter(Routek))*φPl(Pl(Routek))}

(18)

(19)

(20)

(21)

其中rd,rdj,rpl,分別為懲罰系數(shù)，rd>1，rdj>1,rpl>1。適應(yīng)度函數(shù)使用懲罰函數(shù)，對(duì)不符合服務(wù)質(zhì)量要求的解路由，其適應(yīng)度值加大，以形成劣質(zhì)解。

算法過程如下：

第二步： 將m只螞蟻放在源節(jié)點(diǎn)s，t=t+1,設(shè)置螞蟻序號(hào)k=1。

第三步 螞蟻k按照上次搜到的解，選擇合適的路徑選擇公式，選擇下一節(jié)點(diǎn)j。

若j=d，則k=k+1，螞蟻k本次搜索完畢，轉(zhuǎn)向第三步。

若j≠d且j?φ，則螞蟻k繼續(xù)搜索，轉(zhuǎn)向第三步。

若j≠d且j∈φ，螞蟻k無法選擇下一路徑，本次搜索無效，將螞蟻放在源節(jié)點(diǎn)s，轉(zhuǎn)向第三步。

第五步：更新本次迭代路徑上信息素的量，根據(jù)式(15)調(diào)整路徑信息素量。

第六步：根據(jù)Literbest(t)，Lgbest判斷算法是否陷入局部最優(yōu)。若陷入局部最優(yōu)，根據(jù)式(16)，式(17)調(diào)整τmin，τmax。轉(zhuǎn)向第二步。

第七步：若t=Nc，則輸出最優(yōu)值，算法結(jié)束。

4仿真實(shí)驗(yàn)分析

仿真實(shí)驗(yàn)平臺(tái)采用MatLab7.8, 采用改進(jìn)的Salam網(wǎng)絡(luò)拓?fù)潆S機(jī)生成算法，生成網(wǎng)絡(luò)拓?fù)湟妶D1。

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

網(wǎng)絡(luò)中各參數(shù)設(shè)置如下：節(jié)點(diǎn)數(shù)量N=40, 網(wǎng)絡(luò)中各節(jié)點(diǎn)的參數(shù)范圍如表1所示。

表1　參數(shù)取值范圍

設(shè)仿真實(shí)驗(yàn)參數(shù)如下：螞蟻數(shù)量m=20，α=1，β=2，ρ=0.1，Q=10，τmin=0.01，τmax=1，μ1=2，μ2=0.4，λ=2，θ1=0.01，θ2=0.01，迭代最大次數(shù)Nc=200。網(wǎng)絡(luò)服務(wù)質(zhì)量各參數(shù)[B,D,Dj,Pl]要求為[40 Mb/s,100 ms,40 ms,10e-3]。以下對(duì)5個(gè)路由請(qǐng)求進(jìn)行仿真實(shí)驗(yàn)，分別采用基本蟻群算法，最大-最小蟻群算法，本文改進(jìn)的蟻群算法進(jìn)行實(shí)驗(yàn)，每個(gè)實(shí)驗(yàn)運(yùn)行200次，相關(guān)實(shí)驗(yàn)結(jié)果總結(jié)在表2、表3、表4中。

表2　基本蟻群算法實(shí)驗(yàn)結(jié)果

表3　最大-最小蟻群算法實(shí)驗(yàn)結(jié)果

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

由表2，表3，表4可以看出，基本蟻群算法，最大-最小蟻群算法，本文改進(jìn)蟻群算法都能取得最優(yōu)解。本文改進(jìn)蟻群算法多次實(shí)驗(yàn)所求解方差比基本蟻群算法與最大-最小蟻群算法小，說明改進(jìn)算法比基本蟻群算法與最大-最小蟻群算法穩(wěn)定，每次實(shí)驗(yàn)所求解的差別不大。改進(jìn)蟻群算法所求最優(yōu)解的比率比基本蟻群算法高，并且所求解的平均值比基本蟻群算法優(yōu)，說明我們改進(jìn)的蟻群算法尋優(yōu)性能好于基本蟻群算法。通過改進(jìn)的蟻群算法與最大-最小蟻群算法的實(shí)驗(yàn)結(jié)果做對(duì)比，改進(jìn)蟻群算法搜索性能優(yōu)于最大-最小蟻群算法。

以路由請(qǐng)求，源節(jié)點(diǎn)s=4，目的節(jié)點(diǎn)d=33, 服務(wù)質(zhì)量約束要求如上實(shí)驗(yàn)為例，分別運(yùn)行以上三種算法，得到的最優(yōu)代價(jià)進(jìn)化曲線圖如圖2所示。

圖2　三種算法最優(yōu)解進(jìn)化曲線

由三種算法最優(yōu)代價(jià)進(jìn)化曲線可以看出，基本蟻群算法陷入了局部最優(yōu)解，改進(jìn)蟻群算法與最大-最小蟻群算法收斂到全局最優(yōu)解。由于改進(jìn)蟻群算法在運(yùn)行過程中路徑信息素上下限會(huì)改變，導(dǎo)致其收斂速度稍慢于最大-最小蟻群算法。

5結(jié)語

本文提出了一種改進(jìn)的蟻群算法，使螞蟻在構(gòu)造解的過程中，將路徑上的信息素，期望值等外部因素與自身的搜索狀態(tài)相結(jié)合：上次迭代循環(huán)搜索狀態(tài)佳的螞蟻在本次搜索選擇轉(zhuǎn)移的邊時(shí)，將在自己搜索到的最優(yōu)解附近進(jìn)行搜索，力圖獲取更優(yōu)的解；上次迭代搜索狀態(tài)差的螞蟻在本次搜索路徑選擇時(shí)，將避開自己搜索到的最差解，提高螞蟻在當(dāng)前迭代循環(huán)中搜索到解的質(zhì)量。仿真實(shí)驗(yàn)表明具有個(gè)體記憶的蟻群算法能夠獲得比最大-最小螞蟻系統(tǒng)與基本蟻群算法更優(yōu)的搜索性能。

參考文獻(xiàn)：

[1]Crawley E, Nair R, Rajagopalan B and Sandiek H. A Frameework for QoS-based Routing in the Internet[S], RFC no.2386, Internet RFC, Aug.1998.

[2]WANG Z, Crowcroft J. Quality-of-Service for Routing Supporting Multimedia Applications[J]. IEEE Journal of Selected Areas in Communications, 1996;14(7):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]. 西安：西安科技大學(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 Ling, 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]. 計(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.

[9]Stutzle T, HH Hoos. MAX-MIN Ant System[J]. Future Gener. Comput. Syst, 2001,16(8):889-914.

Ant Colony Algorithm with Individual Memory and Its Application in QoS Routing

WANG Wen-guo, LIU Yang

(Dept. of Info. Science & Engineering, Qufu Normal University, Rizhao Shandong 276826, China)

Abstract：QoS routing aims to find a route satisfying restraint requirements of bandwidth, delay, delay jitter, and packet-loss rate in modern network. Artificial ant colony algorithm is one of the effective methods to solve QoS routing problems. Similar to real ants in nature, artificial ants with short term memory could compare current search result with its best/worst paths in the past, and then adjust its selection behavior dynamically. Simulation with Matlab indicates that the modified ant colony algorithm could acquire better searching performances as compared to the basic ant colony algorithm and max-min ant system.

Key words：ant colony algorithm; QoS routing; individual memory; dynamic selection

doi:10.3969/j.issn.1002-0802.2016.05.011

* 收稿日期：2015-12-20；修回日期：2016-04-02Received date:2015-12-20；Revised date：2016-04-02

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

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

中圖分類號(hào)：TP311

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

文章編號(hào)：1002-0802(2016)05-0563-06

作者簡介：

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

劉洋(1981—) 男，碩士，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)。