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

作　　者：王宝伟[1] 王洪国[1] 刘乐[1] 

机构地区：[1]山东师范大学信息科学与工程学院,济南250014

出　　处：《信息技术与信息化》2009年第3期14-17,共4页Information Technology and Informatization

基　　金：山东省自然科学基金(Q2006003)

摘　　要：本文提出了一种求解QoS多播路由算法,该算法基于量子遗传算法(Quantum Genetic Algorithm,QGA)和IMST算法(Improved Minimum Spanning Tree,IMST),首先在量子个体上实施量子交叉,这一操作有利于保留相对较好的基因段;其次,采用量子比特相位法更新量子门和自适应调整搜索网格的策略,使得种群的多样性强;最后,引入改进的MST算法进行受约束最小Steiner树的生成,解的收敛精度高,收敛速度快;通过仿真实验标明此算法在种群规模较小,迭代次数较少的情况下就可以收敛到最优解,该算法的优化质量和效率都强于传统遗传算法和量子遗传算法。This paper proposes a QoS muhicast 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.

关 键 词：量子遗传算 法旋转量子门 量子交叉 IMST算法 

分 类 号：TP393.01[自动化与计算机技术—计算机应用技术]