引入梯度下降的蟻群算法求解多約束服務質量路由

梁本來，楊忠明，秦 勇，蔡昭權

(1.中山職業技術學院 信息工程學院，廣東 中山 528404; 2.廣東科學技術職業學院 計算機工程技術學院，廣東 珠海 519090;3.東莞理工大學 計算機學院，廣東 東莞 523808; 4.惠州學院 教育技術中心，廣東 惠州 516007) (*通信作者電子郵箱187198468@qq.com)

引入梯度下降的蟻群算法求解多約束服務質量路由

梁本來1*，楊忠明2，秦 勇3，蔡昭權4

(1.中山職業技術學院 信息工程學院，廣東 中山 528404; 2.廣東科學技術職業學院 計算機工程技術學院，廣東 珠海 519090;
3.東莞理工大學 計算機學院，廣東 東莞 523808; 4.惠州學院 教育技術中心，廣東 惠州 516007) (*通信作者電子郵箱187198468@qq.com)

針對目前多數改進蟻群算法求解多約束服務質量路由(QoSR)存在收斂速度慢、易陷入局部最優從而效率不高的問題，提出一種引入梯度下降的蟻群算法(ACAGD)。該算法將梯度下降法引入到蟻群的局部搜索中，結合殘余信息素，綜合決定螞蟻的下一跳選擇策略。蟻群不僅以一定概率按照信息素濃度搜索下一跳，還將以一定概率按照梯度下降法搜索下一跳，從而降低傳統蟻群算法容易陷入局部最優的可能性。利用Waxman網絡模型隨機生成不同路由節點數量的網絡拓撲進行仿真實驗。實驗結果表明，ACAGD相比其他改進蟻群算法，能夠在收斂速度不受影響的情況下，取得綜合代價相對較低的路由，且算法的穩定性較好。

服務質量路由；蟻群算法；梯度下降法；信息素濃度；收斂速度；收斂結果；算法穩定性

0 引言

蟻群優化(Ant Colony Optimization, ACO)算法是智能優化應用中的經典算法之一，最早由意大利學者Dorigo等在20世紀90年代提出。原始蟻群算法并不能直接應用于路由尋優，在對該算法進行改進后，可以用于求解多約束服務質量路由(Quality of Service Routing, QoSR)問題。由于QoSR本身是一個難以處理的NP完全(Non-deterministic Polynomial Complete, NP-C)問題[1]，因此改進蟻群算法求解QoSR問題一直以來都是學者研究的熱點和難點。 Stützle等[2]提出一種最大最小蟻群系統(Max-Min Ant System, MMAS)，是一種經典的組合優化算法。MMAS算法的優點是防止過早的停滯現象，尋求全局最優解，但該算法需要將信息素限制在[τmax,τmin]，然而τmax和τmin的取值不太容易界定，取值不當反而難以解決局部最優問題，且該算法的收斂速度并不理想。楊潔等[3]提出一種基于信息素強度的蟻群算法，該算法在選擇路徑時只考慮信息素強度，但信息素強度的初始化和更新結合了路徑長度這一因素。文獻[4]借助相遇搜索策略對傳統蟻群算法進行了改進，將各條尋優路徑上的殘留信息數限定在一個特定區間，使得改進算法能夠相對迅速地收斂。文獻[5]在狀態轉移規則和信息素更新兩方面對傳統蟻群算法作了部分改進(簡稱為葉華喬蟻群算法)，能夠一定程度解決蟻群算法收斂速度慢的問題，但以上蟻群算法的改進重點是收斂速度，而非收斂結果，且以上幾種改進蟻群算法的實驗模型相對簡單，缺乏復雜實驗的證明。王宏霞等[6]提出一種量子蟻群算法，該算法針對QoS路由特性對量子蟻群進行了改進，在一定程度上克服了易陷入局部最優的問題，但算法的復雜度有些偏高。文獻[7-8]將蟻群算法同免疫算法相融合，有效抑制了蟻群的局部最優問題，缺點同樣是增加了算法的復雜度，且沒有對改進算法的穩定性進行分析。邢志娟[9]提出一種適用于多目標優化問題的改進蟻群算法，該算法對初始蟻群中處于可行解位置的每只螞蟻添加一個比較小的隨機擾動值，以降低陷入局部最優解的可能性。該算法的改進思想有借鑒作用，但隨機擾動值的取值范圍較為粗略，作者并沒有對隨機擾動值如何取值進行深入的理論分析。王永[10]提出一種基于云模型的多目標蟻群算法(Cloud-basedMulti-objectiveAntColonyAlgorithm,CMACA)，通過引入云模型次支配解模糊判定機制，找出次支配解，增加蟻群的搜索空間，提高QoSR尋優過程中可行解的多樣性。仿真實驗結果顯示CMACA的Pareto最優解分布更加均勻，但該算法并未對收斂速度進行分析。王健安[11]提出一種基于蟻群優化算法的分布式多約束QoSR算法，將參數自適應策略與最大最小螞蟻的改進策略結合起來實現對基本蟻群算法的改進，但仿真實驗環境較為簡單，且并未對算法的收斂速度進行分析。

