基于量子遗传算法和IMST算法的QoS多播路由算法

摘要

This paper proposes a QoS multicast routing algorithm based on Quantum Genetic Algorithm (QGA) and Improved Minimum Spanning Tree (IMST) ,First, the quantum crossover is used which can maintain the relatively good gene blocks ,Second, the strategies of updating quantum gate using qubit phase approach and adjusting search grid adaptively are introduced,which causes the population multiple ; Third, The IMST is introduced as a scheme to form restrained Steiner tree , which is characterized by good global search capability and short computing time ;The experiments show that the proposed algorithm can find the global optimal solution with less computation and evolving time ; This method is superior to conventional genetic algorithms and quantum genetic algorithm in quality and efficiency.%本文提出了一种求解QoS多播路由算法,该算法基于量子遗传算法(Quantum Genetic Algorithm ,QGA)和IMST算法(Improved Minimum Spanning Tree,IMST),首先在量子个体上实施量子交叉,这一操作有利于保留相对较好的基因段;其次,采用量子比特相位法更新量子门和自适应调整搜索网格的策略,使得种群的多样性强;最后,引入改进的MST算法进行受约束最小Steiner 树的生成,解的收敛精度高,收敛速度快;通过仿真实验标明此算法在种群规模较小,迭代次数较少的情况下就可以收敛到最优解,该算法的优化质量和效率都强于传统遗传算法和量子遗传算法.