解复杂连续函数优化问题的动态量子遗传算法

黄　山　覃　华　苏一丹　冯志新

(1.广西大学计算机与电子信息学院　南宁　530004)(2.广西通信规划设计咨询有限公司　南宁　530022)



解复杂连续函数优化问题的动态量子遗传算法

黄山1覃华1苏一丹1冯志新2

(1.广西大学计算机与电子信息学院南宁530004)(2.广西通信规划设计咨询有限公司南宁530022)

研究了一种解复杂连续函数优化的动态量子遗传算法(DQGA)。设计一种动态量子旋转角的更新策略及量子门调整策略,以加快算法收敛速度,同时为淘汰适应度差的个体,量子旋转策略表中动态地嵌入了变异算子。在算法进化后期引入灾变算子使算法及时跳出局部最优,避免早熟收敛。五个复杂连续函数的测试实验表明:所提算法对复杂连续函数优化问题的寻优能力较QGA更强,算法的稳定性更高,算法的迭代次数亦优于传统量子遗传算法。

复杂连续函数优化; 量子遗传算法; 动态调整旋转角; 灾变算子

Class NumberTP18

1　引言

量子遗传算法(Quantum Genetic Algorithm,QGA)将量子计算原理引入到传统的遗传算法中,用量子比特编码来表示染色体,用量子门来更新染色体,进而完成进化搜索,提高遗传算法搜索的性能,使其具有种群规模小却不影响算法性能、同时兼有“探索”(exploration)和“利用”(exploitation)的能力、收敛速度快和全局寻优能力强的特点。文献[1]首次提出了量子遗传算法的概念;文献[2～3]分别提出了遗传量子算法和并行量子遗传算法,并将两算法都用来求解组合优化问题,结果表明以量子比特为基础的量子遗传算法更适合于解决组合优化问题,为将量子遗传算法应用于连续函数优化问题,国内外学者陆续提出了一些改进的量子算法[4～7]。

量子遗传算法常用Han等提出的量子旋转门在量子态中搜索获得问题的解,此旋转门利用旋转角的改变对种群进行更新,但旋转角的选取一般都很小,探索(exploration)解的效率较低,在复杂函数优化上容易导致迭代次数多、收敛速度慢、容易陷入局部极值等问题。针对上述问题很多学者对其进行了改进,文献[7]采用量子比特相位比较法更新量子门和自适应调整搜索网格的策略,极大地保持种群的多样性,提高算法性能。文献[8]采用动态调整量子旋转角和优体交叉的策略,提高量子遗传算法的计算性能。文献[9]结合小生境技术和惩罚函数淘汰相似性高的个体,并使用动态调整旋转角策略,实验结果表明,算法性能优于QGA。以上改进的量子遗传算法虽提高了算法的性能,但改进的效果还有进一步优化的可能。本文正是在以上改进算法的基础上再进一步进行优化,提出了一种改进的动态量子遗传算法(DQGA),采用新的量子旋转门调整策略及动态调整量子旋转角,以加快收敛速度,同时将变异算子动态地嵌入到量子旋转策略表中,改变适应度差的个体,此外,在算法进化后期引入灾变算子使算法及时跳出局部最优,避免早熟收敛,提高算法性能。在五个复杂连续函数优化问题上验证算法,结果表明:算法的全局寻优能力、收敛速度、迭代次数均较传统QGA更好,说明本文的改进是可行的。

2　解复杂连续函数优化的DQGA

2.1改进的量子门

在QGA中,量子位是信息表示的最小单元,量子位又称为量子比特(quantum bit,qubit)。单量子比特的任意状态都可以表示为两个基本状态的线性组合。单量子位的状态可表示为

|Ψ〉=α|0〉+β|1〉

(1)

其中α和β称为量子态的概率幅,|α|2、|β|2分别表示观测到|0〉态和|1〉态的概率,且满足

|α|2+|β|2=1

(2)

在QGA中,第t代的量子种群表示为

(3)

式(3)中,m表示染色体基因数,即染色体长度。

用量子旋转门更新量子种群的方法如下:

(4)

(5)

式(5)中,θi为旋转角,θi=s(αi,βi)·Δθi,s(αi,βi)为旋转角的符号,Δθi为旋转角的大小,它们由事先设计的调整策略确定。

本文采用一种新的量子旋转门调整策略(如表1),其核心思想是:在任何状态下,个体的每一位量子位都朝着最优个体的量子位方向旋转变化。例如:如果当前染色体的第i位为xi=0,最优染色体的第i位bi=1,若f(xi)≥f(bi),θi将根据(αi,βi)所在象限进行逆时针或顺时针旋转,使几率幅(αi,βi)向着有利“1”状态出现的方向演化。

