第6期 孔笋，等：一种新的混沌蚁群算法及其在QS组播路由优化问题中的应用 ·499· 问题中，文献[7]提出一种用遗传蚁群算法来求解 3)bandwialth(P(s,t))=min bandwiath(e), QoS组播路由问题，采用遗传算法对蚁群算法的4 eEP(s,t); 个控制参数进行编码、优化操作，为参数的选择提供 4)delay_jitter(P(s))=delay_jitter(e) 了依据，更快地引导蚁群系统找到全局最优解；文献 delay_jitter(n); [8]基于蚁群算法的组播路由问题中，设计了一种 nepst) 自适应的挥发因子，用来控制算法的全局搜索能力； 5)packet_os(Pr(s,)）=1-.及，（1-pack- 文献[9]提出一种改进的自适应蚁群算法，在信息 et_lass(n)). 素更新策略中引入全局最优系数，然后以全局最优 式中：Pr(s,t)为组播树T(s,M)上源点s到终点t 系数为条件来自适应调整挥发因子和信息素强度常 的路由路径.以下给出QoS组播路由问题中约束条 数 件的定义：进行QoS路由的目的寻找一棵组播树 考虑到混沌优化算法具有随机性、遍历性、规律 T(s),满足： 性的搜索特点，一些研究者将混沌优化算法与蚁群 1)延迟约束：delay(P,(s,t))≤D; 算法相结合来提高蚁群算法性能0)，主要有以下 2)带宽约束：bandwidth(Pr(s,t))≥B; 几种结合形式：1)采用混沌初始化进行改善个体质 3)延迟抖动约束：delay_jitter(Pr（s,t))≤DJ; 量；2)在调整信息量中，加入混沌扰动，以使解跳出 4)包丢失率约束：packet_loss(Pr(s,t))≤PL,; 局部极值区间；3)使用混沌搜索算子在当前迭代的 5)费用约束：在满足上述4个约束条件下， 全局最优解附近搜索更好的解 cost(T(s,M))最小 与前面的混沌蚁群算法不同，文中结合蚁群算 其中：B、D、DJ、PL分别代表业务对网络带宽、延迟 法的参数特性，提出了一种新的混沌蚁群优化算法， 延迟抖动、包丢失率的约束限制.在本模型中假设所 其基本思想是采用混沌搜索对蚁群算法中的控制参 有的组播终点的带宽约束、延迟、延迟抖动和包丢失 数进行优化，从而得到更好的参数组合使蚁群系统 率约束均相同。 能更好、更快地找到全局最优解.文中将其应用于求 2蚁群算法及参数分析 解QoS组播路由问题，仿真结果显示混沌蚁群算法 的求解性能要优于遗传算法及蚁群算法， 本文将Dorigo等人提出的ACS算法「2-l3]中的 选路方式引入到基本的蚂蚁算法中，下面针对n个 1QoS组播路由问题描述 城市的旅行商问题(traveling salesman problem, 网络模型表示为赋权图G=(V,E)3,式中V TSP)给出相应的算法模型， 是图中所有网络节点组成的集合，E是网络双向链 1)路径选取原则. 路的集合，每一条边表示2个节点间的通信路径，假 蚁群算法是一种基于模型的搜索算法，它的搜 设网络是对称的.s∈V为源点，M∈{V-{s}}为终 索过程也是解的构造过程.对于求解TSP问题，当 点 蚂蚁在当前城市i选择下一个将要移动的城市⑧ 对于任一网络节点n∈V,定义4种属性，分别 时，依据式(1)、(2)给出的伪随机比例规则进行. 为：延迟函数delay(n)、延迟抖动函数 [arg,ma,r(·(t)i,i道q≤go; delay_.jitter(n)、包丢失率函数packet_.loss(n)、费用 else. 函数cost(n). (1) 对于任意链路e∈E,定义4种属性：延迟函数 P= delay(e),延迟抖动函数deday._jter(e),带宽函数 bandwidth(e)和费用函数cost(e). 「r(t)·t)/∑r()·()allowed; 0 else. 对于给定的源点s∈V,终点集合M,节点t∈M, (2) s和M组成的组播树T(s,M)存在下列关系： 式中：allowed={0,1,…,n-1}表示蚂蚁k下一步 1)delay(P,(s,)）=eA.delay(e）+.eAn 允许选择的城市集合；r:为边(i,)上的信息素强 delay(n); 度；ng为边(i,)的能见度；a为信息启发式因子，表 2)cost(T(s,M)）=.e8 ost(e）+An 示信息素对路径选择的重要性；B为期望启发式因 cost(n); 子，表示启发信息对路径选择的重要性；9是在[0