綜上所述，目前多數改進蟻群算法求解QoSR問題仍然存在局部最優以及收斂速度過慢的問題[12]，并且改進算法自身的穩定性也較少有人進行研究。為解決以上問題，本文提出一種引入梯度下降的蟻群算法(AntColonyAlgorithmwithGradientDescent,ACAGD)，將梯度下降法引入到蟻群算法的局部搜索中，結合殘余信息素，綜合影響決定螞蟻的下一跳選擇行為策略。螞蟻不僅以一定概率pi按照信息素濃度搜索下一跳，還以一定概率1-pi按照梯度下降法搜索下一跳，從而降低傳統蟻群算法容易陷入局部最優的可能性，得到較優的收斂結果。本文對改進蟻群算法的參數取值進行了實驗分析，在一定的參數條件下，ACAGD能夠在收斂速度不受影響的情況下取得綜合代價相對較低的路由，且算法的穩定性較好。

1 QoSR問題描述

1.1QoSR網絡模型

約定圖1中的各符號函數如下：G=(V,E)：表示該網絡模型，其中V、E分表代表節點集和路徑集；B、D、L分別表示典型的QoS度量參數：剩余可用帶寬、傳輸時延及丟包率；Eij為節點Vi(i=1,2,…，10)到相鄰節點Vj(j=1,2,…,10，且i≠j)的路徑，Bij表示路徑Eij的剩余可用帶寬；Dij表示路徑Eij的傳輸時延；Lij表示路徑Eij的平均丟包率。

1.2 多約束QoSR模型

QoSR問題就是求解源節點Vi(i=1,2,…,10)到目標節點Vj(j=1,2,…,10，且i≠j)之間符合QoSR約束條件的最優路徑。

以典型的QoS度量參數：剩余可用帶寬、傳輸時延和丟包率為代表進行分析，滿足QoSR約束條件的路由需符合以下條件：

1)QoSR請求路由中，每條路徑的剩余可用帶寬不應小于QoSR請求的最小帶寬限制：

MinBp(p)≥B；p∈Ep

(1)

其中:Bp表示路徑的剩余可用帶寬，Ep表示QoSR請求的路徑集合，p為該集合中的一條路徑，B表示QoSR請求的最小可用帶寬限制。

2)QoSR路由源點到終點的時延不應大于QoSR請求的最大時延限制：

(2)

其中:Dn表示路由節點處理時延，Dp表示路徑時延，D表示QoSR請求的最大時延限制，Vn表示QoSR請求的節點集合，n為該集合中的一個節點，Ep，p符號的含義同式(1)。

3)QoSR路由源點到終點的丟包率不應大于QoSR請求的最大丟包率限制：

(3)

其中：Ln表示路由節點的平均丟包率，Lp表示路徑的平均丟包率，L表示QoSR請求的最大丟包率限制，Vn，n，Ep，p符號的含義同式(1)、式(2)。

綜合上述QoSR約束條件式(1)～(3)，得出多約束QoSR模型如下：

(4)

圖1 QoSR網絡模型

2 ACO求解QoSR問題的理論分析

2.1ACO求解QoSR的基本步驟

蟻群算法求解QoSR問題，其實就是將所有m只螞蟻放到源節點Va，將食物放到目標節點Vb，由螞蟻自動搜尋食物，尋找符合QoSR約束條件的最優路徑，將該過程簡述如下：

步驟1 初始化源節點Va和目標節點Vb，初始化迭代次數x為1，初始化各節點和路徑參數和各路徑殘余信息素。

步驟2 將m只螞蟻放到源點位置Va。

