基于克隆遗传的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