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

毕业论文（设计）文献综述

题 目： 基于量子遗传算法的函数寻优算法设计
学 院： 数理与信息学院
学生姓名：
专 业： 计算机科学与技术
班 级：
指导教师：
起止日期： 2014年11月28日至2015年1月16日

2015年 1月 15 日
文献综述
一、前言
量子遗传算法（Quantum Genetic Algorithm，QGA）[1]是量子计算（Quantum Computing，QC）[2]与遗传算法(Genetic Algorithm，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]。
六、量子交叉概述
量子遗传算法中最能体现个体结构信息的是其进化目标，即个体当前最优确定解以及对应的适应度值。因此，考虑互换个体进化目标以实现个体间信息的交换，从而实现量子交叉的目的。其基本操作就是在个体之间暂时交换最优确定解和最优适应度值，个体接受交叉操作后，它的进化方向将受到其他个体的影响，从而获取新的进化信息。
七、退火算法概述
模拟退火（simulated annealing ,SA）算法的思想最早是由Metropolis等提出的。其出发是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性。模拟退火法是一种通用的优化算法，其物理退火过程由以下三部分组成：
（1）加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高的时候，固体将融为液体，从而消除系统原先存在的非均匀状态。
（2）等温过程。对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由减少的方向进行的，当自由能减少到最小时，系统达到平衡状态。
（3）冷却过程。使粒子热运动减弱，系统能量下降，得到晶体结构。
其中，加温过程对应算法的设定初温，等温过程对应算法的Metropolis抽样过程，冷却过程对应控制参数的下降，这里能量的变化就是目标函数，要得到的最优解就是能量最低态。Metropolis准则是SA算法收敛于全局最优解关键所在，Metropolis准则以一定的概率接受恶化解，这样就使得算法跳离局部最优的陷阱。
八、函数优化相关概述
函数优化问题是量子遗传算法的经典应用领域，也是对量子遗传算法进行性能评价的常用算法.对于一些非线性、多模型、多目标的函数优化问题，用其他方法较难求解，而用量子遗传算法却可以方便地得到较好的结果。
函数优化[17]问题是指对象在一定区间的连续变量，通常可描述为：设S为Rn上的有界子集，：S->R为n维实值函数。函数f在域上全局最小化，就是寻找点使得在S域上全局最小，即。
函数优化问题是一个复杂的优化问题，特别是不可微或者多峰的函数，往往不能有效地求解。而遗传算法作为一种高度并行、随机、自适应的全局优化概率搜索算法，它将每个可能的问题表示为“染色体”，从而得到一个由染色体组成的“群体，然后按遗传学规律进行选择、交叉、变异操作，直到满足终止条件为止。
九、总结
量子遗传算法在许多应用领域发挥着重要作用，量子遗传算法与遗传算法一样，都是一种基于生物和进化机制的适合复杂系统优化计算的自适应概率优化[18]技术.相比于经典遗传算法具有种群规模小、收敛速度夸、全局搜索能力强的优点。目前的量子遗传算法主要存在如下问题：首先，通过测量量子位的状态获得二进制解，这是个概率操作过程，具有很大的随机性和盲目性，因此在种群进化的同时，部分个体将不可避免地产生退化；其次，二进制编码对于连续优化，由于频繁解码操作加大了计算量，严重降低了优化效率；第三，对于量子旋转门的转角方向、大小，一视同仁，没有考虑染色体之间的差异。因此，应加注重量子遗传的种群大小的选择，进化策略[19]的设计与实施。如何让量子遗传算法更好的发挥性能，未来还需要做进一步研究
参考文献
[1] Han K-H. Genetic Quantum Algorithm and its Application to Combinatorial Optimization Problem. In: IEEE Proc. Of the 2000 Congress on Evolutionary Computation. San Diego. USA. IEEE Press. July 2000.1354~1360
[2] Melanie Mitchell. An introduction to genetic algorithms. Cambridge, MA: The MIT Press, 1996
[3] Holland J H. Genetic algorithms and classifier systems: foundations and their application[C]// Proceedings of the Second International Conference on Genetic Algorithms. Hillsdale, NJ: Lawrence Erlbaum Associates, 1987: 82-89
[4] Bennett C H, DiVincenzo D Y. Quantum Information and Computation. Nature, 2000. 404.247一255
[5] Shor P W. Algorithms for Quantum Computation: Discrete Logarithms and Factoring. In: Goldwasser S, ed. Proc. of the 35th Annual Symposium on the Foundation of Computer Sciences, Los Alamitos: IEEE Computer Society Press.1994.20一22
[6] Grover L K. A Fast Quantum Mechanical Algorithm for Database Search.In:Proc.28th Annual ACM Symposium on the Theory of Computing .Philadelphia, Pennsylvania, ACM Press. 1996，212一22I
[7] Zalka C. Grover's quantum searching algorithm is optimal [J].Physical Reuiew A, 1999, 60:2746-2751
[8] Jen E. Stable or Robust? What’s the difference?[J].Complexity,2003,8(3):12-18
[9] Tony H.Quantum computing:An introduction[J].Computing&Control Engineering Journal,1996,10(3):105-112.
[10] Narayanan A. An introductory tutorial to quantum computing[A].Proc of IEE Colloquium on Quantum Computing: Theory, Applications and Implications[C].London: IEE Press,1997.1/1-1/3.
[11] Michalewicz Z, Janikow C, and Kjrawczyk, J.A modified genetic algorithm for optimal control problems. Computers and Mathematical Appliancations, 1992, 23(12): 83-94
[12] Deutsch D. Quantum computational networks. Proc Roy Soc London A,1989,425:73-90
[13] Han Kuk-Hyun and Kim Jong-Hwan. Quantum-inspired Evolutionary Algorithm for a Class of Combinatorial Optimization.IEEE Transaction son Evolutionary Computation，IEEE Press, 2002, 6 (6):580-593
[14] Han Kuk-Hvun and Kim Jong-Hwan. Quantum一Inspired Evolutionary Algorithms With a New Termination Criterion, Gate, and Two-Phase Scheme. Transactions on Evolutionary Computation, 2004, 8 (2):156-169
[15] Nielsen M A, Chuang I L量子计算与量子信息(一)量子计算部分[M ].赵千川，译.北京:清华人学出版社，2004:13-17.
[16] 杨俊安，庄镇泉，史亮.多宇宙并行量子遗传算法[j].电子学报，2004, 32(6):923-928
[17] 李士勇.智能优化算法原理与应用.哈尔滨工业大学出版社，2012.12
[18] J.N. Siddall. Probabilistic Engineering Design —Principle and Application. Marcel Dekker Inc., 1983
[19] 杨淑媛,刘芳，焦李成. “量子进化策略”[J].电子学报，第124期，第29卷，2001年12月