计算机论文：基于Hadamard门变异的量子遗传算法

　　计算机论文：基于Hadamard门变异的量子遗传算法

　　摘 要：为了解决量子遗传算法在函数优化过程中容易陷入局部极值问题，提出了一种Hadamard门变异的量子遗传算法，核心思想是利用小生境协同进化策略初始化种群，并采用动态调整量子旋转门策略对种群进行更新进化，加快算法的收敛速度，在量子变异过程中不采用量子非门变异而是利用Hadamard门变异操作，增加了种群的多样性，提高了全局搜索能力，保留了优秀信息。通过对典型复杂函数的优化测试，实验结果表明，提出的Hadamard门变异的量子遗传算法在效率和质量上与传统遗传算法和一般的量子遗传算法相比具有一定的优势。

　　关键词：遗传算法；量子旋转门；Hadamard门；量子遗传算法；小生境协同进化策略

　　中图分类号：TP18 文献标识码：A

　　1 引 言

　　量子遗传算法[1-3]（Quantum Genetic Algorithm，QGA）是融合了遗传算法和量子计算的一种概率优化算法，兴起于20世纪90年代后期并引起广泛的关注。量子计算是量子力学和计算科学结合的产物，具有经典算法不具有的量子超并行能力，能够对某些重要的经典算法进行加速[4]。利用量子计算理论中的叠加态、纠缠态以及相干性等特性，是量子遗传算法与其他优化算法的最大不同之处，利用量子计算中的量子旋转门理论来实现更新进化操作并且用量子比特编码来表示染色体。

　　量子遗传算法第一次被提出是在1996年，Narayanan[5]等人在遗传算法中引入了量子理论中的多宇宙概念，但是由于算法中没有涉及到量子态的更新进化，所以并不是真正意义上的量子遗传算法。2002年，Han[6]等人提出将量子理论中的量子比特和量子旋转门的概念引入了遗传算法中，提出了真正意义上的量子遗传算法。

　　把常规的二进制编码用量子比特编码代替是量子遗传算法的一大特点[7]。在解决优化问题上，文献[8]利用自适应调整搜索网格的策略和量子比特相位比较的方法对量子遗传算法进行调整，并用典型连续函数进行了测试，得到了很好的优化效果；文献[9-10]将小生境技术引入了量子遗传算法中,提高了算法的效率收敛效果；文献[11]中提出了一种新的寻优策略，将搜索空间扩展到3Bloch球面，通过测试函数证明改进算法提高了种群的多样性和算法的搜索能力；文献[12]将聚类和量子遗传算法相结合提出了一种混合算法，使用聚类选择小部分非冗余代表基因并应用量子遗传算法来确定，还提出了一种新的适应度函数，以减少不牺牲分类精度的基因的数目，该算法降低了高维微阵列数据的量子遗传算法的计算时间。同时，量子遗传算法在模糊控制和人工智能[13]方面的优化也有很明显的效果。本文基于对量子遗传算法的分析，提出了Hadamard门变异操作来代替原有的量子非门变异操作。本文中的HQGA的算法思想是在种群初始化过程中使用小生境协同进化策略，采用动态调整量子旋转门策略更新进化种群，并且在量子变异操作时利用Hadamard门变异，提高了算法的收敛速度、寻优和全局搜索能力。

　　2 量子遗传算法

　　量子遗传算法的关键是量子旋转门和量子比特编码的使用。在量子遗传算法中，染色体编码用量子比特的几率幅表示，利用量子旋转门策略在进化过程中使所有个体向最优解靠近，避免退化保证了进化方向，从而达到目标的优化求解的目的。

　　2.1 量子比特编码

　　在经典量子计算理论中，充当信息存储单元的物理介质是量子比特（qubit），分别用两个量子态即本征态和来表示，然后与经典位的0和1对应编码。量子遗传算法中与传统算法的最大不同之处在于，染色体的基因是用两个量子比特的状态表示，即一个量子比特可以表示“0”态或“1”态，还可以表示两种状态的任意叠加态，是一个线性组合的形式。这样该染色体就包含了所求问题的所有可能得信息，而不是再只表示某一个确定的信息。

　　一个量子比特编码可以表示为：

　　（1）

　　其中，和是概率福，表示对应的量子比特，是一对复数。量子比特处于态的概率表示为，量子比特处于态的概率表示为。

　　假设一条染色体具有个量子比特，其表示形式为：

　　（2）

　　其中，表示第代第个染色体，表示为染色体的基因数，为种群大小。

　　2.2 量子旋转门调整

