张清富

(广东阳江市广播电视大学，广东 阳江 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 生成候选路径集合

在明确……