摘  要： 经典遗传算法在解决QoS组播路由问题时存在易发生早熟现象、进化后期搜索效率低以及收敛后稳定性差等不足，为此，在遗传算法中引入混沌优化以及自适应调整交叉与变异概率两个改良措施。仿真实验表明，改良后的算法性能优良，在收敛速度、最优解的质量以及收敛后稳定性等方面有很大的提高。
关键词： 混沌；自适应；遗传算法；早熟；QoS组播路由

　QoS是指数据通过网络时向用户提供端到端的服务质量保证，其质量指标一般包括业务的延迟、延迟抖动、费用、带宽和丢包率等多个度量约束。如果QoS路由涉及两个以上的度量约束问题，则QoS组播路由计算是NP完全(NP-Complete)问题[1]，很难找到多项式时间的求解算法。
遗传算法GA(Genetic Algorithm)是模拟生物进化过程的一种智能算法，具有自适应性、并行性以及鲁棒性强等多方面的特点，可有效解决QoS组播路由选择问题。但经典遗传算法存在易发生早熟现象、进化后期搜索效率低以及收敛后稳定性差等缺点，而保持群体的多样性可有效避免遗传算法早熟的产生。为此，本文在遗传算法基础上，引入混沌优化以及早熟处理机制两个改良措施对群体进行扰动以增加群体的多样性。

2.4 群体初始化
　分别从到达每个目的节点候选路径集中任选一条路由组成一棵组播树作为初始群体的染色体。这样构成的组播树覆盖了所有的目的节点，群体多样性更有保证，并且消除了算法中的带宽约束，优化了网络的性能，减少了算法的搜索空间。
2.5 选择操作
2.5.1 引入Tent映射混沌优化
　混沌优化具有伪随机性、遍历性、周期性等特征，是一种全局和局部搜索能力都很强的新型算法，但是常用的Logistic映射的概率密度呈两头多、中间少的分布性质，故本文在遗传算法的选择操作中采用均匀分布特性更好的Tent映射混沌优化，可更有效抑制遗传算法产生早熟，并提高进化后期的收敛速度。Tent映射表达式为：

2.7 交叉操作
　遗传算法的全局随机搜索能力主要取决于交叉策略，本文以自适应的交叉概率进行交叉操作。在两个选中的染色体中选择一个公共基因作为交叉点，若存在两个或两个以上公共基因位时，则随机选取一个作为交叉点，交叉时，各染色体交换交叉点之后的基因段生成两个新子体，交叉过程示如图1所示。图中，节点n2、n5为潜在交叉点，选定n2为交叉点。
2.8 变异操作
　变异操作使遗传算法具有局部随机搜索能力，是保持群体多样性的一种有效进化操作，本文以自适应的变异概率进行变异操作。从染色体中随机选择两个基因为变异点n1、n2，以路径费用为指标，采用Dijkstra最短路径算法计算节点n1、n2之间的最短路径作为变异后的新路径，变异过程如图2所示。

2.9 染色体的修正操作[7]
　群体经过交叉和变异之后，可能会产生违反约束条件及产生环路的个体。修正操作就是维护违反约束条件及产生环路的染色体。修正维护操作可以采用惩罚策略和删除循环的方法来实现。
2.10 算法描述
　假设网络拓扑结构和QoS组播要求已知。网络中包含n个节点，其中包括m个目的节点。P为群体规模，i为当前进化代数，G为最大进化次数。组播要求包括源节点s，目的节点集M，QoS组播要求R(s，M，b，d，j，l)，算法运行步骤如下：
　(1)初始化相关参数；
　(2)对网络节点进行整数编码，生成侯选路径集并对路径进行整数编码；
　(3)根据侯选路径集随机生成初始化群体；
　(4)计算群体中所有个体的适应度函数值f；
　(5)根据本文描述的Tent混沌优化选择法进行选择操作；
　(6)若早熟，则自适应调整交叉概率Pc与变异概率Pm，群体交叉与变异并维护；
　(7)如果迭代次数大于G或当前最优解达到要求，则转到步骤(8)，否则转到步骤(4)；
　(8)解码并输出群体中适应度最大的个体，此即全局最优解，算法结束。
3 仿真实验与结果分析
　通过C#语言编写的程序实现本QoS组播网络路由算法[8]，采用的网络拓扑模型及网络链路参数[4]如图3与表1所示。

　QoS约束表示为R(s，M，b，d，j，l)，其中，以节点0为源节点s，目的节点为集合M={4，6，5}。设置组播具体要求：R(0，M，99，60，20，0.045)，QoS约束的权重参数(Wb，Wd，Wj，Wl，Wc)分别赋值(1，1，1，1E-06)，惩罚系数(rb，rd，rj，rl)分别取值(1，0.9，0.85，0.96)，群体规模P=50，最大进化次数G=200，交叉概率初始值Pc及其增强系数α分别取0.85、0.05，变异概率初始值Pm及其增强系数β分别取0.05、0.01。以费用的最小值为目标函数，用经典遗传算法和本文算法分别对组播路由计算进行仿真实验。结果显示，本文算法与经典GA在相同环境下求解速度分别为12.512 635 s和13.75 621 s，本文算法明显占优。从图4与图5的收敛曲线比较可知，本算法能更快速收敛到全局最优解且收敛后稳定性很高。

　在解决QoS组播路由计算问题时，经典遗传算法的群体多样性难以保证，易产生早熟现象，使搜索过早收敛于局部最优解且收敛后不够稳定。为此，本文改良了经典遗产算法，引入Tent映射混沌优化选择操作以及采用自适应的交叉与变异概率来处理群体早熟现象。仿真实验表明，本算法性能良好，在收敛速度、最优解质量以及收敛后稳定性等方面都很大的改善。
参考文献
[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].2008，34(4)：1-3.
[3] 王宇．基于遗传算法的QoS组播路由[D]．成都：四川大学，2003．
[4] 王军，马范援．基于遗传算法的QoS组播路由算法的适应度函数改进探索[J]．微型电脑，2008，24(8)：12-14．
[5] 邹恩，刘泽华，方仕勇，等．基于混沌遗传算法的组播路由优化研究[J]．计算机工程，2011，37(3)：155-157．
[6] 董勇，郭海敏．基于群体适应度方差的自适应混沌粒子群算法[J]．计算机应用研究，2011，28(3)：854-856．
[7] 孙宝林，李腊元.基于遗传算法的QoS多播路由优化算法[J].计算机工程，2005，31(14)：70-73.
[8] 王小平，曹立明．遗传算法一理论、应用与软件实现[M]．西安：西安交通大学出版社，2002．