盧權(quán)

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

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

中圖分類號：TP393 文獻(xiàn)標(biāo)志碼：A 文章編號：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 引言

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

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

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

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

2.1 編碼

2.3 克隆算子

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

2.4 交叉算子和變異算子

2.5 克隆選擇算子

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

2.6 ACGA算法的基本步驟

ACGA算法的基本步驟如下：

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

Step2 對群體里的每一個個體進(jìn)行適應(yīng)度的評價；

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

Step4 當(dāng)t?MaxGen時，輸出符合要求的染色體，算法結(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）對每對節(jié)點(diǎn)進(jìn)行連接，并按照Salama算法使網(wǎng)絡(luò)拓?fù)浞抡婺Ｐ偷钠骄?jié)點(diǎn)度滿足指定的值。一般n為仿真模型的節(jié)點(diǎn)數(shù)，網(wǎng)絡(luò)拓?fù)渲械拈L邊和短邊比例以及邊的密度分別由α和β這兩個參數(shù)進(jìn)行控制。實(shí)驗(yàn)中相關(guān)參數(shù)的設(shè)置如表1所示。當(dāng)節(jié)點(diǎn)數(shù)n=20時，不同時延約束下ACGA算法的組播樹代價如表2所示。

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

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

4 總結(jié)

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

參考文獻(xiàn)：

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

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

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

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

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

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