[1]刘文杰,马廷淮,闫荞荞,等.NIQGA改进及基于可变角距离的新型量子进化算法[J].东南大学学报(自然科学版),2011,41(3):487-491.[doi:10.3969/j.issn.1001-0505.2011.03.011]
　Liu Wenjie,Ma Tinghuai,Yan Qiaoqiao,et al.Improvement on NIQGA and novel quantum-inspired evolutionary algorithm based on variable angle-distance[J].Journal of Southeast University (Natural Science Edition),2011,41(3):487-491.[doi:10.3969/j.issn.1001-0505.2011.03.011]
点击复制

NIQGA改进及基于可变角距离的新型量子进化算法()
分享到：

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
41
期数:
2011年第3期
页码:
487-491
栏目:
自动化
出版日期:
2011-05-20

文章信息/Info

Title:
Improvement on NIQGA and novel quantum-inspired evolutionary algorithm based on variable angle-distance
作者:
刘文杰; 马廷淮; 闫荞荞; 郑玉
(南京信息工程大学计算机与软件学院, 南京 210044)
Author(s):
Liu Wenjie; Ma Tinghuai; Yan Qiaoqiao; Zheng Yu
(School of Computer and Software, Nanjing University of Information Science and Technology, Nanjing 210044, China)
关键词:
量子进化算法; NIQGA; 可变角距离旋转; 0/1背包问题
Keywords:
quantum-inspired evolutionary algorithm;  NIQGA(novel improved quantum genetic algorithm);  variable angle-distance rotation;  0/1 knapsack problem
分类号:
TP18;TP301.6
DOI:
10.3969/j.issn.1001-0505.2011.03.011
摘要:
为了提高量子进化算法的执行效率,在NIQGA算法基础上,通过改进Δθi和S(αi,βi)参数表提出了一种改进算法INIQGA.又通过引入量子比特间角距离定义,提出了一种基于可变角距离旋转的量子进化算法QEA-VAR,该算法采用旋转门操作进行种群进化时,依据当前染色体中量子比特|φ〉i与最优解对应基态|0〉或|1〉的角距离Δθ|φ〉i,*来动态选取旋转角度和方向,无须进行繁琐的查表操作.与以前基于查表机制的量子进化算法相比,QEA-VAR算法的执行过程更简单灵活,易于理解.0/1背包问题实验表明:INIQGA算法收敛速度和进化结果优于NIQGA原算法; QEA-VAR算法性能又优于INIQGA算法和其他同类进化算法QEA,CGA等,且随着物件个数的增长这种趋势越来越明显.
Abstract:
In order to enhance the efficiency of the quantum-inspired evolutionary algorithm, on basis of the original NIQGA algorithm, an improved algorithm (INIQGA) is put forward by revising the parameter table of Δθi and S(αi, βi). Through introducing the definition of angle-distance between qubits, a novel quantum-inspired evolutionary algorithm based on the variable angle-distance rotation strategy (QEA-VAR) is proposed. In the QEA-VAR algorithm, the rotation angle is dynamically chosen according to the angle-distance between the qubit |φ〉i in current chromosome and the basis state |0〉 or |1〉 of the optimal solution, when the corresponding rotation gate is performed to evolve the quantum population. The whole process does not need complicated look-up table operation. Compared with previous algorithms based on the look-up table mechanism, the QEA-VAR algorithm is more simple, feasible and comprehensible. Experiments on the well-known 0/1 knapsack problem show that INIQGA has a faster convergence and better profits than NIQGA, and QEA-VAR has even higher performance than INIQGA and other similar evolutionary algorithms like QEA, CGA. This effect is getting more apparent with the increase of the items in 0/1 knapsack problem.

参考文献/References:

[1] Kennedy J,Eberhart R C,Shi Y.Swarm intelligence [M].San Francisco:Morgan Kaufman Publishers,2001.
[2] Dorigo M,Blum C.Ant colony optimization theory:a survey [J].Theoretical Computer Science,2005,344 (2):243-278.
[3] Han K H,Kim J H.Genetic quantum algorithm and its application to combinatorial optimization problem [C]//Proc IEEE Congress on Evolutionary Computation. La Jolla,CA,USA,2000:1354-1360.
[4] Han K H,Kim J H.Quantum-inspired evolutionary algorithm for a class of combinatorial optimization [J].IEEE Trans Evol Comput,2002,6(6):580-593.
[5] Han K H,Kim J H.Quantum-inspired evolutionary algorithms with a new termination criterion,Hε gate,and two-phase scheme [J].IEEE Trans Evol Comput,2004,8(2):156-169.
[6] Narayanan A,Moore M.Quantum-inspired genetic algorithms [C]//Proc IEEE Int Conf Evolutionary Computation.Nagoya,Japan,1996:61-66.
[7] Kim Y,Kim J H,Han K H.Quantum-inspired multiobjective evolutionary algorithm for multiobjective 0/1 knapsack problems [C]//Proc IEEE Congress on Evolutionary Computation.Vancouver,BC,Canada,2006:2601-2606.
[8] Li B B,Wang L.A hybrid quantum-inspired genetic algorithm for multiobjective flow shop scheduling [J].IEEE Transactions on Systems,Man,and Cybernetics—Part B:Cybernetics,2007,37(3):576-591.
[9] Kim Y H,Kim J H.Multiobjective quantum-inspired evolutionary algorithm for fuzzy path planning of mobile robot[C]//Proc IEEE Congress on Evolutionary Computation. Trondheim,Norway,2009:1185-1192.
[10] Meng K,Wang H G,Dong Z Y,et al.Quantum-inspired particle swarm optimization for valve-point economic load dispatch [J].IEEE Transactions on Power Systems, 2010,25(1):215-222.
[11] 邢焕来,潘炜,邹喜华.一种解决组合优化问题的改进型量子遗传算法[J].电子学报,2007,35(10):1999-2002.
　　Xing Huanlai,Pan Wei,Zou Xihua.A novel improved quantum genetic algorithm for combinatorial optimization problems [J].Acta Electronica Sinica,2007,35(10):1999-2002.(in Chinese)
[12] Han K H,Kim J H.On the analysis of the quantum-inspired evolutionary algorithm with a single individual [C]//Proc IEEE Congress on Evolutionary Computation.Vancouver,BC,Canada,2006:2622-2629.

备注/Memo

备注/Memo:
作者简介:刘文杰(1979—),男,博士,讲师,wenjiel@163.com.
基金项目:江苏省自然科学基金资助项目(BK2010570)、江苏省高校自然科学基金资助项目(09KJB520008)、南京信息工程大学科研启动基金资助项目(20080298).
引文格式: 刘文杰,马廷淮,闫荞荞,等.NIQGA改进及基于可变角距离的新型量子进化算法[J].东南大学学报:自然科学版,2011,41(3):487-491.[doi:10.3969/j.issn.1001-0505.2011.03.011]
更新日期/Last Update: 2011-05-20