摘  要： 經(jīng)典遺傳算法在解決QoS組播路由問題時存在易發(fā)生早熟現(xiàn)象、進化后期搜索效率低以及收斂后穩(wěn)定性差等不足，為此，在遺傳算法中引入混沌優(yōu)化以及自適應調(diào)整交叉與變異概率兩個改良措施。仿真實驗表明，改良后的算法性能優(yōu)良，在收斂速度、最優(yōu)解的質(zhì)量以及收斂后穩(wěn)定性等方面有很大的提高。
關(guān)鍵詞： 混沌；自適應；遺傳算法；早熟；QoS組播路由

　QoS是指數(shù)據(jù)通過網(wǎng)絡時向用戶提供端到端的服務質(zhì)量保證，其質(zhì)量指標一般包括業(yè)務的延遲、延遲抖動、費用、帶寬和丟包率等多個度量約束。如果QoS路由涉及兩個以上的度量約束問題，則QoS組播路由計算是NP完全(NP-Complete)問題[1]，很難找到多項式時間的求解算法。
遺傳算法GA(Genetic Algorithm)是模擬生物進化過程的一種智能算法，具有自適應性、并行性以及魯棒性強等多方面的特點，可有效解決QoS組播路由選擇問題。但經(jīng)典遺傳算法存在易發(fā)生早熟現(xiàn)象、進化后期搜索效率低以及收斂后穩(wěn)定性差等缺點，而保持群體的多樣性可有效避免遺傳算法早熟的產(chǎn)生。為此，本文在遺傳算法基礎(chǔ)上，引入混沌優(yōu)化以及早熟處理機制兩個改良措施對群體進行擾動以增加群體的多樣性。

2.4 群體初始化
　分別從到達每個目的節(jié)點候選路徑集中任選一條路由組成一棵組播樹作為初始群體的染色體。這樣構(gòu)成的組播樹覆蓋了所有的目的節(jié)點，群體多樣性更有保證，并且消除了算法中的帶寬約束，優(yōu)化了網(wǎng)絡的性能，減少了算法的搜索空間。
2.5 選擇操作
2.5.1 引入Tent映射混沌優(yōu)化
　混沌優(yōu)化具有偽隨機性、遍歷性、周期性等特征，是一種全局和局部搜索能力都很強的新型算法，但是常用的Logistic映射的概率密度呈兩頭多、中間少的分布性質(zhì)，故本文在遺傳算法的選擇操作中采用均勻分布特性更好的Tent映射混沌優(yōu)化，可更有效抑制遺傳算法產(chǎn)生早熟，并提高進化后期的收斂速度。Tent映射表達式為：

2.7 交叉操作
　遺傳算法的全局隨機搜索能力主要取決于交叉策略，本文以自適應的交叉概率進行交叉操作。在兩個選中的染色體中選擇一個公共基因作為交叉點，若存在兩個或兩個以上公共基因位時，則隨機選取一個作為交叉點，交叉時，各染色體交換交叉點之后的基因段生成兩個新子體，交叉過程示如圖1所示。圖中，節(jié)點n2、n5為潛在交叉點，選定n2為交叉點。
2.8 變異操作
　變異操作使遺傳算法具有局部隨機搜索能力，是保持群體多樣性的一種有效進化操作，本文以自適應的變異概率進行變異操作。從染色體中隨機選擇兩個基因為變異點n1、n2，以路徑費用為指標，采用Dijkstra最短路徑算法計算節(jié)點n1、n2之間的最短路徑作為變異后的新路徑，變異過程如圖2所示。

