摘  要： 提出了一种基于遗传多蚁群的QoS组播路由算法，前期利用遗传算法的快速性、全局收敛性生成蚁群算法的初期信息素；后期引入多蚁群思想，克服蚁群算法容易陷入局部最优，导致算法停滞的缺点。仿真结果表明，该算法在多节点情况下具有更强的寻优能力和可靠性，是一种有效的QoS路由方法。
关键词： QoS组播；遗传算法；蚁群算法；多蚁群

    随着网络应用越来越广泛，在传统的HTTP、FTP、E-mail等数据业务的基础上增加了各种实时和多媒体业务。要满足这些业务的需求，特别是要保证一些实时业务的带宽、时延等特殊需求，仅以目前Internet中“尽最大努力交付”的服务是难以完成的[1]。因此，组播技术的研究成为这个领域的热点，同时也对于组播的服务质量提出了更高的要求，QoS组播的需求已成为Internet相关技术的研究热点。Qos组播路由技术是网络支持QoS保证的关键技术之一，因此，高效的QoS组播路由算法就显得至关重要。而QoS路由的目的就是在网络中寻找满足用户对线路的带宽、延迟、延迟抖动、费用要求的路由，即向用户提供端到端的服务质量保证，而基于多个不相关可加度量的QoS路由问题是NP完全问题。目前一般采用智能优化算法来求解，如遗传算法、蚁群算法、模拟退火算法等。
    遗传算法[2]GA(Genetic Algorithm)的特点在于具有搜索能力、潜在的并行性及较强的鲁棒性，计算过程简单，能很好地解决开发最优解和探寻搜索空间的矛盾；蚁群算法[3]AC(Ant Colony Algorithm)是一个增强型学习系统，通过信息素的积累和更新收敛于最优路径上，具有正反馈、分布式的计算特性和很强的鲁棒性。
    将遗传算法和蚁群算法用于QoS组播路由已经取得较好的效果，但是缺点也很明显。遗传算法对于系统中的反馈信息利用不够，在中后期往往做大量无谓的迭代，求最优解的效率降低；蚁群算法则由于初期蚂蚁的随机活动使得前期信息素的更新较慢、求解速度慢，由于在后期容易早熟，而陷入局部最优。
    本文针对目前应用蚁群算法解决NP完全问题的研究现状，以基本蚁群算法为基础，提出一种遗传多蚁群融合算法(GAMAC_QoS)来解决QoS多约束组播路由问题，对多个约束QoS组播路由问题进行了研究。利用基本蚁群算法的分布式和全局搜索能力，使信息素积累和更新收敛于最优路径上。


    (3)初始种群生成
    采用随机方法从中选择若干个个体组成初始种群，首先删除不满足QoS约束条件的节点以及与之相连的链路，再删除不满足带宽要求的链路，得到一个新的精简后的网络拓扑。利用随机深度优先算法，生成源节点为根，目的节点为叶子的组播树。
    (4)选择算子
    采用个体最佳保留策略(最佳个体保留个数设置为2)与采用遗传算法中运用最广的轮盘赌选择机制执行选择功能。
    (5)交叉算子
    采用Davis顺序交叉方法，先进行常规的双点交叉，再进行维持原有相对访问顺序的巡回线路修改[5]。具体交叉如下：
    ①随机在父串上选择一个交配区域，如两父串选定为：
    old1=12|3456|789
    old2=98|7654|321
    ②将old2的交配区域加到old1的前面，将old1的交配区域加到old2的前面：
    old1’=7654|123456789
    old2’=3456|987654321
    ③依次删除old1’，old2’中与交配区相同的数码，得到最终的两子串：
    new1=765412389
    new2=345698721
    (6)变异算子
    采用逆转变异法逆转。如染色体(1-2-3-4-5-6)在区间2-3和区间5-6处发生断裂，断裂片段又以反向顺序插入，于是逆转之后的染色体变为(1-2-5-4-3-6)。这里的进化，是指逆转算子的单方向性，只有经逆转后，适应值有提高的才接受下来，否则逆转无效。
