量子粒子群算法求解QoS组播路由

Quantum-behaved particle swarm optimization algorithm for QoS multicast routing

QoS组播路由问题是一个非线性的组合优化问题,已证明了该问题是NP完全问题。将量子粒子群算法用于此类问题的求解。并在此基础上对基本的量子粒子群算法进行改进,针对群体智能和约束优化问题的特点,提出了一种在每次迭代中有选择地保留一定数量不可行解的方法,并把它结合到量子粒子群优化(QDPSO)算法中。该算法可以利用保留下来的不可行解来帮助搜索靠近边界的最优解,同时又可以避免罚因子的选择问题,使之更适合于QoS组播路由的求解。仿真实验结果显示,该算法能快速搜索并收敛到全局(近似)最优解,且随着网络规模的增大算法保持了良好的特性,在寻优速度上与解的质量上优于其他粒子群算法与基本的量子粒子群算法。

QoS muhicast routing is a combination of nonlinear optimization problem,which has been proved that the problem is NP-complete problems.This paper applies Quantum-behaved Particle Swarm Optimization algorithm to such problems.The basic Quantum-behaved Particle Swarm Optimization algorithm is improved.Aiming at the characteristics of swarm intelligence and constraint optimization problems,a new iteration of each selected solution is not feasible to retain a certain number of ways, and it is combined into Quantum-behaved Particle Swarm Optimization algorithm.The algorithm can make use of the retained feasible solution to help search near the border of the optimal solution,at the same time avoid the penalty factor of choice to make it more suitable for QoS multicast routing solution.The simulation results show the algorithm can quickly search and convergence to the global （approximate） optimal solution,as the network size and the increase of algorithms to maintain good characteristics,the optimization of speed and the quality are superior to other evolutionary algorithm and the basic Quantum evolutionary algorithm.