改进量子遗传算法在函数寻优中的应用

张　晨，谭小球，杨林峰

(1.广西大学 计算机与电子信息学院，广西 南宁 530004；2.浙江海洋学院 数理与信息学院，浙江 舟山 316000)



改进量子遗传算法在函数寻优中的应用

张晨1，谭小球2，杨林峰1

(1.广西大学 计算机与电子信息学院，广西 南宁 530004；2.浙江海洋学院 数理与信息学院，浙江 舟山 316000)

标准的量子遗传算法容易陷入局部最优，且在定义域范围较广的函数寻优中易出现优化精度不高的情况。将量子交叉与模拟退火操作适当地加入量子遗传算法中可以有效地避免算法陷入局部最优解。根据第一次的优化结果，缩小算法寻优区域，以提高算法寻优的精确度。最后对其用复杂二元函数进行测试，计算结果表明，通过该改进方式明显提高了优化算法的性能。

量子遗传算法；量子交叉；退火操作；寻优区域

引用格式：张晨，谭小球，杨林峰. 改进量子遗传算法在函数寻优中的应用[J].微型机与应用，2016,35(11)：83-86.

0　引言

量子遗传算法[1](Quantum Genetic Algorithm，QGA)是将经典量子计算与传统遗传算法的操作方式相互融合产生的新的优化算法。与传统遗传算法相比，量子遗传算法具有种群多样性好、全局搜索能力强和收敛速度快等特点[2]。

标准的量子遗传算法在一些特别复杂的、病态的优化函数中不能充分地发挥其优越的性能。为了提高算法的优化性能，本文将模拟退火操作与量子交叉操作引入标准量子遗传算法中。该算法在量子个体上实施量子交叉操作，增强种群中染色体的结构信息交流，引入退火思想尽量避免算法在早期时陷入局部极值[3]。在实施第一轮寻优计算操作后，求出相应的最优解，再在最优解附近的小范围内进行第二轮寻优计算，提高算法的寻优精确度。

针对改进后的量子遗传算法，本文用几个复杂二元函数进行测试，结果表明，改进后的算法具有较强全局搜索[4]的特点。

1　量子遗传算法

1.1量子编码

量子遗传算法的编码方式是量子编码。量子编码中，信息的存储单元是量子比特[5]。采用|0>和|1>的单量子比特的叠加态来表示遗传信息。

在量子遗传算法中的量子位可以是|0>到|1>中的任意值，所以一个量子位的状态的表达式可以为[6]：

|ρ>=λ|0>+μ|1>

(1)

其中量子态的概率幅λ与μ是一对平方和为1的复数。对优化种群进行一次测量操作，|ρ>可能会以|λ|2的概率坍缩到| 0>状态，或者会以|μ|2的概率坍缩到|1>的状态，并且它们满足下面的表达式条件：

|α|2+|β|2=1

(2)

在式(2)中，|α|2表示|0>的概率，|β|2表示|1>的概率，量子态坍缩是为了结合适应度值来优选种源。因此，如果一个系统有m个量子位，则该系统可同时描述2m个状态。然而，对于量子态[4]的每一次观察，该量子位都只会坍缩到一个确定的状态。

1.2染色体表示方法

在量子遗传算法中，基因采用量子比特来表示[5]。该基因可以是“0”态或“1”态，也可以是它们之间的任意叠加态，即每一个基因位代表的不再是某一确定的遗传信息，而是包含该优化函数所需要的所有的优化解集信息。因此，对于任意基因位的任一操作都可能会使种群中所有的优化解集信息产生变化。本文使用一对平方和为1的复数对(α,β)来表示染色体中的一个量子比特，则c个j位基因构成的一个染色体可以表示为：

(3)

2　量子遗传算法的改进

2.1量子交叉

在标准的量子遗传算法中，没有量子交叉，种群中染色体都相互独立，个体间的结构信息不能被充分利用。

[7]采用一种叫做“全局干扰交叉”的交叉操作，在该交叉操作中所有的染色体都参与其中。表1简单地描述了本文中量子交叉方式，即该种群的大小为3，染色体的个数为3，每个染色体的长度为5。

其中第二个染色体的第2个量子比特用B(2)来表示，用递归的方式来进行全局干扰操作。交叉后的染色体的基因位的确定方法是：交叉前的基因位以现在的基因位序号大小减1在种群中向下移动几位，如果移动的位数超过种群染色体数则除以现在种群的大小，然后取得的余数减1就是该基因向下移动的位数。

表2所示是经过全局干扰交叉操作后的染色体组，如：B(1)—A(2)—C(3)—B(4)—A(5)。通过此类操作，优化种群中每个染色体上的量子位信息将会被充分利用，在种群演化的后期能够充分保证染色体的多样性，提高了算法的性能。

