基于自适应混沌遗传算法的QoS组播路由

张清富

(广东阳江市广播电视大学，广东 阳江 529500)

QoS是指数据通过网络时向用户提供端到端的服务质量保证，其质量指标一般包括业务的延迟、延迟抖动、费用、带宽和丢包率等多个度量约束。如果QoS路由涉及两个以上的度量约束问题，则QoS组播路由计算是NP完全(NP-Complete)问题[1]，很难找到多项式时间的求解算法。

遗传算法GA(Genetic Algorithm)是模拟生物进化过程的一种智能算法，具有自适应性、并行性以及鲁棒性强等多方面的特点，可有效解决QoS组播路由选择问题。但经典遗传算法存在易发生早熟现象、进化后期搜索效率低以及收敛后稳定性差等缺点，而保持群体的多样性可有效避免遗传算法早熟的产生。为此，本文在遗传算法基础上，引入混沌优化以及早熟处理机制两个改良措施对群体进行扰动以增加群体的多样性。

1 网络模型[2]

2 自适应混沌遗传算法设计

2.1 编码设计

传统的二进制编码和实数编码不能精确地描述组播树的特性，本算法采用变长整数编码这种最自然、最简单的组播路由表示方式。给定一个源点和一组目的节点，群体中的每个个体(染色体)代表一棵多播树，可用树型数据结构描述个体结构。染色体码长为目的节点的个数m，第i位上的数值表示组播树中到第i个目的节点的路径的编号。 例如组播树{3，5，6，4，7，9}表示有 6 个目的节点，对第1个目的节点采用3号路径，对第2个目的节点采用5号路径，以此类推，每条路径是一个节点集合。

2.2 生成候选路径集合

在明确QoS组播要求之后，对每个目的节点 ti，采用Dijkstra前k条最短路算法找到从源点s到ti的满足带宽要求的所有路径并对路径进行整数编码，而其中的路径由网络节点的编号组成(节点集)，这就形成了组播树的候选路径集合。

2.3 适应度函数设计

其中，fb=φb(B(T(s，M))-b)，fd=φd(D(T(s，M))-d)，fj=φj(J(T(s，M))-j)，fl=φl(L(T(s，M))-l)，fc=φc(C(T(s，M))-c)，φb(x)

其中，fx表示s到ti路径的实际值与约束值的差值，Wb、Wd、Wj、Wl、Wc分别为 QoS 约束的权重参数，φ(x)为一个惩罚函数，其系数 rx∈(0，1)。

2.4 群体初始化

分别从到达每个目的节点候选路径集中任选一条路由组成一棵组播树作为初始群体的染色体。这样构成的组播树覆盖了所有的目的节点，群体多样性更有保证，并且消除了算法中的带宽约束，优化了网络的性能，减少了算法的搜索空间。

2.5 选择操作

2.5.1引入Tent映射混沌优化

混沌优化具有伪随机性、遍历性、周期性等特征，是一种全局和局部搜索能力都很强的新型算法，但是常用的Logistic映射的概率密度呈两头多、中间少的分布性质，故本文在遗传算法的选择操作中采用均匀分布特性更好的Tent映射混沌优化，可更有效抑制遗传算法产生早熟，并提高进化后期的收敛速度。Tent映射表达式为：

Tent映射在函数域空间中其概率密度的分布较均匀，可避免主要集中在变量空间的边缘区域进行搜索的不足。

2.5.2选择进化过程

自适应混沌遗传算法采用最佳混沌个体保留法与轮盘赌选择法相结合的选择方式。利用Tent映射函数混沌优化群体中个体的适应度函数值，选出最佳值个体，直接遗传到子代群体中，其余个体采用轮盘赌选择法选择。

2.6 自适应交叉概率与变异概率的设计

通过监测群体适应度方差与群体当前最优解的适应度连续变化情况来判断群体是否产生早熟。采用如下群体适应度方差公式[5]：

其中，P为群体规模，fi为个体适应度，favg为群体平均适应度，f为归一函数。数值实验发现，早熟收敛和群体适应度方差σ2存在某种相关度：当早熟收敛产生时，在连续数次迭代中σ2变化不大，趋于稳定，但是当算法收敛到全局最优解时，σ2同样存在以上的情况。综合考虑，判断群体产生早熟收敛的依据为：群体适应度方差与群体当前最优解的适应度的差值连续3次分别小于预先设定的阈值∈1、∈2，即 Δσ2<∈1、Δfmax<∈2。

产生早熟收敛的群体的多样性较差，个体相似度大，“劣种”较多，群体需要“突变“，这时可以加大群体的繁殖强度并增强群体的扰动，即增大交叉概率与变异概率，使其跳离局部最优解，采用如下公式：

2.7 交叉操作

遗传算法的全局随机搜索能力主要取决于交叉策略，本文以自适应的交叉概率进行交叉操作。在两个选中的染色体中选择一个公共基因作为交叉点，若存在两个或两个以上公共基因位时，则随机选取一个作为交叉点，交叉时，各染色体交换交叉点之后的基因段生成两个新子体，交叉过程示如图1所示。图中，节点n2、n5为潜在交叉点，选定n2为交叉点。

2.8 变异操作

变异操作使遗传算法具有局部随机搜索能力，是保持群体多样性的一种有效进化操作，本文以自适应的变异概率进行变异操作。从染色体中随机选择两个基因为变异点n1、n2，以路径费用为指标，采用Dijkstra最短路径算法计算节点n1、n2之间的最短路径作为变异后的新路径，变异过程如图2所示。

图1 染色体的交叉操作

图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所示。

图3 组播网络拓扑结构

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的收敛曲线比较可知，本算法能更快速收敛到全局最优解且收敛后稳定性很高。

表1 网络链路参数

在解决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.