学位论文-—基于量子遗传算法的函数寻优算法设计.pdf

《学位论文-—基于量子遗传算法的函数寻优算法设计.pdf》由会员分享，可在线阅读，更多相关《学位论文-—基于量子遗传算法的函数寻优算法设计.pdf（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、毕毕 业业 论论 文（设计）文（设计）题目： 基于量子遗传算法的函数寻优算法设计学院：数理与信息学院学生姓名：专业：计算机科学与技术班级：指导教师：起止日期： 2014 年 11 月 16 日至 2015 年 6 月 12 日2015 年 5 月 13 日基于量子遗传算法的函数寻优算法设计基于量子遗传算法的函数寻优算法设计摘摘 要要量子遗传算法(QGA)是 20 世纪 90 年代后期兴起的一种崭新的遗传进化算法。该算法主要是将量子计算的概念引入其中，将量子的态矢量表达引入了遗传编码，使一条染色体可以表达多个信息态的叠加，同时利用量子旋转门实现染色体的演化，实现了目标解的进化。相比传统遗传算法，

2、量子遗传算法能够在较小的种群规模下，快速的收敛到全局最优解。本文首先介绍了量子遗传算法的基本原理与算法结构，然后对量子遗传算法提出疑问。虽然量子遗传算法的优化性能大大优于传统遗传算法，但是，对于一些多峰函数的优化问题，该类算法依旧容易陷入“局部最优” 。在实际的应用中有很多优化问题都是多变量的连续优化问题，现有的量子遗传算法不能有效的解决这些问题。针对量子遗传算法容易陷入局部最优和未成熟收敛的缺陷，我们提出了一种新的优化算法含有退火操作的量子遗传算法，该优化算法能够以可变的概率选择性地接受恶化的优化函数解，使种群解集的进化方向改变，不在依靠当前解进行遗传演化。从而使算法不易“早熟收敛” 。而且

3、在该算法中加入了全干扰的量子交叉操作，使各染色体能进行遗传信息的交换，使种群染色体更具有代表性。最后根据改进后的方案，对改进的量子遗传算法进行了数值仿真。有效地证明了改进算法在函数寻优方面的优越性。【关键词】【关键词】量子遗传算法，量子编码，退火思想，量子交叉，函数寻优IDiscovery of Function Extreme Value Based on QuantumGenetic AlgorithmAbstractAbstractQuantum genetic algorithm (QGA) was originated in the late 1990s as a newgeneti

4、c evolution algorithm, which introduces the concept of quantum computation intogenetic algorithm, i.e., introducing quantum state vector expression of the genetic codeso that a chromosome can express the superposition of multiple kinds of information.Moreover, the evolution of the chromosome by usin

5、g quantum revolving door, realizethe goal of evolution. Compared with the traditional genetic algorithm, The quantumgenetic algorithm cans rapidly convergence to the global optimal solution under thesmaller population size.This paper first introduces the basic principle of quantum genetic algorithm

6、andalgorithm structure. And then the defects existing in the current quantum geneticalgorithm is proposed. Although quantum genetic algorithm to optimize performancegreatly superior to the traditional genetic algorithm. Especially for multimodal functionoptimization problems, QGA also has the tenden

7、cy to fall into local optimum. As formany multivariate continuous optimization problems in actual application, the existingQGA can not solve these problems effectively. Since QGA may be trapped in localoptimum and the defect of premature convergence, we proposed a new algorithm,Quantum Genetic Algor

8、ithm with Annealing Operation (QGAAO). The algorithm canselectively accept deteriorating at a certain probability so that population has morechance to jump out the local optimal to avoid premature convergence. Moreover, globaldisturb has been added to the algorithm of the quantum crossover operation

9、, it can makechromosomes exchange more genetic information.It can better represent thechromosome population. Finally, according to the improved scheme, the improvedquantum genetic algorithm was committed for the numerical simulation. The test provedthat the improved algorithm effectively superiority

10、 in terms of function optimization.【KeywordsKeywords】quantum genetic algorithm, quantum coding, annealing thought,quantum crossover, function optimizationII目录摘 要. IABSTRACT . II1.绪论. 11.1 遗传算法. 11.2 量子计算. 11.3 函数优化. 11.4 选题背景和意义. 22.量子遗传算法. 32.1 量子遗传算法概述 . 32.2 量子遗传算法研究意义. 32.3 量子遗传算法的基本原理. 42.3.1.量

