NIQGA改进及基于可变角距离的新型量子进化算法  

Improvement on NIQGA and novel quantum-inspired evolutionary algorithm based on variable angle-distance

作　　者：刘文杰[1] 马廷淮[1] 闫荞荞[1] 郑玉[1] 

机构地区：[1]南京信息工程大学计算机与软件学院,南京210044

出　　处：《东南大学学报（自然科学版）》2011年第3期487-491,共5页Journal of Southeast University：Natural Science Edition

基　　金：江苏省自然科学基金资助项目(BK2010570);江苏省高校自然科学基金资助项目(09KJB520008);南京信息工程大学科研启动基金资助项目(20080298)

摘　　要：为了提高量子进化算法的执行效率,在NIQGA算法基础上,通过改进Δθi和S(αi,βi)参数表提出了一种改进算法INIQGA.又通过引入量子比特间角距离定义,提出了一种基于可变角距离旋转的量子进化算法QEA-VAR,该算法采用旋转门操作进行种群进化时,依据当前染色体中量子比特φ〉i与最优解对应基态0〉或1〉的角距离Δθφ〉i,*来动态选取旋转角度和方向,无须进行繁琐的查表操作.与以前基于查表机制的量子进化算法相比,QEA-VAR算法的执行过程更简单灵活,易于理解.0/1背包问题实验表明:INIQGA算法收敛速度和进化结果优于NIQ-GA原算法;QEA-VAR算法性能又优于INIQGA算法和其他同类进化算法QEA,CGA等,且随着物件个数的增长这种趋势越来越明显.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.

关 键 词：量子进化算法 NIQGA 可变角距离旋转 0/1背包问题 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP301.6[自动化与计算机技术—控制科学与工程]