2.9 染色體的修正操作[7]
　群體經(jīng)過交叉和變異之后，可能會產(chǎn)生違反約束條件及產(chǎn)生環(huán)路的個體。修正操作就是維護違反約束條件及產(chǎn)生環(huán)路的染色體。修正維護操作可以采用懲罰策略和刪除循環(huán)的方法來實現(xiàn)。
2.10 算法描述
　假設(shè)網(wǎng)絡拓撲結(jié)構(gòu)和QoS組播要求已知。網(wǎng)絡中包含n個節(jié)點，其中包括m個目的節(jié)點。P為群體規(guī)模，i為當前進化代數(shù)，G為最大進化次數(shù)。組播要求包括源節(jié)點s，目的節(jié)點集M，QoS組播要求R(s，M，b，d，j，l)，算法運行步驟如下：
　(1)初始化相關(guān)參數(shù)；
　(2)對網(wǎng)絡節(jié)點進行整數(shù)編碼，生成侯選路徑集并對路徑進行整數(shù)編碼；
　(3)根據(jù)侯選路徑集隨機生成初始化群體；
　(4)計算群體中所有個體的適應度函數(shù)值f；
　(5)根據(jù)本文描述的Tent混沌優(yōu)化選擇法進行選擇操作；
　(6)若早熟，則自適應調(diào)整交叉概率Pc與變異概率Pm，群體交叉與變異并維護；
　(7)如果迭代次數(shù)大于G或當前最優(yōu)解達到要求，則轉(zhuǎn)到步驟(8)，否則轉(zhuǎn)到步驟(4)；
　(8)解碼并輸出群體中適應度最大的個體，此即全局最優(yōu)解，算法結(jié)束。
3 仿真實驗與結(jié)果分析
　通過C#語言編寫的程序?qū)崿F(xiàn)本QoS組播網(wǎng)絡路由算法[8]，采用的網(wǎng)絡拓撲模型及網(wǎng)絡鏈路參數(shù)[4]如圖3與表1所示。

　QoS約束表示為R(s，M，b，d，j，l)，其中，以節(jié)點0為源節(jié)點s，目的節(jié)點為集合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，最大進化次數(shù)G=200，交叉概率初始值Pc及其增強系數(shù)α分別取0.85、0.05，變異概率初始值Pm及其增強系數(shù)β分別取0.05、0.01。以費用的最小值為目標函數(shù)，用經(jīng)典遺傳算法和本文算法分別對組播路由計算進行仿真實驗。結(jié)果顯示，本文算法與經(jīng)典GA在相同環(huán)境下求解速度分別為12.512 635 s和13.75 621 s，本文算法明顯占優(yōu)。從圖4與圖5的收斂曲線比較可知，本算法能更快速收斂到全局最優(yōu)解且收斂后穩(wěn)定性很高。

　在解決QoS組播路由計算問題時，經(jīng)典遺傳算法的群體多樣性難以保證，易產(chǎn)生早熟現(xiàn)象，使搜索過早收斂于局部最優(yōu)解且收斂后不夠穩(wěn)定。為此，本文改良了經(jīng)典遺產(chǎn)算法，引入Tent映射混沌優(yōu)化選擇操作以及采用自適應的交叉與變異概率來處理群體早熟現(xià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].2008，34(4)：1-3.
[3] 王宇．基于遺傳算法的QoS組播路由[D]．成都：四川大學，2003．
[4] 王軍，馬范援．基于遺傳算法的QoS組播路由算法的適應度函數(shù)改進探索[J]．微型電腦，2008，24(8)：12-14．
[5] 鄒恩，劉澤華，方仕勇，等．基于混沌遺傳算法的組播路由優(yōu)化研究[J]．計算機工程，2011，37(3)：155-157．
[6] 董勇，郭海敏．基于群體適應度方差的自適應混沌粒子群算法[J]．計算機應用研究，2011，28(3)：854-856．
[7] 孫寶林，李臘元.基于遺傳算法的QoS多播路由優(yōu)化算法[J].計算機工程，2005，31(14)：70-73.
[8] 王小平，曹立明．遺傳算法一理論、應用與軟件實現(xiàn)[M]．西安：西安交通大學出版社，2002．