步驟3 螞蟻i(i=1,2,…,m)根據路徑綜合代價值和路徑上的殘余信息素值為參考依據，選擇下一節點，對經過的路徑上的信息素進行局部更新，并將經過的節點加入到禁忌表UNi中，防止螞蟻訪問重復節點。

步驟4 第i+1只螞蟻重復執行步驟3，直到m只螞蟻都到達目標節點Vb，此時完成螞蟻的一輪迭代。

2.2ACO算法的關鍵定義及規則

1)定義在t時刻路徑Eij的剩余可用帶寬、傳輸時延和丟包率的綜合代價公式為fij(t)，則有如下公式：

(5)

其中:σ是路徑綜合代價系數，該數值為一個常數；Bij、Dij和Lij分別表示在t時刻，路徑Eij的剩余可用帶寬、傳輸時延和平均丟包率；路徑的綜合代價對殘余信息素有著決定性的作用。

2)下一跳節點集合。

用禁忌表UNk來記錄螞蟻k已經走過的節點，用Ak表示允許螞蟻k(k=1,2,…,m)選擇的下一跳節點集合，Qk表示螞蟻k所在節點位置上所有相鄰的節點集合，則有如下公式：

AK={QK-QK∩UNK}

(6)

3)啟發函數。

(7)

對于螞蟻而言，在t時刻路徑Eij的綜合代價fij(t)越小，則啟發函數ηij(t)越大，ηij(t)用來表示螞蟻從節點Vi到Vj的期望程度。

4)下一跳節點選擇概率公式。

(8)

5)信息素的局部更新公式。

在t時刻，螞蟻k從節點Vi移動到相鄰節點Vj(Vj∈AK)后，路徑Eij上信息素濃度的局部更新公式為：

(9)

(10)

6)信息素全局更新公式。

假設在x次迭代后，第k只螞蟻生成了當前最優解，則該螞蟻經過的路徑Eij上信息素濃度的全局更新公式如下：

(11)

(12)

3 引入梯度下降的蟻群算法ACAGD

3.1 梯度下降法

梯度下降法是一個有效的最優化算法，很多優化算法以它為基礎進行改進和修正。梯度下降法最早由數學家Cauchy在1847年提出，該算法以某一點的負梯度方向作為下降方向[13]，其簡要步驟如下:

步驟1 求解函數f(a)的最優值，令初始點a0∈Rn，精度ε>0，x=0，x表示迭代次數；

步驟2 沿負梯度方向搜索，計算sx=-▽f(ax)，如果‖sx‖≤ε，則停止迭代，最優值a*=ax；

梯度下降法在最優化中具有重要的理論意義，該算法中的下降方向反映了被優化目標的局部性質。本文將梯度下降法引入到蟻群的局部搜索過程中，結合殘余信息素濃度，綜合影響蟻群的下一跳選擇行為，增強蟻群算法的局部搜索能力，在一定程度上，改進傳統蟻群算法的搜索性能，盡量避免陷入局部最優的可能性。

3.2ACAGD中螞蟻局部搜索方法的改進

傳統蟻群算法中，螞蟻完全依賴式(8)搜索下一跳，也就是完全取決于當前節點和下一節點路徑上的殘余的信息量這一因素，該局部搜索機制很大程度上降低了蟻群算法的搜索效率，且容易陷入局部最優。為解決以上問題，特將梯度下降法引入到蟻群的局部搜索中，使得蟻群的搜索更具有全局性，在一定程度上提高尋找其他還未發現的優化路徑的可能性，但簡單的引入梯度下降法并不能避免局部最優問題。為解決該問題，特設計如下的局部搜索方法：

改進1 第i(i=1,2,…,m)只螞蟻在節點Vk(k=1,2,…,n)位置上，選擇下一跳節點的機制如下，其中pi∈(0,1)：

1)以概率pi按式(8)進行搜索，確定螞蟻下一跳；

2)以概率1-pi按梯度下降法搜索，確定螞蟻下一跳。

螞蟻i的下一跳節點選擇公式如式(13)所示：

(13)

改進2 設置螞蟻已搜尋路徑中節點個數上限，屏蔽明顯不合理的螞蟻搜索路徑。以hop*表示允許螞蟻從源點Va到終點Vb搜尋過程中，所經過路徑中包含的節點個數上限，如果超過hop*該螞蟻還沒有找到終點，則表示該螞蟻搜索過的路徑一定非最優路徑，停止該螞蟻搜索，在一定程度上提高螞蟻搜索的準確率。