2.2 GAMAC_QoS中的多蚁群算法规则
    GAMAC_QoS算法定义了三种类型的蚂蚁：
    (1)全智能蚂蚁。蚂蚁按照传统蚁群算法选择规则选择下一节点，此蚂蚁称为全智能蚂蚁，简称为M1。
    (2)非智能蚂蚁。蚂蚁不按照选择规则来选择路径，而是随机地选择下一节点，此蚂蚁称为非智能蚂蚁，简称为M2。引入非智能蚂蚁是为了在算法陷入停滞时扩大搜索空间。
    (3)半智能蚂蚁。在选择下一节点时以δ概率按照全智能蚂蚁的选择策略选择下一节点，以1－δ概率按照非智能蚂蚁的选择策略选择下一节点，此蚂蚁称为半智能蚂蚁，简称为M3。考虑到算法在陷入停滞的时候，前期的部分次优解还是有价值的，因此引入半智能蚂蚁是最大程度地利用之前的次优解，增加搜索最优解的成功率。
    算法开始之时，蚂蚁的初值全为智能蚂蚁，数目为M，执行蚁群算法。当算法进行到停滞状态且比当前的参考值差的时刻，全智能蚂蚁发生变化，一部分转变成非智能蚂蚁，一部分转变成半智能蚂蚁，余下部分保持全智能蚂蚁的性质不变，其中半智能蚂蚁由智能蚂蚁和非智能蚂蚁组成，引入参数δ(0<δ<1)来决定其组成比例。蚂蚁状态发生变化后算法得以继续推进，智能蚂蚁的数目逐渐增加，非智能和半智能蚂蚁的数量逐步减少，最终为零，保证算法的收敛。
    (1)适应值函数与遗传算法的适应值函数相同。
    (2)路径选择策略[6]。全智能蚂蚁M1，其选择策略为：

    对于非智能蚁群M2，选择前进策略是不考虑任何信息素的反馈信息，随机选择下一节点，其前进策略如下：
 
    图2表示网络费用与迭代次数的关系，目的节点为20个，从图中可以看出，随着迭代次数的增加，该算法比基本蚁群算法具有更快的收敛性，最终组播树的费用也更低，与参考文献[7]算法相比收敛速度上相差无几，但是最终最优组播树的费用更低。

    针对蚁群算法的特点进行了改进，将遗传算法和蚁群算法相融合，并结合多蚁群的行为，提出了GAMAC_QoS组播路由算法。通过仿真实验证明，该算法相比于基本蚁群算法和参考文献[7]算法，在多节点中寻找组播树，具有更好的寻优能力、可靠性更高，是一种解决QoS组播路由的有效算法。该算法涉及参数较多，对于不同规模模型的网络的最佳参数设置问题，值得今后深入研究。
参考文献
[1] 孙倩，王新华，刘丽.QoS组播路由算法分析[J].计算机技术与发展，2009，8(19):97-99.
[2] HOLLAND J H. Adaptation in natural and artificial Systems[M]. Michigan: the University of Michigan Press， 1975.
[3] DORIGO M， GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation， 1997，1(1):53-66.
[4] 孙力娟，王汝传.基于蚁群算法和遗传算法融合的QoS组播路由问题求解[J].电子学报，2006，34(8):1391-1395.
[5] WHITE T， PAGUREK B， OPPACHER F. ASGA:Improving the ant system by integration with genetic algorithms[C]. In: Proe.3rdGenetic Programming Conf.. July 1998.
[6] 张凌，毛力.基于一种新的蚁群算法的QoS组播路由问题的研究[J].计算机工程与应用，2009，45(23):123-126.
[7] GONG B， LI L， WANG X I. A novel QoS multicast routing algorithm based on ant algorithm[C]//International Conference on IEEE Wireless Communications， Networking and Mobile Computing， 2007.