基于自適應混沌遺傳算法的QoS組播路由

張清富

(廣東陽江市廣播電視大學，廣東 陽江 529500)

QoS是指數據通過網絡時向用戶提供端到端的服務質量保證，其質量指標一般包括業務的延遲、延遲抖動、費用、帶寬和丟包率等多個度量約束。如果QoS路由涉及兩個以上的度量約束問題，則QoS組播路由計算是NP完全(NP-Complete)問題[1]，很難找到多項式時間的求解算法。

遺傳算法GA(Genetic Algorithm)是模擬生物進化過程的一種智能算法，具有自適應性、并行性以及魯棒性強等多方面的特點，可有效解決QoS組播路由選擇問題。但經典遺傳算法存在易發生早熟現象、進化后期搜索效率低以及收斂后穩定性差等缺點，而保持群體的多樣性可有效避免遺傳算法早熟的產生。為此，本文在遺傳算法基礎上，引入混沌優化以及早熟處理機制兩個改良措施對群體進行擾動以增加群體的多樣性。

1 網絡模型[2]

2 自適應混沌遺傳算法設計

2.1 編碼設計

傳統的二進制編碼和實數編碼不能精確地描述組播樹的特性，本算法采用變長整數編碼這種最自然、最簡單的組播路由表示方式。給定一個源點和一組目的節點，群體中的每個個體(染色體)代表一棵多播樹，可用樹型數據結構描述個體結構。染色體碼長為目的節點的個數m，第i位上的數值表示組播樹中到第i個目的節點的路徑的編號。 例如組播樹{3，5，6，4，7，9}表示有 6 個目的節點，對第1個目的節點采用3號路徑，對第2個目的節點采用5號路徑，以此類推，每條路徑是一個節點集合。

2.2 生成候選路徑集合

在明確QoS組播要求之后，對每個目的節點 ti，采用Dijkstra前k條最短路算法找到從源點s到ti的滿足帶寬要求的所有路徑并對路徑進行整數編碼，而其中的路徑由網絡節點的編號組成(節點集)，這就形成了組播樹的候選路徑集合。

2.3 適應度函數設計

其中，fb=φb(B(T(s，M))-b)，fd=φd(D(T(s，M))-d)，fj=φj(J(T(s，M))-j)，fl=φl(L(T(s，M))-l)，fc=φc(C(T(s，M))-c)，φb(x)

其中，fx表示s到ti路徑的實際值與約束值的差值，Wb、Wd、Wj、Wl、Wc分別為 QoS 約束的權重參數，φ(x)為一個懲罰函數，其系數 rx∈(0，1)。

2.4 群體初始化

分別從到達每個目的節點候選路徑集中任選一條路由組成一棵組播樹作為初始群體的染色體。這樣構成的組播樹覆蓋了所有的目的節點，群體多樣性更有保證，并且消除了算法中的帶寬約束，優化了網絡的性能，減少了算法的搜索空間。

2.5 選擇操作

2.5.1引入Tent映射混沌優化

混沌優化具有偽隨機性、遍歷性、周期性等特征，是一種全局和局部搜索能力都很強的新型算法，但是常用的Logistic映射的概率密度呈兩頭多、中間少的分布性質，故本文在遺傳算法的選擇操作中采用均勻分布特性更好的Tent映射混沌優化，可更有效抑制遺傳算法產生早熟，并提高進化后期的收斂速度。Tent映射表達式為：

Tent映射在函數域空間中其概率密度的分布較均勻，可避免主要集中在變量空間的邊緣區域進行搜索的不足。

2.5.2選擇進化過程

自適應混沌遺傳算法采用最佳混沌個體保留法與輪盤賭選擇法相結合的選擇方式。利用Tent映射函數混沌優化群體中個體的適應度函數值，選出最佳值個體，直接遺傳到子代群體中，其余個體采用輪盤賭選擇法選擇。

2.6 自適應交叉概率與變異概率的設計

通過監測群體適應度方差與群體當前最優解的適應度連續變化情況來判斷群體是否產生早熟。采用如下群體適應度方差公式[5]：

其中，P為群體規模，fi為個體適應度，favg為群體平均適應度，f為歸一函數。數值實驗發現，早熟收斂和群體適應度方差σ2存在某種相關度：當早熟收斂產生時，在連續數次迭代中σ2變化不大，趨于穩定，但是當算法收斂到全局最優解時，σ2同樣存在以上的情況。綜合考慮，判斷群體產生早熟收斂的依據為：群體適應度方差與群體當前最優解的適應度的差值連續3次分別小于預先設定的閾值∈1、∈2，即 Δσ2<∈1、Δfmax<∈2。

產生早熟收斂的群體的多樣性較差，個體相似度大，“劣種”較多，群體需要“突變“，這時可以加大群體的繁殖強度并增強群體的擾動，即增大交叉概率與變異概率，使其跳離局部最優解，采用如下公式：

2.7 交叉操作