表1 量子染色体结构表1A(1)A(2)A(3)A(4)A(5)2B(1)B(2)B(3)B(4)B(5)3C(1)C(2)C(3)C(4)C(5)表2 交叉后量子染色体结构表1A(1)C(2)B(3)A(4)C(5)2B(1)A(2)C(3)B(4)A(5)3C(1)B(2)A(3)C(4)B(5)

2.2模拟退火操作

模拟退火操作是通过设置初始温度的大小与现实降温过程的速率来实现的。在温度较高时，算法能够以较高的概率接受差的优化解，而温度较低时能较好地接受好的优化解，通过此操作使算法避免陷入局部极值。模拟退火的搜索模式提高了算法的搜索能力和效率。

模拟退火算法实际上是一种迭代求解的过程，算法反复执行“产生新状态→计算目标函数→判断是否接受新状态→接受/舍弃”的过程。它的基本流程如下：

(1)初始化，初始温度T，初始解S，每个T值的迭代次数。

(2)对种群完成步骤(3)～(6)。

(3)产生新的解S′。

(4)计算增量Δ=E(S′)-E(S),其中E(S)为目标函数。

(5)若Δ<0，则接受S′作为新的当前解，否则以概率exp(-Δ/T)接受S′为新的当前解。

(6)如果满足终止条件则输出当前解作为最优解，结束循环。

(7)产生新的温度T′=0.95×T，逐步降低T(温度)。

(8)转到步骤(2)。

在算法的执行过程中，为了保证算法的收敛能力，要保证退火的初始温度T尽可能的大，一般情况下T取值为100。

2.3二次寻优计算

2.3.1粗格子点法

粗格子点法是先用少数的格子点进行粗糙计算，在求出相应的最优解后，再在最优解附近的小范围内进一步细分，并求在细分格子点上的最优解，如此继续细分直到满足要求为止。

2.3.2二次寻优计算方式

二次寻优计算方式与粗格子点法相似。二次寻优计算是第一次寻优计算后在得到的最优解附近的小范围内再利用量子遗传算法进行寻优计算操作。优点在于优化函数定义域缩小，最优值所在的区域更加明显，染色体解的精度更高。

2.3.3二次寻优计算区域

二次寻优计算区域为第一次寻优计算时每代的最优值解组成的连续区域集合。如下图1所示，以第一次寻优计算的全局最优解A为中心点，以中心点到边界点B的距离为长度，确定该方向上二次寻优计算的区间。

图1　二次寻优计算区域

在图1中，如果a

2.4改进算法选择

每个改进的量子遗传算法都具有不同的寻优计算特性。如果在第一次优化计算函数时，发现全局最优解的出现代数较小，且寻优效果不佳，多数情况是由于算法的“早熟收敛”造成的。因此，在下次的寻优计算时，可以将退火操作引入算法中，防止算法的“早熟收敛”。如果出现最优解的迭代次数较晚，且寻优效果较差，多数情况是由于各染色体过于孤立，染色体结构信息交流少，收敛速度慢造成的。因此，在下次寻优计算时，将量子交叉操作引入优化算法中，增加种群的多样性，提高算法的寻优性能。使用二次寻优计算，可以有效地提高算法寻优的精度。

2.5优化算法流程

改进量子遗传算法(IQGA)流程主要分为以下步骤：

(2)对初始种群中的每个个体进行一次测量，得到对应确定的解P(t0)。

(3)对各确定染色体优化解P(t0)进行适应度评估操作，以此来得到每个解的适应度值的大小，用来进行下一步的遗传淘汰选择操作。

(4)记录最优个体和对应的适应度。

(5)判断优化算法是否可以结束优化操作，如果现有的优化解集满足优化结束的条件则执行步骤(12)，否则继续执行优化操作。

(6)对优化解集种群Q(t)中的每个个体即染色体优化解进行一次染色体基因位大小的确定操作，通过此操作得到对应遗传代数种群的函数优化解集。

(7)对各确定解进行适应度评估。

(8)利用量子旋转门U(t)对每个染色体个体进行一次遗传演化操作，若当代全局适应度值与前代适应度值之差Δ小于零，则接受当代最优个体作为新的当前解，以此得到新的优化函数的最优解集种群Q(t+1)，否则以概率exp(-Δ/T)接受新的当前解，以此得到新的优化函数的最优解集种群Q(t+1)。

(9)对量子染色体进行全干扰的量子交叉操作。

(10)记录最优个体和对应的适应度。

(11)将迭代次数t加1，返回步骤(5)。

(12)确定二次优化解集区域，并将算法迭代次数减半，修正退火系数。

(13)根据第一次优化方法，执行步骤(1)～(11)。

3　算法性能测试

3.1典型测试函数

(1)多峰函数Shubert[8]

此函数具有760个局部极小值，其中全局最小值18个，理论上的全局最小解fmin(x1,x2)=-186.731。

(2)Goldsten-Price函数[9]

此函数在其定义域内只有一个极小值点f2(0,-1)=3。

(3)Six-hump Camel Back函数

