改 进 进 化 方 向 的 量 子 遗 传 算 法

安 秀 芳

(徐州工业职业技术学院 信息与电气工程学院,江苏 徐州 221400)

0 引 言

随着计算机技术的发展，利用计算机强大计算能力的全局寻优算法，如遗传算法、粒子群算法均得到了大量应用，取得了良好效果。近年来，随着量子理论的应用，全局搜索算法的寻优能力得到进一步提升。量子遗传算法(Quantum Genetic Algorithm，QGA)是一种基于量子计算与遗传算法的概率优化算法，比传统的遗传算法具有更强的搜索能力和更快的搜索速度[1-2]。

QGA在运算过程中，主要利用量子比特的角度改变来实现进化，转角的变化方式直接关系到算法的寻优能力和收敛速度。通过研究，得出当转角步长在0.005π～0.1π之间变动时，具有良好的搜索效果[3]。依据根据进化的代数调整转角步长，提高了QGA的算法全局寻优能力[4]；根据种群的规模和个体的信息对进化步长进行调整，确保了搜索效果[5]。上述方法均提高了QGA的全局搜索能力，但在算法执行过程中，对进化方向的选择仍具有一定的随意性和模糊性，降低了算法的运算速度。

针对上述问题，本文提出改进进化方向的量子遗传算法(QGAIED)。该算法依据当前全局最优解选择进化方向，根据两个进化方向共同调整转角步长，实现了算法进化步长的自动调整，在提高搜索能力的同时加速了进化速度。

1 量子遗传算法

1.1 优化算法的量子编码

QGA采用量子比特来表达每一个个体，一个量子比特表示如下[6-9]：

|φi〉=α|0〉+β|1〉

(1)

式中:α和β分别表示|0〉和|1〉的量子概率幅，满足归一化条件：

(2)

因此，在实际运用中可将α和β的范围设置为[-1,1]。

对于优化问题：

(3)

式中，aj和bj为决策向量X=(x1，x2，…，xn)T∈Rn的分量xj的上限和下限。直接应用概率幅对QGA中的个体进行编码，结合式(3)可知，在种群的第t代，每一个个体需要n个量子比特进行编码，其量子编码形式为：

(4)

式中:θij为角度，θij=2π×rnd，rnd表示[-1，1]之间数值;i=1，2，…，m表示种群规模；j=1，2，…，n表示每一个个体中的量子比特总数。cos2θij+sin2θij=1，符合量子概率幅的归一化条件。可知，pi属于n维量子空间In=[-1，1]n。

如果式(3)的优化问题在实数空间有M个全局最优解，利用式(4)进行编码之后，n维量子空间In=[-1，1]n中可以搜索到2n+1M个解[5]。换言之，将实数空间转换到量子空间，全局最优解以指数级增长，极大的提高了算法的搜索速度和搜索能力。

1.2 量子门

QGA在进化过程中，主要通过对每一个量子比特的角度进行变换以实现进化[10-14]，通常采用旋转量子门更新量子比特相位：

(5)

(6)

式中:Δθ称为量子门中的转角步长，包含大小和方向，在QGA进化过程中，Δθ起着更新个体的作用。易知，Δθ的变化最终将表现为个体的变化，直接影响算法的收敛速度和寻优能力。Δθ取值过小，算法转角步长太小，无法跨出局部最优解，难以寻找到全局最优解；Δθ取值过大，算法步长太大，运算速度较快，但容易忽视目标的细节变化，降低了寻优精度。

1.3 变异处理

在进化过程中，如果只采用转角步长进行逐步进化，不利于全局搜索，因此在进化过程中还需要考虑个体的变异[15-17]，突破当前种群限制，采用量子非门对个体进行变异：

(7)

可以看出，量子非门对调了正弦和余弦的位置。由于sinθ=cos(π/2-θ)，cos(θ)=sin(π/2-θ)，从本质上看，相当于量子比特在进化过程中改变了π/2-2θ，本质上仍然为量子门旋转。由于变化的角度较大，故变异操作有助于增加种群的多样性，突破早熟收敛。

