基于克隆遺傳的QoS多播路由優(yōu)化模型

盧權(quán)

摘 要： 針對(duì)QoS組播路由問(wèn)題的特點(diǎn)，采用固定長(zhǎng)度的基因編碼方式并利用克隆算子擴(kuò)大遺傳算法的種群規(guī)模，設(shè)計(jì)了自適應(yīng)交叉算子和變異算子控制染色體的生成，從而有效保持群體的多樣性，有利于算法尋找到全局的最優(yōu)解。實(shí)驗(yàn)結(jié)果表明，經(jīng)過(guò)改進(jìn)的遺傳算法具有良好的運(yùn)行速度和收斂性，能有效解決QoS組播路由的問(wèn)題，對(duì)于求解多目標(biāo)節(jié)點(diǎn)的情況具有良好的效果。

關(guān)鍵詞： QoS； 遺傳算法； 克??； 自適應(yīng)； 組播路由

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2015）04-15-03

Abstract： According to the features of the QoS multicast routing problem， by using the fixed-length gene encoding and the cloning operator to expand the population scale for genetic algorithm， the adaptive crossover operator and the mutation operator to control the generating of chromosomes are designed， which can effectively maintain population diversity and help the algorithm to find the global optimal solution. The experimental results show that the improved genetic algorithm has high speed and good convergence， can effectively solve the QoS multicast routing problem and has good results for solving multi-objective node case.

Key words： Quality of Service； Genetic algorithm； clonal； adaptive； multicast routing

0 引言

近年來(lái)隨著網(wǎng)絡(luò)的普及，網(wǎng)絡(luò)數(shù)據(jù)的傳輸也逐漸向多媒體數(shù)據(jù)方向邁進(jìn)。多媒體數(shù)據(jù)信息量大，在傳輸?shù)倪^(guò)程中，一旦發(fā)生網(wǎng)絡(luò)擁堵，數(shù)據(jù)很可能會(huì)全部丟失。為滿足用戶不同的傳輸要求，QoS[1]（Quality of Service）技術(shù)應(yīng)運(yùn)而生。該技術(shù)的運(yùn)用能有效預(yù)知網(wǎng)絡(luò)是否暢通，能夠根據(jù)實(shí)時(shí)的網(wǎng)絡(luò)狀況來(lái)分配網(wǎng)絡(luò)帶寬，從而使更合理地利用網(wǎng)絡(luò)通信資源成為可能。

遺傳算法（Genetic Algorithm， GA）是一種仿生算法[2]，它通過(guò)模擬生物的進(jìn)化過(guò)程對(duì)問(wèn)題進(jìn)行求解。GA算法能有效的對(duì)全局進(jìn)行搜索，從而能快速的找到問(wèn)題的解。它具有很強(qiáng)的魯棒性，是一種并行的搜索方法。但GA方法在進(jìn)化過(guò)程中，只對(duì)優(yōu)秀的個(gè)體簡(jiǎn)單的選擇保留，而且經(jīng)典GA算法的交叉和變異環(huán)節(jié)存在隨機(jī)性，這就導(dǎo)致算法的搜索效率不高，易于陷入局部極值。為了能有效解決傳統(tǒng)GA算法的這些問(wèn)題，引入克隆算子[3]增加GA算法的群體規(guī)模，增加種群的多樣性，設(shè)計(jì)自適應(yīng)的交叉算子和變異算子，提出一種基于自適應(yīng)克隆遺傳算法（Adaptive Clonal Genetic Algorithm，ACGA）并把該方法用于解決QoS路由優(yōu)化問(wèn)題，以期能更好的解決QoS多目標(biāo)路由的問(wèn)題。

1 QoS的網(wǎng)絡(luò)模型及數(shù)學(xué)描述[1-2]

2 基于ACGA的QoS多播路由優(yōu)化模型

2.1 編碼

2.3 克隆算子

ACGA算法通過(guò)克隆算子增大群體規(guī)模，有效增加種群的多樣性，利于尋找到全局最優(yōu)解。算法采用如下的方式對(duì)群體進(jìn)行克隆操作：對(duì)于群體里的每一個(gè)染色體ai按方程ln（α×N/i）克隆到新的群體中，α為克隆系數(shù)，ln（*）為自然對(duì)數(shù)函數(shù)。

2.4 交叉算子和變異算子

2.5 克隆選擇算子

在選擇環(huán)節(jié)設(shè)計(jì)如下的克隆選擇算子：對(duì)變異前的種群A（x）和變異后的種群A'（x'）進(jìn)行合并，形成新的種群D（x）。計(jì)算D（x）所有染色體的適應(yīng)度值并排序，選擇前N個(gè)且互不相同的染色體組成新種群。

2.6 ACGA算法的基本步驟