　　与传统遗传算法不同，量子遗传算法并没有采用选择、交叉和变异等操作，而是利用量子理论中特有的量子门调整策略来实现种群的更新进化。量子遗传算法是通过量子门的旋转调整改变量子态概率来保持种群的多样性，其核心思想是使当前解收敛到一个具有更高适应度的个体，在量子遗传算法中利用量子旋转门调整策略的更新进化操作就显得非常的重要，其公式如下：

　　（3）

　　其中，表示的是当前染色体的第个基因，表示的是当前染色体经过旋转门更新后的新基因。但是传统的量子旋转门调整策略的角度取值是固定的，这会给算法造成一定的局限性，如果旋转角的幅度太小，影响算法的收敛速度；相反，如果旋转角的幅度太大，则会导致算法出现过早成熟。针对这一问题，设计了一种动态调整旋转角的策略，如下[14]：

　　（4）

　　其中，的取值区间为，区间是的最小值用表示，区间上的最大值用表示。

　　（5）

　　其中，搜索到的最优个体适应度用来表示，当前个体的适应度用表示。

　　3 基于Hadamard门变异的量子遗传算法

　　3.1 小生境协同进化策略

　　由于小生境协同进化策略可以有效地解决多峰优化问题，在许多优化算法中都有广泛的应用。本文的算法将基于概率划分的小生境协同进化策略引入了种群初始化进程，其主要核心思想是将量子位划分成N个概率空间，通过式（6）对概率空间进行划分，使每个子种群在初始化时具有相同概率。

　　（6）

　　其中，公式（6）表示N个种群中第个种群的初始值。引入小生境协同进化策略的初始化方法比传统的初始化方法更易于寻到最优染色体。

　　3.2 Hadamard门变异操作

　　在量子遗传算法的进化过程中，量子染色体在量子旋转门调整策略的作用下向某一确定的方向发生坍缩。如果算法在进化过程中没有加入变异操作，当量子位出现收敛状态时，测量值就会固定于0或1，很难再跳出，算法易出现过早熟问题。量子非门的变异操作实际上就是将当前选中的量子比特的叠加状态进行更改，使量子比特的状态原来倾向于状态“1”的改变成倾向于状态“0”，或者相反。通过这种变异方法来增加量子染色体的多样性，提高局部搜索能力，避免出现早熟现象。

　　本文在量子变异操作过程中改变了变异方法，引入了Hadamard门执行变异操作，实现方法如下：

　　（7）

　　其中，Hadamard门的变异角度，、分别表示第个染色体的第位。以往的量子变异操作常采用量子非门的方法实现，就是将用角度编码的量子位的两个基因位角度幅值旋转。假设某一基因位角度为，则旋转后的角度为，角度正向旋转了。事实上，个体在经过量子旋转门更新之后，其子代个体有可能已经非常的接近最优解，如果在这种情况下再采取量子非门执行变异，就会使量子比特原本倾向于状态“0”的变为倾向于状态“”，这样造成量子位的更新向着完全相反的方向进行，极有可能造成种群震荡，导致优秀信息的丢失。

　　因此，在本文中的量子遗传算法，在进化的过程中采用Hadamard门执行变异操作。首先设定一定的变异概率，然后根据变异概率选择染色体和基因位，利用Hadamard门变异操作对染色体施加轻微的波动，这样可以有效地使种群跳出当前最优解，增加种群的多样性，进行多方向的搜索，同时也保持了种群的稳定性，保证了子代种群中的优秀信息不会丢失。

　　由图1可以看出，利用Hadamard门变异操作的QGA的收敛速度和寻优能力都明显的优于量子非门变异的QGA。

　　图1量子非门和Hadamard门变异操作的比较

　　Fig.1 Comparison of quantum gate and Hadamard gate mutation

　　3.3 算法流程

　　（1）种群初始化，首先确定种群大小，量子染色体的长度，变异概率为，利用小生境协同进化策略将种群空间划分为若干段相同概率的量子染色体，如公式（6），以此减少种群进化的迭代次数，设进化代数；

　　（2）测量，根据种群的概率幅取值构建其观测态；

　　（3）评估和保存，对观测态中的每个个体用适应度函数进行评估，记录下最优结果，判断是否满足终止条件，若满足，则终止算法，否则执行下一步；

　　（4）更新，更新种群，根据公式（4）动态调整量子旋转角度策略计算出量子旋转门的旋转角；

　　（5）执行Hadamard门变异操作；

　　（6），回到（2）继续寻优，直到算法结束。

　　4 算法的性能分析

　　4.1 算法收敛性分析