1.4 解空间变换

在量子编码中每个个体包含n个量子比特，需要将这n个比特从量子空间转换到实数空间，才能够得出式(3)的优化解。由于一个量子比特包含两个概率幅，故从量子空间变换到实数空间也存在两个解。

根据α、β解得相应解空间中决策向量X的第j位为：

Xic,j=0.5[bi(1+αij)+ai(1-αij)]

(8)

(2) 根据β解得相应解空间中决策向量X的第j位为：

Xis,j=0.5[bi(1+βij)+ai(1-βij)]

(9)

Xic,j由量子态|0〉的概率αij求出，Xis,j由量子态|1〉的概率幅βij求出，每个量子位对应待求解问题在该位置的两个解。因此，QGA必然具有更多的优化解，在量子空间更容易找到全局极值。

2 基于进化方向的繁殖策略

2.1 进化方向

进化算法的最终目标就是寻找到目标的最优解，因此其结果与目前搜索到的全局最优解的变化密切相关。每一个个体和目前的全局最优解都在进化，但两者之间仍可以形成一个进化方向，用于指导个体的进化。对于当前种群P(t)中的任意个体ai(t)，定义其进化方向为：

D(Pi(t))=C(g(t),Pi(t))

(10)

Pi(t)∈P(t)

式中:C(g(t),Pi(t))用于计算g(t)和ai(t)的相似度，方向从Pi(t)指向g(t)，t代表当前种群代数，g(t)为进化到第t代时的全局最优解，当前种群中个体Pi(t)的进化方向是由Pi(t)和当前全局最优解g(t)来共同决定的。由上述的定义可知，D(Pi(t))值越大，则个体与当前全局最优解的差距越小;反之亦然。

2.2 优化方向

进化中能提高种群中个体适应度的进化方向即为优秀的进化方向。利用当前个体与当前全局最优解之间的相似度来确定进化方向，仍具有模糊性和随机性。有必要对个体进化方向的加以判别和约束，从而使进化过程朝更优秀的方向进行。

进化方向用于指导群体进化，需要通过一系列特定的操作，从当前种群P(t)的个体进化方向中选择出优化方向，提高进化速度，即

(11)

式中:Θs表示对进化方向的选择操作;Φ表示确定优化方向时的准则;and表示“且”;where表示约束条件。式(11)表示，在t代和t-1代之间进行比较，选择进化后适应度更大的个体，然后依据选择出的个体进一步确定优化方向。由于沿选择出的方向进化后能提高个体的适应度，故本文根据种群个体的适应度进行选择，选择出的方向为基于个体适应度的优化方向。

2.3 基于优化方向的繁殖策略

当前种群中的最优个体通常被认为是适应度最大的个体，而当前种群中个体的优化进化方向通常被认为能速度提高个体适应度方向，如果让当前的种群个体沿着当前优化进化方向进化，则其子代个体可能会具有更优的性能，但如果所有的个体都向一个优化方向进化，易导致局部最优解，因此需要进一步加以改进。

记Op={Pp,1(t),…,Pp,k(t),…,Pp,m1(t)}为到t代为止全局搜索到的适应度最大的前m1个个体，记Dopt={Dopt,1,Dopt,2,…,Dopt,m2}为当前种群中个体进化方向中前m2个优化方向，让这m1个个体沿着当前种群的m2个优化方向进化，形成具有m1+m1×m2个个体的新群体。为保证种群规模，假设初始种群规模为m，当m1+m1×m2≥m，则去除适应度低的个体。如果m1+m1×m2

优化方向最终的执行要体现在转角的变化上，因此在接一下来的内容中，将利用优化方向对转角步长进行自适应调整。

3 自适应转角步长算子

设一个量子个体由n个量子比特代表，Pi(t-1)变为Pi(t)的转角步长为{Δθi1,Δθi2,…,Δθin}，每个Δθij代表一个量子比特的转角步长。为保证运算的精度。为兼顾精度和速度，需要使得转角步长自适应变化。

