文献综述--基于量子遗传算法的函数寻优算法设计.doc

毕业论文（设计）文献综述题目：基于量子遗传算法的函数寻优算法设计学院：数理与信息学院学生姓名：专业：计算机科学与技术班级：指导教师：起止日期：2014年11月28日至2015年1月16日2015年1月15日文献综述一、前言量子遗传算法（QuantumGeneticAlgorithm，QGA）[1]是量子计算（QuantumComputing，QC）[2]与遗传算法(GeneticAlgorithm，GA)[3]相结合的产物。量子计算中采用量子态[4]作为基本的信息单元，利用量子态的叠加、纠缠和干涉等特性，可以解决经典计算中的NP问题。如1994年Shor提出第一个量子算法，求解大数质因子分解的经典计算难题，该算法可用于公开秘钥系统RSA[5]；1996年Crover提出随机数据库搜索的量子算法，在量子计算机上可实现对未加整理的数据库量级的加速搜索[6]。遗传算法是处理复杂优化问题的一种方法，其基本思想是模拟生物进化的优胜劣汰规则与染色体的交换机制，通过选择、交叉、变异三种基本操作寻找最优个体。二、遗传算法概述遗传算法通过模仿生物的选择、交叉、变异操作，并遵循优胜劣汰的准则及个体染色体的互相交叉这些特点处理问题的一种方法。遗传算法通过目标函数进行全局自适应的概率搜索操作[7]，可以解决传统算法不能解决的难题，它与优化规则、问题的特性没有任何关系。由于它有着较好的适用性和鲁棒特性[8]，因此它具有诱人的研究和应用前景。然而，若遗传算法中的选择、交叉及变异的操作方式选取不当，那么算法将会在迭代次数、收敛速度方面受到影响，且容易产生局部极值的现象。三、量子遗传算法概述量子遗传算法就是基于量子计算原理[9,10]的一种遗传算法，将量子的态矢量表达引入了遗传编码[11]，利用量子逻辑门[12]实现染色体的演化，实现了比常规遗传算法更好的效果。量子遗传算法建立在量子的态矢量表示的基础之上，将量子比特的概率幅[13]表示应用于染色体的编码，使得一条染色体可以表达多个态的叠加，并利用量子逻辑门实现染色体的更新操作，具有种群规模小而不影响算法性能、同时兼有“勘探”和“开采”的能力、收敛速度快和全局寻优能力强的特点[13]。此算法已在多种优化问题中有所应用[14]四、量子比特编码相关概述在量子遗传算法中使用的编码方式是基于量子比特的编码。最小信息单儿元一个量子位一一量子比特。一个量子比特的状态可以取0或1，其状态可以表示为|Ψ>=α|0>+β|1>,式中：α，β为代表相应状态出现概率的两个复数（|α|2+|β|2=1）；|α|2，|β|2分别为量子比特处于状态0和状态1的概率。所以量子位可以同时包含|0>和|1>两种状态的信息，一般地，用n个量子位就可以同时表示2n个状态[15]五、量子门更新相关概述在量子计算中，通过对量子位状态进行一系列的酉变换来实现某些逻辑变换功能。因此，在一定时间间隔内实现逻辑变换的量子装置，称其为量子门。量子们是在物理上实现量子计算的基础。量子门的更新操作是优化过程中最重要的单元，传统量子遗传算法基本包含量子旋转门更新。其旋转的大小、方向根据事先设计的调整策略而确定[16]。六、量子交叉概述量子遗传算法中最能体现个体结构信息的是其进化目标，即个体当前最优确定解以及对应的适应度值。因此，考虑互换个体进化目标以实现个体间信息的交换，从而实现量子交叉的目的。其基本操作就是在个体之间暂时交换最优确定解和最优适应度值，个体接受交叉操作后，它的进化方向将受到其他个体的影响，从而获取新的进化信息。七、退火算法概述模拟退火（simulatedannealing,SA）算法的思想最早是由Metropolis等提出的。其出发是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性。模拟退火法是一种通用的优化算法，其物理退火过程由以下三部分组成：（1）加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高的时候，固体将融为液体，从而消除系统原先存在的非均匀状态。（2）等温过程。对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由减少的方向进行的，当自由能减少到最小时，系统达到平衡状态。（3）冷却过程。使粒子热运动减弱，系统能量下降，得到晶体结构。其中，加温过程对应算法的设定初温，等温过程对应算法的Metropolis抽样过程，冷却过程对应控制参数的下降，这里能量的变化就是目标函数，要得到的最优解就是能量最低态。Metropolis准则是SA算法收敛于全局最优解关键所在，Metropolis准则以一定的概率接受恶化解，这样就使得算法跳离局部最优的陷阱。八、函数优化相关概述函数优化问题是量子遗传算法的经典应用领域，也是对量子遗传算法进行性能评价的常用算法.对于一些非线性、多模型、多目标的函数优化问题，用其他方法