表1　量子旋转门调整策略

表1中的调整角步长δ影响着收敛速度,如果过大,更新幅度过大,容易导致早熟;如果过小,会使收敛速度减慢,甚至处于停滞状态。所以,本文提出了一种新的动态调整旋转角策略,并将变异算子动态地嵌入到量子旋转策略中。该策略下δ的取值公式如下:

(6)

依据文献[10]建议的旋转角度取值范围一般在0.001π～0.05π之间,并结合多次试验的结果,令式(6)中θmin=0.01π,θmax=0.05π。fx为当前个体的适应度值,fb为种群当前的进化目标适应度值,favg为每代种群平均适应度值。

若fx>favg,采用动态旋转角机制调整旋转角度δ:当前个体与最优个体相差较大时,即(fb-fx)的值较大时,δ就比较大,增大搜索网格,以加快搜索速度;反之,当前个体与最优个体相差较小时,即(fb-fx)的值较小时,δ就比较小,缩小搜索网格,可以实现细搜索。

若fx≤favg,令δ=0.5π,采取量子变异操作,量子旋转门转换成量子非门(如式(7)),改变该量子位的叠加状态,使原来倾向于坍缩到“0”状态的变为倾向于坍缩到“1”状态,或者使原来倾向于坍缩到“1”状态的变为倾向于坍缩到“0”状态,从而产生新的个体。

(7)

这种将变异算子动态地嵌入到量子旋转策略中的方法实现简单,并且能有效地淘汰适应度低的个体,甚至产生新个体,从而增加种群的多样性,同时也能有效地避免早熟收敛,增强寻优能力。

2.2灾变算子

灾变算子就是模拟自然界的灾变现象来提高算法性能的一种方法。当算法连续数代的最优个体都无任何变化时,表明算法已陷入局部极值,需要采取措施使其跳出局部极值的束缚。对种群实施灾变操作,给种群一个较大的扰动,宛如自然界中种族濒临灭绝后的重生,可以使算法跳离局部最优点,开始新的搜索。

灾变的方法有很多,可以是突然增大变异概率或者对不同个体实施不同规模的突变,以产生不同数目的大量后代等。灾变方法可以打破原有基因的垄断,增加基因的多样性。本文使用的量子灾变的具体做法是:只保留进化目标值和最优个体,重新初始化所有新个体。

2.3DQGA算法流程

改进的动态量子遗传算法的具体流程步骤如下:

3) 对所有二进制解P(t0)进行适应度评估。对于函数优化问题,若函数为求最大值问题,适应度函数可直接取目标函数,若函数为求最小值问题,则通过f(x)=-f(x)变形,调整为求最大值问题。

4) 记录最优个体和对应的适应度值,并作为下一代进化目标。

5) 判断是否满足终止条件,如果满足则结束进化,输出最优个体,否则继续下面的步骤。

6) 迭代次数t=t+1。

7) 对种群Q(t)中的每个个体进行一次测量,得到对应的二进制解P(t)。

8) 对所有二进制解P(t)进行适应度评估。

9) 利用新量子旋转门U对Q(t)进行动态调整,得到新的下一代种群Q(t+1)。

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

11) 判断是否进行灾变操作。本文根据算法在进化过程中,如果最优个体的适应度连续数代或数十代都没有变化,则进行灾变操作。返回步骤5)。

3　实验测试与分析

3.1实验环境

本实验的运行环境为:CPU为Intel Pentium G640,主频2.8GHz;内存2GB;操作系统Windows 7—32位,用Matlab R2014a实现算法。

选取五个典型的连续复杂函数进行改进算法的验证,各函数如下:

1) 简单平方和函数

该函数只有一个极小点f(0,0)=0。

2) De Jong函数

-2.048≤xi≤2.048,i=1,2

这是一个二维函数,在整个解域中只有一个全局最小点f(1,1)=0,该函数虽然是单峰函数,但却是病态的,难以进行全局优化。

-2≤xi≤2,i=1,2

该函数在其定义域内有四个极小值点,只有一个全局最小值点f(0,-1)=3。

4) 六峰值驼背函数

-3≤xi≤3,i=1,2

该函数共有六个局部极小值点,其中有两个全局最小值点,即:

f(-0.0898,0.7126)=f(0.0898,-0.7129)

=-1.031628