ACAGD的局部搜索使得螞蟻i在搜索下一跳時，并不全部依賴于下一跳選擇式(8)，還有1-pi的概率基于梯度下降法進行搜索，信息素和梯度下降法的結合，使得蟻群算法降低了陷入局部最優的可能性;同時螞蟻已搜尋路徑中節點個數上限hop*的引入與干涉，使得螞蟻搜索結果的準確率進一步得到提升。

3.3ACAGD偽代碼

ACAGD偽代碼如下，其中各項符號的解釋參見本文第1章QoSR問題描述部分。

算法1ACAGD。

4 ACAGD的理論分析

多約束QoSR問題本身是一個NP完全問題，因此改進蟻群算法求解多約束QoSR具有NP-C的復雜度。因為蟻群算法在t時刻達到最優狀態的概率p*(t)在實際算法運行中很難準確確定[14]，所以對于改進蟻群算法求解QoSR問題的收斂速度的時間界定很難進行理論求證;同時，ACAGD主要是改進螞蟻的下一跳搜索策略，在一定程度上提高了尋找其他還未發現的優化路徑的可能性，盡可能地避免了局部最優問題，重點不是改進蟻群算法的收斂速度，因此，本文主要從收斂性和復雜度兩方面對改進蟻群算法ACAGD進行理論分析。

4.1ACAGD的收斂性證明

引理1 假設在ACAGD的全部迭代過程中，信息素濃度τij(t)的全局最大值為τmax，可行最優解集合為S(S??)，s*為S中一個解，τij(s*)為任意時刻路徑Eij上最大的信息素濃度，μ為一常數，μ∈[0,1]，對于?tij，有如下公式成立：

(14)

(15)

收斂性證明即證明定理1和定理2的過程。

定理1 假設p*(t)為t時刻內ACAGD求出最優解的概率，則對于?δ>0和足夠長的時間t，則有p*(t)≥1-δ，當t→∞時，應有式(16)成立：

(16)

(17)

其中：τmin為信息素濃度τij(t)的全局最大值，τmin為信息素濃度τij(t)的全局最小值，α為螞蟻在運動中信息素對選擇下一跳的影響權重參數，xmax為迭代次數上限。

(18)

證畢。

定理2 假設t0為ACAGD首次求得最優解的時刻，對于?(vi,vj)∈s*，?(x,y)∈ZG∩((x,y)?s*)，存在一個時刻Δt，當?t>t0+Δt，應有式(19)成立：

τij(t)>τxy(t)

(19)

其中:ZG是網絡模型圖G中兩兩相鄰節點的集合。

(20)

在t0+t′時刻，有式(21)成立：

(21)

可以推導出式(22)：

(22)

結合引理2可以推導出式(23)：

t′>(1-μ)/μ

(23)

分析式(23)，即t′∈(0,∞)時式(22)一直成立，因此可以推導出，當?t>t0+Δt時，有定理2中的式(19)成立：

即τij(t)>τxy(t)

證畢。

4.2ACAGD復雜度分析

4.2.1 時間復雜度分析

分析算法1可以得出，時間復雜度最高的語句應為5)，即螞蟻i選擇下一跳語句的復雜度。而螞蟻i選擇下一跳又以概率pi按式(8)確定下一跳；以概率1-pi按梯度下降法確定下一跳。無論是式(8)還是梯度下降法，螞蟻i選擇下一跳時均與兩個集合UNi及Ai相關，而UNi和Ai均與網絡拓撲節點個數n直接相關，因此，算法1中語句5)的時間復雜度應為O(n2)。

因螞蟻數量為m，所以m個螞蟻執行完一次全局搜索，時間復雜度為O(m·n2)。假設ACAGD收斂完畢需總共執行xmax次，則ACAGD的完整時間復雜度應為O(xmax·m·n2)，并沒有增加原ACO算法的時間復雜度。

4.2.2 空間復雜度分析

因網絡拓撲節點數量為n，則網絡拓撲模型G需要一個n×n的二維數組來存儲數據，此處空間復雜度為O(n2)；G中的信息素變量也需要一個n×n的二維數組來存儲數據，此處空間復雜度也為O(n2)；兩個集合UNi及Ai中的元素均為G中的節點，因此空間復雜度為O(n)，考慮到螞蟻數量為m，此處空間復雜度為O(n·m)。

