摘要
在量子遗传算法(QGA)的基础上,提出了一种解决组合优化问题的改进型量子遗传算法(NIQGA).为充分利用量子态的干涉性和纠缠性,该算法引入了动态调整量子门旋转角步长机制、量子交叉操作和量子变异操作,因而具有更高的搜索效率.利用两种典型组合优化问题——0/1背包问题和路由选择问题进行验证.结果表明,相比于GA和QGA,NIQGA具有收敛速度快和全局搜索能力强的特点,在解决基因间弱关联性的组合优化问题时有更优的性能.
Based on quantum genetic algorithm（QGA）, a novel improved quantum genetic algorithm（ NIQGA） to solve combinatorial optimization problem is proposed. To make full use of interference and entanglement characteristics of quantum state, dynamic step length in adjustment of angle of quantum gate, quantum crossover operation and quantum mutation operation are introduced, therefore high efficiency for optimization is achieved. Two typical combinatorial optimization problems--0/1 knapsack problem and route selection problem, are adopted to confim the performance of NIQGA. Experimental results show that compared with GA and QGA,NIQGA is characterized by fast convergence rate and excellent capability on global optimization, especially better performance for combinatorial optimization problem with less correlation of genes.
出处
《电子学报》
EI
CAS
CSCD
北大核心
2007年第10期1999-2002,共4页
Acta Electronica Sinica
基金
国家自然科学基金(No.10174057
No.90201011)
教育部科学技术研究重点项目(No.105148)
关键词
量子计算
量子遗传算法
组合优化
quantum computation
quantum genetic algorithm
combinatorial optimization