5) Shaffer’s F1函数

-5.12≤xi≤5.12,i=1,2

该函数为典型的多峰函数,在其定义域内有很多个局部极大值点,全局极大点f(0,0)=0。

其中,测试函数F1～F4是求最小值问题,适应度函数Fit(Fi)=-Fi(i=1,2,3,4),而测试函数F5是求最大值问题,适应度函数Fit(F5)=F5。

本文采用传统遗传算法(GA)、传统量子遗传算法(QGA)和改进的动态量子遗传算法(DQGA)对上述五个函数进行优化,从而进行比较。

传统遗传算法(GA):种群大小n=100,交叉率Pc=0.7,变异概率Pm=0.05,染色体长度L=40,进化代数g=1000,采用二进制编码。

传统量子遗传算法(QGA):种群大小n=40,染色体长度L=40,进化代数g=1000,量子旋转角调整策略取自文献[11]。

本文改进的动态量子遗传算法(DQGA):种群大小n=40,染色体长度L=40,进化代数g=1000。

3.2实验结果与分析

为说明本文DQGA算法具有良好的收敛性和寻优能力,DQGA和传统遗传算法GA、传统量子遗传算法QGA分别对上述测试函数F1～F5进行优化,从质量和效率两方面来评估算法的性能。

表2是本文算法计算结果与GA、QGA算法的比较。用最优值、最差值、平均值、平均值与理论最优值的偏差值、平均精度提高量这五个指标来衡量算法的质量。其中,平均精度提高量是指DQGA相对GA、QGA在平均值的精度上所提高的数量级。

从表2的最优值可以看出,DQGA解的质量要明显优于GA,略优于QGA,但从平均值来看,DQGA解的精度远优于GA和QGA。从平均偏差值来看,DQGA的值最小,与理论最优值相差最小,更接近理论最优值,说明DQGA比GA和QGA稳定性更高。从平均精度提高量来看,DQGA相对GA提高的精度最大能达到1010,最小也能达到103;DQGA相对QGA提高的精度最大能达到108,最小也能达到101。表明改进算法在解的质量上有很大的改进,说明本文算法是可行有效的。

表2　测试函数优化结果比较

表3是本文DQGA与其他改进量子遗传算法对函数优化结果的比较。从表3可以看出,在求解上述复杂连续函数时,本文DQGA的最优值和平均值的计算精度都要高于其他改进算法,且本文算法的解更接近理论最优值,说明本文算法具有更强的寻优能力和全局搜索能力。

表4是五个测试函数的收敛结果比较。算法的最大进化代数设置为1000,每个算法进行100次测试,收敛精度为10-3,即当|优化值-理论最优值|<10-3时,则认为算法收敛。

从表4的收敛次数来看,DQGA对五个测试函数优化的收敛次数都是100,说明DQGA能够100%全局收敛,且算法稳定性高;QGA对F1和F3函数优化的收敛次数也是100,但对于像F2这样的病态函数的优化却很难全局收敛;GA收敛效果最差,100次实验测试只有几次甚至0次的收敛,极其容易早熟。从平均收敛迭代次数和平均收敛时间来看,DQGA的收敛迭代次数、收敛时间都是最少的,而且DQGA相对GA时间减少71%以上,相对QGA时间减少43%以上,说明算法能够较快的收敛到全局最优值。说明本文改进的量子遗传算法是可行的。

表3　DQGA与其他改进算法的优化结果比较

表4　测试函数收敛结果比较

图1是DQGA与QGA、GA对测试函数F2、F4的一次优化过程曲线,即函数值随进化代数的变化曲线。从图1可以看出,GA最快陷入早熟,收敛到局部最优值,而DQGA的收敛速度最快,说明本文提出的改进方法能够大大地提高量子遗传算法的效率。

4　结语

本文对QGA算法机理进行了分析,针对其解复杂连续函数优化问题时存在的收敛速度慢的不足,提出采用新的量子旋转门调整策略并动态调整量子旋转角的改进方法,加快收敛速度,同时在量子旋转策略表中动态的嵌入变异算子,改变适应度差的个体,从而产生新的个体。考虑QGA的早熟现象,在算法进化后期加入灾变算子使其能及时跳出局部最优点,从而最大限度地避免早熟收敛。根据仿真实验的测试实验证明,改进的动态量子遗传算法在全局搜索能力和收敛速度以及解的质量上均优于传统的量子遗传算法,且算法的平均收敛时间也要优于基本的QGA算法,说明本文的改进算法是可行的并且是有效的。