因此，ACO的空間復雜度應為O(n2)+O(n·m)，但考慮到ACAGD為螞蟻i搜索下一跳時引入了梯度下降法，需要增加額外的空間復雜度，其中，每只螞蟻均需要一個梯度變量si存儲下一跳代價遞減值，因為空間復雜度為O(m)；而控制精度ε和搜尋路徑中節點個數上限hop*均為常數，因此需要2個變量存儲；綜合以上分析ACAGD的復雜度為O(n2)+O((n+1)·m)+2，基本等同于原ACO的空間復雜度O(n2)+O(n·m)。

5 仿真實驗與結果分析

5.1 仿真環境

服務器采用HPProLiantML10，內存8GB，3 100MHz主頻四核CPU，Windows7操作系統。采用Lingo14.0軟件進行算法建模，基于Waxman網絡模型連續生成10～100個路由節點的仿真網絡拓撲，構造鄰接矩陣，隨機給出基于剩余帶寬、傳輸時延和丟包率的路徑狀態和約束條件。限于篇幅原因，節點過多時，網絡拓撲圖較難全部繪出。鑒于不同節點數量的網絡模型圖類似，只是節點數量不同。下面以其中10個路由節點的網絡拓撲圖作代表，見圖2(以10節點作代表，節點數量1～100)。

圖2中，每條路徑上的三個數字參數分別表示：剩余帶寬(單位為Mb/s)、傳輸時延(單位為ms)和丟包率(單位為1%)。

圖2 實驗拓撲圖

5.2ACAGD參數的實驗分析

5.2.1ACAGD參數的取值分析

ACAGD的主要改進是在螞蟻下一跳搜索策略，為保證ACO的收斂性，螞蟻應以較大的概率按照下一跳搜索式(8)來搜尋路由，以較小的概率按照梯度下降法來搜尋下一跳，因此，與梯度下降法沒有直接關聯的參數，可以參照一般改進蟻群算法求解QoSR問題的取值范圍。參閱文獻[10-11]可知，改進蟻群求解QoSR問題的主要參數一般設置如表1所示。

表1 求解QoSR問題的一般參數

而參數pi和ε是梯度下降法中的重要參數，它們的取值對于ACAGD的收斂性能和穩定性有著重要的影響。其中，pi則控制著螞蟻i以1-pi的概率按照梯度下降法來搜索下一跳，而ε控制著螞蟻i對比下一跳路徑代價差的對比精度。下面將對這兩個參數的取值范圍，進行詳細的實驗證明。

5.2.2 不同參數組合的實驗分析

1)實驗方法與計算公式。

s*=min{s1,s2,…，s100}

(24)

(25)

t*=min{t1,t2,…，t100}

(26)

(27)

根據統計學理論，定義如下樣本偏差公式：

(28)

即：

(29)

(30)

即：

(31)

其中：Δs為100次實驗所求的路由代價的偏差，Δt為收斂時間的偏差，偏差Δs和Δt越小，表明ACAGD的穩定性越高。

2)參數的取值范圍。

根據網絡拓撲中剩余帶寬、傳輸時延及丟包率的一般取值范圍進行經驗總結，ε∈[0.05,0.15]是比較合適的取值范圍，如果ε取值超過此集合上限，容易觸發梯度下降法，降低ACAGD的收斂速度；而如果ε取值低于此集合下限，則難以讓梯度下降法搜索到有意義的下一跳，失去了ACAGD改進的意義。

螞蟻i下一跳搜索概率pi的取值對ACAGD的搜索結果有較大的影響，如果pi的取值趨近于1，則使得ACAGD失去了梯度下降法搜索的作用；pi的取值如果過小，則使得ACAGD的局部搜索很大程度上偏離了原始ACO局部搜索式(8)的搜索結果，容易出現尋優結果的不穩定性，難以快速收斂。ACAGD收斂結果的穩定性主要還是體現在ACO算法的穩定性上，根據大量仿真實驗數據分析，pi∈[0.80,0.95]是合理的取值空間。

以上是ACAGD的參數pi和ε的較為粗糙的取值空間，為獲取更具指導意義的參數取值范圍，將參數pi和ε的實驗取值范圍進行組合編排進行實驗驗證，具體參數組合和取值范圍列在表2。

表2 參數組合和取值范圍

3)實驗結果分析。