用Op结合进化方向Dp={Dp,1,…,Dp,l,…,Dp,m2}来计算自适应转角步长。设Dp,l对应的个体为Pp,l(t)，一个优化方向可能引起局部最优解，不利于全局最优解的搜索。为保证最优解的搜索能力，结合优化方向计算转角步长时，采用Dp中的两个方向来共同确定步长：

(12)

式中:

f(θp,kj(H)-θp,lj)=

(13)

f(θp,kj(L)-θp,lj)=

(14)

j=1，2，…，n，表示个体中的第j个量子比特;θp,kj表示当前全局最优解集合Op中Pp,k(t)对应的第j个量子比特的相位;θp,lj表示优化方向Dp,l对应的Pp,l(t)的第j个量子比特的相位;S，T为权值，S，T∈[0，1]，S+T=1。Dp中的两个方向对应两个个体，H表示适应度更大的一个个体，L表示适应度更小的个体。FS表示适应度更大的一个个体的适应度值，FT表示适应度更小的一个个体的适应度值。

Dp中的两个方向对应两个个体，对新一代个体旋转步长产生的贡献由权值S和T决定，考虑到搜索速度，具有更大适应值的Pp,l(H)所占的比重应当更大，才能更快的寻找到最优解，同时Pp,l(L)应当对进化方向进行修正，以避免局部最优解的出现。综上，参数S和T的计算公式为：

(15)

(16)

可知，步长式(12)由两个方向共同决定，且适应度更大的值所占权值重，起主导作用；适应度更小的值起修正作用。该步长计算方式一方面避免了局部最优，又可以提高收敛速度。可以发现，进化时在适应值变化小的地方，转角步长变大，加快进化速度；在适应值变化大的地方，转角步长减小，不至于越过全局最优解，同时兼顾了搜索能力和搜素速度。

4 对比实验分析

QGAIED通过权值同时控制优化方向，在保证全局搜索能力的同时也提高了搜索速度，因此可用于函数极值搜索和工程应用中的参数优化。

4.1 数学函数寻优

目标函数如下:

(17)

求其极大值点，函数图形如图1所示。

图1 目标函数

该函数具有无限个局部极大值，全局最大值为1，且全局只有(0,0)位置为最优解，最优解具有唯一性。

采用QGAIED进行寻优，设置总群规模m=20，量子比特数n=2，变异概率p=0.1，转角的初始值为θ0=0.05π，最大进化代数tmax=300，适应度函数取-f(x,y)，全局寻优结果对比见表1。表中数据为50次实验平均值。可以看出，QGAIED的全局搜索能力最强、全局搜索速度最快，其次是QGA。遗传算法GA的寻优效果最差，50次实验均未找到全局最优解。

表1 函数极值优化结果对比

4.2 工程参数寻优

将QGAIED用于优化神经网络参数，并将神经网络用于轴承运行状态分类。在旋转试验台上进行轴承试验，在轴承的内圈和外圈分别用电火花加工出凹坑，用于模拟单点故障。外圈故障的实测转速为1 800 r/min，内圈故障的实测转速为1 700 r/min。

轴承振动信号包括正常、外圈故障、内圈故障3类，使用小波将每一个采样振动信号分解到8个频带，统计每个频带的特征，并对特征进行归一化处理，以降低故障强弱的影响。每种状态采集30个振动信号，10个样本用于训练，20个样本用于测试。

设置神经网络的网格层数c=3，输入节点l1=10，隐层节点l2=10，输出节点l3=10，种群规模m=20，变异概率p=0.01，转角初值θ0=0.05π，最大进化代数lmax=500，适应度函数取分类正确率。优化后神经网络的故障分类效果对比见表2，表中数据为40次实验平均值。

从表2可以看出，QGAIED优化后的神经网络各方面表现突出，在3种方法中具有最低的分类错误率。此外，在寻优过程中，QGAIED也具有最快的速度。

表2 神经网络优化结果对比