11、子比特. 42.3.2 染色体表示方法. 52.3.3 量子旋转门. 62.5 量子遗传算法步骤及流程图 . 72.5.1 量子遗传算法的步骤流程. 72.5.2 量子遗传算法的流程图. 73 量子遗传算法的改进 . 93.1 量子遗传算法存在问题. 93.2 改进方案的基本思想. 93.2.1 全局量子交叉. 93.2.2 模拟退火思想. 103.2.3 模拟退火算法的概念. 113.2.4 模拟退火算法的基本流程. 123.3 改进的量子遗传算法的具体实现 . 123.3.1 模拟退火算子及参数选取. 133.3.2 基于模拟退火的量子遗传算法具体实现 . 133.3.3 基于模拟退火的量

12、子遗传算法流程图. 133.4 改进的量子遗传算法的优点. 14III4 算法性能测试及分析 . 164.1 典型测试函数. 164.1.1 简单平方和函数. 164.1.2Rastrigrin 函数. 164.1.3De Jong 函数 F2 . 174.1.4Goldsten-Price 函数. 174.1.5Six-hump Camel Back 函数 . 184.2 算法参数设定. 184.3 测试结果即分析. 195 总结与展望. 245.1 论文总结 . 245.2 展望 . 24参考文献. 26IV浙江海洋学院毕业论文1. 1.绪论绪论1.11.1 遗传算法遗传算法在 20 世纪

13、 70 年代美国密西根大学教授 J.Holland 第一个提出了基于概率的优化算法遗传算法 （GA）。遗传算法的原理跟自然界的遗传进化演化原因是一致的。遗传算法根据优化函数的目标函数来进行全局自适应的概率搜索 ，寻找优化函数的最优值。 由于遗传算法可以不依靠优化函数的形式与不受外界因素的影响，所以，遗传算法在实际优化应用中得到了良好的应用。因为遗传算法具有良好的适用性、全局性、并行高效的优化性能与鲁棒性 ，所以它具有诱人的吸引力，吸引人们前去研究。对于现实中的应用，它对外界的要求不严格，能够广泛的应用，所以它具有很好的应用前景。但是，如果在遗传算法中的选择、交叉和变异的操作方式选取不当，那么算

14、法在迭代次数、收敛速度、优化性能等方面都会轻易地受到影响，并且，这都会使优化函陷入局部极值的这一陷阱。3211.21.2 量子计算量子计算量子计算4（QC）的概念是在二十世纪七十年代提出来的。那时的主要研究内容是计算三个特性之间相互的关系。 P.Benioff 与八十年代率先提出了量子计算可以用来进行仿真数据的计算 。在1994 年，美国的Shor 教授第一次将量子计算运用到了大数的因子分解中，从那时开始，量子计算的研究方向有了充分的拓宽 。量子计算有新的研究动力。使用量子态4作为65计算中的基本的信息的存储单位，是量子计算的一大特色。使用量子态具有的叠加、纠缠和干涉等特点可以很好的解决一些常

15、见的经典问题。通常信息是用一种物质或存在的状态来表示的。计算机最早是使用纸带的穿孔方式来表示二进制的，但随着科学技术的发展，到后来计算机开始使用晶体管的开关状态来表示二进制的信息。现在随着量子力学的发展，其揭示了微观粒子的运动状态。开始使用原子的运动状态来表示二进制。量子计算就是利用原子中电子的两种自旋状态来表示信息的 。量子计算要想实现其真正意义上的并行计算就必须在量子计算机上面，但是我们可以将量子计算机制和量子信息运用到智能算法中，或者是将已有的优化算法和量子算法相结合，使算法的优化性能得到提高，使它具有传统优化算法所不具有的优异性能。71.31.3 函数优化函数优化函数优化问题是量子遗传