图1　测试函数的优化曲线

[1] Narayanan A, Moore M. Quantum-inspired genetic algorithms[C]//Evolutionary Computation, 1996, Proceedings of IEEE International Conference on. IEEE,1996:61-66.

[2] Han K H, Kim J H. Genetic quantum algorithm and its application to combinatorial optimization problem[C]//Evolutionary Computation, 2000. Proceedings of the 2000 Congress on. IEEE,2000,2:1354-1360.

[3] Kuk-Hyun Han, Kui-Hong Park, Chi-Ho Lee, et al. Parallel quantum-inspired genetic algorithm for combinatorial optimization problem[C]//Evolutionary Computation, 2001. Proceedings of the 2001 Congress on IEEE,2001,2:1422-1429.

[4] Cruz A V A D, Pacheco M A C. Quantum-Inspired Evolutionary Algorithm for Numerical Optimization[J]. Studies in Computational Intelligence,2008,121:115-132.

[5] Qin C, Liu Y, Zheng J. A real-coded quantum-inspired evolutionary algorithm for global numerical optimization[C]//Cybernetics and Intelligent Systems, 2008 IEEE Conference on,2008:1160-1164.

[6] 陈辉,张家树,张超.实数编码混沌量子遗传算法[J].控制与决策,2005,20(11):1300-1303.

CHEN Hui, ZHANG Jiashu, ZHANG Chao. Real-coded Chaotic Quantum-inspired Genetic Algorithm[J]. Control and Decision,2005,20(11):1300-1303.

[7] 张葛祥,李娜,金炜东,等.一种新量子遗传算法及其应用[J].电子学报,2004,32(3):476-479.

ZHANG Gexiang, LI Na, JIN Weidong, et al. A Novel Quantum Genetic Algorithm and Its Application[J]. Acta Electronica Sinica,2004,32(3):476-479.

[8] 张宗飞.一种改进型量子遗传算法[J].计算机工程,2010,36(6):181-183.

ZHANG Zongfei. Novel Improved Quantum Genetic Algorithm[J]. Computer Engineering,2010,36(6):181-183.

[9] 傅德胜,张蓉.一种改进的量子遗传算法研究[J].计算机仿真,2013,30(12):321-325.

FU Desheng, ZHANG Rong. Improved Quantum Genetic Algorithm by Balancing Convergence and Diversity.

[10] Han K H, Kim J H. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization[J]. IEEE Transactions on Evolutionary Computation,2002,6(6):580-593.

[11] 李士勇,盼池.量子计算与量子优化算法[M].哈尔滨:哈尔滨工业大学出版社,2009,76.

LI Shiyong, LI Panchi. Quantum Computation and Quantum Optimization Algorithms[M]. Harbin: Harbin Institute of Technology Press,2009.76.

Complex Continuous Function Optimization Problem of Dynamic Quantum Genetic Algorithm
HUANG Shan1QIN Hua1SU Yidan1FENG Zhixin2
(1. College of Computer and Electronic Information, Guangxi University, Nanning530004)

(2. Guangxi Communications Planning and Design Consulting Limited Company, Nanning530022)

A complex continuous function optimization of dynamic quantum genetic algorithm (DQGA) is studied. A dynamic update strategy of quantum rotation angle and quantum gate adjust strategy is designed to speed up the algorithm convergence speed, at the same time for the elimination of poor fitness individuals, the mutation operator dynamically is embedded in the quantum rotation strategy table. Introducing the cataclysm operator in the late evolution algorithm makes the algorithm timely and jump out of local optimum, premature convergence is avoid. Five complex continuous functions of the test results show that the proposed algorithm’s optimization ability for optimization of complex continuous function is stronger than QGA, the stability of the algorithm is higher, the iteration number of the algorithm is superior to traditional quantum genetic algorithm.

complex continuous function optimization, quantum genetic algorithm, dynamic adjusting rotation angle, the cataclysm operator

2016年2月1日,

2016年3月11日

面向大规模不完备不一致数据的自适应粒化分类模型及高效分类方法研究(编号:61363027);教育部人文社会科学研究规划基金项目(编号:11YJAZH080)资助。

黄山,女,硕士,研究方向:智能优化及在数据挖掘中的应用。覃华,男,博士,教授,研究方向:量子计算理论与近似动态规划最优化方法、数据挖掘。苏一丹,男,博士,教授,研究方向:自然计算、电子商务、信息安全。

TP18

10.3969/j.issn.1672-9722.2016.08.003