基于并行量子遗传算法的QoS组播路由方法

通信网络时延受限且满足带宽要求的最小代价组播树问题是NP完全问题,传统方法难以求解,一般采用启发式方法求解.提出了一种基于并行量子遗传算法的服务质量(QoS)组播路由算法,算法中将各个子群体独立地并行进化,并通过相邻子群体间的信息交换实现克服早熟,避免局部收敛的目的,还提出了一种新的动态旋转角调整策略,使算法具有更好的种群多样性和全局寻优能力.仿真实验表明,新算法在求解性能上优于遗传算法(GA)和采用静态旋转角的量子遗传算法(QGA).

A QoS Multicast Routing Approach Based on Parallel Quantum Genetic Algorithm

The problem of minimum cost multicast tree satisfying bandwidth request and delay-constraint in communication network is a NP-complete problem.It is difficult to be solved by traditional methods.At present,heuristic methods(such as GA algorithm) are used.In this paper,an approach based on parallel quantum genetic algorithm(PQGA) is proposed to solve QoS(Quality of Service) multicast routing.In this algorithm,each subpopulation evolves independently and concurrently,and prematurity and partial convergence are avoided by information exchange among neighboring subpopulations.In addition a new dynamic rotating angle adjustment policy is proposed,leading to better seed population diwersity and glolal optimization capability of the algorithm.The simulation results have shown that PQGA has better performance than QGA with static rotating angle and GA.