16、算法的经典应用领域19，也是对量子遗传算法进行性能评价的常用算法.对于一些不规则或者是多变的与多值的函数的优化问题，使用其它方法去优化解决它们，是比较麻烦的，但是如果我们使用量子遗传算法就可能很好的解决这些问题，轻易地1得到较好的优化结果。函数优化 问题简单讲就是求取一个函数中的最小值或者是最大值。 函数的优化问题通常的描述是：设S 是R上的有界的子集，f：S-R 是 n 维的实值函数。如果在领域内能找到一个点的值小于该领域内其它所有点的值，那么我们就称该点是该函数在领域内的最小值所在的点。通常，此点就是我要求的最优值的点。函数优化问题通常是一个非常复杂的优化问题，特别是对于那些不可微的或者多

17、极值的函数优化，常常是不能很好的求到有效解的。但是，对于新出现的量子遗传算法来讲，它可以较好的避免此类情况，在处理一些复杂的优化函数时，依旧能保持较好的性能，原因在于量子遗传算法能很好的描绘出全局最优的解集，它将每种可能的最优解都可由一个染色体来描述，相比传统的遗传算法的染色体只能表示一个确定的解，但对于量子遗传算法的一个染色体，却可以表示多个优化解，有如此特性的染色体组成的种群，能更好的代表优化解集。之后它在按遗传进化学的规律来进行选择、交叉与变异操作，使染色体根据每代的进化目标来进行遗传“进化”，直到最后满足终止条件为止。n81.41.4 选题背景和意义选题背景和意义量子遗传算法在现代的许

18、多的应用优化领域发挥着至关重要的作用。量子遗传算法与传统的遗传算法的内在原理是一样，它们都是一种基于自然界生物“优胜劣汰”的生存规则的一种进化优化算法。它是一种适合复杂系统优化计算的优化技术.然而现在的量子遗传算法也存在着种种的问题。它的不足方面有：第一，由于算法是通过概率搜索来获得最优值的，因此会不可避免的产生概率搜索 所具有的普遍问题盲目性与随机性， 部分个体将不可避免的产生退化，从而会大大降低算法的寻优能力。第二，由于要进行大量的适应度值的计算与个体染色体的进化操作，这些操作大大的增加了算法的计算量，因而影响算法的运行时间，降低了算法的性能；第三，对于量子旋转门的转角方向、大小，一视同仁

19、，没有考虑染色体之间的差异。因此，应加注重量子遗传的种群大小的选择，即进化策略的设计与实施。第四，在算法优化的后期，优化算法可能会处于停滞阶段或进化的速度很缓慢，因此那是算法容易陷入“早熟收敛”这一缺陷。第五，算法每次进化的方向都是以最优值适应度值的个体。容易陷入局部的最优解。第六，现有的量子遗传算法缺少染色体之间的信息交流，不能充分的使用染色体的进化的特点。对于存在的问题，本课题进行了详细的研究，并且提出了一些解决方案。本课题提出了一种基于退火思想和量子交叉的量子遗传算法。这个算法使量子遗传算法的种群具有更好的代表性，通过这种算法极大的提高了量子遗传算法的性能。722. 2.量子遗传算法量子

20、遗传算法2.12.1 量子遗传算法概述量子遗传算法概述将经典量子计算 （QC） 与传统遗传算法它们的算法操作方式相互的融合之后产生了新的优化算法量子遗传算法（Quantum Genetic Algorithm，QGA） 。它既具有传统遗传算法所具有的优化算法的普遍性与通用性， 又能利用量子计算中信息存储方式的优点， 使算法具有比以往更好的优化性能。是一种21 世纪新发展起来的概率自优化的进化算法。量子遗传算法与传统的遗传算法相比较它的优点在染色体的表示方式上， 传统的遗传算法的染色体是一个确定的值，只能代表一个优化解，然而，量子遗传算法中的染色体不是一个确定值，一个普通的染色体能表示该优化函数

21、所需要的所有的优化解， 因此， 量子遗传算法中的染色体对于优化解集具有更好的代表性， 更能完整地描述优化函数的优化解集， 而且，相比传统的遗传算法的进化方向与进化的值是唯一确定的， 但对于量子遗传算法来讲， 它的进化操作是通过量子旋转门来实现的，而且旋转门的大小与方向都是随着遗传的迭代次数可以改变的，所以通过此类操作能更好的使染色体进行优化演化。 总之，实现了比传统的遗传算法更好的效果。它基于量子计算的原理， 使用量子的特性来表达优化函数的解集， 即染色体，所以相比普通算法的优化解集它能携带更多的信息。 也因为如此， 他能更好的表达全体优化函数的解集。使优化解集种群更加地多样化， 最后，使用旋

