量子进化组播路由算法

Quantum inspired evolutionary multicast algorithm

近年来,时延受限的代价最小组播树问题备受关注。作为全局优化算法,遗传算法(GA)越来越多的用于解决组播路由问题。GA拥有比经典算法更强的搜索能力,但是它容易陷入"早熟",很难得到最优组播树。基于量子计算的机理和特性并结合进化计算,提出了一种新颖的量子进化组播路由算法(QEA),有效地解决了遗传组播路由算法中的"早熟"问题,并且在每代个体更新中采用量子旋转门策略加速了算法的收敛速度。算法实现简单,控制灵活。仿真结果表明QEA算法性能优于改进的进化算法即克隆多播路由算法(CS)和传统的遗传算法(GA)。

The problem of computing delay-constrained minimum-cost multicast trees is of great interest in the last few years.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-inspired evolutionary algorithm（QEA） to deal with multicast routing problem is presented,which saliently solves the ＂prematurity＂ problem in Genetic based multicast algorithm.Furthermore,in QEA,the individuals in a population are represented by multistate gene quantum bits and this representation has a better characteristic of generating diversity in population than any other representations.In the individual′s updating,the quantum rotation gate strategy is applied to accelerate convergence.The algorithm has the property of simple realization and flexible control.The simulation results show that QEA has a better performance than CS and traditional GA.