刘 洋，王文国

0 引言

随着网络的发展，特别是多媒体数据在网络中的大量传输，对网络的服务质量(QoS)提出了越来越高的要求，这些要求包括带宽、时延、延时抖动、丢包率［1］等。文献［2］证明基于两个或两个以上不相关可加度量的路由选择问题是NPC问题，传统算法无法在有效时间内找到最优路由。目前大部分学者采用启发式算法如遗传算法、蚁群算法、模拟退火算法等来解决这一问题。文献［3］采用Grover量子搜索算法解决多约束QoS路由问题，获得较好的效果。文献［4］利用自适应蚁群算法来搜索最优解，判断搜索过程中是否陷入局部最优，通过动态调整蚁群算法的参数来跳出局部最优。文献［5］采用了蚁群算法与遗传算法相结合的方式来解决QoS路由问题，获得了比使用单一算法更优的效果。文献［6］采用改进遗传算法来解决QoS路由问题，修改了遗传算法的编码、交叉和变异方式。文献［7］基于蚁群系统来解决多约束QoS路由问题。文献［8］通过路径交换来构造邻域解，利用模拟退火操作来解决多约束QoS组播路由问题。

蚁群算法作为一种群智能算法，通过蚂蚁之间的协作，利用信息素的正反馈来搜索最优解。但基本蚁群算法存在搜索时间长，易停滞等缺点。本文提出一种改进的蚁群算法，即将蚁群分为两个种群，其中一个种群的蚂蚁在寻路时将考虑到该链路蚂蚁聚集度的影响，并且降低选择蚂蚁聚集度较高链路的概率，防止在算法初始阶段蚂蚁大量聚集某一链路而陷入局部最优;另一种群的蚂蚁则按照基本蚁群算法来寻路。……