f3(x,y)=(4-2.1x2+x4/3)x2+xy+(-4+4y2)y2，-3≤x≤3，-2≤y≤2

Six-hump Camel Back函数有多个相似极小值点，很难准确地取得最小值点，其中(-0.089 8，0.712 6)和(0.089 8，-0.712 6)为全局最小点，最小值为f3(-0.089 8,0.712 6)=-1.031 628和f3(0.089 8,-0.712 6)=-1.031 628。

本文采用的方法与现有方法的计算结果对比如表3所示，每个函数分别用改进后的算法计算20次。量子遗传算法的种群大小设置为40，迭代次数设置为200，函数的每个变量的二进制长度设置为20，退火初始温度设置为100℃，退火系数为0.95。算法的优化性能从算法的效率与算法质量两个方面进行评价。

表3　仿真实验数据比较表

注：QGA为基本量子遗传算法；CQGA为含量子交叉的算法；SQGA为含退火操作的算法；SCQGA为基于量子交叉与退火操作的算法

根据表3数据可以看出，改进后的量子遗传算法在性能上有了一定的提高。针对不同的优化函数，改进算法都体现了其优越的性能。含量子交叉与退火思想的量子遗传算法对于不同特点的优化函数都能保持较好的搜索能力。

3.2二次寻优计算测试

为测试二次寻优计算的性能，利用上文提及的3个典型函数进行性能测试。将最大遗传代数设置为100，染色体长度为20，种群大小为40。计算结果和对照比较内容如表4所示。

表4　二次寻优计算性能比较表

从表4可以看出，二次寻优计算得到的全局最优值比第一次得到的解更加接近理论最优值，并且收敛速度更快。

4　结论

本文通过在原有的量子遗传中添加全干扰的量子交叉与退火操作，提高了量子遗传算法的搜索寻优能力，有效地避免传统算法易陷入“早熟收敛”与局部极值的问题。本文使用的二次寻优计算提高了算法的精确度。

但是，本文的研究还有很多需要改进的地方，比如，在二次优化时优化区域的确定过于单一，没有加入权值，可以考虑在优化时对每代的最优值赋权值，根据权值来确定二次优化的寻优区域；可以将全局交叉设置为概率交叉，在不影响性能的情况下减少交叉次数；可以使用并行算法缩减含量子交叉操作的量子遗传算法的运行时间。因此，本文的后续工作是在现有基础上改进和完善优化算法，使其能更好地进行函数寻优。

参考文献

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

[2] 周传华，钱锋.改进量子遗传算法及其应用[J].计算机应用，2008,28(2)：286-288.

[3] 郭海燕，金炜东，李丽，等．分组量子遗传算法及其应用[J]．西南科技大学学报，2004，19(1)：18-21.

[4] 何兵.基于改进量子遗传算法的巡航导弹水平航迹规划[J].计算机仿真，2012,29(9):109-112.

[5] 张济涛，樊静波，高亮．基于量子遗传算法的拆除序列规划[J]．现代制造工程，2015(4)：110-115.

[6] HAN K H. Genetic quantum algorithm and its application to combinatorial optimization problem[C]. In: IEEE Proc. of the 2000 Congress on Evolutionary Computation, San Diego, USA, 2000:1354-1360.

[7] 祁正萍，孙合鸣．一种改进的量子遗传算法[J]．科学技术与工程，2012，12(12)：2835-2839.

[8] 席红雷．自适应梯度小环境混合优化算法[J]．计算机与数字工程，2012,40(2):37-39.

[9] 李敏强，寇纪淞．遗传算法的基本理论与应用[M]．北京：科学出版社，2002.

Application of improved quantum genetic algorithm in function optimization

Zhang Chen1，Tan Xiaoqiu2，Yang Linfeng1

(1.School of Computer, Electronics & Information, Guangxi University, Nanning 530004, China; 2.School of Mathematics, Physical and Information, Zhejiang Ocean University, Zhoushan 316000, China)

Ordinary quantum genetic algorithm has the tendency to fall into local optimum and has the disadvantage of accuracy is not high for a wide range of areas. Quantum genetic algorithm with the quantum crossover and annealing operation can efficiently avoid falling into local optimum. According to the optimization results of the first time, the algorithm optimization area is reduced, and the accuracy of the optimization algorithm is improved. Finally, the paper uses complex function of two variables to test the improved quantum genetic algorithm, the result proves that the improved quantum genetic algorithm has higher efficiency.

quantum genetic algorithm; quantum crossover; annealing operation; optimization area

TP319

A

10.19358/j.issn.1674- 7720.2016.11.025

2016-01-04)

张晨(1992-)，男，硕士研究生，主要研究方向：计算机应用技术。

谭小球(1974-)，男，博士，副教授，主要研究方向：智能优化及自然语言处理。

杨林峰(1979-)，男，博士，副教授，主要研究方向：并行计算最优化、混合整数规划算法及其在电力系统中的应用。