量子克隆多播路由算法  

Quantum Clonal Algorithm for Multicast Routing Problem

作　　者：李阳阳[1] 焦李成[1] 

机构地区：[1]西安电子科技大学电子工程学院智能信息处理研究所,陕西西安710071

出　　处：《软件学报》2007年第9期2063-2069,共7页Journal of Software

基　　金：Supported by the National Natural Science Foundation of China under Grant No.60372045(国家自然科学基金);the National Basic Research Program of China under Grant No.2006CB705700(国家重点基础研究发展计划);the National Research Foundation for the Doctoral Program of Ministry of Education of China under Grant No.20030701013(国家教育部博士点基金)

摘　　要：BSMA(bounded shortest multicast algorithm)被认为是最好的受限多播路由算法;然而,过长的计算时间限制了其应用.作为一种全局优化算法,遗传算法(GA)被越来越多地应用于解决多播路由问题.与传统的算法相比,遗传算法的全局搜索能力更强,但其易"早熟"的特点使它并不总是能够得到最优多播树.提出量子克隆多播路由算法,有效地解决了"遗传"多播路由算法中的"早熟"问题,量子交叉的引入,加快了算法的收敛速度.算法实现简单、控制灵活.仿真结果表明,该算法的性能优于BSMA算法和传统的遗传算法.The bounded shortest multicast algorithm （BSMA） is believed the best constrained multicast algorithm. However, the large computation time restricts its application. As a global optimizing algorithm, genetic algorithm （GA） is applied to solve the problem of multicast more and more. GA has more powerful searching ability than traditional algorithm, however its property of ＂prematurity＂ makes it difficult to get a good multicast tree. A quantum clonal algorithm （QCA） to deal with multicast routing problem is presented in this paper, which saliently solves the ＂prematurity＂ problem in Genetic based multicast algorithm. Furthermore, the algorithm is accelerated by using quantum crossover. The algorithm has the property of simple realization and flexible control. The simulation results show that QCA has a better performance than BSMA and traditional GA.

关 键 词：多播路由 BSMA 克隆算子 量子交叉 时延限制 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]