5 结 语

通过选择进化方向，本文对量子遗传算法的进化步长进行了优化，提出了改进进化方向的量子遗传算法QGAIED。在进化过程中，QGAIED的步长根据两个优化方向自适应调整，在提高搜索速度的同时，有效避免了局部最优。数学函数寻优和工程参数寻优均表明，QGAIED在保证搜索能力的同时，显著缩短了搜索时长，在极值搜索和工程优化中均有良好应用前景。

[1] Lü Fengmao, Yang Guowu, Yang Wenjing,etal. The convergence and termination criterion of quantum-inspired evolutionary neural networks[J]. Neurocomputing, 2017, 238(5): 157-167.

[2] 王瑞琪, 李 珂, 张承慧, 等. 基于RQGA和非支配排序的多目标混沌量子遗传算法[J]. 电机与控制学报, 2012, 16(4): 91-99.

[3] Narayanan A, Moore M. Quantum-inspired genetic algorithm[C]∥Proc of IEEE Conf. on Evolutionary Computation. Piscataway: 1996:61-66.

[4] Qu Zhijian, Liu Xiaohong, Zhang Xianwei,etal. Hamming-distance-based adaptive quantum-inspired evolutionary algorithm for network coding resources optimization[J]. The Journal of China Universities of Posts and Telecommunications, 2015, 22(3): 92-99.

[5] Patvardhan C, Bansal S, Srivastav A. Solving the 0-1 quadratic knapsack problems with a competitive quantum inspired evolutinary algprithm[J]. Journal of Computional and Applied Mathematics, 2015, 285(8):86-99.

[6] 罗玉玲, 杜明辉. 基于量子Logistic映射的小波域图像加密算法[J]. 华南理工大学学报(自然科学版), 2013, 4 (6): 53-62.

[7] 付晓薇, 丁明跃, 周成平, 等. 基于量子概率统计的医学图像增强算法研究[J]. 电子学报, 2010, 38(7): 1590-1596.

[8] 付晓薇, 丁明跃, 蔡 超, 等. 基于量子衍生参数估计的医学超声图像去斑算法[J]. 电子学报, 2011, 39(4): 812-818.

[9] 张培林, 陈彦龙, 王怀光, 等. 考虑信号特点的合成量子启发结构元素[J]. 吉林大学学报(工学版):2015, 45(4):1181-1188.

[10] Luciano R, Ricardo T, Marley M. Quantum-inspired evolutionary algorithm for ordering problems[J]. Expert Systems with Application, 2017, 67(1):71-83.

[11] Chen Yanlong, Zhang Peilin, Wang Zhengjun,etal. Denoising algorithm for mechanical vibration signal using quantum Hadamard transformation [J]. Measurement, 2015, 66:168-175.

[12] Tsai J, Hsiao F Y, Li Y J,etal. A quantum search algorithm for future spacecraft attitude determination[J]. Acta Astronautica, 2011, 68(7): 1208-1218.

[13] Mangone F, He J, Tang J,etal. A PAPR reduction technique using Hadamard transform combined with clipping and filtering based on DCT/IDCT for IM/DD optical OFDM systems[J]. Optical Fiber Technology, 2014, 20(4): 384-390.

[14] Xu J, Zhu Z M, Liu C X,etal. The processing method of spectral data in Hadamard transforms spectral imager based on DMD[J]. Optics Communications, 2014, 325(30): 122-128.

[15] 陈汉武, 朱建锋, 阮 越, 等. 带交叉算子的量子粒子群优化算法[J]. 东南大学学报(自然科学版), 2016, 46(1): 23-29.

[16] 张 磊, 方洋旺, 柴 栋, 等. 基于改进量子进化算法的巡航导弹航路规划方法[J]. 兵工学报, 2014, 35(11): 1820-1827.

[17] 张宇献, 李 松, 李 勇, 等. 基于量子位实数编码的优化算法及轧制规程多目标优化[J]. 仪器仪表学报, 2014, 35(11): 2440-2447.