第6期 孔笋，等：一种新的混沌蚁群算法及其在QS组播路由优化向题中的应用 ·501· 机选择下一个要行走的节点，启发函数？取 ③将混沌变量映射为优化变量，如式(8)： 1/(cost(e:)+cost(n)),期望值启发因子B采用B/ y=a;+(b-a;). (8) :代替，使期望值在迭代的后期减少对路径选择的 ④利用适应值函数对当前所得到参数运行后 干扰，避免陷入局部最优，加快逼近最优解的速度. 的算法性能作出评价，适应值评价函数设计如下： 当每只蚂蚁对任一目的节点选择了一条路径，则对 Fit(s)=61L.(s)+82V(s)+63G(s), 该路径进行局部信息素更新；当M只蚂蚁对所有的 L(s)=Lave, 目的节点都选择了一条到达的路径后，根据目标函 Vi(s)=ewk 数[3]计算各蚂蚁的所对应的目标函数值，并进行比 G(s）=1/Gm 较，获得当前迭代最优组播树和全局最优组播树，若 式中：Fi(s)为第k次搜索所找到的算法参数所对 当前迭代最优组播树包含环路，则逆序查询，直到找 应的适应值；6、62、63为权系数，并满足61+62+ 到无环路组播树，将该树作为当前迭代最优组播树， 83=1;L,(s)表示蚁群算法搜索到的最优路径的能 最后对全局最优组播路径进行信息素的更新.对于 力；Lw。为M只蚂蚁寻找到的组播树的平均目标函 每项约束，本文假设各目的节点的约束限制相同，且 数值；V(s)表示蚁群算法的收敛速度：D是蚁群当 delay(Pr(s,t))delay_jitter(Pr(s,t))packet_ 前迭代次数；K为总迭代次数；G(s)表示蚁群算法 loss(P,(s,t))分别取组播树中源节点到达各目的 的全局搜索能力；G为蚁群5个参数变量的和. 节点的最大约束值，目标函数为式(6) ⑤经比较如果当前搜索到的参数使得适应度 1 =comt[), 函数偏大，则采用该参数进行下一轮寻径，若适应度 函数偏小，则继续混沌搜索，直到寻找到更优的参数 fa=Φ.(delay(Pr(s,t)）-D), 或达到了最大步数 (中(z)= s0》 4)重复执行以上步骤，直到寻找到最优组播树. f=a(delay_jitter(Pr(s,t))-DJ), 4 仿真实验及比较 (Φg(z)= s0. 本文通过程序实现了混沌蚁群算法在解决QoS 组播路由优化的应用，仿真在Matlal7.0环境下实 fa=Φ，(packet_loss(Pr(s,t)-PL), 现.为了验证本文算法的有效性，本文采用了文献 (中(z）= 1,≤01 (6) [3]的网络结构模型进行实验仿真，并将混沌蚁群 ,2>0] 算法与应用于组播路由问题的遗传算法]、蚁群算 式中：Φ(z)是延时度量的惩罚函数，当满足延时约 法[8进行比较，网络拓扑图如图1所示： 束(delay(Pr(s,t)≤D)时，其值为l,否则等于ra (1,1,10,4)/ (0≤ra≤1)；中(z)是延时抖动度量的惩罚函数，当 满足延时抖动约束(delay-jitter(P,(s,t)≤DJ)时， 9,0.80,2) (1.1.10,112 (183,100.9) 3,0,80,3) (5,1,10,1) 其值为1，否则等于T(0≤r≤1)；中(z)是包丢失 5 3,1,1,10,2) (7,2.90.6) 率度量的惩罚函数，当满足包丢失率约束(packet_ 3,1,90,3) 3 loss(P(s,)≤PL))时，其值为1，否则等于tu(0≤ 6.1、30,8) 1 0,4) 3 (6.0 ra≤1)；Ta Ta Tp三者的值的大小决定惩罚的程度. 9,1,120,1) 在本文试验仿真中，ra=T=Tu=0.5. 6 (11,1,10.5) 3)将9、a、B、p1lp4ba作为待优化的混沌变 9 (2.0.10,9) 40.7) 量，并给定各参数相应的取值范围，利用Logistic映 (4,1,130,10) 1 射进行混沌搜索。 (12,2,80,12) (7,31,10,3) (2,0,10°，7) ①首先将5个参数变量利用式(7)映射为混沌 变量，取值范围为[0,1]， 图18节点网络模型] x=(y-a)/(b,-a). Fig.1 Eight-node network3] (7) 仿真实验以节点1为源节点，以节点2、节点4、 式中：y为优化变量，y:∈[a,b:],i=1,2,…,n,x 节点5、节点7为目的节点，寻找满足约束条件的最 为混沌变量。 优路径.参数go、aBp1 elobel为优化对象，初始值 ②用式(5)对混沌变量进行优化搜索