基于量子遗传算法的函数寻优算法设计[毕业论文]

毕业论文（设计）题目：基于量子遗传算法的函数寻优算法设计学院：数理与信息学院学生姓名：专业：计算机科学与技术班级：A11计算机指导教师：谭小球起止日期：2014年11月16日至2015年6月12日2015年5月13日基于量子遗传算法的函数寻优算法设计摘要量子遗传算法(QGA)是20世纪90年代后期兴起的一种崭新的遗传进化算法。该算法主要是将量子计算的概念引入其中，将量子的态矢量表达引入了遗传编码，使一条染色体可以表达多个信息态的叠加，同时利用量子旋转门实现染色体的演化，实现了目标解的进化。相比传统遗传算法，量子遗传算法能够在较小的种群规模下，快速的收敛到全局最优解。本文首先介绍了量子遗传算法的基本原理与算法结构，然后对量子遗传算法提出疑问。虽然量子遗传算法的优化性能大大优于传统遗传算法，但是，对于一些多峰函数的优化问题，该类算法依旧容易陷入“局部最优”。在实际的应用中有很多优化问题都是多变量的连续优化问题，现有的量子遗传算法不能有效的解决这些问题。针对量子遗传算法容易陷入局部最优和未成熟收敛的缺陷，我们提出了一种新的优化算法——含有退火操作的量子遗传算法，该优化算法能够以可变的概率选择性地接受恶化的优化函数解，使种群解集的进化方向改变，不在依靠当前解进行遗传演化。从而使算法不易“早熟收敛”。而且在该算法中加入了全干扰的量子交叉操作，使各染色体能进行遗传信息的交换，使种群染色体更具有代表性。最后根据改进后的，对改进的量子遗传算法进行了数值仿真。有效地证明了改进算法在函数寻优方面的优越性。【关键词】量子遗传算法，量子编码，退火思想，量子交叉，函数寻优DiscoveryofFunctionExtremeValueBasedonQuantumGeneticAlgorithmZhangChen(SchoolofMathematics，PhysicsandInformation，ZhejiangOceanUniversity316000)AbstractQuantumgeneticalgorithm(QGA)wasoriginatedinthelate1990sasanewgeneticevolutionalgorithm,whichintroducestheconceptofquantumcomputationintogeneticalgorithm,i.e.,introducingquantumstatevectorexpressionofthegeneticcodesothatachromosomecanexpressthesuperpositionofmultiplekindsofinformation.Moreover,theevolutionofthechromosomebyusingquantumrevolvingdoor,realizethegoalofevolution.Comparedwiththetraditionalgeneticalgorithm,Thequantumgeneticalgorithmcansrapidlyconvergencetotheglobaloptimalsolutionunderthesmallerpopulationsize.Thispaperfirstintroducesthebasicprincipleofquantumgeneticalgorithmandalgorithmstructure.Andthenthedefectsexistinginthecurrentquantumgeneticalgorithmisproposed.Althoughquantumgeneticalgorithmtooptimizeperformancegreatlysuperiortothetraditionalgeneticalgorithm.Especiallyformultimodalfunctionoptimizationproblems,QGAalsohasthetendencytofallintolocaloptimum.Asformanymultivariatecontinuousoptimizationproblemsinactualapplication,theexistingQGAcannotsolvetheseproblemseffectively.SinceQGAmaybetrappedinlocaloptimumandthedefectofprematureconvergence,weproposedanewalgorithm,QuantumGeneticAlgorithmwithAnnealingOperation(QGAAO).Thealgorithmcanselectivelyacceptdeterioratingatacertainprobabilitysothatpopulationhasmorechancetojumpoutthelocaloptimaltoavoidprematureconvergence.Moreover,globaldisturbhasbeenaddedtothealgorithmofthequantumcrossoveroperation,itcanmakechromosomesexchangemoregeneticinformation.Itcanbetterrepresentthechromosomepopulation.Finally,accordingtotheimprovedscheme,theimprovedquantumgeneticalgorithmwascommittedforthenumericalsimulation.Thetestprovedthattheimprovedalgorithmeffectivelysuperiorityintermsoffunctionoptimization.【Keywords】quantumgeneticalgorithm,quantumcoding,annealingthought,quantumcrossover,functionoptimization目录摘要 IAbstract II1.绪论 11.1遗传算法 11.2量子计算 11.3函数优化 11.4选题背景和意义 22.量子遗传算法 32.1量子遗传算法概述 32.2量子遗传算法研究意义 32.3量子遗传算法的基本原理 42.3.1.量子比特 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基于模拟退火的量子遗传算法流程图 133.4改进的量子遗传算法的优点 144算法性能测试及分析 164.1典型测试函数 164.1.1简单平方和函数 164.1.2Rastrigrin函数 164.1.3DeJong函数F2 174.1.4Goldsten-Price函数 174.1.5Six-humpCamelBack函数 184.2算法参数设定 184.3测试结果即分析 195总结与展望 245.1论文总结 245.2展望 24参考文献 261.绪论1.1遗传算法在20世纪70年代美国密西根大学教授J.Holland第一个提出了基于概率的优化算法——遗传算法[1]（GA）。遗传算法的原理跟自然界的遗传进化演化原因是一致的。遗传算法根据优化函数的目标函数来进行全局自适应的概率搜索[2]，寻找优化函数的最优值。由于遗传算法可以不依靠优化函数的形式与不受外界因素的影响，所以，遗传算法在实际优化应用中得到了良好的应用。因为遗传算法具有良好的适用性、全局性、并行高效的优化性能与鲁棒性[3]，所以它具有诱人的吸引力，吸引人们前去研究。对于现实中的应用，它对外界的要求不严格，能够广泛的应用，所以它具有很好的应用前景。但是，如果在遗传算法中的选择、交叉和变异的操作方式选取不当，那么算法在迭代次数、收敛速度、优化性能等方面都会轻易地受到影响，并且，这都会使优化函陷入局部极值的这一陷阱。1.2量子计算量子计算[4]（QC）的概念是在二十世纪七十年代提出来的。那时的主要研究是计算三个特性之间相互的关系。P.Benioff与八十年代率先提出了量子计算可以用来进行仿真数据的计算[5]。在1994年，美国的Shor教授第一次将量子计算运用到了大数的因子分解中，从那时开始，量子计算的研究方向有了充分的拓宽[6]。量子计算有新的研究动力。使用量子态[4]作为计算中的基本的信息的存储单位，是量子计算的一大特色。使用量子态具有的叠加、纠缠和干涉等特点可以很好的解决一些常见的经典问题。通常信息是用一种物质或存在的状态来表示的。计算机最早是使用纸带的穿孔方式来表示二进制的，但随着科学技术的发展，到后来计算机开始使用晶体管的开关状态来表示二进制的信息。现在随着量子力学的发展，其揭示了微观粒子的运动状态。开始使用原子的运动状态来表示二进制。量子计算就是利用原子中电子的两种自旋状态来表示信息的[7]。量子计算要想实现其真正意义上的并行计算就必须在量子计算机上面，但是我们可以将量子计算机制和量子信息运用到智能算法中，或者是将已有的优化算法和量子算法相结合，使算法的优化性能得到提高，使它具有传统优化算法所不具有的优异性能。1.3函数优化函数优化问题是量子遗传算法的经典应用领域[19]，也是对量子遗传算法进行性能评价的常用算法.对于一些不规则或者是多变的与多值的函数的优化问题，使用其它方法去优化解决它们，是比较麻烦的，但是如果我们使用量子遗传算法就可能很好的解决这些问题，轻易地得到较好的优化结果。函数优化[8]问题简单讲就是求取一个函数中的最小值或者是最大值。函数的优化问题通常的描述是：设S是上的有界的子集，：S->R是n维的实值函数。如果在领域内能找到一个点的值小于该领域内其它所有点的值，那么我们就称该点是该函数在领域内的最小值所在的点。通常，此点就是我要求的最优值的点。函数优化问题通常是一个非常复杂的优化问题，特别是对于那些不可微的或者多极值的函数优化，常常是不能很好的求到有效解的。但是，对于新出现的量子遗传算法来讲，它可以较好的避免此类情况，在处理一些复杂的优化函数时，依旧能保持较好的性能，原因在于量子遗传算法能很好的描绘出全局最优的解集，它将每种可能的最优解都可由一个染色体来描述，相比传统的遗传算法的染色体只能表示一个确定的解，但对于量子遗传算法的一个染色体，却可以表示多个优化解，有如此特性的染色体组成的种群，能更好的代表优化解集。之后它在按遗传进化学的规律来进行选择、交叉与变异操作，使染色体根据每代的进化目标来进行遗传“进化”，直到最后满足终止条件为止。1.4选题背景和意义量子遗传算法在现代的许多的应用优化领域发挥着至关重要的作用。量子遗传算法与传统的遗传算法的内在原理是一样，它们都是一种基于自然界生物“优胜劣汰”的生存规则的一种进化优化算法。它是一种适合复杂系统优化计算的优化技术.然而现在的量子遗传算法也存在着种种的问题。它的不足方面有：第一，由于算法是通过概率搜索来获得最优值的，因此会不可避免的产生概率搜索[7]所具有的普遍问题——盲目性与随机性，部分个体将不可避免的产生退化，从而会大大降低算法的寻优能力。第二，由于要进行大量的适应度值的计算与个体染色体的进化操作，这些操作大大的增加了算法的计算量，因而影响算法的运行时间，降低了算法的性能；第三，对于量子旋转门的转角方向、大小，一视同仁，没有考虑染色体之间的差异。因此，应加注重量子遗传的种群大小的选择，即进化策略的设计与实施。第四，在算法优化的后期，优化算法可能会处于停滞阶段或进化的速度很缓慢，因此那是算法容易陷入“早熟收敛”这一缺陷。第五，算法每次进化的方向都是以最优值适应度值的个体。容易陷入局部的最优解。第六，现有的量子遗传算法缺少染色体之间的信息交流，不能充分的使用染色体的进化的特点。对于存在的问题，本课题进行了详细的研究，并且提出了一些解决方案。本课题提出了一种基于退火思想和量子交叉的量子遗传算法。这个算法使量子遗传算法的种群具有更好的代表性，通过这种算法极大的提高了量子遗传算法的性能。2.量子遗传算法2.1量子遗传算法概述将经典量子计算（QC）与传统遗传算法它们的算法操作方式相互的融合之后产生了新的优化算法——量子遗传算法（QuantumGeneticAlgorithm，QGA）[9]。它既具有传统遗传算法所具有的优化算法的普遍性与通用性，又能利用量子计算中信息存储方式的优点，使算法具有比以往更好的优化性能。是一种21世纪新发展起来的概率自优化的进化算法。量子遗传算法与传统的遗传算法相比较它的优点在染色体的表示方式上，传统的遗传算法的染色体是一个确定的值，只能代表一个优化解，然而，量子遗传算法中的染色体不是一个确定值，一个普通的染色体能表示该优化函数所需要的所有的优化解，因此，量子遗传算法中的染色体对于优化解集具有更好的代表性，更能完整地描述优化函数的优化解集，而且，相比传统的遗传算法的进化方向与进化的值是唯一确定的，但对于量子遗传算法来讲，它的进化操作是通过量子旋转门来实现的，而且旋转门的大小与方向都是随着遗传的迭代次数可以改变的，所以通过此类操作能更好的使染色体进行优化演化。总之，实现了比传统的遗传算法更好的效果。它基于量子计算的原理，使用量子的特性来表达优化函数的解集，即染色体，所以相比普通算法的优化解集它能携带更多的信息。也因为如此，他能更好的表达全体优化函数的解集。使优化解集种群更加地多样化，最后，使用旋转门来实现染色体的进化演化操作，通过旋转门的演化操作使染色体的进化过程更加地稳定，从而使算法性能更加的优越。2.2量子遗传算法研究意义传统的遗传算法在对于处理一些简单的优化函数问题时，表现了优越的优化性能。通过最基本的三个遗传操作选择、交叉、变异来寻找最优的优化解。特别是遗传算法所具有的不受优化问题的性质，大小以及优化的依据等外界因素的影响。它只是通过概率的普遍搜索来获得优化函数的优化解，所以，他能具有良好的通用性能，在社会实践中得到了广泛的应用。但随着应用范围的增加，人们也逐渐的发现遗传算法所具有的一些缺陷。由于传统遗传操作的随机性，如选择、交叉与变异都是基于概率的选择的操作[10]，所以不可避免的会存在概率优化算法的缺点。传统遗传算法会表现出遗传次数增加却依旧得不到较好的优化解集，对于全局的优化搜索能力较弱，而且容易陷入局部极值这一缺点。在传统的遗传算法中如果种群的大小选择不当，对于优化的效果的影响将会非常地明显，种群小将会使优化算法的选择领域受到限制，不能很好地搜索全局的优化解集，影响寻优能力，然而种群过大则会使优化算法的计算复杂度急速的上升。，传统的遗传算法的染色体优化解是一个确定的值，只能代表一个优化函数的优化解，然而，量子遗传算法中的染色体优化解不是一个确定值，一个普通的染色体能表示该优化函数所需要的所有的优化解，因此，量子遗传算法中的染色体对于优化函数的全局优化解集具有更好的代表性，更能充分的描绘优化函数的优化解集，并且，利用旋转门来实现每个染色体解的进化操作，使算法的遗传进化演化操作更加的稳定，算法性能更加优越。量子遗传算法是利用量子计算表示信息的特点，来构成它特有的染色体的形态，使得量子遗传算法的染色体具有更多地优化函数的优化解集的信息。更好的表达了全局函数优化解集的样貌。最后则是再通过量子的概率幅交叉操作来实现种群解的多样性。2.3量子遗传算法的基本原理2.3.1.量子比特在传统的遗传算法中，我们使用计算机中的二进制表示方式来表示优化解集的遗传信息。我们将存储遗传信息的二进制称之为比特(Bit)。而在量子遗传算法中，我们采用|0>和|1>的单量子比特的叠加态来表示遗传信息[11]。它们跟传统的信息表达的方式的区别在于它不止止只有两种状态可以选择，而且它们可以是两种基本状态的任意的叠加，所以使用此种的信息表示方式编码组成染色体也是一个不定值，能更好的代表函数的优化解集。在量子遗传算法中的量子位可以是|0>到|1>中的任意的值，所以一个量子位的状态的表达式可以为：(2.1)其中量子态的概率幅与是一对平方和1的复数，对优化种群进行一次测量操作，可能会以2的概率大小坍缩到|0>状态，或者它会以||2的概率坍缩到|1>的状态，并且它们会满足下面的表达式条件：2+||2=1(2.2)在式(2.2)中，2表示|0>的概率，||2表示|1>的概率，量子态坍缩是为了结合适应度值来优选种源，因此，如果一个系统有m个量子位，则该系统可同时描述2m个状态，然而，对于量子态[12]的每一次观察，该量子位都只会坍缩到一个确定的状态。在这里会得到量子态的确定值，此值的形体都是由量子比特概率的大小所决定的的。产生|0>或|1>状态的具体过程如下：首先，先生成一个在零到一之间的随机数r,如果r>2，则坍缩到|0>的状态，否则坍缩到|1>的状态.2.3.2染色体表示方法在传统遗传算法中，染色体的表示方式在进化演化计算之前就是确定的（使用确定的二进制表示优化函数的染色体解集），所以在优化解集的表示方面，会存在一些缺陷。然而，在现在的量子遗传算法中，一个基因采用的是量子比特来表示[13]。该基因可以是“0”态或“1”态，也可以是它们之间的任意叠加态。即每一个基因位不再代表地是某一确定的遗传信息，而是包含该优化函数所需要的所有的优化解集信息，因此，我们对于任意基因位的任一操作都可能会使种群中所有的优化解集信息产生变化。这里将继续使用传统遗传算法中的二进制，对于优化函数的目标解集采用量子比特编码，这样就可以用一个量子比特来表示解集的两个状态，两个量子比特就可以表示四种状态。此种编码方式具有通用性好，且实现简单等优点。量子遗传是使用量子比特来表达一个基因，由若干个基因来组成一个染色体解。这里将会使用一对平方和为1的复数对来表示染色体中的一个量子比特，则c个j位基因构成的一个染色体可以表示为：(2.3)式中：i是染色体的编号，n是染色体当前进化的代数，c是基因位的个数，第n代第i个个体的染色体用qtj描述的，j是每个用二进制表示的每个优化解中含有的量子比特数。在刚开始的初始化情况下，都会以的形式来初始化种群中的全部染色体解集的所有基因，等概率的叠加是量子遗传算法中染色特初始化的一中特殊情况。如果是在一个以3个量子比特位的染色体中，那么它会具有3对概率幅，如下所示：（2.4）则这个系统的状态可以描述为：(2.5)从上面的系统状态描述可以知道优化函数的染色体解集的状态：|000>、|001、|010>、|011>、|100>、|101>、|110>、|111>的状态的概率大小分别为：3/32，1/32，9/32，3/32，3/32，1/32，9/32，3/32。所以上式（2.4）描述的三个比特量子系统能同时包含8个状态，如果用传统的表示方法那么至少需要8条的染色体来表示，这就是量子遗传染色体组少，却能拥有丰富种群的关键，并且随着趋近与1或0，染色体收敛于一个确定的状态。2.3.3量子旋转门量子旋转门作为量子遗传算法中进化演化操作的执行机构[14]，在优化算法中具有重要的地位。所以对于不同的优化函数的优化问题我们要区别的对待，在了解需要优化函数的特性之后才能正确的选择合适的量子旋转门操作[15]。量子旋转门的功能结构如下所示：(2.6)它的更新过程如下：(2.7)其中，第i个染色体进行旋转门演化操作前后的概率幅由描述；为旋转角的大小，其大小由事先定好的调整策略决定，该调整策略是一种通用的。与优化问题无关的调整策略，如表2-1表2-1旋转角度选择表00FALSE0000000TRUE0000001FALSE0.01+1-1001TRUE0.01-1+1010FALSE0.01-1+1010TRUE0.01+1-1011FALSE0000011TRUE00000表中中i来表示当前值是染色体的第几位；中的i表示的是为当前的最优染色体的第i位上的表示情况；适应度函数为；为旋转角方向；旋转角的大小用来描述，它的大小的取值通常是在0.005到0.05之间的某一值，旋转角的大小可以是某一确定值，也可以根据进化的实际情况来进行动态微调整，同过此类操作能很好的达到函数优化效果的要求。它们的值都是根据表2-1中所列的选择策略确定的。量子旋转门的运行过程如下所示：首先，将通过适应度函数计算出当前的个体的适应度值，然后与当前优化种群最佳的适应度值进行比较，如果当代优化种群个体的适应度值大于现有的最优优化适应度值,那么就应该调整中相应的量子比特位，能够让概率幅的演化方向是朝着向着量子位的，不然，如果<,那么就应该中量子比特位进行微调，确保概率幅的演化方向是朝着的方向。2.5量子遗传算法步骤及流程图2.5.1量子遗传算法的步骤流程量子遗传算法的步骤流程：1) 对初始种群Q（）进行函数优化解集种群的初始化操作,描述的是所有优化解集种群中每个染色体上的一个基因位，是它们初始的大小，这就表明一个染色体所描述地是其全部可能的优化解集状态的等概率的组合。染色体使用的是随机生成的n个量子比特的编码；2) 对出使种群中的每个个体进行一次测量，得到对应确定的解P，测量过程为：随机产生一个在0~1之间的随机数，若它的大于概率幅的平方，那么测量结果取值为1，反之，测量结果取值为0；3) 对各确定染色体优化解P进行适应度评估操作，以此来得到每个解的适应度值的大小，以此来进行下一步的遗传淘汰选择操；4) 记录最优个体和对应的适应度；5) 判断优化算法是否可以结束优化操作，如果现有的优化解集满足优化结束的条件则退出优化算法，不然继续执行优化操作；6) 对优化解集种群Q中的每个个体即染色体优化解进行一次染色体基因位大小的确定操作，通过此操作来得到对应遗传代数种群的函数优化解集；7) 对各确定解进行适应度评估；8) 利用量子旋转门U(t)对每个染色体个体进行一次遗传演化操作，以此得到新的优化函数的最优解集种群Q(t+1);9) 记录最优个体和对应的适应度；10) 将迭代次数t加1，返回步骤(5);2.5.2量子遗传算法的流程图对应的流程图如图2-1所示。图2-1量子遗传算法运行流程框图3量子遗传算法的改进3.1量子遗传算法存在问题现有的量子遗传算法在优化某些不规则函数时，能拥有较好的优化性能。但，对于一些特别复杂的、病态的优化函数却不能很好的发挥其优越的性能。量子遗传算法海存在较多需改进的内容：比如说现有的算法中没有加入量子交叉操作，使得染色体之间的信息不能充分的被利用。而且，与传统的遗传算法相比较，虽然现在的量子遗传算法的性能有了巨大的飞跃，但依旧存在许多缺陷，如下：对于一些多峰值函数的优化问题，普通的量子遗传算法不能很好的求其最优解，然而，现实生活中的很多地实际优化应用问题都是多峰值、不规则与变态的优化函数。并且，对于染色体的演化操作太过单一化，不能充分表达生物的进化过程。而且当我们采用经典的轮盘赌[16]的方式来决定染色体中基因位的形态时，很容易让在进化选择的早起产生的个别好的个体，在优化算法演化地后期产生严重的影响，从而使优化算法的优化性能降低。此类操作也会在优化算法演化的后期产生严重后果，使染色体演化的操作变得缓慢，使量子旋转门的功能效果不够明显。这也会降低函数优化的性能。为了能在实际的优化应用中更好的发挥量子遗传算法的优化作用。急需我们改进量子遗传算法。将模拟退火与量子交叉引入量子遗传算法中以此来提高算法的优化性能。该算法在量子个体上实施量子交叉，增加各染色体之间的信息交流，引入退火思想尽量避免算法在早期时陷入局部的最优。使得算法很好的避免了早熟与进化停滞不前的情况。3.2改进方案的基本思想3.2.1全局量子交叉优化函数的解集（染色体）的演化方向是量子遗传算法中最能体现优化种群染色体的现有量子位信息的，即在现有的优化解集种群中的当前染色体解个体的最优确定解以及其对应的优化适应度值的大小。在染色体之间考虑某些基因位的互换有利于实现染色体之间信息的交流，增强种群遗传的信息利用率[17]。在量子遗传算法中，由于染色体的状态处于叠加的状态，不同于传统的遗传算法，交叉仅仅局限于两个染色体之间进行。在量子遗传算法中我们不能使用传统的交叉操作，但我们可以采用一种叫做全局干扰交叉的交叉操作，在该交叉操作中使所有的染色体都参于到其中，下面的图表是我们用来简单的描述该交叉方式的，即该种群的大小值为3，染色体的个数为3个，每个染色体的长度为5，该种群结构如表3.1表3.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个量子比特用B（2）来表示，用递归的方式来进行全局干扰操作。交叉后的染色体的基因位的确定方法是：交叉前的基因位以现在的基因位序号大小减一在种群中向下移动几位，如果移动的位数超过种群染色体数则除以现在种群的大小后取得的余数减1就是该基因为向下移动的位数。表3.2表示的是经过全局干扰交叉操作后的染色体组。表3.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)上表展示了染色体解集的的另外一种演化方式，其中新的交叉后的函数优化解是用大写字母来描述的，如：B（1）—A（2）—C（3）—B（4）—A（5）。通过此类操作，优化种群中每个染色体上的量子位信息将会被充分的利用，在种群演化的后期能够充分保持优化解集的多样性，从而改进了算法的性能。同过量子交叉演化，它会产生个多的新个体使种群更加的多样化，进而使进化的过程更具有活力，使算法不易陷入局部的最优。此操作是借用了量子计算中的量子相干的特性来实现的，在加入该操作后量子遗传算法的早熟现象能够很好地得到改善。3.2.2模拟退火思想Metropolis由自然界的高温退火操作进而得到启发，提出了一种模拟自然界退火操作的算法，它也是全局优化算法中的一种，通过一种可变的突跳概率使算法跳出局部最优这一致命性的缺陷。退火算法的思想是模仿金属冶炼操作过程来寻找优化函数的全局的最优优化解。模拟退火法是一种通用的优化算法。以下两个操作是模拟退火算法的主要操作：1) 热静力学操作，用于安排降温过程；2) 随机张弛操作，用于搜索在特定温度下的平衡态；从金属冶炼的退火过程，我们可以对退火操作进行简单的描述，加入模拟退火操作的算法不仅会接受比现在好的优化解，还以一定的可变概率接受比现有的解不好的优化解，使算法在刚开始演化时不是一直向着最优解的方向演化，而且，在刚开时进行优化算法演化操作时，设置的初始温度会比较高，所以它接受恶化的概率也就比较大，但当温度降低到一定程度的时候，接受恶化解的概率就会接近0，则只会接受优化解，算法就趋于最优。算法的主要特点有一下几点：1) 以一定的概率接受恶化的解。2) 温度控制参数T，它会将优化算法的寻优过程划分为几个阶段，通过使用Metropolis准则计算得到地值来决定各个阶段状态的取舍。含有退火操作的优化算法最优能否寻找到全局的最优值，Metropolis准则是非常关键的起到决定性作用，通过使用Metropolis准则能较好地避免陷入局部最优。模拟退火算法的最显著的优点在于它能够成功地避免陷入局部的最优这一缺陷。形象的形容：好比一名登山运动员要攀登该地区最高的山峰，在刚刚开始的时候运动员先登上山，但他不知道这山峰是不是附近最高的，所以他还要以一定的概率，下山，尝试攀登有没有别的山峰比现在的要更高。3.2.3模拟退火算法的概念1) 温度（temperature）是一个重要的参数，对于含有退火操作的优化算法而言。它随着算法的演化时间而逐步的降低，用来模拟金属冶炼过程中的降温过程，刚开始，温度用于限制算法产生的新解与当代解之间的差距，即使算法的搜索范围；其次，接受现有解的概率的大小由现有的温度所决定的。2) 优化算法中温度的下降速度用退火进度表(annealingschedule)来描述的，要使算法寻找到较好的全局优化解，那么就应该不退火过程设置得缓慢一些，这样就能更好地寻找到函数的最优解，但相应的程序运行的时间也会增加。退火进度表包括初始温度(initialtemperature)以及温度的更新函数(temperatureupdatefunction)等参数。3) Meteopolis准则：决定着每代函数优化解的保留情况。对于要获得全局最小值的函数优化寻优问题，优化算法能够接受新的优化解的概率为：（3.1）其中，x是当前的解；为新的解；f(x)为x解的适应度的值；T为温度。式（3.1）的含义是：对于当前的解x与新的解，如果f(x)>f(),那么就接受新解为当前解；如果大于(0,1)区间的随机数，则依旧接受新的解为当前的解，否则，就会拒绝新的解而保留现在的解。该过程会不断的重复，可以知道，开始的温度比较高，算法接受差解的概率也会比较高，这就让算法有更大的机会跳出局部的最优解，随着退火的进行，温度会逐渐降低，算法接受差解的概率就会变小。3.2.4模拟退火算法的基本流程模拟金属冶炼退火操作的主要操作有两个：第一个，温度下降的大小值是由固体冷却过程中的热静力学操作来实现确定的，第二个，在每个的温度下进行随机搜索的次数。在实际应用中，退火算法必须有时间的限制，这个需要的条件有：第一，一个起始温度；第二，一个控制温度下降的函数；第三，一个决定在每个温度下状态转移参数的；第四，一个停止温度；第五，算法停止的条件。模拟退火算法实际上是一种迭代求解的过程，算法反复执行“产生新状态->计算目标函数->判断是否接受新状态->接受/舍弃的”过程，它的基本流程如下：1) 初始化，初始温度T，初始解S，每个T值的迭代次数；2) 对种群完成第（3）到第（6）；3) 产生新的解;4) 计算增量,其中E(S)为目标函数；5) 若，则接受作为新的现在的解，不然以概率接受为新的当前的解；6) 如果满足终止条件则输出当前的解作为最优解，结束循环；7) T（温度）会逐步的降低，而且T会慢慢的趋近于0，转到步骤（2）。在算法的执行过程中，为了保证算法的收敛能力，要保证退火的初始温度T尽可能的大，一般情况下T取值为100，L表示对于每一个温度取值T进行的遗传进化的演化次数，考虑到运行算法的时间，我们通常取值在10—20之间。3.3改进的量子遗传算法的具体实现模拟退火操作的寻优过程是通过设置初始温度的大小与现实降温过程的速率来实现的，在温度较高时候，算法能够以较高的概率接受比现在不好的优化解，通过此操作能避免算法陷入局部极值，而能较好的接受好的优化解是在温度较低的时候，模拟退火的这种搜索模式增强了算法的搜索能力和效率。量子遗传算法通过使用量子计算中存储信息的方式，充分的描述了优化函数所有的解集，进而大大的提升了优化算法的寻优能力。量子遗传算法是使用量子位来表示遗传的信息，利用量子计算的一些特性，进行染色体的量子编码。实现了比传统的遗传算法更好的效果。将量子遗传能充分的描述优化的解集的特点与退火操作寻找全局最优的能力相结合，我们称这种算法为基于模拟退火的量子遗传算法[20]，算法中，两种搜索性能相互互补，能使新算法获得质量较高的优化解。3.3.1模拟退火算子及参数选取在模拟退火算子中，初始温度越大，退回系数越大（退回系数小于1的正数），收敛到全局最优解的概率就越大，收敛的时间也就会越长。所以进行参数选择的同时要考虑搜索的效率与求解的质量。在执行完模拟退火操作后，需要把每个染色体个体的量子位信息反应到量子编码上，以便进行量子遗传算法的操作。在算法的运行过程中退火的温度系数一般取为0.95。3.3.2基于模拟退火的量子遗传算法具体实现引入模拟退火思想后的量子遗传算法，在每一次迭代进化的时候引入模拟退火算法，来确定每个个体的进化方向。基于模拟退火操作的量子遗传算法具体步骤如下：1) 随机生成种群并进行初始化；2) 对种群进行测量得到一组确定的状态；3) 记录最佳适应度值和对应的个体将其作为下一步种群进化的目标；4) 查看优化算法是否可以停止，若满足结束条件则退出，否则继续进行计算；5) 模拟退火操作；6) 当温度过高时，是算法以一定的概率让量子旋转门不朝着种群目标值的进化方向进化，当温度较低时，是算法接受目标值的进化方向，利用量子旋转门对种群进行更新，然后按照全局交叉的策略对种群进行量子交叉操作，得到子代Q(t+1)7) 记录最优个体和对应的适应度值；8) 将迭代的次数加1，返回步骤(4)；3.3.3基于模拟退火的量子遗传算法流程图对应的流程图如图3-1图3-1基于模拟退火算法的量子遗传算法流程图引入模拟退火思想后的新量子遗传算法，对个体的进化方向进行模拟退火的操作，然后将整个迭代过程中的最优解保留作为下一次进化迭代的目标值。3.4改进的量子遗传算法的优点将改进好的量子遗传算法跟传统的量子遗传算法进行性能的比较，可以发现它具有以下几方面的优点：1) 加入量子交叉操作。在这个函数的优化过程中，为量子遗传算法添加了“全干扰的交叉”量子遗传交叉方式。在使用这种递归的量子交叉后，算法中的染色体的量子位的信息可以得到充分地交流，使得解集种群更加的多样化。通过此操作可以很好的克服算法的“早熟收敛”。该操作的原理是借用量子计算中的相干性，较好的克服了染色体进化过程中易陷入局部最优的缺陷。2) 加入模拟退火思想。在现有的量子遗传算法中，添加了模拟退火算子，其新染色体状态的产生依靠现有的温度的大小来决定是否接受恶化解的能力大小，该操作使进化算法从局部最优的局限中脱离出来，继续进行遗传进化，搜索于全局，然后逐步趋近于最优的解。加入了“全干扰交叉”的量子交叉方式与模拟退火思想的之后量子遗传算法能够对于一些多峰函数的优化问题，体现出很好的优越性，就算量子遗传算法早期演化时产生的个体优化解的差异性比较大，该算法也能够很好地收敛到全局的最优解或近似全局最优解。就算是使用轮盘赌方式选择优化函数的染色体解集，对优化算法的影响也不会太大。4算法性能测试及分析为了检验上面改进好的量子遗传算法的可行性与有效性，我们将会改进好的算法对5个典型的函数进行算法优化性能的验证，通过与传统的量子遗传算法在运行时间、收敛效率、优化性能等方面的比较。4.1典型测试函数4.1.1简单平方和函数图4-1简单平方和函数此函数具有多个局部的最小值，但只有一个全局的最小值。4.1.2Rastrigrin函数图4-2Rastrigrin多极值函数此函数具有多个局部的最小值，但只有一个全局的最小值。4.1.3DeJong函数F2图4-3DeJong函数F2DeJong函数F2是一个变态函数，很难寻找全局最小值，它具有全局最小值。4.1.4Goldsten-Price函数图4-4Goldstren-Price函数这个函数在其定义域内只有一个极小值点。4.1.5Six-humpCamelBack函数图4-5Six-humpCamelBack函数Six-humpCamelBack函数共有多个相似极小值点，很难准确地取得最小值点，其中(-0.0898，0.7126)和(0.0898，-0.7126)为全局最小点，最小值为。4.2算法参数设定1) 普通量子遗传算法的参数设定：将每个初始种群规模的大小都设置为40，最大的遗传代数设为200，函数的每一个变量的二进制长度设为20。2) 含量子交叉的量子遗传算法的参数设定：将每个初始种群规模的大小都设置为40，最大的遗传代数设为200，函数的每一个变量的二进制长度设为20。量子交叉采用的是量子全干扰交叉算法。3) 含退火思想的量子遗传算法参数设定：将每个初始种群规模的大小都设置为40，最大的遗传代数设为200，函数的每一个变量的二进制长度设为20，初始的温度设置为100度。退火系数设置为0.9.4) 含量子交叉和退火思想的量子遗传算法参数设定：将每个初始种群规模的大小都设置为40，最大的遗传代数设为200，函数的每一个变量的二进制长度设为20，初始的温度设置为100度。退火系数设置为0.9.并且采用量子全干扰交叉操作。4.3测试结果即分析对于每个测试的函数，普通量子遗传算法、含量子交叉的量子遗传算法、含退火思想的量子遗传算法、含量子交叉和退火思想的量子遗传算法他们各自独立的运行20次，他们的最优搜索值与搜索平均值的统计结果如下表4.1所示。表4.1仿真实验数据统计表优化函数优化算法最优搜索值平均搜索值迭代次数理论最优值简单平方和函数QGA1.00021.0012401CQGA1.00121.0017501SQGA1.00011.0005971SCQGA1.00001.00091251Rastrigrin函数QGA0.00520.0501710CQGA0.00190.0180780SQGA0.00660.0147920SCQGA0.00300.0147980DeJong函数F2QGA0.00360.2472120CQGA0.00670.068070SQGA0.00280.0088160SCQGA0.00040.0052180Goldsten-Price函数QGA3.09394.0303443CQGA3.05423.8750173SQGA3.50733.645343SCQGA3.0143.352563Six-humpCamelBack函数QGA-1.0315-1.0311119-1.031628CQGA-1.0316-1.031071-1.031628SQGA-1.0315-1.030086-1.031628SCQGA-1.0315-1.0314104-1.031628对于上面的5个优化性能测试函数，它们都采用了二进制的编码，染色体的长度设置为20，分别用普通量子遗传、含量子交叉的量子遗传、含退火思想的量子遗传算法和含量子交叉与退火思想的量子遗传的四种算法进行20次的函数优化寻优，种群的规模设置为40，最大的迭代的次数为200，采用全局量子交叉，模拟退火的初始温度设置为100度，退火系数设置为0.9。1.对于第一个简单平方和测试函数的算法性能比较图：图4-6简单平方和函数量子遗传进化过程由上面图4-6可以得知，对于简单的平方函数在种群的大小与迭代的次数一样的情况下，普通的量子遗传算法的寻优迭代次数是最短的，但是它寻优能力都不如其它的三种优化算法的能力，由图中得知，基于量子交叉与退火操作的量子遗传算法是寻优能力最强的取得了全局的最小值1，相比其他的优化函数最优值都只有取到1.0012与1.0001，由此可以说明含退火算法与量子交叉操作的量子遗传算法对于简单的函数有化具有更好的性能，但我们也从中看出，相比于其它的优化操作，它进行的迭代时间是最长的。2.Rastrigrin测试函数的算法性能比较图：图4-7Rastrigrin函数量子遗传进化过程由上面图4-7可以得知，对于多峰值的优化函数在种群的大小与迭代的次数一样的情况下，加入量子交叉操作的量子遗传算法的寻优性能是最好的，其它的优化算法在一般的情况下，都不如它的优化能，虽然在一些算法中加入了退火操作以此来使染色体种群的具有更好的多样性，但似乎没有达到预期的目标，原因可能是，多个峰值间隔太近，导致算法一直在实行退火操作，在冷却是算法并没有很好的跳出局部最优这一陷阱，导致了算法性能的降低。3.DeJong函数F2的测试函数的算法性能比较图:图4-8DeJong函数F2量子遗传进化过程由上面图4-8可以得知，对于一些病态的函数优化能力，采用了量子交叉与退火操作的量子遗传算法的性能是最优的，可以将全局的最小值搜索到0.002，相比其它的优化算法只能搜索到0.3,0.15与0.36。它的性能是远远的优于其它的优化算法。由此，可以得出含有退火思想与量子交叉操作的量子遗传算法对于病态的函数寻优具有更好的性能。4.Goldstren-Price测试函数的算法性能比较图:图4-9Goldstren-Price函数量子遗传进化过程由上面图4-9可以得知，对于一些连续的多元的函数的优化能力，采用了量子交叉与退火操作的量子遗传算法的性能是最优的，可以将全局的最小值搜索到3.014，与其它的优化算法相比较它搜索到的最优值是5.2,3.5与4.7。它的性能是远远的优于其它的优化算法。由此，可以得出含有退火思想与量子交叉操作的量子遗传算法对于一些连续的多元的函数寻优具有更好的性能。5.Goldstren-Price测试函数的算法性能比较图:图4-10Six-humpCamelBack函数量子遗传进化过程由上面图4-10可以得知，对于一些含有多个极值点的函数的优化能力，采用了量子交叉与退火操作的量子遗传算法的性能是最优的，可以将全局的最小值搜索到-1.0315，其它的优化算法只能搜索到的最优值是-1.0307与-1.0309。可以从数据判断得知，它的性能是远远的优于其它的优化算法。由此，可以得出含有退火思想与量子交叉操作的量子遗传算法对于一些含有多个极值点的函数的寻优具有更好的性能。从上面的仿真实验可以了解到，含量子交叉与退火思想的量子遗传算法在求最优解的时，发现首次最优解的能力是最强的，相比其它的算法它的性能有了很大的提高。含量子交叉与退火思想的量子遗传算法能够在早起发现最优解，并且在早期与其他的量子算法相比较，它的种群更加地具有多样性，它同过量子交叉操作与退火操作使其种群的种类更加的多样，使其能更加完整、全面的表达种群的样貌，通过此种群搜索所有的染色体，获得最佳适应度值也就更加地能代表该算法的最优值的大小。因此，从最优解的收敛概率上来看，含量子交叉与退火思想的量子遗传是在这些算法中性能最好的。但是，含量子交叉与退火思想的量子遗传算法在搜索最优的上花费的时间也比其他的量子遗传算法要多得多。这是由于我们在该算法中添加了适用于全局的量子全干扰交叉的量子交叉与退火操作。这些操作增加了算法的复杂度，影响了算法的搜索能力。对于全干扰的量子递归交叉操作，该操作让种群中所有的染色体的基因位进行一次循环对调操作，以此来打乱原有染色体解集的样貌，使其能更好的描述优化函数全局解集的样貌。退火操作不仅使该算法能在子代的产生过程中接受适应度值高的个体，它还以一定的概率接受适应度值较差的个体，因此增加了该算法的搜索范围，虽然在优化算法中引入这些操作会在一定的程度上增加算法寻优的运行的时间，但它却有效的避免了算法的“早熟收敛”这一问题。根据这些我们可以得出含量子交叉与退火思想的量子遗传算法是一种寻优能力较好的搜索算法。以此算法我们能很好的得到连续的多峰函数的最优值。5总结与展望量子遗传算法是将量子计算中信息存储的优点与传统遗传算法具有的通用性相结合，从而提升了优化算法的寻优能力。本文通过在原有的量子遗传中添加全干扰的量子交叉与退火操作，从而提升了原有量子遗传算法的搜索寻优能力，通过在算法中添加交叉与退火操作，使算法在多元连续的多峰函数中，具有更好的适应性，能有效的避免陷入传统算法易陷入的“早熟收敛”这一问题。5.1论文总结本文的研究内容主要包括以下几个方面：1) 对于传统的遗传算法与量子遗传算法进行简单的学习，包括对于量子比特的特点与概率幅的叠加态的表现形式，量子旋转门的性质与功能，并且简单的介绍了量子旋转的策略选择。2) 通过对于量子遗传算法的研究发现，基本的量子遗传算法还具有较多的问题，有许多可以改进的方面。对最近几年改进过的量子遗传算法进行研究与总结，并且提出了一种新的优化进化算法，通过仿真数据的仿真实验证明，经过改进的量子遗传算法具有更好的优化寻优能力，能够在多元的连续多峰函数中搜索到较好的最优值。3) 对于量子遗传的改进研究主要时集中在现有的理论基础之上，其思想就是充分的表达种群的样貌，使种群能更好的代表函数的优化解。因此，在该算法中添加了量子全干扰的交叉与退火操作，将退火操作引入量子遗传算法，使其在子代中能以一定的概率接受父代中适应度较差的个体，有效地抑制了子代种群容易陷入局部最优的确点，并且以退火温度T来控制算法的选择压力，有效地保证了算法在后期的全局收敛性。这些操作可以有效的使染色体之间的信息交互。使染色体更具有多样性。这一性能在随后的仿真实验中充分得到了证明。4) 是用5个经典的优化函数测试改进后的量子遗传算法的性能，并且有效证明了改进的优化算法的优越性能。5.2展望文中的改进量子遗传算法--基于全干扰与退火操作的量子遗传算法，在多元连续的多峰函数中取得了一定的成果，弥补了传统量子遗传方面的一些缺点，但它依然存在着一些不完善的地方，需要在今后的学习与研究中继续地努力改进。1) 基于量子交叉与退火操作的量子遗传算法在搜索的速度上有待改进，需要一种既能很好的搜索全局，又不会影响函数运行的时间的搜索策略。2) 在量子遗传算法中的演化操作过程，需要使用到量子旋转门进行演化操作，在确定基因位时，需要进行大量的计算操作，非常消耗寻优的运行时间，影响了优化算法的寻优性能，所以需要我们姨现有的量子旋转门进行改进，以此来提高算法寻优的速度。3) 可以在后续的改进算法中，实行顺序与逆序染色体分别作为一个初始化个体，这样，对个体的量子位进行测量一次就能得到两条染色体，大大加快了初始化的速度4) 可以在以后的算法中加入精英库与干扰库，精英库在进化的早起大大提高了种群的搜索速度，干扰库可以在进化的一定情况下，对种群进行人为的干扰，使其避免算法的早熟收敛[18]。5) 在以后的改进算法中，把量子旋转门的旋转角能根据不同的情况而改变，这样对于适应度值高的个体，就能更好的进入到下一代的计算中，而对于适应度值低的个体就会尽快的淘汰。算法自适应的旋转角，既能保证群体解集的多样性，也维护算法的收敛性。参考文献[1]HollandJH.Geneticalgorithmsandclassifiersystems:foundationsandtheirapplication[C]//ProceedingsoftheSecondInternationalConferenceonGeneticAlgorithms.Hillsdale,NJ:LawrenceErlbaumAssociates,1987:82-89[2]KalkaC.Grover'squantumsearchingalgorithmisoptimal[J].PhysicalReviewA,1999,60:2746-2751[3]JenE.StableorRobust?What’sthedifference?[J].Complexity,2003,8(3):12-18[4]MelanieMitchell.Anintroductiontogeneticalgorithms.Cambridge,MA:TheMITPress,1996[5]BennettCH,DiVinceNzoDY,QuantumInformationandComputation.Nature,2000.404.247一255