王文国，樊丽娟，刘 洋

（曲阜师范大学 信息科学与工程学院，山东 日照 276826）

改进的蚁群算法与网络QoS组播路由研究

王文国，樊丽娟，刘 洋

（曲阜师范大学 信息科学与工程学院，山东 日照 276826）

组播路由和网络服务质量（QoS），是当前Internet研究的两个重要应用课题。QoS组播路由是寻找满足特定QoS约束的一棵最优组播树，是一个典型的NPC完全多目标优化问题。针对传统蚁群算法，首次引入“蚁王”概念，使其能对路径寻优过程进行存储、排序和指导，从而使群体搜索过程更加协调有序。蚁群信息素的变化则采用精英信息素矩阵更新策略，以加快算法的收敛速度。相关仿真实验证明，这种改进的算法在解决QoS组播问题时，能够获得比基本蚁群算法明显优越的收敛性能。

蚁群算法；QoS组播路由；精英信息素；蚁王

0 引 言

蚁群算法（Ant Colony Optimization，ACO）是通过蚂蚁个体在候选解的空间中独立搜索解，并在搜寻的解上留下一定量的信息素；蚂蚁间以信息素为媒介进行间接、异步的信息传递。随着算法的推进，较优解路径上的信息素浓度会不断增加，同时其他路径上信息素浓度随着时间逐渐变弱；当算法趋于收敛时，在最优解路径上的信息素浓度最大。整个蚁群算法的最优解路径，在蚂蚁个体的共同协作下求得。意大利学者Dorigo等人通过模拟蚂蚁寻路觅食的群体行为提出了蚁群算法[1]，具有正反馈、分布式计算和贪婪启发式搜索的特点，广泛用于求解复杂的组合优化等问题[2-4]。近年来，也一些学者对该算法提出了若干优化方案[5-8]，并在不同应用领域进行了有益探索。……