22、转门来实现染色体的进化演化操作， 通过旋转门的演化操作使染色体的进化过程更加地稳定，从而使算法性能更加的优越。92.22.2 量子遗传算法研究意义量子遗传算法研究意义传统的遗传算法在对于处理一些简单的优化函数问题时， 表现了优越的优化性能。 通过最基本的三个遗传操作选择、 交叉、变异来寻找最优的优化解。 特别是遗传算法所具有的不受优化问题的性质， 大小以及优化的依据等外界因素的影响。 它只是通过概率的普遍搜索来获得优化函数的优化解， 所以， 他能具有良好的通用性能， 在社会实践中得到了广泛的应用。但随着应用范围的增加， 人们也逐渐的发现遗传算法所具有的一些缺陷。 由于传统遗传操作的随机性，如选

23、择、交叉与变异都是基于概率的选择的操作10，所以不可避免的会存在概率优化算法的缺点。 传统遗传算法会表现出遗传次数增加却依旧得不到较好的优化解集， 对于全局的优化搜索能力较弱，而且容易陷入局部极值这一缺点。在传统的遗传算法中如果种群的大小选择不当，对于优化的效果的影响将会非常地明显，种群小将会使优化算法的选择领域受到限制， 不能很好地搜索全局的优化解集， 影响寻3优能力，然而种群过大则会使优化算法的计算复杂度急速的上升。 ，传统的遗传算法的染色体优化解是一个确定的值， 只能代表一个优化函数的优化解， 然而，量子遗传算法中的染色体优化解不是一个确定值， 一个普通的染色体能表示该优化函数所需要的所

24、有的优化解， 因此， 量子遗传算法中的染色体对于优化函数的全局优化解集具有更好的代表性， 更能充分的描绘优化函数的优化解集， 并且，利用旋转门来实现每个染色体解的进化操作， 使算法的遗传进化演化操作更加的稳定， 算法性能更加优越。 量子遗传算法是利用量子计算表示信息的特点， 来构成它特有的染色体的形态， 使得量子遗传算法的染色体具有更多地优化函数的优化解集的信息。 更好的表达了全局函数优化解集的样貌。 最后则是再通过量子的概率幅交叉操作来实现种群解的多样性。2.32.3 量子遗传算法的基本原理量子遗传算法的基本原理2.3.1.2.3.1.量子比特量子比特在传统的遗传算法中，我们使用计算机中的二

25、进制表示方式来表示优化解集的遗传信息。我们将存储遗传信息的二进制称之为比特(Bit)。而在量子遗传算法中，我们采用|0和|1的单量子比特的叠加态来表示遗传信息11。它们跟传统的信息表达的方式的区别在于它不止止只有两种状态可以选择， 而且它们可以是两种基本状态的任意的叠加， 所以使用此种的信息表示方式编码组成染色体也是一个不定值，能更好的代表函数的优化解集。在量子遗传算法中的量子位可以是|0到|1中的任意的值， 所以一个量子位的状态的表达式可以为：| 0 |1 (2.1)其中量子态的概率幅与是一对平方和 1 的复数，对优化种群进行一次测量操作，2|可能会以|2的概率大小坍缩到| 0状态， 或者它

26、会以| 的概率坍缩到| 1的状态，并且它们会满足下面的表达式条件：|2+|2=1 (2.2)在式(2.2)中，|表示|0的概率，| 表示|1的概率，量子态坍缩是为了结合适22应度值来优选种源，因此，如果一个系统有 m 个量子位，则该系统可同时描述 2 个状态，然而，对于量子态12的每一次观察，该量子位都只会坍缩到一个确定的状态。在这里会得到量子态的确定值， 此值的形体都是由量子比特概率的大小所决定的的。 产生|0或|1状态的具体过程如下：首先，先生成一个在零到一之间的随机数r,如果 r|，则坍缩到| 02m的状态，否则坍缩到| 1的状态.42.3.22.3.2 染色体表示方法染色体表示方法在传

