量子遗传算法及其改进与应用

于合谣+刘蕊蕊+冀鹏飞

【摘要】文章在介绍基本量子遗传算法（QGA）的原理、方法和基本流程的基础上，主要归纳总结了最近几年QGA的改进，包括理论基础的编码扩展、算子的创新和量子门旋转角度、复杂高维函数优化、混合算法等，以及新的应用研究成果，以及在不同领域的一些应用，进而提出了QGA未来的发展方向。

【关键词】遗传算法 量子遗传算法 量子门 人脸识别

一、引言

量子遗传算法（Quantum Genetic Algorithm），简称QGA，结合了量子计算的并行运算和遗传算法的种群多样性等优势，具有较高的全局搜索效率和种群多样性[1]。在遗传算法中，通过对适应度函数的研究，可以提升遗传算法的优化效果[1]。Narayanan等人[2]最先提出量子衍生遗传算法（QIGA）的概念；紧接着Han等人[3]提出真正意义上的基于量子比特和量子态叠加特性的量子遗传算法（QGA），并应用到解决背包问题，实现了比常规遗传算法更好的效果。目前，量子遗传算法的研究已经取得了一些研究成果，文献[4]总结了2011年以前对量子遗传算法的研究进展情况。

二、量子遗传算法QGA

QGA算法：基于量子位的表示方法和量子力学的态叠加原理，QGA的具体算法如下：

第一，初始化，包含n个个体的种群，其中Ptj（j=1，2，…，n）为种群中第t代的一个个体，且有，其中m为量子位数目，即量子染色体的长度。在开始时，所有αi，βi（i=1，2，…，m）都取。

第二，根据P（t）中概率幅的取值情况构造出R（t），，其中 是长度为m的二进制串。

第三，用适应值评价函数对R（t）中的每个个体进行评价，并保留次代中的最优个体。若获得满意解，则算法终止，否则，转入第四继续进行。

第四，使用恰当的量子门U（t）更新P（t）。

第五，遗传代数t=t+1，算法转至第二继续进行。

三、量子遗传算法QGA的改进

目前，对量子遗传算法的研究主要集中在染色体编码方式和参数更新方面，其本质仍是单纯的引入量子计算的基本原理。但是，对如何能更好地实现量子遗传算法，并应用于量子计算机等研究还不够深入，从而，导致现有量子遗传算法的运算效率和特征选择效果没有达到预期目标，因此，本文提出了一种新的特征选择算法—基于通用量子门的量子遗传算法（Quantum Genetic Algorithmwith Universal Quantum Gate，UQGA）。在该算法中，首先，以Hadamard门为基础，之后，根据新的旋转角度函数，利用通用量子门对染色体中各个基因进行遗传操作，最后，以适应度函数值为标准，得到求解问题的全局最优解集。

基于通用量子门的量子遗传算法整体结构描述如下：

第一，量子态描述：其中公式为

第二，种群初始化：设量子种群Q（t）={q1，q2，…，qm}，qj为其中的一个量子染色体，含有m个量子位，则

第三，Hadamard门变换。Hadamard门变换是量子计算逻辑运算的基础，对qj进行Hadamard门变换，以便于幺正变换。

第四，构造适应度函数。为了提高适应度函数的灵敏度，根据规范性、合理性和计算量简单等设计原则，以函数的下界为标准，在原有适应度函数的基础上，设计了新的适应度函数，根据下界对qj计算适应度值，以判断量子染色体的质量。

第五，选择操作。利用受控门Ucnot依据适应度值对qj进行选择，以达到优胜劣汰的目标。又由于Fit（f（x））∈[0，1]，适应度函数值越大，其特征越少，可避免算法造成欺骗，因此，根据经验所得，本文选择0.9950作为节点，如下判别方式：

①若Fit（f（x））∈[0，0.9950]，则该染色体被淘汰；

②若Fit（f（x））∈[0.9950，1]，则该染色体被选择，保留最佳个体。

其函数表达式为

其中，q”j值是根据Fit（f（x））判别并经Ucnot后的。

第六，遗传操作。若当代染色体被选择，则使用量子旋转门R对q”j进行遗传操作，以更新染色体中的量子位，其函数表达式为

虽然遗传操作没有明确的交叉和变异操作，但是由于量子态的概率表示和量子旋转门的操作，使得种群可以保持多样性。同时，对于旋转角度的局部最优解，一般采用经验方式，来寻找适应度函数的全局最优解。

第七，终止条件。当达到设定的最大迭代次数tmax或者Fit（f（x））的值達到最佳时，循环终止；否则，将返回步骤第三迭代计算。

四、量子遗传算法QGA的应用

根据QGA的种群多样性好，全局收敛性强的优点，基于QGA的人脸图像分割，将其应用于人脸图像的阈值分割，从而达到提高计算速度和计算精度的目的。运用QGA时，必须进行两个重要步骤：即把所有问题的解编码成染色体；永和市的适应度函数返回值来评价个体的好坏。

参考文献

[1]李胜，张培林，李兵，胡胜海，胡浩.基于通用量子门的量子遗传算法以及应用[J].计算机工程及应用.2017，53（7）：54-59.

[2]Narayanan A，MOORE M.Quantum-inspired genetic algorithm[C].Proc of IEEE Internation on Conference on Congress on EvolutionaryComputation.1996：61-66.

[3]Han K H，Kim J H.Genetic quantum algorithm and its application to combinatorial optimization problem[C].Proc of IEEE Congress on Evolutionary Computation，2000：1354-1360.

[4]梁昌勇，柏桦，蔡美菊等.量子遗传算法研究进展[J].计算机应用研究，2012，29（7）：2401-2405.

作者简介：于合谣（1993-），女，汉族，山东日照人，就读于山东科技大学，研究方向：控制理论。