在表2描述出的不同參數組合條件下，應用ACAGD算法分別進行100次獨立實驗，分別記錄每次實驗的路由低價和收斂時間，按照式(25)和式(27)計算路由代價的平均值、收斂時間的平均值，按照式(29)和式(31)計算路由代價的偏差以及收斂時間的偏差，將結果繪于圖3～6中。

圖3 不同參數組合下的路由代價平均值

圖4 不同參數組合下的路由代價偏差

圖5 不同參數組合下的收斂時間平均值

圖6 不同參數組合下的收斂時間偏差

分析圖3，參數組合5或者組合6的路由代價平均值一直處于相對較低的位置，表明在這兩組參數條件下，ACAGD的收斂結果較好。

分析圖4，參數組合5的路由代價偏差一直較低，表明在參數組合5的條件下，ACAGD收斂結果的穩定性較好。

分析圖5，參數組合5和組合7的收斂時間相對較小，表明在這兩組參數條件下，ACAGD的收斂速度較好。

分析圖6，參數組合5和組合6的收斂時間偏差相對較低，表明在參數組合5和組合6的條件下，ACAGD收斂速度的穩定性較好。

將以上實驗結果簡列于表3。

表3 較優的參數組合

分析表3，可以看出，在參數組合5的條件下，ACAGD的收斂結果和收斂速度都較為優秀，且收斂結果和收斂速度的穩定性也相對較好。

因此，在參數組合5以及表1中的參數條件下，將ACAGD同其他改進蟻群算法進行對比實驗。

5.3ACAGD同其他算法的對比實驗

仿真實驗采用Lingo14.0軟件進行仿真，為增加算法的計算復雜度，在不同路由節點的網絡拓撲中，隨機選取相距較遠的兩節點作為源點和終點，針對每次路由請求分別用ACAGD、葉華喬蟻群算法、量子蟻群算法、基于云模型的多目標蟻群算法CMACA和基于蟻群的分布式多約束QoSR算法分別進行100次獨立實驗。

5.3.1 算法收斂結果和收斂速度的對比分析

對以上五種改進蟻群算法分別進行100次獨立實驗，分別記錄每次實驗的路由代價和收斂時間，按照式(25)和式(27)計算以上五種算法收斂后的路由代價和收斂時間的平均值，如圖7、8所示。

分析圖7，五種改進蟻群算法在含有較少路由節點的網絡環境中，搜尋到的路徑總路由代價的平均值基本相同，但隨著網絡路由節點的增加，ACAGD、CMACA和蟻群分布式多約束算法的總路由代價的平均值相比其他兩種算法一直有一定的優勢，尤其是ACAGD的路由代價的平均值一直處于相對較低的位置，且優勢越來越明顯，表明ACAGD在避免陷入局部最優的改進上取得了一定成功。這是由于ACAGD中螞蟻進行下一跳搜索時不僅僅依賴于信息素濃度，還取決于梯度下降法，因此ACAGD在一定程度上提高了尋找其他還未發現的優化路徑的可能性，盡可能地避免了局部最優問題，搜尋到了綜合代價相對較低的路由。

分析圖8，五種改進蟻群算法在含有較少路由節點的網絡環境中，達到收斂所需的收斂時間的平均值基本相同，且隨著網絡路由節點的增加均呈上升趨勢，但ACAGD、CMACA和蟻群分布式多約束算法的收斂時間的平均值相比其他兩種算法較少的優勢卻越發明顯。表明在中大型網絡拓撲中，ACAGD、CMACA和蟻群分布式多約束算法的搜索QoSR路由速度有一定程度的優勢，但ACAGD的收斂時間相比CMACA和蟻群分布式多約束算法并沒有明顯的優勢，這是因為在蟻群的局部搜索中引入梯度下降法是為了避免陷入傳統蟻群的局部最優問題，并不是追求收斂速度，但ACAGD并沒有明顯提高傳統蟻群算法的復雜度，因此，ACAGD的收斂速度仍不差。

圖7 不同算法的路由代價平均值

圖8 不同算法的收斂時間平均值

5.3.2 算法穩定性的對比分析

算法穩定性的對比，主要從收斂結果和收斂時間的穩定性兩方面去驗證，因此，將以上五種改進蟻群算法分別進行100次獨立實驗，分別記錄每次實驗的路由代價和收斂時間，按照式(29)和式(31)計算以上五種算法收斂后的路由代價的偏差以及收斂時間的偏差，結果如圖9～10所示。