27、统遗传算法中， 染色体的表示方式在进化演化计算之前就是确定的 （使用确定的二进制表示优化函数的染色体解集） ，所以在优化解集的表示方面，会存在一些缺陷。然而，在现在的量子遗传算法中，一个基因采用的是量子比特来表示13。该基因可以是“0”态或“1”态，也可以是它们之间的任意叠加态。即每一个基因位不再代表地是某一确定的遗传信息，而是包含该优化函数所需要的所有的优化解集信息， 因此，我们对于任意基因位的任一操作都可能会使种群中所有的优化解集信息产生变化。 这里将继续使用传统遗传算法中的二进制， 对于优化函数的目标解集采用量子比特编码， 这样就可以用一个量子比特来表示解集的两个状态，两个量子比特就可以

28、表示四种状态。 此种编码方式具有通用性好， 且实现简单等优点。量子遗传是使用量子比特来表达一个基因，由若干个基因来组成一个染色体解。这里将会使用一对平方和为1 的复数对(,)来表示染色体中的一个量子比特，则 c 个 j位基因构成的一个染色体可以表示为：nnnnnnnn11.1nj21.21222j.c1c2.cjqn|n|n|n|n|n|n|nn.1j2 jcjc1c221221112ni|(2.3)式中： i 是染色体的编号， n 是染色体当前进化的代数， c 是基因位的个数， 第 n 代第 i个个体的染色体用 qj描述的，j 是每个用二进制表示的每个优化解中含有的量子比特数。t 11 ,2

29、 的形式来初始化种群中的全部染色体解集的在刚开始的初始化情况下，都会以2所有基因， 等概率的叠加是量子遗传算法中染色特初始化的一中特殊情况。 如果是在一个以3 个量子比特位的染色体中，那么它会具有 3 对概率幅，如下所示：121212323212（2.4）则这个系统的状态可以描述为：3133|000|001|010|0114 24 24 24 23133|100|101|110|1114 24 24 24 2(2.5)从上面的系统状态描述可以知道优化函数的染色体解集的状态： |000、 |001、 |010、 |011、|100、|101、|110、|111的状态的概率大小分别为：3/32，1

30、/32，9/32，3/32，3/32，1/32，9/32，3/32。所以上式（2.4）描述的三个比特量子系统能同时包含8 个状态，如果用传统的表示方法那么至少需要 8 条的染色体来表示， 这就是量子遗传染色体组少， 却能拥有丰富种群的关键，并且随着、趋近与 1 或 0，染色体收敛于一个确定的状态。52.3.32.3.3 量子旋转门量子旋转门量子旋转门作为量子遗传算法中进化演化操作的执行机构14， 在优化算法中具有重要的地位。 所以对于不同的优化函数的优化问题我们要区别的对待， 在了解需要优化函数的特性之后才能正确的选择合适的量子旋转门操作15。量子旋转门的功能结构如下所示：cos(i)(i)

31、sin()isin(i) (2.6)cos(i)sin(i)i (2.7)cos(i)i它的更新过程如下：iicos(i)(i)iisin(i)其中， 第 i 个染色体进行旋转门演化操作前后的概率幅由(i,i)T和(i,i)T描述；i为旋转角的大小，其大小由事先定好的调整策略决定， 该调整策略是一种通用的。 与优化问题无关的调整策略，如表2-1表 2-1 旋转角度选择表xibestif (x) f (best)is(i,i)ii 0ii 0i 0i 00000111100110011FALSETRUEFALSETRUEFALSETRUEFALSETRUE000.010.010.010.0100

32、00+1-1-1+10000-1+1+1-1000000010011000100表中xi中 i 来表示当前值是染色体的第几位；besti中的 i 表示的是为当前的最优染色体的第 i 位上的表示情况；适应度函数为f (x)；s(i,i)为旋转角方向；旋转角的大小用i来描述，它的大小的取值通常是在 0.005到 0.05之间的某一值，旋转角的大小可以是某一确定值， 也可以根据进化的实际情况来进行动态微调整， 同过此类操作能很好的达到函数优化效果的要求。 它们的值都是根据表 2-1 中所列的选择策略确定的。 量子旋转t门的运行过程如下所示：首先，将通过适应度函数f (x)计算出当前的个体qj的适应度

