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

毕业论文（设计）题目基于量子遗传算法的函数寻优算法设计学院数理与信息学院学生姓名张晨专业计算机科学与技术班级A11计算机指导教师谭小球起止日期2014年11月16日至2015年6月12日2015年5月13日基于量子遗传算法的函数寻优算法设计张晨（浙江海洋学院数理与信息学院，浙江舟山316022）摘要量子遗传算法QGA是20世纪90年代后期兴起的一种崭新的遗传进化算法。该算法主要是将量子计算的概念引入其中，将量子的态矢量表达引入了遗传编码，使一条染色体可以表达多个信息态的叠加，同时利用量子旋转门实现染色体的演化，实现了目标解的进化。相比传统遗传算法，量子遗传算法能够在较小的种群规模下，快速的收敛到全局最优解。本文首先介绍了量子遗传算法的基本原理与算法结构，然后对量子遗传算法提出疑问。虽然量子遗传算法的优化性能大大优于传统遗传算法，但是，对于一些多峰函数的优化问题，该类算法依旧容易陷入“局部最优”。在实际的应用中有很多优化问题都是多变量的连续优化问题，现有的量子遗传算法不能有效的解决这些问题。针对量子遗传算法容易陷入局部最优和未成熟收敛的缺陷，我们提出了一种新的优化算法含有退火操作的量子遗传算法，该优化算法能够以可变的概率选择性地接受恶化的优化函数解，使种群解集的进化方向改变，不在依靠当前解进行遗传演化。从而使算法不易“早熟收敛”。而且在该算法中加入了全干扰的量子交叉操作，使各染色体能进行遗传信息的交换，使种群染色体更具有代表性。最后根据改进后的方案，对改进的量子遗传算法进行了数值仿真。有效地证明了改进算法在函数寻优方面的优越性。【关键词】量子遗传算法，量子编码，退火思想，量子交叉，函数寻优DISCOVERYOFFUNCTIONEXTREMEVALUEBASEDONQUANTUMGENETICALGORITHMZHANGCHENSCHOOLOFMATHEMATICS，PHYSICSANDINFORMATION，ZHEJIANGOCEANUNIVERSITY316000ABSTRACTQUANTUMGENETICALGORITHMQGAWASORIGINATEDINTHELATE1990SASANEWGENETICEVOLUTIONALGORITHM,WHICHINTRODUCESTHECONCEPTOFQUANTUMCOMPUTATIONINTOGENETICALGORITHM,IE,INTRODUCINGQUANTUMSTATEVECTOREXPRESSIONOFTHEGENETICCODESOTHATACHROMOSOMECANEXPRESSTHESUPERPOSITIONOFMULTIPLEKINDSOFINFORMATIONMOREOVER,THEEVOLUTIONOFTHECHROMOSOMEBYUSINGQUANTUMREVOLVINGDOOR,REALIZETHEGOALOFEVOLUTIONCOMPAREDWITHTHETRADITIONALGENETICALGORITHM,THEQUANTUMGENETICALGORITHMCANSRAPIDLYCONVERGENCETOTHEGLOBALOPTIMALSOLUTIONUNDERTHESMALLERPOPULATIONSIZETHISPAPERFIRSTINTRODUCESTHEBASICPRINCIPLEOFQUANTUMGENETICALGORITHMANDALGORITHMSTRUCTUREANDTHENTHEDEFECTSEXISTINGINTHECURRENTQUANTUMGENETICALGORITHMISPROPOSEDALTHOUGHQUANTUMGENETICALGORITHMTOOPTIMIZEPERFORMANCEGREATLYSUPERIORTOTHETRADITIONALGENETICALGORITHMESPECIALLYFORMULTIMODALFUNCTIONOPTIMIZATIONPROBLEMS,QGAALSOHASTHETENDENCYTOFALLINTOLOCALOPTIMUMASFORMANYMULTIVARIATECONTINUOUSOPTIMIZATIONPROBLEMSINACTUALAPPLICATION,THEEXISTINGQGACANNOTSOLVETHESEPROBLEMSEFFECTIVELYSINCEQGAMAYBETRAPPEDINLOCALOPTIMUMANDTHEDEFECTOFPREMATURECONVERGENCE,WEPROPOSEDANEWALGORITHM,QUANTUMGENETICALGORITHMWITHANNEALINGOPERATIONQGAAOTHEALGORITHMCANSELECTIVELYACCEPTDETERIORATINGATACERTAINPROBABILITYSOTHATPOPULATIONHASMORECHANCETOJUMPOUTTHELOCALOPTIMALTOAVOIDPREMATURECONVERGENCEMOREOVER,GLOBALDISTURBHASBEENADDEDTOTHEALGORITHMOFTHEQUANTUMCROSSOVEROPERATION,ITCANMAKECHROMOSOMESEXCHANGEMOREGENETICINFORMATIONITCANBETTERREPRESENTTHECHROMOSOMEPOPULATIONFINALLY,ACCORDINGTOTHEIMPROVEDSCHEME,THEIMPROVEDQUANTUMGENETICALGORITHMWASCOMMITTEDFORTHENUMERICALSIMULATIONTHETESTPROVEDTHATTHEIMPROVEDALGORITHMEFFECTIVELYSUPERIORITYINTERMSOFFUNCTIONOPTIMIZATION【KEYWORDS】QUANTUMGENETICALGORITHM,QUANTUMCODING,ANNEALINGTHOUGHT,QUANTUMCROSSOVER,FUNCTIONOPTIMIZATION目录摘要IABSTRACTII1绪论111遗传算法112量子计算113函数优化114选题背景和意义22量子遗传算法321量子遗传算法概述322量子遗传算法研究意义323量子遗传算法的基本原理4231量子比特4232染色体表示方法5233量子旋转门625量子遗传算法步骤及流程图7251量子遗传算法的步骤流程7252量子遗传算法的流程图73量子遗传算法的改进931量子遗传算法存在问题932改进方案的基本思想9321全局量子交叉9322模拟退火思想10323模拟退火算法的概念11324模拟退火算法的基本流程1233改进的量子遗传算法的具体实现12331模拟退火算子及参数选取13332基于模拟退火的量子遗传算法具体实现13333基于模拟退火的量子遗传算法流程图1334改进的量子遗传算法的优点144算法性能测试及分析1641典型测试函数16411简单平方和函数16412RASTRIGRIN函数16413DEJONG函数F217414GOLDSTENPRICE函数17415SIXHUMPCAMELBACK函数1842算法参数设定1843测试结果即分析195总结与展望2451论文总结2452展望24参考文献261绪论11遗传算法在20世纪70年代美国密西根大学教授JHOLLAND第一个提出了基于概率的优化算法遗传算法1（GA）。遗传算法的原理跟自然界的遗传进化演化原因是一致的。遗传算法根据优化函数的目标函数来进行全局自适应的概率搜索2，寻找优化函数的最优值。由于遗传算法可以不依靠优化函数的形式与不受外界因素的影响，所以，遗传算法在实际优化应用中得到了良好的应用。因为遗传算法具有良好的适用性、全局性、并行高效的优化性能与鲁棒性3，所以它具有诱人的吸引力，吸引人们前去研究。对于现实中的应用，它对外界的要求不严格，能够广泛的应用，所以它具有很好的应用前景。但是，如果在遗传算法中的选择、交叉和变异的操作方式选取不当，那么算法在迭代次数、收敛速度、优化性能等方面都会轻易地受到影响，并且，这都会使优化函陷入局部极值的这一陷阱。12量子计算量子计算4（QC）的概念是在二十世纪七十年代提出来的。那时的主要研究内容是计算三个特性之间相互的关系。PBENIOFF与八十年代率先提出了量子计算可以用来进行仿真数据的计算5。在1994年，美国的SHOR教授第一次将量子计算运用到了大数的因子分解中，从那时开始，量子计算的研究方向有了充分的拓宽6。量子计算有新的研究动力。使用量子态4作为计算中的基本的信息的存储单位，是量子计算的一大特色。使用量子态具有的叠加、纠缠和干涉等特点可以很好的解决一些常见的经典问题。通常信息是用一种物质或存在的状态来表示的。计算机最早是使用纸带的穿孔方式来表示二进制的，但随着科学技术的发展，到后来计算机开始使用晶体管的开关状态来表示二进制的信息。现在随着量子力学的发展，其揭示了微观粒子的运动状态。开始使用原子的运动状态来表示二进制。量子计算就是利用原子中电子的两种自旋状态来表示信息的7。量子计算要想实现其真正意义上的并行计算就必须在量子计算机上面，但是我们可以将量子计算机制和量子信息运用到智能算法中，或者是将已有的优化算法和量子算法相结合，使算法的优化性能得到提高，使它具有传统优化算法所不具有的优异性能。13函数优化函数优化问题是量子遗传算法的经典应用领域19，也是对量子遗传算法进行性能评价的常用算法对于一些不规则或者是多变的与多值的函数的优化问题，使用其它方法去优化解决它们，是比较麻烦的，但是如果我们使用量子遗传算法就可能很好的解决这些问题，轻易地得到较好的优化结果。函数优化8问题简单讲就是求取一个函数中的最小值或者是最大值。函数的优化问题通常的描述是设S是上的有界的子集，SR是N维的实值函数。如果在领域内能找NRF到一个点的值小于该领域内其它所有点的值，那么我们就称该点是该函数在领域内的最小值所在的点。通常，此点就是我要求的最优值的点。函数优化问题通常是一个非常复杂的优化问题，特别是对于那些不可微的或者多极值的函数优化，常常是不能很好的求到有效解的。但是，对于新出现的量子遗传算法来讲，它可以较好的避免此类情况，在处理一些复杂的优化函数时，依旧能保持较好的性能，原因在于量子遗传算法能很好的描绘出全局最优的解集，它将每种可能的最优解都可由一个染色体来描述，相比传统的遗传算法的染色体只能表示一个确定的解，但对于量子遗传算法的一个染色体，却可以表示多个优化解，有如此特性的染色体组成的种群，能更好的代表优化解集。之后它在按遗传进化学的规律来进行选择、交叉与变异操作，使染色体根据每代的进化目标来进行遗传“进化”，直到最后满足终止条件为止。14选题背景和意义量子遗传算法在现代的许多的应用优化领域发挥着至关重要的作用。量子遗传算法与传统的遗传算法的内在原理是一样，它们都是一种基于自然界生物“优胜劣汰”的生存规则的一种进化优化算法。它是一种适合复杂系统优化计算的优化技术然而现在的量子遗传算法也存在着种种的问题。它的不足方面有第一，由于算法是通过概率搜索来获得最优值的，因此会不可避免的产生概率搜索7所具有的普遍问题盲目性与随机性，部分个体将不可避免的产生退化，从而会大大降低算法的寻优能力。第二，由于要进行大量的适应度值的计算与个体染色体的进化操作，这些操作大大的增加了算法的计算量，因而影响算法的运行时间，降低了算法的性能；第三，对于量子旋转门的转角方向、大小，一视同仁，没有考虑染色体之间的差异。因此，应加注重量子遗传的种群大小的选择，即进化策略的设计与实施。第四，在算法优化的后期，优化算法可能会处于停滞阶段或进化的速度很缓慢，因此那是算法容易陷入“早熟收敛”这一缺陷。第五，算法每次进化的方向都是以最优值适应度值的个体。容易陷入局部的最优解。第六，现有的量子遗传算法缺少染色体之间的信息交流，不能充分的使用染色体的进化的特点。对于存在的问题，本课题进行了详细的研究，并且提出了一些解决方案。本课题提出了一种基于退火思想和量子交叉的量子遗传算法。这个算法使量子遗传算法的种群具有更好的代表性，通过这种算法极大的提高了量子遗传算法的性能。2量子遗传算法21量子遗传算法概述将经典量子计算（QC）与传统遗传算法它们的算法操作方式相互的融合之后产生了新的优化算法量子遗传算法（QUANTUMGENETICALGORITHM，QGA）9。它既具有传统遗传算法所具有的优化算法的普遍性与通用性，又能利用量子计算中信息存储方式的优点，使算法具有比以往更好的优化性能。是一种21世纪新发展起来的概率自优化的进化算法。量子遗传算法与传统的遗传算法相比较它的优点在染色体的表示方式上，传统的遗传算法的染色体是一个确定的值，只能代表一个优化解，然而，量子遗传算法中的染色体不是一个确定值，一个普通的染色体能表示该优化函数所需要的所有的优化解，因此，量子遗传算法中的染色体对于优化解集具有更好的代表性，更能完整地描述优化函数的优化解集，而且，相比传统的遗传算法的进化方向与进化的值是唯一确定的，但对于量子遗传算法来讲，它的进化操作是通过量子旋转门来实现的，而且旋转门的大小与方向都是随着遗传的迭代次数可以改变的，所以通过此类操作能更好的使染色体进行优化演化。总之，实现了比传统的遗传算法更好的效果。它基于量子计算的原理，使用量子的特性来表达优化函数的解集，即染色体，所以相比普通算法的优化解集它能携带更多的信息。也因为如此，他能更好的表达全体优化函数的解集。使优化解集种群更加地多样化，最后，使用旋转门来实现染色体的进化演化操作，通过旋转门的演化操作使染色体的进化过程更加地稳定，从而使算法性能更加的优越。22量子遗传算法研究意义传统的遗传算法在对于处理一些简单的优化函数问题时，表现了优越的优化性能。通过最基本的三个遗传操作选择、交叉、变异来寻找最优的优化解。特别是遗传算法所具有的不受优化问题的性质，大小以及优化的依据等外界因素的影响。它只是通过概率的普遍搜索来获得优化函数的优化解，所以，他能具有良好的通用性能，在社会实践中得到了广泛的应用。但随着应用范围的增加，人们也逐渐的发现遗传算法所具有的一些缺陷。由于传统遗传操作的随机性，如选择、交叉与变异都是基于概率的选择的操作10，所以不可避免的会存在概率优化算法的缺点。传统遗传算法会表现出遗传次数增加却依旧得不到较好的优化解集，对于全局的优化搜索能力较弱，而且容易陷入局部极值这一缺点。在传统的遗传算法中如果种群的大小选择不当，对于优化的效果的影响将会非常地明显，种群小将会使优化算法的选择领域受到限制，不能很好地搜索全局的优化解集，影响寻优能力，然而种群过大则会使优化算法的计算复杂度急速的上升。，传统的遗传算法的染色体优化解是一个确定的值，只能代表一个优化函数的优化解，然而，量子遗传算法中的染色体优化解不是一个确定值，一个普通的染色体能表示该优化函数所需要的所有的优化解，因此，量子遗传算法中的染色体对于优化函数的全局优化解集具有更好的代表性，更能充分的描绘优化函数的优化解集，并且，利用旋转门来实现每个染色体解的进化操作，使算法的遗传进化演化操作更加的稳定，算法性能更加优越。量子遗传算法是利用量子计算表示信息的特点，来构成它特有的染色体的形态，使得量子遗传算法的染色体具有更多地优化函数的优化解集的信息。更好的表达了全局函数优化解集的样貌。最后则是再通过量子的概率幅交叉操作来实现种群解的多样性。23量子遗传算法的基本原理231量子比特在传统的遗传算法中，我们使用计算机中的二进制表示方式来表示优化解集的遗传信息。我们将存储遗传信息的二进制称之为比特BIT。而在量子遗传算法中，我们采用|0和|1的单量子比特的叠加态来表示遗传信息11。它们跟传统的信息表达的方式的区别在于它不止止只有两种状态可以选择，而且它们可以是两种基本状态的任意的叠加，所以使用此种的信息表示方式编码组成染色体也是一个不定值，能更好的代表函数的优化解集。在量子遗传算法中的量子位可以是|0到|1中的任意的值，所以一个量子位的状态的表达式可以为211|0|其中量子态的概率幅与是一对平方和1的复数，对优化种群进行一次测量操作，可能会以2的概率大小坍缩到|0状态，或者它会以|2的概率坍缩到|1的状态，|并且它们会满足下面的表达式条件2|2122|在式22中，2表示|0的概率，|2表示|1的概率，量子态坍缩是为了结合适应度值来优选种源，因此，如果一个系统有M个量子位，则该系统可同时描述2M个状态，然而，对于量子态12的每一次观察，该量子位都只会坍缩到一个确定的状态。在这里会得到量子态的确定值，此值的形体都是由量子比特概率的大小所决定的的。产生|0或|1状态的具体过程如下首先，先生成一个在零到一之间的随机数R,如果R2，则坍缩到|0的状态，否则坍缩到|1的状态232染色体表示方法在传统遗传算法中，染色体的表示方式在进化演化计算之前就是确定的（使用确定的二进制表示优化函数的染色体解集），所以在优化解集的表示方面，会存在一些缺陷。然而，在现在的量子遗传算法中，一个基因采用的是量子比特来表示13。该基因可以是“0”态或“1”态，也可以是它们之间的任意叠加态。即每一个基因位不再代表地是某一确定的遗传信息，而是包含该优化函数所需要的所有的优化解集信息，因此，我们对于任意基因位的任一操作都可能会使种群中所有的优化解集信息产生变化。这里将继续使用传统遗传算法中的二进制，对于优化函数的目标解集采用量子比特编码，这样就可以用一个量子比特来表示解集的两个状态，两个量子比特就可以表示四种状态。此种编码方式具有通用性好，且实现简单等优点。量子遗传是使用量子比特来表达一个基因，由若干个基因来组成一个染色体解。这里将会使用一对平方和为1的复数对,来表示染色体中的一个量子比特，则C个J位基因构成的一个染色体可以表示为23|2122112NCJCNNJNJNNIQ式中I是染色体的编号，N是染色体当前进化的代数，C是基因位的个数，第N代第I个个体的染色体用QTJ描述的，J是每个用二进制表示的每个优化解中含有的量子比特数。在刚开始的初始化情况下，都会以21,的形式来初始化种群中的全部染色体解集的所有基因，等概率的叠加是量子遗传算法中染色特初始化的一中特殊情况。如果是在一个以3个量子比特位的染色体中，那么它会具有3对概率幅，如下所示（24）21321则这个系统的状态可以描述为251|2430|310|24|3|0|从上面的系统状态描述可以知道优化函数的染色体解集的状态|000、|001、|010、|011、|100、|101、|110、|111的状态的概率大小分别为3/32，1/32，9/32，3/32，3/32，1/32，9/32，3/32。所以上式（24）描述的三个比特量子系统能同时包含8个状态，如果用传统的表示方法那么至少需要8条的染色体来表示，这就是量子遗传染色体组少，却能拥有丰富种群的关键，并且随着趋近与1或0，染色、体收敛于一个确定的状态。233量子旋转门量子旋转门作为量子遗传算法中进化演化操作的执行机构14，在优化算法中具有重要的地位。所以对于不同的优化函数的优化问题我们要区别的对待，在了解需要优化函数的特性之后才能正确的选择合适的量子旋转门操作15。量子旋转门的功能结构如下所示26COSINSINCIII它的更新过程如下27IIIIIICOSNSN其中，第I个染色体进行旋转门演化操作前后的概率幅由描述；TITI,和为旋转角的大小，其大小由事先定好的调整策略决定，该调整策略是一种通用的。与优I化问题无关的调整策略，如表21表21旋转角度选择表,ISIXIBESTBESTFXFI0II0II00FALSE0000000TRUE0000001FALSE001110101TRUE00111010FALSE00111010TRUE001110111FALSE0000011TRUE00000表中中I来表示当前值是染色体的第几位；中的I表示的是为当前的最优染XIBEST色体的第I位上的表示情况；适应度函数为；为旋转角方向；旋转角的大XF,I小用来描述，它的大小的取值通常是在0005到005之间的某一值，旋转角的大I小可以是某一确定值，也可以根据进化的实际情况来进行动态微调整，同过此类操作能很好的达到函数优化效果的要求。它们的值都是根据表21中所列的选择策略确定的。量子旋转门的运行过程如下所示首先，将通过适应度函数计算出当前的个体的适应XFTJQ度值，然后与当前优化种群最佳的适应度值进行比较，如果当代优化种群个体的BESTF适应度值大于现有的最优优化适应度值,那么就应该调整中相应的量子比XFTJ特位，能够让概率幅的演化方向是朝着向着量子位的，不然，如果F,那么就接受新解为当前解；如果大于0,1区间的随机数，则依旧接受新的解为TXFFEXP当前的解，否则，就会拒绝新的解而保留现在的解。该过程会不断的重复，可以知道，开始的温度比较高，算法接受差解的概率也会比较高，这就让算法有更大的机会跳出局部的最优解，随着退火的进行，温度会逐渐降低，算法接受差解的概率就会变小。324模拟退火算法的基本流程模拟金属冶炼退火操作的主要操作有两个第一个，温度下降的大小值是由固体冷却过程中的热静力学操作来实现确定的，第二个，在每个的温度下进行随机搜索的次数。在实际应用中，退火算法必须有时间的限制，这个需要的条件有第一，一个起始温度；第二，一个控制温度下降的函数；第三，一个决定在每个温度下状态转移参数的标准；第四，一个停止温度；第五，算法停止的条件。模拟退火算法实际上是一种迭代求解的过程，算法反复执行“产生新状态计算目标函数判断是否接受新状态接受/舍弃的”过程，它的基本流程如下1初始化，初始温度T，初始解S，每个T值的迭代次数；2对种群完成第（3）到第（6）；3产生新的解4计算增量,其中ES为目标函数；SE5若，则接受作为新的现在的解，不然以概率接受为新的0/EXPTS当前的解；6如果满足终止条件则输出当前的解作为最优解，结束循环；7T（温度）会逐步的降低，而且T会慢慢的趋近于0，转到步骤（2）。在算法的执行过程中，为了保证算法的收敛能力，要保证退火的初始温度T尽可能的大，一般情况下T取值为100，L表示对于每一个温度取值T进行的遗传进化的演化次数，考虑到运行算法的时间，我们通常取值在1020之间。33改进的量子遗传算法的具体实现模拟退火操作的寻优过程是通过设置初始温度的大小与现实降温过程的速率来实现的，在温度较高时候，算法能够以较高的概率接受比现在不好的优化解，通过此操作能避免算法陷入局部极值，而能较好的接受好的优化解是在温度较低的时候，模拟退火的这种搜索模式增强了算法的搜索能力和效率。量子遗传算法通过使用量子计算中存储信息的方式，充分的描述了优化函数所有的解集，进而大大的提升了优化算法的寻优能力。量子遗传算法是使用量子位来表示遗传的信息，利用量子计算的一些特性，进行染色体的量子编码。实现了比传统的遗传算法更好的效果。将量子遗传能充分的描述优化的解集的特点与退火操作寻找全局最优的能力相结合，我们称这种算法为基于模拟退火的量子遗传算法20，算法中，两种搜索性能相互互补，能使新算法获得质量较高的优化解。331模拟退火算子及参数选取在模拟退火算子中，初始温度越大，退回系数越大（退回系数小于1的正数），收敛到全局最优解的概率就越大，收敛的时间也就会越长。所以进行参数选择的同时要考虑搜索的效率与求解的质量。在执行完模拟退火操作后，需要把每个染色体个体的量子位信息反应到量子编码上，以便进行量子遗传算法的操作。在算法的运行过程中退火的温度系数一般取为095。332基于模拟退火的量子遗传算法具体实现引入模拟退火思想后的量子遗传算法，在每一次迭代进化的时候引入模拟退火算法，来确定每个个体的进化方向。基于模拟退火操作的量子遗传算法具体步骤如下1随机生成种群并进行初始化；2对种群进行测量得到一组确定的状态；3记录最佳适应度值和对应的个体将其作为下一步种群进化的目标；4查看优化算法是否可以停止，若满足结束条件则退出，否则继续进行计算；5模拟退火操作；6当温度过高时，是算法以一定的概率让量子旋转门不朝着种群目标值的进化方向进化，当温度较低时，是算法接受目标值的进化方向，利用量子旋转门对种群进行更新，然后按照全局交叉的策略对种群进行量子交叉操作，得到子代QT17记录最优个体和对应的适应度值；8将迭代的次数加1，返回步骤4；333基于模拟退火的量子遗传算法流程图对应的流程图如图31迭代数加1开始结束随机生成种群并进行初始化记录最佳适应度值和对应的个体作为下一步种群更新的目标值满足终止条件模拟退火算法根据模拟退火算法的返回值确定种群进化的方向，利用量子旋转门更新种群进行全局交叉，改变种群形态，得到Q（T1）记录最优个体和对应的适应度值NY图31基于模拟退火算法的量子遗传算法流程图引入模拟退火思想后的新量子遗传算法，对个体的进化方向进行模拟退火的操作，然后将整个迭代过程中的最优解保留作为下一次进化迭代的目标值。34改进的量子遗传算法的优点将改进好的量子遗传算法跟传统的量子遗传算法进行性能的比较，可以发现它具有以下几方面的优点1加入量子交叉操作。在这个函数的优化过程中，为量子遗传算法添加了“全干扰的交叉”量子遗传交叉方式。在使用这种递归的量子交叉后，算法中的染色体的量子位的信息可以得到充分地交流，使得解集种群更加的多样化。通过此操作可以很好的克服算法的“早熟收敛”。该操作的原理是借用量子计算中的相干性，较好的克服了染色体进化过程中易陷入局部最优的缺陷。2加入模拟退火思想。在现有的量子遗传算法中，添加了模拟退火算子，其新染色体状态的产生依靠现有的温度的大小来决定是否接受恶化解的能力大小，该操作使进化算法从局部最优的局限中脱离出来，继续进行遗传进化，搜索于全局，然后逐步趋近于最优的解。加入了“全干扰交叉”的量子交叉方式与模拟退火思想的之后量子遗传算法能够对于一些多峰函数的优化问题，体现出很好的优越性，就算量子遗传算法早期演化时产生的个体优化解的差异性比较大，该算法也能够很好地收敛到全局的最优解或近似全局最优解。就算是使用轮盘赌方式选择优化函数的染色体解集，对优化算法的影响也不会太大。4算法性能测试及分析为了检验上面改进好的量子遗传算法的可行性与有效性，我们将会改进好的算法对5个典型的函数进行算法优化性能的验证，通过与传统的量子遗传算法在运行时间、收敛效率、优化性能等方面的比较。41典型测试函数411简单平方和函数3,1,21221XXXF图41简单平方和函数此函数具有多个局部的最小值，但只有一个全局的最小值。10,1F412RASTRIGRIN函数3,2COSS1020,2112112XXXXF图42RASTRIGRIN多极值函数此函数具有多个局部的最小值，但只有一个全局的最小值。0,2F413DEJONG函数F20482,0482110,12223XXXXF图43DEJONG函数F2DEJONG函数F2是一个变态函数，很难寻找全局最小值，它具有全局最小值。01,3F414GOLDSTENPRICE函数2,7364812382304191,12211214XXXXXXF图44GOLDSTRENPRICE函数这个函数在其定义域内只有一个极小值点。31,04F415SIXHUMPCAMELBACK函数2343124,2245YXYXYXYXF图45SIXHUMPCAMELBACK函数SIXHUMPCAMELBACK函数共有多个相似极小值点，很难准确地取得最小值点，其中00898，07126和00898，07126为全局最小点，最小值为。031628720,8971260,8955FF42算法参数设定1普通量子遗传算法的参数设定将每个初始种群规模的大小都设置为40，最大的遗传代数设为200，函数的每一个变量的二进制长度设为20。2含量子交叉的量子遗传算法的参数设定将每个初始种群规模的大小都设置为40，最大的遗传代数设为200，函数的每一个变量的二进制长度设为20。量子交叉采用的是量子全干扰交叉算法。3含退火思想的量子遗传算法参数设定将每个初始种群规模的大小都设置为40，最大的遗传代数设为200，函数的每一个变量的二进制长度设为20，初始的温度设置为100度。退火系数设置为094含量子交叉和退火思想的量子遗传算法参数设定将每个初始种群规模的大小都设置为40，最大的遗传代数设为200，函数的每一个变量的二进制长度设为20，初始的温度设置为100度。退火系数设置为09并且采用量子全干扰交叉操作。43测试结果即分析对于每个测试的函数，普通量子遗传算法、含量子交叉的量子遗传算法、含退火思想的量子遗传算法、含量子交叉和退火思想的量子遗传算法他们各自独立的运行20次，他们的最优搜索值与搜索平均值的统计结果如下表41所示。表41仿真实验数据统计表优化函数优化算法最优搜索值平均搜索值迭代次数理论最优值QGA1000210012401CQGA1001210017501SQGA1000110005971简单平方和函数SCQGA10000100091251QGA0005200501710CQGA0001900180780SQGA0006600147920RASTRIGRIN函数SCQGA0003000147980QGA0003602472120CQGA000670068070SQGA0002800088160DEJONG函数F2SCQGA0000400052180QGA3093940303443CQGA3054238750173SQGA350733645343GOLDSTENPRICE函数SCQGA30143352563QGA10315103111191031628CQGA1031610310711031628SQGA1031510300861031628SIXHUMPCAMELBACK函数SCQGA10315103141041031628对于上面的5个优化性能测试函数，它们都采用了二进制的编码，染色体的长度设置为20，分别用普通量子遗传、含量子交叉的量子遗传、含退火思想的量子遗传算法和含量子交叉与退火思想的量子遗传的四种算法进行20次的函数优化寻优，种群的规模设置为40，最大的迭代的次数为200，采用全局量子交叉，模拟退火的初始温度设置为100度，退火系数设置为09。1对于第一个简单平方和测试函数的算法性能比较图图46简单平方和函数量子遗传进化过程由上面图46可以得知，对于简单的平方函数在种群的大小与迭代的次数一样的情况下，普通的量子遗传算法的寻优迭代次数是最短的，但是它寻优能力都不如其它的三种优化算法的能力，由图中得知，基于量子交叉与退火操作的量子遗传算法是寻优能力最强的取得了全局的最小值1，相比其他的优化函数最优值都只有取到10012与10001，由此可以说明含退火算法与量子交叉操作的量子遗传算法对于简单的函数有化具有更好的性能，但我们也从中看出，相比于其它的优化操作，它进行的迭代时间是最长的。2RASTRIGRIN测试函数的算法性能比较图图47RASTRIGRIN函数量子遗传进化过程由上面图47可以得知，对于多峰值的优化函数在种群的大小与迭代的次数一样的情况下，加入量子交叉操作的量子遗传算法的寻优性能是最好的，其它的优化算法在一般的情况下，都不如它的优化能，虽然在一些算法中加入了退火操作以此来使染色体种群的具有更好的多样性，但似乎没有达到预期的目标，原因可能是，多个峰值间隔太近，导致算法一直在实行退火操作，在冷却是算法并没有很好的跳出局部最优这一陷阱，导致了算法性能的降低。3DEJONG函数F2的测试函数的算法性能比较图图48DEJONG函数F2量子遗传进化过程由上面图48可以得知，对于一些病态的函数优化能力，采用了量子交叉与退火操作的量子遗传算法的性能是最优的，可以将全局的最小值搜索到0002，相比其它的优化算法只能搜索到03,015与036。它的性能是远远的优于其它的优化算法。由此，可以得出含有退火思想与量子交叉操作的量子遗传算法对于病态的函数寻优具有更好的性能。4GOLDSTRENPRICE测试函数的算法性能比较图图49GOLDSTRENPRICE函数量子遗传进化过程由上面图49可以得知，对于一些连续的多元的函数的优化能力，采用了量子交叉与退火操作的量子遗传算法的性能是最优的，可以将全局的最小值搜索到3014，与其它的优化算法相比较它搜索到的最优值是52,35与47。它的性能是远远的优于其它的优化算法。由此，可以得出含有退火思想与量子交叉操作的量子遗传算法对于一些连续的多元的函数寻优具有更好的性能。5GOLDSTRENPRICE测试函数的算法性能比较图图410SIXHUMPCAMELBACK函数量子遗传进化过程由上面图410可以得知，对于一些含有多个极值点的函数的优化能力，采用了量子交叉与退火操作的量子遗传算法的性能是最优的，可以将全局的最小值搜索到10315，其它的优化算法只能搜索到的最优值是10307与10309。可以从数据判断得知，它的性能是远远的优于其它的优化算法。由此，可以得出含有退火思想与量子交叉操作的量子遗传算法对于一些含有多个极值点的函数的寻优具有更好的性能。从上面的仿真实验可以了解到，含量子交叉与退火思想的量子遗传算法在求最优解的时，发现首次最优解的能力是最强的，相比其它的算法它的性能有了很大的提高。含量子交叉与退火思想的量子遗传算法能够在早起发现最优解，并且在早期与其他的量子算法相比较，它的种群更加地具有多样性，它同过量子交叉操作与退火操作使其种群的种类更加的多样，使其能更加完整、全面的表达种群的样貌，通过此种群搜索所有的染色体，获得最佳适应度值也就更加地能代表该算法的最优值的大小。因此，从最优解的收敛概率上来看，含量子交叉与退火思想的量子遗传是在这些算法中性能最好的。但是，含量子交叉与退火思想的量子遗传算法在搜索最优的上花费的时间也比其他的量子遗传算法要多得多。这是由于我们在该算法中添加了适用于全局的量子全干扰交叉的量子交叉与退火操作。这些操作增加了算法的复杂度，影响了算法的搜索能力。对于全干扰的量子递归交叉操作，该操作让种群中所有的染色体的基因位进行一次循环对调操作，以此来打乱原有染色体解集的样貌，使其能更好的描述优化函数全局解集的样貌。退火操作不仅使该算法能在子代的产生过程中接受适应度值高的个体，它还以一定的概率接受适应度值较差的个体，因此增加了该算法的搜索范围，虽然在优化算法中引入这些操作会在一定的程度上增加算法寻优的运行的时间，但它却有效的避免了算法的“早熟收敛”这一问题。根据这些我们可以得出含量子交叉与退火思想的量子遗传算法是一种寻优能力较好的搜索算法。以此算法我们能很好的得到连续的多峰函数的最优值。5总结与展望量子遗传算法是将量子计算中信息存储的优点与传统遗传算法具有的通用性相结合，从而提升了优化算法的寻优能力。本文通过在原有的量子遗传中添加全干扰的量子交叉与退火操作，从而提升了原有量子遗传算法的搜索寻优能力，通过在算法中添加交叉与退火操作，使算法在多元连续的多峰函数中，具有更好的适应性，能有效的避免陷入传统算法易陷入的“早熟收敛”这一问题。51论文总结本文的研究内容主要包括以下几个方面1对于传统的遗传算法与量子遗传算法进行简单的学习，包括对于量子比特的特点与概率幅的叠加态的表现形式，量子旋转门的性质与功能，并且简单的介绍了量子旋转的策略选择。2通过对于量子遗传算法的研究发现，基本的量子遗传算法还具有较多的问题，有许多可以改进的方面。对最近几年改进过的量子遗传算法进行研究与总结，并且提出了一种新的优化进化算法，通过仿真数据的仿真实验证明，经过改进的量子遗传算法具有更好的优化寻优能力，能够在多元的连续多峰函数中搜索到较好的最优值。3对于量子遗传的改进研究主要时集中在现有的理论基础之上，其思想就是充分的表达种群的样貌，使种群能更好的代表函数的优化解。因此，在该算法中添加了量子全干扰的交叉与退火操作，将退火操作引入量子遗传算法，使其在子代中能以一定的概率接受父代中适应度较差的个体，有效地抑制了子代种群容易陷入局部最优的确点，并且以退火温度T来控制算法的选择压力，有效地保证了算法在后期的全局收敛性。这些操作可以有效的使染色体之间的信息交互。使染色体更具有多样性。这一性能在随后的仿真实验中充分得到了证明。4是用5个经典的优化函数测试改进后的量子遗传算法的性能，并且有效证明了改进的优化算法的优越性能。52展望文中的改进量子遗传算法基于全干扰与退火操作的量子遗传算法，在多元连续的多峰函数中取得了一定的成果，弥补了传统量子遗传方面的一些缺点，但它依然存在着一些不完善的地方，需要在今后的学习与研究中继续地努力改进。1基于量子交叉与退火操作的量子遗传算法在搜索的速度上有待改进，需要一种既能很好的搜索全局，又不会影响函数运行的时间的搜索策略。2在量子遗传算法中的演化操作过程，需要使用到量子旋转门进行演化操作，在确定基因位时，需要进行大量的计算操作，非常消耗寻优的运行时间，影响了优化算法的寻优性能，所以需要我们姨现有的量子旋转门进行改进，以此来提高算法寻优的速度。3可以在后续的改进算法中，实行顺序与逆序染色体分别作为一个初始化个体，这样，对个体的量子位进行测量一次就能得到两条染色体，大大加快了初始化的速度4可以在以后的算法中加入精英库与干扰库，精英库在进化的早起大大提高了种群的搜索速度，干扰库可以在进化的一定情况下，对种群进行人为的干扰，使其避免算法的早熟收敛18。5在以后的改进算法中，把量子旋转门的旋转角能根据不同的情况而改变，这样对于适应度值高的个体，就能更好的进入到下一代的计算中，而对于适应度值低的个体就会尽快的淘汰。算法自适应的旋转角，既能保证群体解集的多样性，也维护算法的收敛性。参考文献1HOLLANDJHGENETICALGORITHMSANDCLASSIFIERSYSTEMSFOUNDATIONSANDTHEIRAPPLICATIONC/PROCEEDINGSOFTHESECONDINTERNATIONALCONFERENCEONGENETICALGORITHMSHILLSDALE,NJLAWRENCEERLBAUMASSOCIATES,198782892KALKACGROVERSQUANTUMSEARCHINGALGORITHMISOPT