基于克隆遺傳的QoS多播路由優化模型

盧權

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

關鍵詞： QoS； 遺傳算法； 克隆； 自適應； 組播路由

中圖分類號：TP393 文獻標志碼：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 引言

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

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

1 QoS的網絡模型及數學描述[1-2]

2 基于ACGA的QoS多播路由優化模型

2.1 編碼

2.3 克隆算子

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

2.4 交叉算子和變異算子

2.5 克隆選擇算子

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

2.6 ACGA算法的基本步驟

ACGA算法的基本步驟如下：

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

Step2 對群體里的每一個個體進行適應度的評價；

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

Step4 當t?MaxGen時，輸出符合要求的染色體，算法結束；否則，t=t+1，跳轉到Step2。

3 仿真實驗及結果分析

實驗借鑒文獻[6]利用改進的Waxman網絡作為實驗的仿真模型。采用的硬件配置為酷睿I3 3.0GHz、4G RAM，在WinXP系統下，利用Matlab7進行多次仿真實驗。Waxman網絡拓撲的特點是以概率p（u，v）=βexp（-d（u，v）/2α·n）對每對節點進行連接，并按照Salama算法使網絡拓撲仿真模型的平均節點度滿足指定的值。一般n為仿真模型的節點數，網絡拓撲中的長邊和短邊比例以及邊的密度分別由α和β這兩個參數進行控制。實驗中相關參數的設置如表1所示。當節點數n=20時，不同時延約束下ACGA算法的組播樹代價如表2所示。

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

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

4 總結

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

參考文獻：

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

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

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

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

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

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