圖9 不同算法的路由代價偏差

分析圖9和圖10，可以看出ACAGD的路由代價偏差和收斂時間偏差相比于其他改進蟻群算法更小，且隨著路由節點數量的增加，ACAGD偏差值的優勢更加明顯。實驗結果證明了ACAGD具有相對較好的穩定性，比較適合用于求解多約束QoSR問題，特別是在中大型網絡拓撲下，ACAGD的穩定性更加明顯。

圖10 不同算法的收斂時間偏差

6 結語

利用改進蟻群算法求解多約束服務質量路由一直是路由優化領域內的研究熱點，本文將梯度下降法引入到到蟻群的局部搜索中，提出一種引入梯度下降的蟻群算法ACAGD。仿真實驗結果表明，同其他改進蟻群算法相比，ACAGD在收斂速度不受影響的情況下搜尋到了綜合路徑代價相對較低的路由，且該算法的穩定性較好，為解決實際網絡中的QoSR問題，提供了一條新的思路。下一步將對ACAGD的收斂速度作進一步研究。

)

[1] 夏小云.隨機啟發式搜索算法的性能分析[D].廣州:華南理工大學,2015:11.(XIAXY.Ontheperformanceanalysisofrandomizedsearchheuristics[D].Guangzhou:SouthChinaUniversityofTechnology, 2015: 11.)

[2]STüTZLET,HOOSHH.MAX-MINantsystem[J].FutureGenerationComputerSystems, 2000, 16(9): 889-914.

[3] 楊潔,楊勝,曾慶光,等.基于信息素強度的蟻群算法[J].計算機應用,2009,29(3):865-867.(YANGJ,YANGS,ZENGQG,etal.Antcolonyalgorithmbasedonpheromoneintensity[J].JournalofComputerApplications, 2009, 29(3): 865-867.)

[4] 段海濱,馬冠軍,王道波,等.一種求解連續空間優化問題的改進蟻群算法[J].系統仿真學報,2007,19(5):974-977.(DUANHB,MAGJ,WANGDB,etal.Improvedantcolonyalgorithmforsolvingcontinuousspaceoptimizationproblems[J].JournalofSystemSimulation, 2007, 19(5): 974-977.)

[5] 葉華喬.基于改進蟻群算法的計算機網絡路由優化研究[J].計算機仿真,2015,32(4):265-268.(YEHQ.Researchonroutingoptimizationofcomputernetworkbasedonimprovedantcolonyalgorithm[J].ComputerSimulation, 2015, 32(4): 265-268. )

[6] 王宏霞,李亞龍.求解QoS最佳路由選擇問題的量子蟻群算法[J].計算機仿真,2014,31(3):295-298.(WANGHX,LIYL.QuantumantcolonyalgorithmforQoSbestroutingproblem[J].ComputerSimulation, 2014, 31(3): 295-298.)

[7] 劉朝華,張英杰,章兢,等.蟻群算法與免疫算法的融合及其在TSP中的應用[J].控制與決策,2010,25(5):695-700.(LIUZH,ZHANGYJ,ZHANGJ,etal.UsingcombinationofantalgorithmandimmunealgorithmtosolveTSP[J].ControlandDecision, 2010, 25(5): 695-700.)

[8] 劉朝華,張英杰,李小花,等.雙態免疫優勢蟻群算法及其在TSP中的應用研究[J].小型微型計算機系統,2010,31(5):937-941.(LIUZH,ZHANGYJ,LIXH,etal.ResearchofusingbinarystateACAbasedonimmunodominancetosolveTSP[J].JournalofChineseComputerSystems, 2010, 31(5): 937-941.)

[9] 邢志娟.多目標優化問題的蟻群算法研究[D].北京:中國地質大學,2010:5.(XINGZJ.Studyonmulti-objectiveoptimizationproblembasedonantcolonyoptimizationalgorithm[D].Beijing:ChinaUniversityofGeosciences, 2010:5.)

[10] 王永.多目標路由問題中的蟻群優化算法研究[D].長沙:湖南大學,2009:5.(WANGY.Theresearchonmulti-objectiveroutingproblemsbasedonantcolonyoptimizationalgorithm[D].Changsha:HunanUniversity, 2009:5.)

