基于自適應(yīng)混沌遺傳算法的QoS組播路由

張清富

(廣東陽(yáng)江市廣播電視大學(xué)，廣東 陽(yáng)江 529500)

QoS是指數(shù)據(jù)通過(guò)網(wǎng)絡(luò)時(shí)向用戶(hù)提供端到端的服務(wù)質(zhì)量保證，其質(zhì)量指標(biāo)一般包括業(yè)務(wù)的延遲、延遲抖動(dòng)、費(fèi)用、帶寬和丟包率等多個(gè)度量約束。如果QoS路由涉及兩個(gè)以上的度量約束問(wèn)題，則QoS組播路由計(jì)算是NP完全(NP-Complete)問(wèn)題[1]，很難找到多項(xiàng)式時(shí)間的求解算法。

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

1 網(wǎng)絡(luò)模型[2]

2 自適應(yīng)混沌遺傳算法設(shè)計(jì)

2.1 編碼設(shè)計(jì)

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

2.2 生成候選路徑集合

在明確QoS組播要求之后，對(duì)每個(gè)目的節(jié)點(diǎn) ti，采用Dijkstra前k條最短路算法找到從源點(diǎn)s到ti的滿(mǎn)足帶寬要求的所有路徑并對(duì)路徑進(jìn)行整數(shù)編碼，而其中的路徑由網(wǎng)絡(luò)節(jié)點(diǎn)的編號(hào)組成(節(jié)點(diǎn)集)，這就形成了組播樹(shù)的候選路徑集合。

2.3 適應(yīng)度函數(shù)設(shè)計(jì)

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

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

2.4 群體初始化

分別從到達(dá)每個(gè)目的節(jié)點(diǎn)候選路徑集中任選一條路由組成一棵組播樹(shù)作為初始群體的染色體。這樣構(gòu)成的組播樹(shù)覆蓋了所有的目的節(jié)點(diǎn)，群體多樣性更有保證，并且消除了算法中的帶寬約束，優(yōu)化了網(wǎng)絡(luò)的性能，減少了算法的搜索空間。

2.5 選擇操作

2.5.1引入Tent映射混沌優(yōu)化

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

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

2.5.2選擇進(jìn)化過(guò)程

自適應(yīng)混沌遺傳算法采用最佳混沌個(gè)體保留法與輪盤(pán)賭選擇法相結(jié)合的選擇方式。利用Tent映射函數(shù)混沌優(yōu)化群體中個(gè)體的適應(yīng)度函數(shù)值，選出最佳值個(gè)體，直接遺傳到子代群體中，其余個(gè)體采用輪盤(pán)賭選擇法選擇。

2.6 自適應(yīng)交叉概率與變異概率的設(shè)計(jì)

通過(guò)監(jiān)測(cè)群體適應(yīng)度方差與群體當(dāng)前最優(yōu)解的適應(yīng)度連續(xù)變化情況來(lái)判斷群體是否產(chǎn)生早熟。采用如下群體適應(yīng)度方差公式[5]：

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

產(chǎn)生早熟收斂的群體的多樣性較差，個(gè)體相似度大，“劣種”較多，群體需要“突變“，這時(shí)可以加大群體的繁殖強(qiáng)度并增強(qiáng)群體的擾動(dòng)，即增大交叉概率與變異概率，使其跳離局部最優(yōu)解，采用如下公式：

2.7 交叉操作

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

2.8 變異操作

變異操作使遺傳算法具有局部隨機(jī)搜索能力，是保持群體多樣性的一種有效進(jìn)化操作，本文以自適應(yīng)的變異概率進(jìn)行變異操作。從染色體中隨機(jī)選擇兩個(gè)基因?yàn)樽儺慄c(diǎn)n1、n2，以路徑費(fèi)用為指標(biāo)，采用Dijkstra最短路徑算法計(jì)算節(jié)點(diǎn)n1、n2之間的最短路徑作為變異后的新路徑，變異過(guò)程如圖2所示。

圖1 染色體的交叉操作

圖2 染色體的變異操作

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

群體經(jīng)過(guò)交叉和變異之后，可能會(huì)產(chǎn)生違反約束條件及產(chǎn)生環(huán)路的個(gè)體。修正操作就是維護(hù)違反約束條件及產(chǎn)生環(huán)路的染色體。修正維護(hù)操作可以采用懲罰策略和刪除循環(huán)的方法來(lái)實(shí)現(xiàn)。

2.10 算法描述

假設(shè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和QoS組播要求已知。網(wǎng)絡(luò)中包含n個(gè)節(jié)點(diǎn)，其中包括m個(gè)目的節(jié)點(diǎn)。P為群體規(guī)模，i為當(dāng)前進(jìn)化代數(shù)，G為最大進(jìn)化次數(shù)。組播要求包括源節(jié)點(diǎn) s，目的節(jié)點(diǎn)集 M，QoS 組播要求 R(s，M，b，d，j，l)，算法運(yùn)行步驟如下：

(1)初始化相關(guān)參數(shù)；

(2)對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行整數(shù)編碼，生成侯選路徑集并對(duì)路徑進(jìn)行整數(shù)編碼；

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

(4)計(jì)算群體中所有個(gè)體的適應(yīng)度函數(shù)值f；

(5)根據(jù)本文描述的Tent混沌優(yōu)化選擇法進(jìn)行選擇操作；

(6)若早熟，則自適應(yīng)調(diào)整交叉概率Pc與變異概率Pm，群體交叉與變異并維護(hù)；

(7)如果迭代次數(shù)大于G或當(dāng)前最優(yōu)解達(dá)到要求，則轉(zhuǎn)到步驟(8)，否則轉(zhuǎn)到步驟(4)；

(8)解碼并輸出群體中適應(yīng)度最大的個(gè)體，此即全局最優(yōu)解，算法結(jié)束。

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

通過(guò)C#語(yǔ)言編寫(xiě)的程序?qū)崿F(xiàn)本 QoS組播網(wǎng)絡(luò)路由算法[8]，采用的網(wǎng)絡(luò)拓?fù)淠Ｐ图熬W(wǎng)絡(luò)鏈路參數(shù)[4]如圖3與表1所示。

圖3 組播網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

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

表1 網(wǎng)絡(luò)鏈路參數(shù)

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

[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ìn)[J].2008，34(4)：1-3.

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

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

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

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

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

[8]王小平，曹立明.遺傳算法一理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安：西安交通大學(xué)出版社，2002.