基于量子遗传算法的函数寻优算法设计[文献综述1]

毕业论文（设计）文献综述题目基于量子遗传算法的函数寻优算法设计学院数理与信息学院学生姓名专业计算机科学与技术班级A11计算机指导教师起止日期2014年11月28日至2015年1月16日2015年1月15日文献综述一、前言量子遗传算法（QUANTUMGENETICALGORITHM，QGA）1是量子计算（QUANTUMCOMPUTING，QC）2与遗传算法GENETICALGORITHM，GA3相结合的产物。量子计算中采用量子态4作为基本的信息单元，利用量子态的叠加、纠缠和干涉等特性，可以解决经典计算中的NP问题。如1994年SHOR提出第一个量子算法，求解大数质因子分解的经典计算难题，该算法可用于公开秘钥系统RSA5；1996年CROVER提出随机数据库搜索的量子算法，在量子计算机上可实现对未加整理的数据库量级的加速搜索6。N遗传算法是处理复杂优化问题的一种方法，其基本思想是模拟生物进化的优胜劣汰规则与染色体的交换机制，通过选择、交叉、变异三种基本操作寻找最优个体。二、遗传算法概述遗传算法通过模仿生物的选择、交叉、变异操作，并遵循优胜劣汰的准则及个体染色体的互相交叉这些特点处理问题的一种方法。遗传算法通过目标函数进行全局自适应的概率搜索操作7，可以解决传统算法不能解决的难题，它与优化规则、问题的特性没有任何关系。由于它有着较好的适用性和鲁棒特性8，因此它具有诱人的研究和应用前景。然而，若遗传算法中的选择、交叉及变异的操作方式选取不当，那么算法将会在迭代次数、收敛速度方面受到影响，且容易产生局部极值的现象。三、量子遗传算法概述量子遗传算法就是基于量子计算原理9,10的一种遗传算法，将量子的态矢量表达引入了遗传编码11，利用量子逻辑门12实现染色体的演化，实现了比常规遗传算法更好的效果。量子遗传算法建立在量子的态矢量表示的基础之上，将量子比特的概率幅13表示应用于染色体的编码，使得一条染色体可以表达多个态的叠加，并利用量子逻辑门实现染色体的更新操作，具有种群规模小而不影响算法性能、同时兼有“勘探”和“开采”的能力、收敛速度快和全局寻优能力强的特点13。此算法已在多种优化问题中有所应用14四、量子比特编码相关概述在量子遗传算法中使用的编码方式是基于量子比特的编码。最小信息单儿元一个量子位一一量子比特。一个量子比特的状态可以取0或1，其状态可以表示为|0|1,式中，为代表相应状态出现概率的两个复数（|2|21）；|2，|2分别为量子比特处于状态0和状态1的概率。所以量子位可以同时包含|0和|1两种状态的信息，一般地，用N个量子位就可以同时表示2N个状态15五、量子门更新相关概述在量子计算中，通过对量子位状态进行一系列的酉变换来实现某些逻辑变换功能。因此，在一定时间间隔内实现逻辑变换的量子装置，称其为量子门。量子们是在物理上实现量子计算的基础。量子门的更新操作是优化过程中最重要的单元，传统量子遗传算法基本包含量子旋转门更新。其旋转的大小、方向根据事先设计的调整策略而确定16。六、量子交叉概述量子遗传算法中最能体现个体结构信息的是其进化目标，即个体当前最优确定解以及对应的适应度值。因此，考虑互换个体进化目标以实现个体间信息的交换，从而实现量子交叉的目的。其基本操作就是在个体之间暂时交换最优确定解和最优适应度值，个体接受交叉操作后，它的进化方向将受到其他个体的影响，从而获取新的进化信息。七、退火算法概述模拟退火（SIMULATEDANNEALING,SA）算法的思想最早是由METROPOLIS等提出的。其出发是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性。模拟退火法是一种通用的优化算法，其物理退火过程由以下三部分组成（1）加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高的时候，固体将融为液体，从而消除系统原先存在的非均匀状态。（2）等温过程。对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由减少的方向进行的，当自由能减少到最小时，系统达到平衡状态。（3）冷却过程。使粒子热运动减弱，系统能量下降，得到晶体结构。其中，加温过程对应算法的设定初温，等温过程对应算法的METROPOLIS抽样过程，冷却过程对应控制参数的下降，这里能量的变化就是目标函数，要得到的最优解就是能量最低态。METROPOLIS准则是SA算法收敛于全局最优解关键所在，METROPOLIS准则以一定的概率接受恶化解，这样就使得算法跳离局部最优的陷阱。八、函数优化相关概述函数优化问题是量子遗传算法的经典应用领域，也是对量子遗传算法进行性能评价的常用算法对于一些非线性、多模型、多目标的函数优化问题，用其他方法较难求解，而用量子遗传算法却可以方便地得到较好的结果。函数优化17问题是指对象在一定区间的连续变量，通常可描述为设S为RN上的有界子集，SR为N维实值函数。函数F在域上全局最小化，就是寻找点使得在SSXMINMINXF域上全局最小，即。MINXFFSX函数优化问题是一个复杂的优化问题，特别是不可微或者多峰的函数，往往不能有效地求解。而遗传算法作为一种高度并行、随机、自适应的全局优化概率搜索算法，它将每个可能的问题表示为“染色体”，从而得到一个由染色体组成的“群体，然后按遗传学规律进行选择、交叉、变异操作，直到满足终止条件为止。九、总结量子遗传算法在许多应用领域发挥着重要作用，量子遗传算法与遗传算法一样，都是一种基于生物和进化机制的适合复杂系统优化计算的自适应概率优化18技术相比于经典遗传算法具有种群规模小、收敛速度夸、全局搜索能力强的优点。目前的量子遗传算法主要存在如下问题首先，通过测量量子位的状态获得二进制解，这是个概率操作过程，具有很大的随机性和盲目性，因此在种群进化的同时，部分个体将不可避免地产生退化；其次，二进制编码对于连续优化，由于频繁解码操作加大了计算量，严重降低了优化效率；第三，对于量子旋转门的转角方向、大小，一视同仁，没有考虑染色体之间的差异。因此，应加注重量子遗传的种群大小的选择，进化策略19的设计与实施。如何让量子遗传算法更好的发挥性能，未来还需要做进一步研究参考文献1HANKHGENETICQUANTUMALGORITHMANDITSAPPLICATIONTOCOMBINATORIALOPTIMIZATIONPROBLEMINIEEEPROCOFTHE2000CONGRESSONEVOLUTIONARYCOMPUTATIONSANDIEGOUSAIEEEPRESSJULY2000135413602MELANIEMITCHELLANINTRODUCTIONTOGENETICALGORITHMSCAMBRIDGE,MATHEMITPRESS,19963HOLLANDJHGENETICALGORITHMSANDCLASSIFIERSYSTEMSFOUNDATIONSANDTHEIRAPPLICATIONC/PROCEEDINGSOFTHESECONDINTERNATIONALCONFERENCEONGENETICALGORITHMSHILLSDALE,NJLAWRENCEERLBAUMASSOCIATES,198782894BENNETTCH,DIVINCENZODYQUANTUMINFORMATIONANDCOMPUTATIONNATURE,2000404247一2555SHORPWALGORITHMSFORQUANTUMCOMPUTATIONDISCRETELOGARITHMSANDFACTORINGINGOLDWASSERS,EDPROCOFTHE35THANNUALSYMPOSIUMONTHEFOUNDATIONOFCOMPUTERSCIENCES,LOSALAMITOSIEEECOMPUTERSOCIETYPRESS199420一226GROVERLKAFASTQUANTUMMECHANICALALGORITHMFORDATABASESEARCHINPROC28THANNUALACMSYMPOSIUMONTHETHEORYOFCOMPUTINGPHILADELPHIA,PENNSYLVANIA,ACMPRESS1996，212一22I7ZALKACGROVERSQUANTUMSEARCHINGALGORITHMISOPTIMALJPHYSICALREUIEWA,1999,60274627518JENESTABLEORROBUSTWHATSTHEDIFFERENCEJCOMPLEXITY,2003,8312189TONYHQUANTUMCOMPUTINGANINTRODUCTIONJCOMPUTINGCONTROLENGINEERINGJOURNAL,1996,10310511210NARAYANANAANINTRODUCTORYTUTORIALTOQUANTUMCOMPUTINGAPROCOFIEECOLLOQUIUMONQUANTUMCOMPUTINGTHEORY,APPLICATIONSANDIMPLICATIONSCLONDONIEEPRESS,19971/11/311MICHALEWICZZ,JANIKOWC,ANDKJRAWCZYK,JAMODIFIEDGENETICALGORITHMFOROPTIMALCONTROLPROBLEMSCOMPUTERSANDMATHEMATICALAPPLIANCATIONS,1992,2312839412DEUTSCHDQUANTUMCOMPUTATIONALNETWORKSPROCROYSOCLONDONA,1989,425739013HANKUKHYUNANDKIMJONGHWANQUANTUMINSPIREDEVOLUTIONARYALGORITHMFORACLASSOFCOMBINATORIALOPTIMIZATIONIEEETRANSACTIONSONEVOLUTIONARYCOMPUTATION，IEEEPRESS,2002,6658059314HANKUKHVUNANDKIMJONGHWANQUANTUM一INSPIREDEVOLUTIONARYALGORITHMSWITHANEWTERMINATIONCRITERION,GATE,ANDTWOPHASESCHEMETRANSACTIONSONEVOLUTIONARYCOMPUTATION,2004,8215616915NIELSENMA,CHUANGIL量子计算与量子信息一量子计算部分M