《毕业设计--基于量子遗传算法的函数寻优算法设计.doc》由会员分享，可在线阅读，更多相关《毕业设计--基于量子遗传算法的函数寻优算法设计.doc（33页珍藏版）》请在金锄头文库上搜索。
1、 毕 业 论 文（设计）题 目： 基于量子遗传算法的函数寻优算法设计学 院： 数理与信息学院 学生姓名： 专 业： 计算机科学与技术 班 级： 指导教师： 起止日期： 2014年11月16日至2015年6月12日2015 年 5 月 13日 28基于量子遗传算法的函数寻优算法设计 摘 要量子遗传算法(QGA)是20世纪90年代后期兴起的一种崭新的遗传进化算法。该算法主要是将量子计算的概念引入其中，将量子的态矢量表达引入了遗传编码，使一条染色体可以表达多个信息态的叠加，同时利用量子旋转门实现染色体的演化，实现了目标解的进化。相比传统遗传算法，量子遗传算法能够在较小的种群规模下，快速的收敛到全局最
2、优解。本文首先介绍了量子遗传算法的基本原理与算法结构，然后对量子遗传算法提出疑问。虽然量子遗传算法的优化性能大大优于传统遗传算法，但是，对于一些多峰函数的优化问题，该类算法依旧容易陷入“局部最优”。在实际的应用中有很多优化问题都是多变量的连续优化问题，现有的量子遗传算法不能有效的解决这些问题。针对量子遗传算法容易陷入局部最优和未成熟收敛的缺陷，我们提出了一种新的优化算法含有退火操作的量子遗传算法，该优化算法能够以可变的概率选择性地接受恶化的优化函数解，使种群解集的进化方向改变，不在依靠当前解进行遗传演化。从而使算法不易“早熟收敛”。而且在该算法中加入了全干扰的量子交叉操作，使各染色体能进行遗传
3、信息的交换，使种群染色体更具有代表性。最后根据改进后的方案，对改进的量子遗传算法进行了数值仿真。有效地证明了改进算法在函数寻优方面的优越性。【关键词】量子遗传算法，量子编码，退火思想，量子交叉，函数寻优Discovery of Function Extreme Value Based on Quantum Genetic Algorithm AbstractQuantum genetic algorithm (QGA) was originated in the late 1990s as a new genetic evolution algorithm, which introduces
4、the concept of quantum computation into genetic algorithm, i.e., introducing quantum state vector expression of the genetic code so that a chromosome can express the superposition of multiple kinds of information. Moreover, the evolution of the chromosome by using quantum revolving door, realize the
5、 goal of evolution. Compared with the traditional genetic algorithm, The quantum genetic algorithm cans rapidly convergence to the global optimal solution under the smaller population size.This paper first introduces the basic principle of quantum genetic algorithm and algorithm structure. And then
6、the defects existing in the current quantum genetic algorithm is proposed. Although quantum genetic algorithm to optimize performance greatly superior to the traditional genetic algorithm. Especially for multimodal function optimization problems, QGA also has the tendency to fall into local optimum.
7、 As for many multivariate continuous optimization problems in actual application, the existing QGA can not solve these problems effectively. Since QGA may be trapped in local optimum and the defect of premature convergence, we proposed a new algorithm, Quantum Genetic Algorithm with Annealing Operat
8、ion (QGAAO). The algorithm can selectively accept deteriorating at a certain probability so that population has more chance to jump out the local optimal to avoid premature convergence. Moreover, global disturb has been added to the algorithm of the quantum crossover operation, it can make chromosom
9、es exchange more genetic information. It can better represent the chromosome population. Finally, according to the improved scheme, the improved quantum genetic algorithm was committed for the numerical simulation. The test proved that the improved algorithm effectively superiority in terms of funct
10、ion optimization. 【Keywords】quantum genetic algorithm, quantum coding, annealing thought, quantum crossover, function optimization 目录摘 要IABSTRACTII1.绪论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量子遗传算
11、法的步骤流程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.3De Jong函数F2174.1.4
12、Goldsten-Price函数174.1.5Six-hump Camel Back函数184.2算法参数设定184.3测试结果即分析195总结与展望245.1 论文总结245.2 展望24参考文献26 1.绪论1.1遗传算法在20世纪70年代美国密西根大学教授J.Holland第一个提出了基于概率的优化算法遗传算法1（GA）。遗传算法的原理跟自然界的遗传进化演化原因是一致的。遗传算法根据优化函数的目标函数来进行全局自适应的概率搜索2，寻找优化函数的最优值。由于遗传算法可以不依靠优化函数的形式与不受外界因素的影响，所以，遗传算法在实际优化应用中得到了良好的应用。因为遗传算法具有良好的适用性、全
13、局性、并行高效的优化性能与鲁棒性3，所以它具有诱人的吸引力，吸引人们前去研究。对于现实中的应用，它对外界的要求不严格，能够广泛的应用，所以它具有很好的应用前景。但是，如果在遗传算法中的选择、交叉和变异的操作方式选取不当，那么算法在迭代次数、收敛速度、优化性能等方面都会轻易地受到影响，并且，这都会使优化函陷入局部极值的这一陷阱。1.2量子计算量子计算4（QC）的概念是在二十世纪七十年代提出来的。那时的主要研究内容是计算三个特性之间相互的关系。P.Benioff与八十年代率先提出了量子计算可以用来进行仿真数据的计算5。在1994年，美国的Shor教授第一次将量子计算运用到了大数的因子分解中，从那时
14、开始，量子计算的研究方向有了充分的拓宽6。量子计算有新的研究动力。使用量子态4作为计算中的基本的信息的存储单位，是量子计算的一大特色。使用量子态具有的叠加、纠缠和干涉等特点可以很好的解决一些常见的经典问题。通常信息是用一种物质或存在的状态来表示的。计算机最早是使用纸带的穿孔方式来表示二进制的，但随着科学技术的发展，到后来计算机开始使用晶体管的开关状态来表示二进制的信息。现在随着量子力学的发展，其揭示了微观粒子的运动状态。开始使用原子的运动状态来表示二进制。量子计算就是利用原子中电子的两种自旋状态来表示信息的7。量子计算要想实现其真正意义上的并行计算就必须在量子计算机上面，但是我们可以将量子计算
15、机制和量子信息运用到智能算法中，或者是将已有的优化算法和量子算法相结合，使算法的优化性能得到提高，使它具有传统优化算法所不具有的优异性能。1.3函数优化函数优化问题是量子遗传算法的经典应用领域19，也是对量子遗传算法进行性能评价的常用算法.对于一些不规则或者是多变的与多值的函数的优化问题，使用其它方法去优化解决它们，是比较麻烦的，但是如果我们使用量子遗传算法就可能很好的解决这些问题，轻易地得到较好的优化结果。函数优化8问题简单讲就是求取一个函数中的最小值或者是最大值。函数的优化问题通常的描述是：设S是上的有界的子集，：S-R是n维的实值函数。如果在领域内能找到一个点的值小于该领域内其它所有点的值，那么我们就称该点是该函数在领域内的最小值所在的点。通常，此点就是我要求的最优值的点。函数优化问题通常是一个非常复杂的优化问题，特别是对于那些不可微的或者多极值的函数优化，常常是不能很好的求到有效解的。但是，对于新
