（计算机软件与理论专业论文）量子进化算法研究及应用.pdf

摘要量子进化算法是基于量子计算原理的一种迸化算法。这种崭新的优化算法，具有很大的生命力和研究价值。它以量子计算的一些概念和原理为基础，用量子位编码，量子门作为更新算子来完成进化搜索。与传统进化算法相比，量子进化算法能够更容易的在探索与开发之间取得平衡，具有种群规模小、收敛速度较快、全局寻优能力强的特点。实验表明量子进化算法在很多问题上比传统进化算法具有更好的性能，但解决一些复杂优化问题的能力不强，容易陷入局部最优。为了使量子进化算法能够更有效的解决实际的优化问题，本文对此做了进一步的研究，使量子进化算法的性能进一步提高，并扩大了它的应用范围。本文所做的贡献和成果主要有以下几部分：1 提出了基于分布估计的量子进化算法。在该算法中同时保存两种概率模型，相辅相成，促使算法在保证种群多样性下快速收敛。还提出了白适应调整旋转角度的策略，使旋转角度随演化的过程自动调整。2 将量子进化算法应用到多选择背包问题和多选择多维背包问题，针对这类特殊问题提出了相应的观测解过程和新的旋转算子。3 将基于分布估计的量子进化算法扩展到多目标优化，取得了很好的效果。关键词：量子计算，进化算法，分布估计，多选择多维背包问题，多目标进化算法a b s t r a c tq u a n t u mi n s p i r e de v o l u t i o n a r ya l g o r i t h m ( q f a ) i sae v o l u t i o n a r ya l g o r i t h mb a s e do np r i n c i p l e so fq u a n t u mc o m p u t i n g ( q 0 t h en o v e lo p t i m i z a t i o nm e t h o dh a ss t r o n gr o b u s t n e s sa n di sv a l u a b l ef o rr e s e a r c h b a s e do nc o n c e p ta n dp r i n c i p l e so fo c 。q e au s e saq b i ta sap r o b a b i l i s t i cr e p r e s e n t a t i o na n daq g a t ea sav a r i a t i o no p e r a t o rt oc o m p l e t ee v o l u t i o n a r ys e a r c h c o m p a r e dw i t hc o n v e n t i o n a le a s ，q e ac a l lb a l a n c eb e t w e e ne x p l o r a t i o na n de x p l o i t a t i o nm o r ee a s i l y ,a d d i t i o n a l l yi ti sc h a r a c t e r i z e db ys m a l lp o p u l a t i o ns i z e ，r a p i dc o n v e r g e n c ea n ds t r o n gg l o b a ls e a r c hc a p a b i l i t y a st h ee x p e r i m e n t a lr e s u l t ss h o w , q e ah a sb e t t e rp e r f o r m a n c e st h a ne a so nm a n yp r o b l e m s ，b u ti ti sw e a ki ns o l v i n gs o m ec o m p l e xo p t i m i z a t i o np r o b l e m sb e c a u s ei tt e n d st oi n ni n t ol o c a lo p t i m a i no r d e rt om a k eq e as o l v ea c t u a lp r o b l e m sm o r ee f f e c t i v e l y , i nt h i sp a p e r , w ed os o m ef u r t h e rr e s e a r c h e so ni t ，m a k i n gt h ep e r f o r m a n c eb e t t e ra n de n l a r g i n gi t sa p p l i c a t i o nf u r t h e r t h em a j o rc o n t r i b u t i o n sa n da c h i e v e m e n t sa r ea sf o l l o w s ：1 q u a n t u mi n s p i r e de v o l u t i o n a r ya l g o r i t h mb a s e d0 1 1e s t i m a t i o no fd i s t r i b u t i o n ( e q e a ) i sp r o p o s e d t h en o v e la l g o r i t h mk e e p st w op r o b a b i l i s t i cm o d e l sw h i c hs u p p o r te a c ho t h e ra n dm a k et h ea l g o r i t h mh a v em o r er a p i dc o n v e r g e n c eu n d e rt h ec i r c u m s t a n c eo fd i v e r s i t i e s i na d d i t i o n ，a na d a p t i v er o t a t i o no p e r a t o ri sp r o p o s e dw h i c hc a na d j u s tt h em a g n i t u d eo fa n g l ew i t he v o l u t i o np r o c e s sa u t o m a t i c a l l y 2 q e ai sa p p l i e dt os o l v em u l t i p l ec h o i c ek n a p s a c kp r o b l e m( m c k p ) a n dm u l t i p l ec h o i c em u l t i d i m e n s i o n a lk n a p s a c kp r o b l e m( m m k p ) f o rt h e s es p e c i a lp r o b l e m s ，an e wm e t h o do fm a k i n gs o l u t i o n sf r o mq u a n t u mc h r o m o s o m e sa n dac o r r e s p o n d i n gr o t a t i o no p e r a t o ra r end e s i g n e d 3 e q e af o rm o p si sp r o p o s e d t h en e wa l g o r i t h mc a l lh a v eg o o dr e s u l t sf o rm u l t i - o b j e c t i v ek n a p s a c kp r o b l e m s k e yw o r d s ：q u a n t u mc o m p u t i n g ，e v o l u t i o n a r ya l g o r i t h m s ，e s t i m a t i o no fd i s t r i b u t i o n ，m u l t i p l ec h o i c em u l t i - d i m e n s i o n a lk n a p s a c kp r o b l e m ,m u l t i o b j e c t i v ee v o l u t i o n a r ya l g o r i t h m sm量子进化算法研究及应用第一章绪论随着科学的发展和社会的进步，人类面临的问题越来越多，这些问题的难度也越来越大。迄今为止，已经有许多的优化方法，如：爬山法、梯度法等。这些方法针对不同的对象都表现出不同的特点。然而，这些方法在应用中都或多或少的表现出一些弊端。为了找到更好的寻优技术，人们在不断的探索着并应用到各个领域。1 1 现代优化方法回顾现代优化算法【1 】包括禁忌搜索( t a b us e a r c h ，t s ) 、模拟退火( s i m u l a t e da n n ea l i n g ，s a ) 、进化算 法( e v o l u t i o n a r ya l g o r i t h m ，e a ) 、神经网络( n e u r a ln e t w o r k s ) 、蚁群算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 、粒子群算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 、分布估计算法( e s t i m a t i o no fd i s t r i b u t i o na l g o r i t h m ，e d a ) 、量子进化算法( q u a n t u mi n s p i r e de v o l u t i o n a r ya l g o r i t h m ，o e a ) 等。这些算法涉及生物进化、人工智能、数学和物理科学、神经系统和统计力学等概念，都是以一定的直观基础构造的算法，称之为启发式算法。禁忌搜索算法( t s ) 是局部领域搜索算法的推广，是人工智能在组合优化算法中的一个成功应用。g l o v e r 在1 9 8 6 年首次提出这一概念，进而形成了一套完整算法。禁忌搜索算法的特点是采用了禁忌技术，所谓禁忌就是禁止重复前面的工作。e a ( e v o l u t i o n a r ya l g o r i t h m , e a ) 【2 】的研究起源于2 0 世纪6 0 年代h o l l a n d 针对机器学习问题发展的遗传算法( g e n e t i ca l g o r i t h m ,g 舢、f o g e l 对于优化模型系统所提出的进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 以及r e c h e n b e r g 和s c h w e f e i 对于数值优化问题提出的进化策略( e v o l u t i o n a r ys t r a t e g y ，e s ) 。e a 是一类模拟生物进化过程与机制求解问题的自组织、自适应人工智能技术。依照达尔文的自然选择和孟德尔的遗传变异理论，生物的进化是通过繁殖、变异、竞争、选择来实现的。e a 就是建立在上述生物模型基础上的随机搜索技术。人工神经网络的早期工作可以追溯到1 9 4 3 年m c c u i l o c h 和p i t t s硕士学位论文建立的第一个模型，后被扩展为“认知”模型f 3 】。人工神经网络有较强的学习能力和自适应性，具有大规模的平行计算能力，且它的发展也较成熟，但它仍然受到计算发展的限制。蚁群算法( a c o ) 、粒子群算法( p s o ) 【4 】是对社会性动物( 蚂蚁群、鸟群) 的自组织行为进行数学建模并用计算机对其仿真而产生的，出现于2 0 世纪9 0 年代。分布估计算法( e d a ) 5 1 是一种基于概率模型的新型进化算法。这种算法不使用交叉和变异算子，而直接提取当前优选解集合中的信息，然后根据这些信息建立概率分布模型，再用这种分布产生新的解，作为下一代种群，如此重复，直到满足终止条件。由于分布估计算法能较好的避免连锁问题，并且有较强的理论基础，近年来已成为研究的热点。1 2 量子进化算法及研究现状量子进化算法( q u a n t u me v o l u t i o n a r ya l g o r i t h m ，q e a ) 【6 j 是基于量子计算原理的一种进化算法，这种崭新的化方法，具有很大的生命力和研究价值。它以量子计算的一些概念和原理( 具体见第二章) 为基础，用量子位编码来表示染色体，通过量子门更新种群来完成进化搜索，与传统进化算法相比，能够更容易的在探索与开发之间取得平衡，具有种群规模小、收敛速度较快、全局寻优能力强的特点。an a r a y a n a n 和m m o o r e 在“q u a n t u m i n s p i r e dg e n e t i ca l g o r i t h m 一文中提出了量子遗传的概念用。k u k h y u nh a n 等人在2 0 0 0 年提出了一种遗传量子算法( g e n e t i cq u a n t u ma l g o r i t h m , g q a ) 嘲，将量子的状态矢量表达引入遗传编码，利用量子旋转门实现染色体基因的调整，并以此策略实现了0 1 背包问题的求解，结果其性能要优于传统的遗传算法。k u k h y u nh a n 的遗传量子算法( g q a ) 实际上是一种概率演化算法，在算法中没有采用任何遗传操作，因为他认为该算法染色体的多态性表达已经能够保证算法具有足够的多样性，同时具有开发能力和探索能力，因而不再需要有交叉和变异。后来又提出了量子进化算法( q u a n t u m i n s p i r e de v o l u t i o n a r ya l g o r i t h m 。q e a ) 9 ，应用于优化问题取得了一些成果。q e a 在g q a 的基础上增加了迁移机制，进量子进化算法研究及应用一步提高了算法性能。在国内，量子进化算法也得到了发展。量子概率编码遗传算法q c g a 1 0 l 设计了基于量子个体的交叉和变异算子效果良好，另外还有一些改进策略，如引入混沌机制做局部搜索【1 1 】、扩展到其他编码方式 1 2 1 、与其他演化算法混合等【1 3 1 4 1 。目前量子进化算法已经应用到数值优化【12 1 只1 6 1 、组合优化i s 、图形图象处理【1 8 】、电路设计f 1 7 】、通信【1 9 1 、多目标优化【1 9 】等领域。1 3 复杂背包问题研究现状背包问题( k n a p s a c kp r o b l e m , k p ) 是运筹学中一个典型的优化难题，在预算控制、材料切割、货物装载等实践中有重要应用，还常作为其他问题的子问题加以研究。背包问题可以衍生出系列与之相关的优化问题，如有限背包问题、无限背包问题、多背包问题、多选择背包问题、多选择多维背包问题。目前背包问题的许多变体已经被广泛研究，求解背包问题的算法主要分为两大类【冽：1 ) 精确算法( 如枚举法、动态规划法、分支定界法、图论法等指数级方法) ，对于一些问题的实例能够在适度的时间内找到最优解。2 ) 近似算法或启发式算法( 如贪心算法、蚁群算法、遗传算法等) ，可以在很短的计算时间内产生一个满意解。多维背包问题( m u l t i d i m e n s i o n a lk n a p s a c kp r o b l e m ，记为m d k p )也是一种背包问题，只是它的约束是多维的。多选择背包问题( m u l t i p l ec h o i c ek n a p s a c kp r o b l e m ，记为m c k p ) 是k p 的另外一个变体，它对选择物体具有更严格的约束。k o l e s a r 、s h i h 、n a u s s 、k h a n t m l j 分别针对0 i k p 、m d k p 、m c k p 、m m k f 提出了分支限界线性规划精确算法。尽管使用线性规划确定任意类中任意物体的可行度可以减少所需要的时间，但是他们还是对很多实际例子不适用。贪心算法可以用来获得近似最优解。对子一般的0 1 背包闯题，可以将物体按照利润重量比降序排序。t o y o d a 将这种方法应用到m d k p 中【4 2 】。该方法要求重复选择物体直到资源约束不满足。硕士学位论文到目前为止，很少有文章专门用来解决多选择多维背包问题( m u l t i p l ec h o i c em u l t i d i m e n s i o n a lk n a p s a c kp r o b l e m ，记为m m k p ) 。m o s e r1 2 1 】等设计了一种方法使用了g r a c e 伽d e g r a d a t i o n 。k h a n l 2 2 】等在t o y o d a 解m d k p 的基础之上将方法扩展到m m k p 。2 0 0 4 年h i f i t z o j 等提出了一种局部搜索算法，该方法通过惩罚之前已经搜索到的解来达到目的，又于2 0 0 6 年提出了一种新的带退化机制的局部搜索算法。1 4 多目标进化算法研究现状在实际应用中，人们经常遇到在给定的区域上需要使多个目标均尽可能最佳的优化问题。例如设计新产品时，既要考虑使产品具有较好的性能，又要考虑其制造成本最低，还要考虑产品的可制造性、可靠性以及可维修性等性能，这些设计目标的改善可能相互抵触，譬如好的维修性会引起可靠性的降低，因此须在这些设计目标之间取一折中结果。这种多个目标在给定的区域上的最优化问题一般就称之为多目标优化问题( m u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m s ，记为m o p s ) 。人们对这个问题已经研究出了许多方法【3 】，如传统的线性加权和法、极大极小法、理想点法、逐次线性加权和法等。这些求解方法各有优点，当然也有各自应用的局限性。最近进化算法已经成为一种有效的多目标优化方法而被广泛应用。它的优点在于可处理大规模的搜索空间、在单轮优化期间产生多个最优解或有效解，可克服经典方法的局限性。常见的多目标进化算法可以分为【3 2 】：简单聚集法、基于种群的非p a r e t o 法、基于种群的p a r e t o 法和n i c h e 感应技术。简单聚集法也称为权重系数变化法，该方法将多目标转化为单目标问题再使用单目标进化算法求解。其缺点是权重系数的选定比较困难。基于种群的非p a r e t o 法也称为并列选择法，以向量进化遗传算法( v e c t o re v a l u a t e dg e n e t i c a l g o r i t h m , v e g a ) t 3 3 l 为代表。该方法容易生个别子函数的极端最优解，要找到所有目标函数的某种程度上的协调最优解比较困难。第三种方法也称为排序选择算法，典型的包括m o g a z 珥 、n s g a t 3 5 1等。其基本思想是基于p a r e t o 最优个体的概念对种群中的各个个体进行排序，依据排序次数来进化选择计算。n i c h i n g 技术主要是适应度4量子进化算法研究及应用共享技术，每次选择计算时都需要进行大量个体之间的优劣关系评价和比较运算，算法的搜索效率相对降低。1 5 本文的研究目的内容及结构安排与传统进化算法相比，量子进化算法能够更容易的在探索与开发之间取得平衡，具有种群规模小、收敛速度较快、全局寻优能力强的特点。q e a 在简单背包闯题上比传统进化算法具有更好的性能，但q e a 解决复杂优化问题的能力不强，容易陷入局部最优【3 6 】。为了使量子进化算法能够更有效的解决实际的优化问题，探索新的量子进化算法是非常必要的。通常在对q e a 测试时都采用简单0 1 背包问题，发现该算法在该问题上表现的性能比较好，而对于复杂多背包问题该算法的效果还有待进一步探讨，特别是多选择多维背包问题。q e a对于单目标组合优化问题表现出比传统g a 好，但在多目标领域的应用研究成果不多，是否能够充分利用其多样性，这里也将对多目标量子进化算法进行研究。本文主要是对量子进化算法的研究、改进及应用，并将其应用到解复杂背包问题的优化问题，除了单目标优化，还提出了一种新的多目标量子进化算法并应用于多目标背包问题。论文共分为六章，分别介绍如下：第一章为绪论，简要介绍了现代优化算法( 包括禁忌搜索、遗传算法、神经网络、群智能算法、分布估计算法) 的基本思想，介绍了量子计算与量子进化算法、复杂背包问题、多目标优化的研究现状。第二章简要介绍量子计算的机制、量子种群表示、观测方式、更新算子以及量子进化算法大致框架。第三章提出了一种将量子进化算法和分布估计算法结合的新算法一基于分布估计的量子进化算法。它通过对二进制解的概率模型重新估计产生个估计个体，更新算子则是基于该估计个体和组内最优解自适应的获得旋转角度的幅度。该算法中两个概率模型相辅相成，让算法的进化过程进展飞速，同时又能获得高质量的解。第四章将量子进化算法在组合优化中应用扩展到m m k p ，提出了求解m m k p 的量子进化算法。根据多选择的特点，采用整数表示硕士学位论文解，量身定制了一种得到观测解的方法，同时提出了相应的旋转更新算子。第五章在第一章的基础上，将该算法扩展到多目标优化问题上，提出了基于分布估计的多目标量子进化算法，该算法基于n s g a i i 框架，并以多目标背包问题为例阐述该算法的每个步骤。第六章对全文做了一个总结，并对下一步的工作进行展望。6量子进化算法研究及应用第二章量子计算原理与量子进化算法简介量子计算的概念起源于对可逆计算机的研究，最早由f e y n m a n在1 9 8 2 年提出量子计算是相对于经典意义上的计算而言，它是基于量子力学而非经典物理学的思想进行的计算【1 1 。目前，有关量子计算的研究在国际上十分活跃。美国、欧洲、日本等各国政府已经将其列入重点发展的高科技项目之一大力扶持。量子理论自诞生1 0 0 多年以来已经取得了巨大的成功，但之前它与计算机科学、信息理论一直是作为不同的学科并行发展，几乎很少有人注意到它们之间有联系和交叉的可能，直到1 9 8 2 年，b e n i o f f 和f e y n m a n发现了将量子力学原理用于计算的可能。s h o r 在1 9 9 4 年提出了大数质因子分解量子算法，g r o v e r 在1 9 9 6 年提出了未加整理数据库的量子搜索算法，这些算法对传统算法实施了近乎指数级的改进。进化计算( e a ) 是一类模拟生物进化过程与机制求解问题的自组织自适应人工智能技术。依照达尔文的自然选择和孟德尔的遗传变异理论，生物的进化是通过繁殖、变异、竞争、选择来实现的。e a 就是建立在上述生物模型基础上的随机搜索技术。e a 具有三个分支：遗传算法、进化规划、进化策略。已经证明，它们均能从概率的意义上以随机的方式寻求到问题的最优解1 2 1 。但是另一方面，由于自然进化和生命现象的不可知性，e a 不可避免的存在概率算法的缺陷。e a 最明显的缺点就是它的收敛问题，包括收敛速度慢和未成熟收敛。e a之所以能使个体得到进化，首先是采用选择操作尽量选出比较好的若干个体，保证下一代个体一般不差于前代，使个体趋于最优。同时采用遗传操作，通过它们的破坏性影响保证产生新的个体，从而生成更好的个体，更重要的是可以维持群体的多样性。若选择压力不足，则算法的收敛速度慢。若个体的多样性不够，则算法易于陷入局部最优。因此e a 的进化过程同时也是一个追求群体的收敛性和个体的多样性之间平衡的过程。分析e a 可以发现【6 j ，它没有利用进化中未成熟优良子群体所提供的信息，因而限制了进化速度。事实证明，在进化中引入好的引导机硕士学位论文制可以增强算法的智能性提高搜索效率，解决e a 中的早熟和收敛速度问题1 4 j 。基于上面的两种计算模式，a n a r a y a n a n 和m m o o r e 在“q u a n t u m i n s p i r e dg e n e t i ca l g o r i t h m ”一文中提出了量子遗传的概念用。k u k h y u nh a n 等人在2 0 0 0 年提出了一种遗传量子算法( g e n e t i cq u a n t u ma l g o r i t h m , g q a ) i s ，将量子的状态矢量表达引入遗传编码，利用量子旋转门实现染色体基因的调整，并以此策略实现了0 1 背包问题的求解，结果显示其性能要优于传统的遗传算法。后来又提出了量子进化算法( q u a n t u m - i n s p i r e de v o l u t i o n a r ya l g o r i t h m ，q e a ) 9 1 ，进一步提高了算法的性能。下面我们分别介绍量子计算的机制和量子进化算法。2 1 量子计算原理量子算法是相对于经典算法而言的，它最本质的特征就是利用了量子态的叠加性、相干性以及量子比特之间的纠缠性，是量子力学直接进入算法领域的产物【6 】。我们也可以从概率算法去认识量子算法。在概率算法中，系统不再处于一个固定的状态，而是对应于各个可能状态有一个几率，即状态几率矢量。如果知道初始状态几率矢量和状态转移矩阵。通过状态凡率矢量和状态转移矩阵相乘可以得到任何时刻的几率矢量。量子算法与此类似，只不过需要考虑量子态的几率幅。因为它们是平方归一的，所以几率幅度相对于经典几率有、万倍的放大，状态转移矩阵则用w a l s hh a d a m a r d 变换、旋转相位操作等酉正变换实现。2 1 1 状态的叠加在经典数字计算机中，信息被编码为位( b i t ) 链。1 比特信息就是两种可能情况中的一种，0 或1 ，假或真，对或错。例如，电容器的板极间的电压可以代表1 比特信息，带电的电容表示1 ，而放电的电容表示o 。在量子计算机中，基本的存储单元是一个量子位( q - b i t ) 。一个简单的量子位是个双态系统。例如半自旋或两能级原子，自旋量子进化算法研究及应用向上表示0 ，向下表示1 ，或者基态代表o ，激发态代表1 。不同的是，一个量子位除了可以处于o 态和1 态之外，还可以处于它们的叠加态。为了便于表示和运算，d i r a c 提出用符号| x 来表示量子态。一个量子位的叠加态可用二维h i l b e r t 空间( - - 维复向量空间) 的单位向量f 妒，来描述，l 妒一口i + 芦1 1 ，k 1 2 + 例2 。1 ，其中口，声为代表相应状态出现概率的两个复数，i 口1 2 、 厣1 2 分别表示量子比特处于状态0 和状态1 的概率。个1 1 位的普通寄存器处于唯一的状态中，而由量子力学的基本假设，一个n 位的量子寄存器可处于z 个基态的相干叠加状态i 妒中，即可以同时表示丁个数。叠加态和基态的关系可以表示为：妒。荟q i p( 2 1 )其e e ，q 为1 1 ；f ，在受到量子计算机系统和纠缠的测量仪器观测时坍塌到基态l 是 的概率，满足归一化条件| c 1 2 + l c 2 2 + + 陲f 2 - 1 。2 1 2 状态的相干量子计算的一个主要原理就是使构成叠加态的各个基态通过量子门的作用发生干涉，从而改变它们之间的相对相位。如一个叠加态为l 妒一万2i + 万1l ，一击，设量子门u 击( ：习作用在其上，结果为l 妒一面3i 吣+ 面11 1 ，可以看到基态l 的概率幅增大而i b的概率幅减小。若量子系统i 妒，处于基态的线性叠加的状态，我们称系统为相干的。当一个相干的系统和它周围的环境发生相互作用( 测量) 时线性叠加就会消失，具体坍塌到某个基态i & 的概率由l c k1 2 决定。如对于上面的i , p ，进行测量，其坍塌到i o ，的概率为0 9 ，这个过程称为消相干。9硕士学位论文2 1 3 状态的纠缠量子计算另一个重要的机制是量子纠缠态，它违背我们的直觉。对于发生相互作用的两个子系统中所存在的一些态，若不能表示成两个子系统态的张量积，这样的态就称为纠缠态。对处于纠缠态的量子位的某几位进行操作，不但会改变这些量子位的状态，还会改变与它们相纠缠的其他量子位的状态。量子计算能够充分实现，也是利用了量子态的纠缠特性。2 2 量子进化算法量子进化算法( q u a n t u me v o l u t i o n a r ya l g o f i t h r a ，q e a ) 是将量子计算和进化算法相结合的一种算法。量子进化算法正是将这种量子机制与迸化算法相结合的概率搜索算法。他的本质特征就是充分利用了量子态的叠加性和相干性。它以量子计算的一些概念和理论为基础，用量子位编码来表示染色体，通过量子门更新种群来完成进化搜索，与传统进化算法相比，能够更容易的在探索与开发之间取得平衡，具有种群规模小、收敛速度较快、全局寻优能力强的特点。2 。2 1 染色体的表示与其他传进化算法相比，q e a 不是采用二进制、十进制和浮点等编码方式，而是采用一种新颖的编码方式量子比特编码。一个量子比特可以表示为：f a l ，具有这种表达形式的个体【卢j牙一i 蓉：差二爱l ，并且满足i qp + i 肛p - 1 ，f - 1 ，2 棚，n 表示量子比特的个数，q 在q e a 中被称为一个量子染色体，q e a 正是用量子染色体对问题进行描述的。由此可知，n 个量子比特可同时表示z 个状态，可表示为：1 0量子迸化算法研究及应用f 妒。荟g i p( 2 2 )其中，c i 为第k 个状态的概率幅，且满足归一化条件虹i 2 + l c ：1 2 + + k ；2 一i ，其中f 妒，是z 维h i l b e r t 空间中的一个单位矢量。它所在空间的维数是随n 呈指数型增长，这明显区别于g a 中随n 呈线性增长的态空间。f1111例如：编码为f 孑三l 的量子个体，其状态可以表示为：i 万万了i专1 0 0 0 + 鲁m ，+ 习0 1 0 + 粤1 0 1 b丢i l o o ，+ 警| 1 0 扣1 1 0 + 字1 1 1 b所有二进制个体有2 3 8 ，分别为0 0 0 ，0 0 1 ，0 1 0 ，0 1 1 ，1 0 0 ，1 0 1 ，1 1 0 ，1 1 1 。而此量子个体取到o o o 的概率为( 匆h ( 匆2 。 2 一面1 ，类似依次可得此量子个体取得上述8 个个体的概率分别为：l3131313五面面五语话面面6采用量子比特的编码方式，一个染色体可以表征任意的线性叠加态，而传统的编码方式只能表示一个具体的状态，所以q e a 比其他传统进化算法更容易保持种群的多样性。而且随着k1 2 或i a1 2 逐渐靠近1 或0 ，量子染色体逐渐收敛到单一的状态，种群的多样性也随之减小，算法收敛。所以采用量子比特的编码方式，q e a 同时具有探索与开发能力。2 2 2 更新算子更新算子是量子进化算法的核心。它的好坏直接影响到该算法表现出来的性能。硕士学位论文在q e a 中，由于染色体处于叠加状态或纠缠状态，因而更新操作不能采用传统g a 中的选择、交叉和变异等操作方式，而采用将量子门分别作用于各叠加态和纠缠态的方式；子代个体的产生不是由父代群体决定，而是由父代的最优个体及其状态的概率幅决定。更新操作主要是将构造的量子门作用于量子叠加态或纠缠态的基态，使其相互干涉，相位发生改变，从而改变各基态的概率幅。因此量子门的构造是q e a 的关键问题。量子门的类型有很多，分类方法也不相同。根据它操作的量子位的数目不同可以分为一位门、二位门和三位门等；根据它的作用不同可以分为量子非门、量子受控非门、h a n d a m a r d 门、量子旋转门等。在o e a 中主要采用的是量子旋转门【，) c o s ( a s t ) - - $ 2 紫曼1( 2 3 )量子位的更新是通过量子门的更新来完成的，其过程如下：讣叭引心削在更新的过程中，口的大小和符号起关键作用。a 8 的符号影响量子门旋转的方向。由图2 - 1 可知：当量子比特位于第一、三象限时，8 被设置成正值时将提高它为状态1 的概率，而当量子比特位于第二、四象限时，口被设置成负值时将提高它为状态1 的概率。当量子比特位于第一、三象限时，a 日被设置成负值时将提高它为状态0 的概率，而当量子比特位于第二、四象限时，a 口被设置成正值时将提高它为状态0 的概率。1 2量子进化算法研究及应用1 。厂 d从壕一。图2 - 1我们可以查询表2 1 得到角度的设置：表2 - 1蕾岛厂o ) 之f ( 6 )a0of a l s e岛00t r u e吃o1f a l s e岛01t r u e只l0f a l b1o1 - m e吼11f a i s e良11t r u e岛其中一般设置岛、岛绝对值为0 0 0 1 ；r 一0 0 5 j r ，具体的正负根据当前所处的象限而定，其他的情况设置为0 。2 2 3 算法流程量子进化算法的一般流程如下：p r o c e d u r eo e ab e g i nt - 0i )i n i t i a l i z eq ( t )硕士学位论文i i )m a k e p ( t ) b yo b s e r v i n gt h es t a t e so fq ( ，)i i i )e v a l u a t ep ( f )i v )s t o r ee ( oi n t ob ( oa n dt h eb e s ts o l u t i o na m o n g p ( t ) i n t obv )w h i l e ( n o tt e r m i n a t i o nc o n d i t i o n ) d ob e g i nv i )m a k ep ( ob yo b s e r v i n gt h es t a t e so f q ( t 一1 )v i i )e v a l u a t ec o )v i i i )u p d a t e q ( t ) u s i n gq - g a t e si x )s t o r et h eb e s ts o l u t i o n sa m o n g b ( t 一1 ) a n d p ( t ) i n t o 口o )x )s t o r et h eb e s ts o l u t i o nba m o n g b ( t )x i )i f ( g l o b a lm i g r a t i o nc o n d i t i o n ) t h e nm i g r a t ebt o 矗( f )g l o b a l l ye l s ei f ( 1 0 c a lm i g r a t i o nc o n d i t i o n ) t h e nm i g r a t e 够i nb ( f ) t o 口( f ) l o c a l l ye n de n d对每一步骤的解释如下：i ) 初始化种群q ( o ) ，种群( 大小为n ) 中全部染色体叫o ；：；曩剖o，一1 ，的所有基因 口；群】7 ( f - 1 ，棚) 都被初始化为( 万1 ，去) ，这一一v二vz意味着一个染色体所表达的是其全部可能状态的等概率叠加：量子进化算法研究及应用呲f i 薹专m其中，瓯为第k 种状态，表现形式为一长度为1 1 的二进串。i i ) 是对初始种群中的个体进行一次观测，以获得一组确定的解p ( f ) 一 巧，雹，墨) k ，其中一( f ) 一“，蔓，z ) 为第t 代种群中第j 个解( 第j 个个体的观测解) ，表现形式为长度为n 的二进制串，其中每一位为0 或1 是根据量子比特的概率i 靠尸( j 口，j 2 ) 而确定。具体观测过程为：对每一个l 岛p ，若设定在【o ，1 】中产生的一个随机数小于i 以r ，则此基因的值取为1 ，否则取为0 。具体的实现过程描述如下：p r o c e d u r em a k e ( x )b e g i nf _ 1w h i l e ( f = c o u n t o ，则蕾= 1 ，否则薯= o 。描述如下：p r o c e d u r ee s t i m a t ei n p u t ：sb i n a r ys o l u t i o n s x = ( x ：，x x ：) ，w h e r ex ：一( x , l ，2 ，毛) ，i l 2 ，so u t p u t ：an e ws o l u t i o nx - “，乇，z 。)b e g i nf o r i = 1t o nc o u n t 0 ：= 0 ，c o u n t l ：= 0 ；f o r j = l t osi f 石口- 1t h e nc o u n t l ：= c o u n t l + l ；e l s ec o u n t 0 ：= c o u n t o + l ；e n d f o ri fc o u n t l = c o u n t 0t h e n 毛：= 1e l s e 毛2 0 ；1 8量子进化算法研究及应用e n d这实际上是两个概率模型在相互作用。量子染色体本身是一个概率模型，由s 个二进制解生成了一个概率模型。前者代表当前0 1 的概率，后者为观测生成的二进制解的0 1 概率。通过后者能促进前者更快收敛。q e a 更新算子中，量子位的旋转角度是由该染色体随机观测的解和当前最好解来决定，该随机解代表的就是染色体的分布大致概率，若用估计个体替代随机观测解，可以更好的反映了量子染色体的0 1 分布概率，随着演化进行，真实性越高。当两个概率分布越来越接近时，量子染色体也随着收敛。由于量子染色体在生成观测二进制解时具有很大的随机性，这里仅从中选取s 个解做代表，排除那些很差的解。从后面的实例中可以看到其优势。在g q a 与q e a 中旋转更新算子旋转角度是由该量子染色体的当前最优二进制解和一个随机生成的观测解确定。观测解并不能很好的代表该量子染色体中的0 1 分布情况，它具有很大的随机性。e q e a采用量子染色体估计个体做替代。更能准确的反映量子位的概率分布，有目的的增长相应的概率幅，从而提高搜索的效率。3 2 自适应旋转更新算子旋转角度的确定包括两个方面：方向和幅度。角度的方向决定了概率幅增长的方向。不适合的旋转幅度导致算法容易陷入局部最优解，过小则收敛速度比较缓慢。3 2 1 角度的方向的设定设x ，b 分别为估计个体和组内当前最优解，旋转方向的确定如- f 当毛一岛时，矿( 6 蝴o ，蝴( x 比6 好) 则增加取薯( 0 或1 ) 的概率，否则增加取1 一毛的概率，具体的正负方向根据q ，尼当前的取值情况而定。硕士学位论文晓的符号薯岛b e t t e r ，6 )q 尼如q 属c oo0f a l s e0o0ot h eoo0lf a l +o1t r u e+10f a l s e+1o1 如e+l1f a l s e0011t n l eoo3 2 2 自适应调整旋转幅度如前所述，旋转角的大小不但对算法的收敛速度有很大的影响，而且也会影响到解的质量，过大导致算法容易陷入局部最优解，过小则收敛速度比较缓慢。为了构造可以自适应调整的角度，考虑了量子染色体的估计个体和组内当前最优解b 的距离和适应度差值，采用以下策略来获得动态的调整。在演化的初期，旋转幅度较大，后期幅度较小，且会根据两个解的差距( 包括二进制位的差距和适应度差距)自适应调整。对于背包问题，第i 个量子染色体的旋转幅度可以按照3 1 来计算。l a o , i - m i n a a + ( m a x 舳一m i l l 的触掣2 高耥( 3 - 1 )其中r a i n a 0 ，m a x a o 是事先设定的旋转角度大小的最大值和最小值，一般设为0 0 1 月r ，o 1 石，缸，吐，2 是两非负数，n 是二进制解的长度，上；是要更新的量子染色体的估计个体，b ；是包含x ，的组内当前最优二进制解。对于背包问题，恍一6 j 0 为两个解的海明距离。对于函数优化问题，可以采用多个位表示一维。假定有k 个变量，每个变量使用n 位表示，量子染色体可以表示为：量子进化算法研究及应用阮：；：= ：列【芦- 一芦- 芦，j则，一个二进制解可以表示为x - “。，x a ：，) ，其c o - - 进制串 讫) 代表一个实数变量。那么k 个变量的实数解可以表示为x 。t “，毫，) 。每一维可以使用不同的旋转角度值，同一维采用相同大小的旋转角度值，第i 维的角度大小可以使用如下表达式设定：l a o , i - m i n a e + ( m i x 6 e - r a i n a t 9 1 而i x ) 二- b , 丽l u p p e rl o w e r 出ma x 然嚣新3 - 2 u j u jit ，p j 。，p ) j l其中u p p e r ( i ) ，l o w e r ( i ) 为第i 维变量的上界和下界，6 - 是x 所在组内的当前最好解。x i , b ： 1 0 w e r ( i ) ，u p p e r ( i ) 】。当w i = c 0 2 = 0 时，相当于固定角度幅度。3 3 算法具体实施基于分布估计的量子进化算法( q u a n t u m - i n s p i r e de v o l u t i o n a r ya l g o r i t h mb a s e do ne s t i m a t i o no fd i s t r i b u t i o n ，记为e q e a ) ，算法具体流程如下：p r o c e d u r ee q e ab e g i nt ：= o ：s e t p l ：i n i t i a l i z eq ( t )s e t p 2 ：m a k ep ( i ) b yo b s e r v i n gt h es t a t e so fq ( t )s e t p 3 ：e v a l u a t ep ( 1 )s e l p 4 ：s t o r et h eb e s ts o l u t i o n si ne a c hg r o u pi