33、值，然后与当前优化种群最佳的适应度值f (best )进行比较，如果当代优化种群个体的适应度t值f (x )大于现有的最优优化适应度值f (best),那么就应该调整qj中相应的量子比特位，6能够让概率幅s(i,i)的演化方向是朝着向着量子位xi的，不然，如果f (x)f(x),那么就接受新解为当前解；如果expf (x) f (x)大于(0,1)区间的随机数，则依旧接受新的解为当T前的解，否则，就会拒绝新的解而保留现在的解。该过程会不断的重复，可以知道，开始的温度比较高， 算法接受差解的概率也会比较高， 这就让算法有更大的机会跳出局部11的最优解，随着退火的进行，温度会逐渐降低，算法接受差解

34、的概率就会变小。3.2.43.2.4 模拟退火算法的基本流程模拟退火算法的基本流程模拟金属冶炼退火操作的主要操作有两个： 第一个， 温度下降的大小值是由固体冷却过程中的热静力学操作来实现确定的， 第二个，在每个的温度下进行随机搜索的次数。 在实际应用中，退火算法必须有时间的限制，这个需要的条件有：第一，一个起始温度；第二，一个控制温度下降的函数；第三，一个决定在每个温度下状态转移参数的标准；第四，一个停止温度；第五， 算法停止的条件。模拟退火算法实际上是一种迭代求解的过程，算法反复执行“产生新状态-计算目标函数-判断是否接受新状态-接受/舍弃的”过程，它的基本流程如下：1)初始化，初始温度T，

35、初始解S，每个T值的迭代次数；2)对种群完成第（3）到第（6） ；3)产生新的解S;4)计算增量 E(S) E(S),其中E(S)为目标函数；5)若 0， 则接受S作为新的现在的解， 不然以概率exp(/T)接受S为新的当前的解；6)如果满足终止条件则输出当前的解作为最优解，结束循环；7)T（温度）会逐步的降低，而且T会慢慢的趋近于0，转到步骤（2） 。在算法的执行过程中， 为了保证算法的收敛能力， 要保证退火的初始温度T尽可能的大，一般情况下T取值为100， L表示对于每一个温度取值T进行的遗传进化的演化次数， 考虑到运行算法的时间，我们通常取值在1020之间。3.33.3 改进的量子遗传算

36、法的具体实现改进的量子遗传算法的具体实现模拟退火操作的寻优过程是通过设置初始温度的大小与现实降温过程的速率来实现的，在温度较高时候， 算法能够以较高的概率接受比现在不好的优化解， 通过此操作能避免算法陷入局部极值， 而能较好的接受好的优化解是在温度较低的时候， 模拟退火的这种搜索模式增强了算法的搜索能力和效率。 量子遗传算法通过使用量子计算中存储信息的方式， 充分的描述了优化函数所有的解集， 进而大大的提升了优化算法的寻优能力。 量子遗传算法是使用量子位来表示遗传的信息， 利用量子计算的一些特性， 进行染色体的量子编码。 实现了比传统的遗传算法更好的效果。 将量子遗传能充分的描述优化的解集的特

37、点与退火操作寻找全局最优的能力相结合， 我们称这种算法为基于模拟退火的量子遗传算法性能相互互补，能使新算法获得质量较高的优化解。20，算法中，两种搜索123.3.13.3.1 模拟退火算子及参数选取模拟退火算子及参数选取在模拟退火算子中，初始温度越大，退回系数越大（退回系数小于1的正数） ，收敛到全局最优解的概率就越大， 收敛的时间也就会越长。 所以进行参数选择的同时要考虑搜索的效率与求解的质量。 在执行完模拟退火操作后， 需要把每个染色体个体的量子位信息反应到量子编码上， 以便进行量子遗传算法的操作。 在算法的运行过程中退火的温度系数一般取为0.95。3.3.23.3.2 基于模拟退火的量子

38、遗传算法具体实现基于模拟退火的量子遗传算法具体实现引入模拟退火思想后的量子遗传算法， 在每一次迭代进化的时候引入模拟退火算法， 来确定每个个体的进化方向。基于模拟退火操作的量子遗传算法具体步骤如下：1)随机生成种群并进行初始化；2)对种群进行测量得到一组确定的状态；3)记录最佳适应度值和对应的个体将其作为下一步种群进化的目标；4)查看优化算法是否可以停止，若满足结束条件则退出，否则继续进行计算；5)模拟退火操作；6)当温度过高时， 是算法以一定的概率让量子旋转门不朝着种群目标值的进化方向进化，当温度较低时，是算法接受目标值的进化方向， 利用量子旋转门对种群进行更新，然后按照全局交叉的策略对种群