遺傳算法的全局隨機搜索能力主要取決于交叉策略，本文以自適應的交叉概率進行交叉操作。在兩個選中的染色體中選擇一個公共基因作為交叉點，若存在兩個或兩個以上公共基因位時，則隨機選取一個作為交叉點，交叉時，各染色體交換交叉點之后的基因段生成兩個新子體，交叉過程示如圖1所示。圖中，節點n2、n5為潛在交叉點，選定n2為交叉點。

2.8 變異操作

變異操作使遺傳算法具有局部隨機搜索能力，是保持群體多樣性的一種有效進化操作，本文以自適應的變異概率進行變異操作。從染色體中隨機選擇兩個基因為變異點n1、n2，以路徑費用為指標，采用Dijkstra最短路徑算法計算節點n1、n2之間的最短路徑作為變異后的新路徑，變異過程如圖2所示。

圖1 染色體的交叉操作

圖2 染色體的變異操作

2.9 染色體的修正操作[7]

群體經過交叉和變異之后，可能會產生違反約束條件及產生環路的個體。修正操作就是維護違反約束條件及產生環路的染色體。修正維護操作可以采用懲罰策略和刪除循環的方法來實現。

2.10 算法描述

假設網絡拓撲結構和QoS組播要求已知。網絡中包含n個節點，其中包括m個目的節點。P為群體規模，i為當前進化代數，G為最大進化次數。組播要求包括源節點 s，目的節點集 M，QoS 組播要求 R(s，M，b，d，j，l)，算法運行步驟如下：

(1)初始化相關參數；

(2)對網絡節點進行整數編碼，生成侯選路徑集并對路徑進行整數編碼；

(3)根據侯選路徑集隨機生成初始化群體；

(4)計算群體中所有個體的適應度函數值f；

(5)根據本文描述的Tent混沌優化選擇法進行選擇操作；

(6)若早熟，則自適應調整交叉概率Pc與變異概率Pm，群體交叉與變異并維護；

(7)如果迭代次數大于G或當前最優解達到要求，則轉到步驟(8)，否則轉到步驟(4)；

(8)解碼并輸出群體中適應度最大的個體，此即全局最優解，算法結束。

3 仿真實驗與結果分析

通過C#語言編寫的程序實現本 QoS組播網絡路由算法[8]，采用的網絡拓撲模型及網絡鏈路參數[4]如圖3與表1所示。

圖3 組播網絡拓撲結構

QoS 約 束表 示 為 R(s，M，b，d，j，l)，其 中 ，以 節 點 0為源節點 s，目的節點為集合 M={4，6，5}。設置組播具體要求：R(0，M，99，60，20，0.045)，QoS 約束的權重參數(Wb，Wd，Wj，Wl，Wc)分別賦 值(1，1，1，1E-06)，懲 罰 系數(rb，rd，rj，rl)分 別 取 值 (1，0.9，0.85，0.96)，群 體 規 模 P=50，最大進化次數G=200，交叉概率初始值Pc及其增強系數 α分別取0.85、0.05，變異概率初始值Pm及其增強系數β分別取0.05、0.01。以費用的最小值為目標函數，用經典遺傳算法和本文算法分別對組播路由計算進行仿真實驗。結果顯示，本文算法與經典GA在相同環境下求解速度分別為12.512 635 s和 13.75 621 s， 本文算法明顯占優。從圖4與圖5的收斂曲線比較可知，本算法能更快速收斂到全局最優解且收斂后穩定性很高。

表1 網絡鏈路參數

在解決QoS組播路由計算問題時，經典遺傳算法的群體多樣性難以保證，易產生早熟現象，使搜索過早收斂于局部最優解且收斂后不夠穩定。為此，本文改良了經典遺產算法，引入Tent映射混沌優化選擇操作以及采用自適應的交叉與變異概率來處理群體早熟現象。仿真實驗表明，本算法性能良好，在收斂速度、最優解質量以及收斂后穩定性等方面都很大的改善。

[1]Yuan Xin.Heuristic algorithms for muhiconstrained quality of-service routing[J].IEEE／ACM Transactions on Networking，2002，10(2)：244-256.

[2]包海潔，盧輝斌.基于遺傳算法的QoS組播路由算法的改進[J].2008，34(4)：1-3.

[3]王宇.基于遺傳算法的 QoS組播路由[D].成都：四川大學，2003.

[4]王軍，馬范援.基于遺傳算法的QoS組播路由算法的適應度函數改進探索[J].微型電腦，2008，24(8)：12-14.

[5]鄒恩，劉澤華，方仕勇，等.基于混沌遺傳算法的組播路由優化研究[J].計算機工程，2011，37(3)：155-157.

[6]董勇，郭海敏.基于群體適應度方差的自適應混沌粒子群算法[J].計算機應用研究，2011，28(3)：854-856.

[7]孫寶林，李臘元.基于遺傳算法的QoS多播路由優化算法[J].計算機工程，2005，31(14)：70-73.

[8]王小平，曹立明.遺傳算法一理論、應用與軟件實現[M].西安：西安交通大學出版社，2002.