基于通用量子门的量子遗传算法及应用
|
摘要
为加快量子遗传算法的参数更新速度,简化遗传操作步骤,提出了一种基于通用量子门的量子遗传算法(Quantum Genetic Algorithm with Universal Quantum Gate,UQGA)。该方法以通用量子门为逻辑计算单位,对染色体进行遗传操作。利用Hadamard门进行基础变换;通用量子门通过新的旋转角度函数,对各个基因位进行选择、变异操作;通过求解适应度函数,得到全局最优解;同时,算法经数学证明是收敛的。该算法应用到函数极值搜索和Iris数据集特征选择中。实验结果表明,UQGA具有较好的全局搜索和特征选择性能,尤其是在收敛速度、运算时间和分类准确率方面明显优于普通量子遗传算法和普通遗传算法。
To fasten the speed of parameters updating and simplified steps of genetic operation in quantum genetic algorithm, a novel algorithm of Quantum Genetic Algorithm with Universal Quantum Gates(UQGA)is proposed. In this method, firstly, universal quantum gate is the unit of logical computation for chromosomes. Then, Hadamard gate is used for basic operation. Each gene is selected and mutated with universal quantum gates through a novel function of rotation angle. Finally, by the solution of fitness function, the global optimal set is got. Meanwhile, the algorithm is mathematically proven to be convergent. The algorithm is applied in function extremum search and feature selection for Iris dataset. The experimental results indicate that, compared with CQGA and CGA, UQGA has better performance in global search and feature selection, especially in convergence speed, execution time and classification accuracy.
To fasten the speed of parameters updating and simplified steps of genetic operation in quantum genetic algorithm, a novel algorithm of Quantum Genetic Algorithm with Universal Quantum Gates(UQGA)is proposed. In this method, firstly, universal quantum gate is the unit of logical computation for chromosomes. Then, Hadamard gate is used for basic operation. Each gene is selected and mutated with universal quantum gates through a novel function of rotation angle. Finally, by the solution of fitness function, the global optimal set is got. Meanwhile, the algorithm is mathematically proven to be convergent. The algorithm is applied in function extremum search and feature selection for Iris dataset. The experimental results indicate that, compared with CQGA and CGA, UQGA has better performance in global search and feature selection, especially in convergence speed, execution time and classification accuracy.
引文
[1]Yang Y,Ma Z,Hauptmann A G,et al.Feature selection for multimedia analysis by sharing information among multiple tasks[J].IEEE Transactions on Multimedia,2013,15(3):661-669.
[2]谢娟英,谢维信.基于特征子集区分度与支持向量机的特征选择算法[J].计算机学报,2014,37(8):1704-1718.
[3]李胜,张培林,李兵,等.量子GA-PLS特征选择算法及其应用[J].量子电子学报,2014,31(2):194-201.
[4]Benenti G,Casati G,Strini G.Principle of quantum computation and information[M].[S.l.]:World Scientific,2007.
[5]辛馡,朱鳌鑫.遗传算法的适应度函数研究[J].系统工程与电子技术,1998,20(11):58-62.
[6]张思才,张方晓.一种遗传算法适应度函数的改进方法[J].计算机应用与软件,2006,23(2):108-110.
[7]Grefenstette J J.Predictive models using fitness distributions of genetic operators[J].Foundation of Genetic Algorithm,2014,3:139-161.
[8]李士勇,李浩.一种基于相位比较的量子遗传算法[J].系统工程与电子技术,2010,32(10):2219-2222.
[9]Sai Toh A.Rahimi R,Nakahara M.A quantum genetic algorithm with quantum crossover and mutation operations[J].Quantum Information Processing,2014,13(3):737-755.
[10]梁昌勇,柏桦,蔡美菊,等.量子遗传算法研究进展[J].计算机应用研究,2012,29(7):2401-2405.
[11]张莎莎,谷延锋,张钧萍,等.一种基于量子遗传算法的红外图像分割方法[J].哈尔滨工业大学学报,2007,39(9):1427-1430.
[12]李士勇,李盼池.基于实数编码和目标函数梯度的量子遗传算法[J].哈尔滨工业大学学报,2006,38(8):1216-1218.
[13]李士勇,李盼池.量子计算与量子优化算法[M].哈尔滨:哈尔滨工业大学出版社,2009.
[2]谢娟英,谢维信.基于特征子集区分度与支持向量机的特征选择算法[J].计算机学报,2014,37(8):1704-1718.
[3]李胜,张培林,李兵,等.量子GA-PLS特征选择算法及其应用[J].量子电子学报,2014,31(2):194-201.
[4]Benenti G,Casati G,Strini G.Principle of quantum computation and information[M].[S.l.]:World Scientific,2007.
[5]辛馡,朱鳌鑫.遗传算法的适应度函数研究[J].系统工程与电子技术,1998,20(11):58-62.
[6]张思才,张方晓.一种遗传算法适应度函数的改进方法[J].计算机应用与软件,2006,23(2):108-110.
[7]Grefenstette J J.Predictive models using fitness distributions of genetic operators[J].Foundation of Genetic Algorithm,2014,3:139-161.
[8]李士勇,李浩.一种基于相位比较的量子遗传算法[J].系统工程与电子技术,2010,32(10):2219-2222.
[9]Sai Toh A.Rahimi R,Nakahara M.A quantum genetic algorithm with quantum crossover and mutation operations[J].Quantum Information Processing,2014,13(3):737-755.
[10]梁昌勇,柏桦,蔡美菊,等.量子遗传算法研究进展[J].计算机应用研究,2012,29(7):2401-2405.
[11]张莎莎,谷延锋,张钧萍,等.一种基于量子遗传算法的红外图像分割方法[J].哈尔滨工业大学学报,2007,39(9):1427-1430.
[12]李士勇,李盼池.基于实数编码和目标函数梯度的量子遗传算法[J].哈尔滨工业大学学报,2006,38(8):1216-1218.
[13]李士勇,李盼池.量子计算与量子优化算法[M].哈尔滨:哈尔滨工业大学出版社,2009.