39、进行量子交叉操作，得到子代Q(t+1)7)记录最优个体和对应的适应度值；8)将迭代的次数加1，返回步骤(4)；3.3.33.3.3 基于模拟退火的量子遗传算法流程图基于模拟退火的量子遗传算法流程图对应的流程图如图3-113开始随机生成种群并进行初始化记录最佳适应度值和对应的个体作为下一步种群更新的目标值Y满足终止条件N模拟退火算法进行全局交叉，改变种群形态，得到 Q（t+1）结束根据模拟退火算法的返回值确定种群进化的方向，利用量子旋转门更新种群记录最优个体和对应的适应度值迭代数加 1图3-1 基于模拟退火算法的量子遗传算法流程图引入模拟退火思想后的新量子遗传算法， 对个体的进化方向进行模拟退火

40、的操作， 然后将整个迭代过程中的最优解保留作为下一次进化迭代的目标值。3.43.4 改进的量子遗传算法的优点改进的量子遗传算法的优点将改进好的量子遗传算法跟传统的量子遗传算法进行性能的比较， 可以发现它具有以下几方面的优点：1)加入量子交叉操作。在这个函数的优化过程中， 为量子遗传算法添加了 “全干扰的交叉”量子遗传交叉方式。在使用这种递归的量子交叉后， 算法中的染色体的量子位的信息可以得到充分地交流， 使得解集种群更加的多样化。 通过此操作可以很好的克服算法的“早熟收敛” 。该操作的原理是借用量子计算中的相干性，较好的克14服了染色体进化过程中易陷入局部最优的缺陷。2)加入模拟退火思想。在现

41、有的量子遗传算法中， 添加了模拟退火算子， 其新染色体状态的产生依靠现有的温度的大小来决定是否接受恶化解的能力大小， 该操作使进化算法从局部最优的局限中脱离出来， 继续进行遗传进化，搜索于全局，然后逐步趋近于最优的解。加入了 “全干扰交叉” 的量子交叉方式与模拟退火思想的之后量子遗传算法能够对于一些多峰函数的优化问题， 体现出很好的优越性， 就算量子遗传算法早期演化时产生的个体优化解的差异性比较大， 该算法也能够很好地收敛到全局的最优解或近似全局最优解。 就算是使用轮盘赌方式选择优化函数的染色体解集，对优化算法的影响也不会太大。154 4 算法性能测试及分析算法性能测试及分析为了检验上面改进好

42、的量子遗传算法的可行性与有效性，我们将会改进好的算法对5个典型的函数进行算法优化性能的验证，通过与传统的量子遗传算法在运行时间、收敛效率、优化性能等方面的比较。4.14.1 典型测试函数典型测试函数4.1.14.1.1 简单平方和函数简单平方和函数2f1(x1,x2) 1 x12 x23 x1,x2 3图4-1 简单平方和函数此函数具有多个局部的最小值，但只有一个全局的最小值f1(0,0) 1。4.1.2Rastrigrin4.1.2Rastrigrin 函数函数2f2(x1,x2) 20 x12 x210(cos2x1cos2x2)3 x1,x2 3图4-2 Rastrigrin 多极值函数

43、16此函数具有多个局部的最小值，但只有一个全局的最小值f2(0,0) 0。4.1.3De Jong4.1.3De Jong 函数函数 F2F2f3(x1,x2) 100(x12 x2)2(1 x1)22.048 x1,x2 2.048图4-3 De Jong函数F2De Jong 函数F2是一个变态函数， 很难寻找全局最小值， 它具有全局最小值f3(1,1) 0。4.1.4Goldsten-Price4.1.4Goldsten-Price 函数函数2f4(x1,x2) 1 (x1 x21)2(1914x13x1214x2 6x1x23x2) *30 (2x123x2)2(1832x112x12

44、 48x236x1x2 27x2) 2 x1,x2 2图4-4 Goldstren-Price函数这个函数在其定义域内只有一个极小值点f4(0,1) 3。174.1.5Six-hump Camel Back4.1.5Six-hump Camel Back 函数函数x42f5(x, y) (42.1x )x xy (4 4y2)y2323 x 32 y 2图4-5 Six-hump Camel Back函数Six-hump Camel Back函数共有多个相似极小值点，很难准确地取得最小值点，其中(-0.0898 ， 0.7126) 和 (0.0898 ， -0.7126) 为 全 局 最 小

