摘 要: 經(jīng)典遺傳算法在解決QoS組播路由問(wèn)題時(shí)存在易發(fā)生早熟現(xiàn)象,、進(jìn)化后期搜索效率低以及收斂后穩(wěn)定性差等不足,為此,,在遺傳算法中引入混沌優(yōu)化以及自適應(yīng)調(diào)整交叉與變異概率兩個(gè)改良措施,。仿真實(shí)驗(yàn)表明,改良后的算法性能優(yōu)良,,在收斂速度,、最優(yōu)解的質(zhì)量以及收斂后穩(wěn)定性等方面有很大的提高。
關(guān)鍵詞: 混沌,;自適應(yīng),;遺傳算法;早熟,;QoS組播路由
QoS是指數(shù)據(jù)通過(guò)網(wǎng)絡(luò)時(shí)向用戶提供端到端的服務(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)以增加群體的多樣性,。
2.4 群體初始化
分別從到達(dá)每個(gè)目的節(jié)點(diǎn)候選路徑集中任選一條路由組成一棵組播樹作為初始群體的染色體,。這樣構(gòu)成的組播樹覆蓋了所有的目的節(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á)式為:
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所示。
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ǔ)言編寫的程序?qū)崿F(xiàn)本QoS組播網(wǎng)絡(luò)路由算法[8],,采用的網(wǎng)絡(luò)拓?fù)淠P图熬W(wǎng)絡(luò)鏈路參數(shù)[4]如圖3與表1所示,。
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的收斂曲線比較可知,本算法能更快速收斂到全局最優(yōu)解且收斂后穩(wěn)定性很高,。
在解決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)定性等方面都很大的改善,。
參考文獻(xià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.