　　定理3.1 设为一阶可归约矩阵：

　　其中，是一个的基本随机矩阵，而且，则

　　是一稳定随机矩阵，且与初始分布无关，并且存在：

　　定理3.2 量子遗传算法是全局收敛的。

　　在量子遗传算法中，假设种群规模为，染色体长度为，因为在种群初始化时的取值是连续的，所以状态空间在理论上是无限的，但在实际运算中的取值是有限精度，所以设状态空间维数为，则种群所在状态空间大小为。

　　算法的整个过程可表示为：

　　其中，、、分别为，，阶随机矩阵，由交叉选择算子的含义可知：

　　其中，是量子染色体维的分布概率向量；、均为普通染色体维的分布概率向量；为维的概率转移矩阵；，，均为维的随机矩阵；，，，为阶的块对角矩阵。

　　由此可知算法的状态转移矩阵为：

　　根据定理3.1知：存在，且

　　与初始分布向量的初值无关。

　　假设记状态处于时刻算法的概率为，记适应度最高的个体的所有状态的集合为，则

　　从而得到

　　即算法是收敛的。

　　4.2 实验分析

　　对本文的算法的性能和有效性的验证，本文选取了以下几个经典连续函数[8,9]，并将传统遗传算法和一般的量子遗传算与本文算法进行对照比较。

　　实验环境：Inter(R) Core(TM) i5 CPU M 480@2.67GHz，操作系统为Windows7，硬盘位320G，算法在MATLAB 2014a开发环境下运行。

　　① Schaffer函数

　　② De Jong函数

　　③ sphere函数

　　④ Goldstein-Price函数

　　其中，在定义域内函数只有一个全局最小值；函数是一个很难收敛的单峰病态函数，在定义域内有一个极小值；定义域范围内函数只有一个极小值；函数在定义域内只有一个全局最小值。

　　本文用MATLAB对算法进行实现，设置传统GA种群大小popsize=20，交叉概率，变异概率；其中，传统QGA和本文的HQGA中的种群大小popsize=30，变异概率，最大遗传代数为200，其中设置子种群个数popnumber=10，每个子种群大小subpopsize=6。对连续函数分别用传统GA、QGA和本文的HQGA进行优化，并且分别运算100次，随机选取任意一次的运行结果,比较说明本文的基于Hadamard门变异的量子遗传算法具有更好的收敛性，寻优速度和局部搜索能力。得到如图2、3、4、5的目标函数变化曲线图。

　　图2 函数Schaffer的收敛曲线

　　Fig.2 Convergence curve of function Schaffer

　　图3 函数De Jong的收敛曲线

　　Fig.3 Convergence curve of function De Jong

　　图4 函数Sphere的收敛曲线

　　Fig.4 Convergence curve of function Sphere

　　图5 函数Goldstein-price的收敛曲线

　　Fig.5 Convergence curve of function Goldstein-price

　　根据算法运行时得出的算法的最优值、平均值、平均计算时间和平均终止代数等方面对算法的优化效率和算法质量进行验证，如表（1）。

　　根据表（1）中的数据可以看出，经过Hadamard门变异操作的量子遗传算法在求取最优解的精度上有很明显的优势，从图2到图5的收敛曲线图也可以看出改进的量子遗传算法的收敛速度更快，并且在迭代次数上，除了函数2也都有明显的减少更早的收敛到全局最优停止迭代。但是在运行时间上与遗传算法和量子遗传算法相比有所增加，主要是因为改进的量子遗传算法在初始化中引入了小生境协同进化策略进行种群的划分，并且还加入了Hadamard门的变异操作，所以本文的改进算法适用于对运行时间要求不高，但对求解精度要求高的场合。总体来说，本文提出的基于Hadamard门的量子遗传算法在函数优化上，具有更快的收敛速度和更好的全局搜索寻优能力。

　　表1 算法对比数据

　　Tab. 1 Algorithm comparison data

　　5 结 论

　　本文根据传统的量子遗传算法提出了一种基于Hadamard门变异的量子遗传算法，它不但融合了量子计算和遗传算法的优点，还利用小生境协同进化策略和Hadamard门变异操作增加种群的多样性，并且在更新过程中采用了动态调整量子旋转门策略，加快收敛速度，避免了在变异操作过程中造成种群震荡，丢失优秀信息的可能，同时也避免了在更新过程中出现的过早成熟的现象。通过算法性能分析结果表明，本文提出的方法在收敛速度和全局寻优能力等方面与传统经典算法相比有较好的效果，而且进一步提高了算法的性能。