[11] 王健安.基于蟻群優化算法的分布式多約束QoS路由算法研究[D].長春:長春理工大學,2014:3.(WANGJA.ResearchofmultipleconstraineddistributedQoSroutingbasedonimprovedantcolonyalgorithm[D].Changchun:ChangchunUniversityofScienceandTechnology, 2014: 3.)

[12] 宋悅.蟻群算法在路由優化中的應用研究[D].北京:北京交通大學,2015:4.(SONGY.Thestudyandapplicationofantcolonyalgorithminthefieldofroutingoptimization[D].Beijing:BeijingJiaotongUniversity, 2015:4.)

[13] 胡朝明.幾類譜共軛梯度方法理論及數值行為研究[D].長沙:中南大學,2012:9.(HUCM.Researchonsometypesofspectralconjugategradientmethodsfromtheviewpointsoftheoryandnumericalperformance[D].Changsha:CentralSouthUniversity, 2012: 9.)

[14] 黃翰,郝志峰,吳春國,等.蟻群算法的收斂速度分析[J].計算機學報,2007,30(8):1345-1353.(HUANGH,HAOZF,WUCG,etal.Theconvergencespeedofantcolonyoptimization[J].ChineseJournalofComputers, 2007, 30(8): 1345-1353.)

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61170193),theScienceandtheTechnologyProjectintheFieldofIndustrialHighandNewTechnologyofGuangdongProvince(2013B010401036),theNaturalScienceFoundationofGuangdongProvince(S2013010013432)andtheScienceandTechnologyProjectforPublicInterestofZhongshanCity(2016B2142).

LIANG Benlai, born in 1983, M. S., lecturer. His research interests include information security, network routing.

YANG Zhongming, born in 1980, M. S., associate professor. His research interests include information security, intelligent algorithm.

QIN Yong, born in 1970, Ph.D., professor.His research interests include computer network routing optimization.

CAI Zhaoquan, born in 1970, M. S., professor. His research interests include computer network technology.

Ant colony algorithm with gradient descent for solving multi-constrained quality of service routing

LIANG Benlai1*, YANG Zhongming2, QIN Yong3, CAI Zhaoquan4

(1.CollegeofInformationEngineering,ZhongshanPolytechnic,ZhongshanGuangdong528404,China; 2.ComputerEngineeringTechnicalCollege,GuangdongPolytechnicofScienceandTechnology,ZhuhaiGuangdong519090,China; 3.ComputerInstitute,DongguanUniversityofTechnology,DongguanGuangdong523808,China; 4.EducationalTechnologyCenter,HuizhouUniversity,HuizhouGuangdong516007,China)

To solve the problem that many improved ant colony algorithms are not efficient to solve the problem of multi-constrained Quality of Service Routing (QoSR), such as slow convergence and local optimization, an Ant Colony Algorithm with Gradient Descent (ACAGD) was proposed. The gradient descent method was introduced into the local search of ant colony, and combined with residual pheromone, the next-hop selection strategy of ants was synthetically determined. Ant colony not only search for the next hop according to the pheromone concentration with certain probability, but also search for the next hop according to the gradient descent method with certain probability, which reduced the possibility that the traditional ant colony algorithm was easy to fall into the local optimum. The Waxman network model was used to randomly generate the network topology with different number of routing nodes. The experimental results show that compared with other improved ACO algorithms, the ACAGD can obtain the route with relatively low comprehensive cost while the convergence rate is not affected, and the stability of the algorithm is better.

Quality of Service Routing (QoSR); ant colony algorithm; gradient descent algorithm; pheromone concentration; convergence speed; convergent result; algorithm stability

2016- 08- 19;

2016- 10- 24。

國家自然科學基金資助項目(61170193)；廣東省工業高新技術領域科技計劃項目(2013B010401036)；廣東省自然科學基金資助項目(s2013010013432)；中山市社會公益科技研究項目(2016B2142)。

梁本來(1983—)，男，山東濟寧人，講師，碩士，主要研究方向：信息安全、網絡路由； 楊忠明(1980—)，男，廣東茂名人，副教授，碩士，CCF會員，主要研究方向：信息安全、智能算法； 秦勇(1970—)，男，湖南邵陽人，教授，博士，主要研究方向：網絡路由優化； 蔡昭權(1970—)，男，廣東陸豐人，教授，碩士，CCF會員，主要研究方向：計算機網絡技術。

1001- 9081(2017)03- 0722- 08

10.11772/j.issn.1001- 9081.2017.03.722

TP393

A