基于遗传模拟退火算法的多约束QoS组播路由算法①

刘金明， 仲光苹

(1.黑龙江八一农垦大学信息技术学院，黑龙江 大庆 163319;2.东北石油大学数学科学与技术学院，黑龙江 大庆 163318)

0 引言

多约束QoS组播路由问题实际上就是带多个QoS约束的Steiner树问题，是典型的NP完全问题[1]，存在大量基于蚁群算法、遗传算法等智能搜索算法的求解方法，其中应用最多的就是遗传算法及其改进算法.文献[2]中Xiang等提出了基于遗传算法来求解QoS路由问题，其算法采用的二进制编码方法，导致其搜索空间会随着网络规模的增大而急剧增大.文献[3]中Wang等提出基于遗传算法求解带宽和时延约束费用最小组播路由问题，其算法采用树型结构编码策略，算法的性能较好，但树形编码却带来了非常复杂的交叉和变异操作.文献[4]中Hamdan等针对时延和时延抖动约束的费用最小组播路由问题，提出了基于整数队列编码策略的遗传算法求解方法，算法的编码方式非常简单，且效率较高.文献[5]中刘金明等提出了基于遗传模拟退火算法求解组播路由问题的相关方法，但是只涉及了带宽和时延两个QoS约束条件.文献[6]中，张琨等提出了基于模拟退火方法的多约束QoS组播路由算法，算法求得的组播路由树的费用性能较好，但由于模拟退火算法自身的不足，导致算法的效率比较低.本文在前人研究基础上，提出基于遗传模拟退火算法的多约束QoS组播路由算法，该组播路由算法采用基于备选路径集策略的整数队列编码方法，结合模拟退火算法……