45、点 ， 最 小 值 为。f5(0.0898,0.7126) f5(0.0898,0.7126) 1.0316284.24.2 算法参数设定算法参数设定1)普通量子遗传算法的参数设定： 将每个初始种群规模的大小都设置为40， 最大的遗传代数设为200，函数的每一个变量的二进制长度设为20。2)含量子交叉的量子遗传算法的参数设定：将每个初始种群规模的大小都设置为40，最大的遗传代数设为200，函数的每一个变量的二进制长度设为20。量子交叉采用的是量子全干扰交叉算法。3)含退火思想的量子遗传算法参数设定： 将每个初始种群规模的大小都设置为40， 最大的遗传代数设为200，函数的每一个变量的二进制长度

46、设为20，初始的温度设置为100度。退火系数设置为0.9.4)含量子交叉和退火思想的量子遗传算法参数设定： 将每个初始种群规模的大小都设置为40，最大的遗传代数设为200，函数的每一个变量的二进制长度设为20，初始的温度设置为100度。退火系数设置为0.9. 并且采用量子全干扰交叉操作。184.34.3 测试结果即分析测试结果即分析对于每个测试的函数，普通量子遗传算法、含量子交叉的量子遗传算法、 含退火思想的量子遗传算法、 含量子交叉和退火思想的量子遗传算法他们各自独立的运行20次， 他们的最优搜索值与搜索平均值的统计结果如下表4.1所示。表4.1 仿真实验数据统计表优化函数简单平方和函数优化

47、算法QGACQGASQGASCQGA最优搜索值1.00021.00121.00011.00000.00520.00190.00660.00300.00360.00670.00280.00043.09393.05423.50733.014-1.0315-1.0316-1.0315-1.0315平均搜索值1.00121.00171.00051.00090.05010.01800.01470.01470.24720.06800.00880.00524.03033.87503.6453.352-1.0311-1.0310-1.0300-1.0314迭代次数40509712571789298127161

48、8441734561197186104理论最优值1111000000003333-1.031628-1.031628-1.031628-1.031628Rastrigrin函数De Jong函数F2函数Six-humpCamel Back函数QGACQGASQGASCQGAQGACQGASQGASCQGAQGAGoldsten-PriceCQGASQGASCQGAQGACQGASQGASCQGA对于上面的5个优化性能测试函数，它们都采用了二进制的编码，染色体的长度设置为20，分别用普通量子遗传、含量子交叉的量子遗传、 含退火思想的量子遗传算法和含量子交叉与退火思想的量子遗传的四种算法进行20次

49、的函数优化寻优， 种群的规模设置为40， 最大的迭代的次数为200，采用全局量子交叉， 模拟退火的初始温度设置为100度，退火系数设置为0.9。191.1. 对于第一个简单平方和测试函数的算法性能比较图：对于第一个简单平方和测试函数的算法性能比较图：图4-6 简单平方和函数量子遗传进化过程由上面图4-6可以得知， 对于简单的平方函数在种群的大小与迭代的次数一样的情况下，普通的量子遗传算法的寻优迭代次数是最短的， 但是它寻优能力都不如其它的三种优化算法的能力， 由图中得知， 基于量子交叉与退火操作的量子遗传算法是寻优能力最强的取得了全局的最小值1，相比其他的优化函数最优值都只有取到1.0012与

50、1.0001，由此可以说明含退火算法与量子交叉操作的量子遗传算法对于简单的函数有化具有更好的性能， 但我们也从中看出，相比于其它的优化操作，它进行的迭代时间是最长的。2. Rastrigrin2. Rastrigrin 测试函数的算法性能比较图：测试函数的算法性能比较图：图4-7 Rastrigrin 函数量子遗传进化过程20由上面图4-7可以得知，对于多峰值的优化函数在种群的大小与迭代的次数一样的情况下， 加入量子交叉操作的量子遗传算法的寻优性能是最好的， 其它的优化算法在一般的情况下， 都不如它的优化能， 虽然在一些算法中加入了退火操作以此来使染色体种群的具有更好的多样性，但似乎没有达到预