ACGA算法的基本步驟如下：

Step1 根據(jù)給定的編碼規(guī)則對(duì)基因進(jìn)行編碼，并初始化群體規(guī)模N、交叉概率Pc、變異概率Pm、進(jìn)化代數(shù)t=0以及最大進(jìn)化代數(shù)MaxGen；

Step2 對(duì)群體里的每一個(gè)個(gè)體進(jìn)行適應(yīng)度的評(píng)價(jià)；

Step3 對(duì)種群分別進(jìn)行克隆、交叉、變異以及克隆選擇操作，得到下一代的群體；

Step4 當(dāng)t?MaxGen時(shí)，輸出符合要求的染色體，算法結(jié)束；否則，t=t+1，跳轉(zhuǎn)到Step2。

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

實(shí)驗(yàn)借鑒文獻(xiàn)[6]利用改進(jìn)的Waxman網(wǎng)絡(luò)作為實(shí)驗(yàn)的仿真模型。采用的硬件配置為酷睿I3 3.0GHz、4G RAM，在WinXP系統(tǒng)下，利用Matlab7進(jìn)行多次仿真實(shí)驗(yàn)。Waxman網(wǎng)絡(luò)拓?fù)涞奶攸c(diǎn)是以概率p（u，v）=βexp（-d（u，v）/2α·n）對(duì)每對(duì)節(jié)點(diǎn)進(jìn)行連接，并按照Salama算法使網(wǎng)絡(luò)拓?fù)浞抡婺Ｐ偷钠骄?jié)點(diǎn)度滿足指定的值。一般n為仿真模型的節(jié)點(diǎn)數(shù)，網(wǎng)絡(luò)拓?fù)渲械拈L(zhǎng)邊和短邊比例以及邊的密度分別由α和β這兩個(gè)參數(shù)進(jìn)行控制。實(shí)驗(yàn)中相關(guān)參數(shù)的設(shè)置如表1所示。當(dāng)節(jié)點(diǎn)數(shù)n=20時(shí)，不同時(shí)延約束下ACGA算法的組播樹代價(jià)如表2所示。

為了能更好的證明ACGA算法的有效性，把ACGA算法和傳統(tǒng)的GA算法做了對(duì)比實(shí)驗(yàn)，如表3所示。從表3中可以看到，ACGA算法具有更低的組播代價(jià)。此外，在試驗(yàn)中設(shè)置節(jié)點(diǎn)數(shù)n的取值從10一直變化到200，在這變化過(guò)程中，ACGA算法和GA算法的運(yùn)行時(shí)間如圖1所示。

從圖1中很明顯的看到，ACGA算法具有更快的運(yùn)行速度，雖然在前面還比GA算法花費(fèi)了更多的時(shí)間，這主要是由于采用克隆算子增大的群體規(guī)模，因而速度會(huì)稍微受到影響，而從圖1中可以看到這個(gè)差距并不明顯。隨著n的增大，ACGA算法的運(yùn)行效率就體現(xiàn)出來(lái)了。

4 總結(jié)

本文提出一種自適應(yīng)克隆遺傳算法解決QoS多播路由的問(wèn)題，算法采用固定長(zhǎng)度的基因編碼方式，設(shè)計(jì)了自適應(yīng)的交叉算子和變異算子，并利用克隆算子來(lái)擴(kuò)大群體規(guī)模，有效增加種群的多樣性，有利于提高算法全局的尋優(yōu)能力，收斂速度快，對(duì)于求解多目標(biāo)節(jié)點(diǎn)的情況具有良好的效果。

參考文獻(xiàn)：

[1] 陳琳，王有平.基于遺傳算法的QoS多播路由策略研究[J].長(zhǎng)江大學(xué)學(xué)報(bào)（自然科學(xué)版），2011.8（11）：58-61

[2] 莫振華，蔡鴻明，姜麗紅.基于遺傳算法的多QoS約束服務(wù)選擇[J].計(jì)算機(jī)應(yīng)用與軟件，2009.26（3）：4-6，48

[3] 李陽(yáng)陽(yáng)，焦李成. 求解SAT問(wèn)題的量子免疫克隆算法[J].計(jì)算機(jī)學(xué)報(bào)，2007.30（2）：176-183

[4] 陳曉娟，陳婧.基于遺傳模擬退火的QoS單播路由算法[J].計(jì)算機(jī)應(yīng)用研究，2012.29（12）：4680-4682

[5] 趙麗娜，劉培玉，朱振方.自適應(yīng)遺傳算法在特征選擇中的改進(jìn)及應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2009.45（7）：39-41

[6] 尹向東，費(fèi)洪曉.基于蟻群優(yōu)化的分布式QoS多播路由方法研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009.30（5）：1107-1109