（控制理论与控制工程专业论文）量子进化算法及其在qos组播路由和网络入侵检测中的应用.pdf

量子进化算法及其在o o s 组播路由和网络入侵检测中的应用摘要量子进化算法是量子计算与进化算法相融合的一种新的优化算法，它较好地弥补了进化算法在求解优化问题上的不足，其收敛速度和寻优能力都要优于进化算法。但是这种算法在求解复杂优化问题上仍然存在收敛速度慢和未成熟收敛问题，需要进一步改进。本文在已有研究的基础上，改进了量子进化算法，提出两种改进策略，并将其应用于o o s 组播路由和网络入侵检测中，主要研究工作和取得的成果如下：1 量子进化算法中量子旋转门旋转角的调整通常采用查表方式，针对这种固定调整策略的不足，提出了基于单种群优化和基于多种群并行优化的两种改进量子进化算法，并通过对典型复杂函数优化问题的求解验证了改进算法的可行性和有效性。2 针对具有n p 难度的q o s 组播路由问题，提出一种求解包含延时、延时抖动、带宽、包丢失率和费用约束的q o s 组播路由问题的改进量子进化算法。算法采用基于单种群优化的改进策略调整量子门旋转角，采用劣体突变策略实旌量子位变异。实验结果表明算法路由性能良好。3 针对网络入侵检测中的入侵特征库存在构建困难、自适应差的缺点，提出一种用于优化入侵特征库的改进量子进化算法。算法采用基于多种群并行优化的改进策略调整量子门旋转角，采用优体交叉策略实施全干扰交叉。最后将算法应用于网络入侵检测，得到了检测率达到9 0 9 6 以上的良好效果。测关键词：量子计算，量子进化算法，改进量子进化算法，o o s 组播路由，网络入侵检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 ma n di t sa p p l i c a t i o ni nq o sm u l t i c a s tr o u t i n ga n dn e t w o r ki n t r u s i o nd e t e c t i o na b s t r a c tq 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 ) i san e wo p t u n i z a t i o na l g o r i t h mo fm e r g i n gq u a n t u mc o m p u t i n gw i t he v o l u t i o n a r ya l g o r i t h m ( e a ) , w h i c hm a k e su pf o rt h ed e f e c t so fs o l v i n go p t i m i z a t i o np r o b l e mw i t he a , a n di ss u p e r i o rt oe ab o t hi nc o n v e r g e n c es p t 地da n do p t u n i z a t i o na b i l i t y b u tt h ep r e m a t u r i t ya n ds l o wc o n v e r g e n c ea 咒t w op r o b l e m se x i s t i n gi nq e af o rs o l v i n gc o m p l e xo p t t m i z a t i o np r o b l e m s ，a n ds t i l ln e e dt ob ei m p r o v e df u g m e l b a s e do nt h er e s u l t so ff o r m e rd d s e a l c 1 ，t h i sp a p e ri m p r o v e sq e a , p u t sf o r w a r dt w oi m p r o v e ds t r a t e g i e s ，a n dw h i c ha a p p l i e dt oq o sm u l t i c a s tr o u t i n ga n dn e t w o r ki n t r u s i o nd e t e c t i o n t h em a j o rc o n t r i b u t i o n so f t h i sp a p e ra r e 嬲f o l l o w s ：a i m i n ga tt h es h o r t c o m i n g so ft h es t a t i oa d j u s t m e n ts t r a t e g yt h a tt h er o t a t i o nc o r n e ro fq u a n t u mr o t a t i o ng a t ei so b t a i n e db yt a b l el o o k u pi nq e a ，t h et w oi m p r o v e dq e a s ( i q e a s ) a r ep r o p o s e di nt h i sp a p e rb a s e do nt h eo p t i m i z a t i o no fs i n g l ep o p u l a t i o na n dt h ep a r a l l e lo p t i m i z a t i o no fm u l t i p l ep o p u l a t i o n s ，a n dt h e i rf e a s i b i l i t ya n de f f i c i e n c ya r ev a l i d a t e db ys o l v i n gt h eo p t i m i z a t i o np r o b l e m sb a s e do nt y p i c a lc o m p l e xf u n c t i o n a c c o r d i n gt ot h eq o sm u l t i c a s tm u t i n gp r o b l e mt h a ti san ph a r dp r o b l e m , t h ei q e ao fs o l v i n gm u l t i - c o n s t r a i n e dq o sm u l t i c a s tm u t i n gp r o b l e m , i n c l u d i n gb a n d w i d t h , d e l a y , d e l a y - j i t t e r ,p a c k e t - l o s sa n dc o s t , i sp r o p o s e d t h ei q e aa d o p t st h ei m p r o v e ds t r a t e g yb a s e do nt h eo p t i m i z a t i o no fs i n g l ep o p u l a t i o nt oa d j u s tt h eq u a n t u mr o t a t i o nc o r n e r , a n d 嗽st h es t r a t e g yo fm u t a t i o ni n f e r i o ri n d i v i d u a l st og e tq u b i tv a r i a t i o n t h er e s u l t ss h o wt h a tt h ei q e ah a sg o o dr o u t i n gp e r f o r m a n c e i nv i e wo ft h es h o r t c o m i n g st h a tt h e r ea r od i f f i c u l t i e so fc o n s t r u c t i n ga n db a ds e l fa d a p t a b i l i t yi nt h ei n t r u s i o ns i g n a t u r es e t sb a s e do nn e t w o r ki n t r u s i o nd e t e c t i o n , t h ei q e a甜a p p l i e dt oo p t i m i z ei n t r u s i o ns i g n a t u r es e t si sp u tf o r w a r d t h ei q e aa d o p t st h ei m p r o v e ds t r a t e g yb a s e d0 1 1t h ep a r a l l e lo p t i m i z a t i o no fm u l t i p l ep o p u l a t i o n st oa d j u s tt h eq u a n t u mr o t a t i o nc o m e r , a n du s e st h ec r o s ss t r a t e g yo fe x c e l l e n ti n d i v i d u a l st og e tt h ew h o l ei n t e r f e r e n c ec r o s s f i n a l l y , t h ei q e ai sa p p l i e dt on e t w o r ki n t r u s i o nd e t e c t i o n , o b t a i n i n gg o o dr e s u l t st h a tt h ed e t e c t i o nr a t ei sm o r et h a n9 0 k e yw o r d s ：q u a n t m nc o m p u t a t i o n , 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 , i m p r o v e dq 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 o sm u l t i c a s tr o u t i n g ，n e t w o r ki n t r u s i o nd e t e c t i o n浙江工业大学学位论文原创性声明本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律责任。作者签名：毵弓，己日期：叩ml z 月2 1 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于l 、保密口，在年解密后适用本授权书。2 、不保密匹( 请在以上相应方框内打“妒，)作者签名：弘字色导师签名：莎了小日期：7 年，z ，月力j 日日期：如| 7 年j 莎月多日浙江工业大学硕：t 二学位论文第1 章绪论优化技术是一种以数学为基础，用以求解各种问题优化解的应用技术。大量的n p 难解问题：如数值优化、组合优化、多目标优化、时序安排等问题以及诸多实际工程领域：如人工智能、模式识别、系统控制、生产调度等，都需要用到优化技术。在实际的生产过程中，结合运用最优化技术，使各项指标得到最优，有利于提高效率，节省资源。因此，优化方法的理论研究以及改进算法性能、拓宽算法应用领域、完善算法体系等方面的研究具有理论意义和实用价值。1 1 优化技术回顾1 1 1 优化问题与优化方法为了使系统达到最优目标所提出的各种求解方法称为最优化方法。最优化方法是在第一次世界大战前后，军事领域中对导弹、雷达控制的研究中逐渐发展起来的，它对促进运筹学、管理科学、控制论和系统工程等新兴学科的发展起到了重要的作用【1 1 。优化问题涉及的工程领域很广，种类繁多，总的可以分为无约束优化问题和约束优化问题同。无约束优化针对的是没有任何约束前提下的极大或极小化某个函数的问题。无约束优化问题通常可用如下数学公式描述：m i n f ( x )( 1 - 1 )s t z x其中，工r ”为决策变量，灭一为问题空间，为目标函数，x r 一为约束集或可行域，如果约束集x = 灭一，则问题( 1 1 ) 为完全无约束最优化问题。无约束优化问题的研究是约束优化问题的基础。大多数实际的优化问题往往都是带有约束条件的，约束优化问题一般可用如下数学公式描述：m i n f ( x )( 1 - 2 )s 上函( 力0 ( = - 1 ，2 ，川)浙江工业大学硕士学位论文h i ( x ) = 0( 产l 2 ，乒)其中，xcscr 为决策变量，s 为可行域，足为问题空间，厂( 曲为目标函数，g j ( 曲、 ，o )为约束函数，霸( x ) o 和j i ，( 力= 0 分别为约束不等式和约束等式。若目标函数与约束函数都是线性函数，则称问题( 1 - 2 ) 为线性最优化问题；若目标函数与约束函数有其中之一是非线性的，则称问题( 1 - 2 ) 为非线性最优化问题。求解约束优化问题的核心是如何处理约束条件。求解最优化问题的优化方法有各种形式，针对相同的优化问题，不同的优化方法具有不同的优化特性，有些优化方法可以快速求解到局部最优解，有些优化方法具有很好的全局最优解。求解最优化问题的理想情况是快速有效地得到全局最优解，由于对最优化问题的性质和最优化方法认识的不足，这种情况只能在有限的条件下实现。对于复杂函数最优化问题，一般很难找到收敛性好且全局最优的优化方法。工程优化应用的大多数问题，都需要先对其进行数学建模，即向数学函数转化，然后对函数进行优化。工程优化所建立的数学函数，往往是带有多种约束条件的复杂函数，而且大都是既不连续、也不可微的隐函数，对于这些复杂函数来说，用传统优化方法很难或根本无法处理。近几十年来，随着计算机的发展，相继出现各种优化算法，一些过去无法解决的复杂优化问题已经能够通过计算机来求得近似解，因此，优化算法的研究也就显得越来越重要了。1 1 2 现代优化算法所谓优化算法，就是一种搜索过程或规则，根据现有优化问题的特点，利用某种思想或机制，按照相应的某种途径和方法来得到满足现实要求的问题解【3 】。在现代优化算法中，目前研究比较多，在优化领域中应用比较广泛的有禁忌搜索( t a b us e a r c h ，t s ) 、模拟退火( s i m u l a t e da n n e a 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 ) 、蚁群算法( a n tc o l o n ya l g o r i t h m ，a c a ) 、粒子群算法( 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 f d i s t r i b u t i o na l g o r i t h m ，e d a ) 等【4 】。这些算法涉及生物进化、人工智能、数学和物理科学、神经系统和统计力学等概念，都是以一定的直观基础构造的算法，称之为启发式算法。在这些启发式算法中，由于进化算法对优化问题无可微性要求，适用范围广，能够适应于不同环境，不同问题领域，具有强鲁棒性，而且这类方法采用随机优化技术，有较大的概率求得全局最优解，在多数情况下都可以得到比较有效的满意解或最优解。尽管这类2浙江工业大学硕士学位论文算法的计算费用较高，但随着计算机硬件技术的飞速发展，已经不再是制约因素。工程系统中存在大量的复杂的非线性的优化问题，而且其中很多问题不满足可微性要求，难以用传统的优化方法来有效解决，而进化算法则可以较好地求解这类优化问题。因此，进化算法逐渐被广泛应用到优化领域。1 2 进化算法概述1 2 1 进化算法的产生生命科学与工程科学的相互交叉、相互渗透与相互促进是近代科学发展的一个显著特点。2 0 世纪中叶以来，生物学的进化论逐渐被推广应用于工程技术，形成一种新型的计算方法进化算法( e a ) ，又称进化计算( e v o l u t i o n a r yc o m p u t a t i o n ，e c ) 。进化计算的研究开始于2 0 世纪5 0 年代，当时几个计算机领域的科学家独立地开始研究进化系统，其思想是将自然界中的进化过程引入工程研究领域以解决工程中的优化问题。依照达尔文的自然选择和孟德尔的遗传变异理论，生物的进化是遵从“生存竞争，优胜劣汰 的原则，通过繁殖、变异、竞争、选择来实现的，进化计算就是建立在上述生物模型基础上的随机搜索技术嘲。进化算法仿效生物学中进化和遗传的过程，采用某种简单编码来表示各种复杂的结构，并将每个编码称之为一个染色体个体，一定数目的个体组成了种群，通过对种群中的每个个体进行一些遗传操作来模拟进化过程，最终获得一些具有较高性能指标的编码。进化算法中常用的遗传操作有选择、交叉和变异等，其中变异是模拟自然界中生物遗传物质的变异，使个体相互之间有区别，为群体的进化和发展创造了条件；交叉是模拟有性生殖过程中的染色体交换过程，使父代个体部分结构重组而生成新个体；选择则是模拟自然界的优胜劣汰过程，从群体中选择优胜个体，淘汰劣质的个体，决定了进化方向。起初研究的进化算法主要包括三个分支：遗传算法( g e n e t i ca l g o r i t h m ，g a ) 、进化策略( e v o l u t i o n a r ys t r a t e g i e s ，e s ) 、进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) ，这三个分支是彼此独立发展起来的，形成进化算法的三种典型算法。美国密歇根大学的j o h nh h o l l a n d 教授针对机器学习问题于1 9 7 5 年提出遗传算法 6 1 ，后由k d ej o n g ，j g r e f e n s t e t t e ，d g o l d b e r g 和l d a v i s 等人进行了改进【 0 1 ；美国科学家l a w r e n c ej f o g e l 等人针对优化模型系统于1 9 6 6 年提出进化规划【1 1 1 ；德国科学家i n g or e c h e n b e r g 等人针对数值优化问题于1 9 7 3 年提出进化策略【1 2 1 。这三种典型算法均起源于达尔文的进化论，在模拟生物进化机制提高计算机求解问题能力的目标和基本思路上是一致的，但是它们的执行策略是有差别3浙江工业大学硕士学位论文的，其中最明显的差别是采用的选择方式不同：遗传算法采用随机型的轮盘赌操作，适应度大的个体被选中的可能性大，适应度小的个体被选中的可能性小，但有时也会“破例入选：进化策略采用确定型操作，它严格按照适应度大小选择，适应度大的个体1 0 0 地被保留，适应度小的个体1 0 0 地被淘汰；进化规划的选择方式界于上述两者之间，它采用g - 竞争选择法，也是一种随机型操作，总体上优良个体入选的可能性较大，但是由于测试群体g 每次都是随机选择的，当g 个个体都不甚好时，则较差的个体可能因得分高而入选。随着三种算法之间相互交流的深入，它们之间相互借鉴、相互渗透，其发展有逐渐融合的趋势。近年来，世界各国的许多研究者加入了该行列研究，对进化算法不断改进，并应用于各种优化问题【协1 6 1 。我国有关进化算法的研究从2 0 世纪9 0 年代以来一直处于不断上升的时期，特别是近年来，进化算法的应用在许多领域取得了令人瞩目的成果，国际刊物上发表的学术文章【1 刀、关于进化算法的专著陆续出现【1 s - , 2 。但是随着研究的深入，进化算法在解决优化问题中也出现了许多新的困难圈。1 2 2 进化算法的优越性性与传统优化方法相比，进化算法具有明显的优越性，主要表现在以下几个方面。( 1 ) 进化算法对问题的整个参数空间给出一种编码方案，而不是对问题本身的具体参数进行处理。因此，进化算法不依赖于具体问题，适用范围比较广。( 2 ) 进化算法的搜索过程是从一群初始点开始搜索，而不是从单一的初始点开始搜索。这样，其获得全局最优解的概率大大提高了。( 3 ) 进化算法进行搜索时用到的是目标函数的信息，而不是用目标函数的导数信息或其他与具体问题有关的特殊领域的知识，具有良好的普适性。( 4 ) 进化算法在进行搜索中采用的是随机变换规则，而不是确定性的规则，具有一定的自适应性。1 2 3 进化算法的局限性由于进化算法是模拟生物进化过程的一种随机优化算法，因此进化算法在求解优化问题时存在一定的局限性，主要体现在以下几个方面。( 1 ) 过早收敛。由于进化算法中选择和交叉算子的作用，造成一些优秀基因过早丢失，从而限制了搜索范围，使得搜索只能在局部范围内找到最优解，而不能得到满意的全局最4浙江工业大学硕士学位论文优解。( 2 ) 较差的局部搜索能力。进化算法在局部搜索能力不如爬山法，模拟退火等，当它搜索到最优解附近时，无法精确的确定最优解的位置，也就是说，它在局部搜索空间不具备微调的能力。( 3 ) 难以得到精确解。进化算法在模拟自然进化过程中存在众多随机因素，因而通常得到的是问题的近似解或满意解，而非精确解。( 4 ) 参数确定随机性大。进化算法中的参数如何选取才能得到最优结果，一直是难解决的问题，最明显的是群体规模与算法收敛速度难以取得很好的平衡。1 3 量子进化算法的产生背景研究表明【2 3 1 ，在求解复杂优化问题的过程中经常会遇到两个棘手问题：一是大规模的问题常常需要大量的计算，求解时需要占用较长的时间资源；二是由于存在较多的局部最优解，所求的解常常会陷入某个局部最优解。要解决这两个问题，需要寻找一种具有快速搜索全局最优解的优化算法。进化算法在求解优化问题的局限性暴露出其本身的缺陷，由于自然进化和生命现象的不可知性，进化算法不可避免的存在概率算法的缺陷收敛问题，包括收敛速度慢和未成熟收敛。为了保证算法的全局收敛性，就需要维持种群中个体的多样性，避免有效基因的丢失；为了加快收敛速度，就需要增加选择压力使种群较快地向最优状态转移，这又将减少种群的多样性，陷入局部极值点。种群多样性和选择压力不易同时实现成为进化算法解决优化问题的瓶劲，至今难以很好地解决 2 2 1 。但是，人们对求解优化问题方法的探索从未停止过：一方面，人们经过分析传统进化算法，发现它没有利用进化中未成熟优良子群体所提供的信息，因而限制了进化速度。因此，研究者尝试采用特定问题的启发式知识来人为地指导约束进化，以此改进进化算法。事实证明，在进化中引入好的引导机制可以增强算法的智能性，提高搜索效率，从而改善算法的早熟和收敛速度问题，但是过程比较复杂1 2 4 - 2 6 。另一方面，人们开始探索寻求能够在收敛速度和种群多样性上取得平衡，具有快速收敛到全局最优解的新型算法。量子信息学是二十世纪诞生的一门新兴学科，是量子力学和经典信息学的交叉学科。量子信息学的研究不断暴出惊人的结果，揭示出超越经典信息学与量子力学两个理论体系本身所包含内容的预想不到的全新概念，量子计算就是其中最为重要的概念之一。1 9 8 2 年b e n i o f 和f e y n m a n 发现了将量子力学系统用于推理计算的可能，并进一步提出量子计算的s浙江工业大学硕士学位论文概念阴阳；1 9 8 5 年d e u t s c h 提出第一个量子计算模型1 2 9 ；1 9 9 4 年s h o r 提出了离散对数问题和大整数质因子分解问题的量子算法，证明了这两个重要且复杂的问题属于b q p 类【3 1 1 。s h o r 算法极大地促进了量子计算的发展，使人们第一次清楚地看到了量子计算独具优势的重要应用前景。量子计算从本质上改变了传统的计算理念，它利用量子叠加性、纠缠性和相干性实现量子的并行计算，能极大地加快对海量信息处理的速度，使得大规模复杂问题能够在有限的指定时间内完成。量子计算的独特计算性能吸引了全世界研究者的注意。在上述背景下，一种新型的启发式算法量子进化算法( 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 ) 应运而生。量子进化算法的研究开始于上个世纪九十年代，a n a r a y a n a n和m m o o r e 首先将遗传算法与量子理论相结合，于1 9 9 6 年提出了量子遗传算法的概念【3 2 】。k u k - h y u nh a n 和j o n g - h w a nk i m 在2 0 0 0 年提出了一种遗传量子算法1 3 3 】，后来他们在遗传量子算法的基础上于2 0 0 2 年提出了量子进化算法，并在优化问题上取得了可喜的成果刚。由于量子进化算法与进化算法相比，能够更容易的在探索与开发之间取得平衡，具有种群规模小、收敛速度较快、全局寻优能力强的优点，世界各国的研究者纷纷投入该领域研究。在我国，量子进化算法也得到发展，扩展了应用领域【3 ”刀。目前量子进化算法已经应用于数值优化d ”9 】、组合优化【4 1 1 、信号处理优化等领域1 4 2 4 3 1 。量子进化算法是量子计算和进化算法相融合的产物，已成为了解决优化问题的一种新方法，该算法利用量子计算的一些概念和理论，如量子位、量子叠加态等，使用量子比特编码染色体，这种概率幅表示可以使一个量子染色体同时表征多个状态的信息，用量子门对叠加态的作用作为主要进化操作，这样能够保持种群多样性和避免选择压力，而且当前最优个体的信息能够很容易的用来引导变异，使得种群以大概率向着优良模式进化，使用染色体交叉、量子位变异等操作，能够避免种群陷于局部最优解，有效防止早熟。因此在求解优化问题上，量子进化算法在收敛速度、寻优能力方面都要优于进化算法，这种崭新的优化方法，具有很大的生命力和研究价值。目前对量子进化算法的理论和应用研究还很不成熟，算法理论研究还没有其他优化算法( 如进化算法等) 普及，有待进一步深入，算法在某些优化领域中的应用( 如动态优化等) 还几乎空白，需要进一步推广。改进算法策略、拓展应用领域是今后研究量子进化算法的方向。6浙江工业大学硕士学位论文1 4 本文的主要研究内容及结构安排本文在分析总结已有研究的基础上，进一步研究了量子进化算法，提出两种改进策略，并将其应用于q o s 组播路由和网络入侵检测中。论文共分为六章，结构安排如下：第一章为绪论。在简单分析了优化问题和优化方法以及进化算法的产生和进化算法在求解优化问题的优点、局限性的基础上，介绍了量子进化算法的产生背景以及已有的研究成果。第二章分析总结了量子进化算法。首先介绍了量子计算的一些基本概念和量子计算的特性，然后分析了量子进化算法的基本要素，并总结了量子进化算法的基本流程。第三章提出了两种改进量子进化算法。针对量子进化算法中量子旋转门旋转角调整策略的不足，提出了应用于单种群优化和多种群并行优化的两种旋转角调整策略，并通过五个典型复杂函数对改进后的算法性能进行测试。结果表明：改进量子进化算法的收敛速度和寻优能力均优于量子进化算法和进化算法。第四章研究了量子进化算法在q o s 组播路由中的应用。首先，在分析了q o s 组播路由相关理论的基础上构造出一种通用的q o s 组播树模型，并给出求解包含延时、延时抖动、带宽、包丢失率和费用约束的q o s 组播路由问题的数学描述；然后设计了一种求解该问题的改进量子进化算法，并通过实验与量子进化算法、进化算法比较，结果表明改进算法的路由性能优于其它两种算法。第五章研究了量子进化算法在网络入侵检测中的应用。首先在分析了入侵检测的必要性和基本原理后，得出入侵检测的核心是入侵特征库的优化，并进一步分析了进化算法在优化网络入侵特征库的局限性，从而引入量子进化算法；然后设计了一种优化网络入侵特征库的改进量子进化算法，并通过实验与量子进化算法、进化算法比较，结果表明改进算法的检测性能优于其它两种算法。第六章是结论与展望。对全文作了简要总结，并提出下一步工作展望。7浙江工业大学硕士学位论文第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 ) 是量子计算和进化算法相融合的一种新的优化算法。它以量子计算的一些概念和理论为基础，用量子位编码来表示染色体，通过量子更新、量子交叉。量子变异、个体选择等操作来完成进化搜索，与进化算法相比，能够更容易在探索与开发之间取得平衡，具有种群规模小、收敛速度较快、全局寻优能力强的特点。2 1 量子计算基础2 1 1 基本概念( 1 ) 量子量子最早出现在光量子理论中，是微观系统中能量的一个力学单位嗍。现代物理将微观世界中所有的微观粒子( 如光子、电子、原子等) 统称为量子。( 2 ) 量子信息利用微观粒子状态表示的信息就称为量子信息嗍。相对于量子信息而言，s h a 皿所定义的信息概念，称为经典信息。( 3 ) 量子比特相对于经典信息的基本存储单元比特( b i t ) ，量子信息的基本存储单元称为量子比特( q u b i t ) 1 4 5 1 。在经典信息处理过程中，1 个比特的状态可以由两个确定的经典状态( 如电压的高低)l 和0 表示。但是实验已经证明嗍，对于量子信息而言，1 个量子比特的状态不但可以处于两个极化状态( 如电子的自旋向上和自旋向下) ，而且还可以处于两者的任意中间态。在量子力学中，用迪拉克标记“1 ) ( 称为右矢或右向量) 来表示量子状态，量子比特的两个极化状态( 也称为基态或本征态) 可以表示为：l o ) 和1 1 ) ，分别对应于经典状态的。和l 。量子比特的重要特性在于一个量子比特能够处在既不是1 0 ) 也不是1 1 ) 的状态上，而是8浙江工业大学硕士学位论文可以处于状态i o ) 和1 1 ) 的一个线性组合的所谓中间状态之上，通常称为状态l o ) 和1 1 ) 的叠加态，一个量子比特的状态可表示为：l 力= 口i o ) + 纠1 )( 2 一1 )其中，口、代表相应状态概率幅，为任意复数，且满足：p 1 2 + i p l 2 = 1 ( 2 - 2 )其中，h 2 、i 剧2 分别表示量子比特处于状态i o ) 和1 1 ) 的概率。( 2 1 ) 式中的线性组合态口l o ) + 剧1 ) 也可以用线性代数中的矩阵圈表示。( 4 ) 多量子比特对两个经典比特而言，共有四种可能状态：0 0 、0 1 、1 0 和1 1 。相应地，对两个量子比特而言有四个基态：i o o ) 、1 0 1 ) 、i l o ) 和1 1 1 ) ，当然，这一对量子比特也可以处于这四个基态的叠加态，因此这一对量子比特的状态可以表示为：l 神= 口1 0 0 ) + 1 0 1 ) + t r ，o l l 0 ) + 。1 1 1 ) ( 2 - 3 )其中，、。、q o 、q 。代表相应状态概率幅，为任意复数，且满足归一化条件：i 卜l 。卜l q 。1 2 + i 嵋。1 2 - l ( 2 - 4 )更一般地，对于刀个量子比特组成的系统，系统的状态可以表示为：i 力= q i 仍)( 2 - 5 )其中，q 代表相应状态概率幅，为任意复数，且满足归一化条件： e i c , 1 2 = 1( 2 6 )( 5 ) 量子逻辑门量子逻辑门( 又称量子门) 是实现量子计算的逻辑装置，其作用是将输入的量子比特转换为另一种状态输出。在量子计算理论中，量子门可以用矩阵形式表示，任何一个幺正矩阵都可以指定为有效的量子逻辑门【4 7 】。2 1 2 量子计算的特性( 1 ) 状态的叠加9浙江工业大学硕= i ：学位论文在经典计算机中，基本信息单位为比特，运算对象是经典比特序列。与此类似，在量子计算机中，基本信息单位是量子比特，运算对象是量子比特序列。与经典比特不同，一个量子比特可以随机地存在于基态i o ) 和1 1 ) 的任意叠加状态。因此，对于经典计算机中的一个刀位普通寄存器，存储n 位经典比特时，这刀位经典比特处于一个唯一的状态中，即该寄存器只表示一个刀位二进制数；而对于量子计算机中的一个刀位量子寄存器，存储刀位量子比特时，由( 2 5 ) 式可知，这一位量子比特可处于2 4 个基态的叠加态中，它们各以一定的概率同时存在，即该寄存器可同时表示2 一个刀位二进制数，当对这个寄存器进行测量时，以l c , 1 2 的概率获得一个对应的疗位二进制数。( 2 ) 状态的相干量子计算的一个主要原理是对处于叠加状态的量子态的各个基态，通过量子门的作用发生干涉，从而改变它们之间的相对相位。例如一个量子比特处于如下的叠加态：i 妨= 石2l o ) + 万11 1 )( 2 7 )假设量子门u = 万1 1 二1 作用于上式量子态l 伊) 上，则两者作用的结果是：”怙忑1 1 廿硼= 帮+ 扣协8 )从( 2 8 ) 式结果可以看出，基态i o ) 的概率幅增大，而基态1 1 ) 的概率幅减小。如果一个量子系统处于其基态的线性叠加态，我们称该系统是相干的，当一个相干的系统和它周围的环境发生相互作用( 测量) 时，线性叠加就会消失，而以一定的概率塌缩到某个相应基态。例如，对( 2 - 8 ) 式p ) 进行测量，其塌缩到基态1 0 的概率是o 9 ，这个过程称之为消相干【铝】。( 3 ) 状态的纠缠量子态的纠缠是量子系统内各子系统或各自由度之间关联的属性【4 9 l 。量子态的纠缠反映在概率幅不相乘上，当量子比特列的叠加状态无法用各量子比特的张量乘积表示时，这种叠加状态就称为量子纠缠状态。例如有如下三个量子叠加态：峨= 万11 0 0 ) + 疆11 0 1 )( 2 9 )1 0浙江工业大学硕士学位论文忱= 万1l 。o ) + 万11 1 1 )( 2 1 0 )i 西c = 万11 0 1 ) + 万11 1 0 )( 2 1 1 )上述三个量子态中，( 2 9 ) 式可以表示成如下的张量积：忱= 西11 0 0 ) + 疆i1 0 1 ) = i 。) 。噎1 0 ) + 疆i1 1 ) )( 2 1 2 )而对于( 2 1 0 ) 式和( 2 i i ) 式，无论采用怎样的方法都无法写成两个量子比特的张量积，因此i 伊) 曰和l 磅c 均为纠缠态。量子的纠缠态对量子计算十分重要，当多个量子位处于纠缠态时，对部分量子位的态的测量将影响其它量子位的态的测量。例如测量( 2 一1 0 ) 式的i 矿) 丑时，测量一个量子位的态，将使另一个量子位的态与之相同；测量( 2 - 1 1 ) 式的l 西c 时，测量一个量子位的态，将使另一个量子位的态与之相反；但测量( 2 9 ) 式的l 妨一时，对右边那位的态不管如何测量，左边那位的态总是为i o ) 。( 4 ) 量子并行性量子并行计算的能力来自于量子态的可叠加性，量子门对h i l l ) e r t 空间( 向量空间) 中处于叠加态的量子态的作用将同时作用于所有基态上。例如，对由刀位量子比特构成的叠加态卜) = 亡i 而) 进行量子门作用，由于砌b 酣空间是线性的，因此：v zi = o12 - - i12 - - l12 - q1 12 _ - 1( 方荟i 而) 户( 赤荟i 毛，o ) 户方荟l 而，0 ) 2 万善k 厂瓴) ) ( 2 - 1 3 )( 2 - l 3 ) 式表示通过量子门的作用：量子态古篓i 而) 一砉善i 毛，厂“) ) ，即对处于叠加态的l x ) 进行变换，可以产生所有z 的i 厂o ) ) ，量子计算的这种特性称为量子并行性1 5 0 】。在经典计算中，计算所有z 【0 ，2 一一l 】的八力，需要2 “次运算，而在量子计算中，只要一次变换就可完成。浙江工业大学硕士学位论文2 2 量子进化算法2 2 1 基本要素( 1 ) 量子比特编码进化算法中常用的编码方式有二进制编码、十进制编码和符号编码，量子进化算法不是采用这种确定的编码方式，而是使用一种新颖的基于量子比特的概率编码方式。用量子比特编码的染色体称作量子染色体( 又称为个体) ，一个有m 个量子比特编码而成的量子染色体可以表示成如下形式：g = 鼢脚( 2 1 4 )且满足：k 1 2 + l p , 1 2 = 1 ，= - 1 , 2 ，3 ，朋。这样的一个个体处在m 个量子比特的叠加状态，可同时代表2 肼种状态。例如，一个具有如下概率幅的3 量子比特个体：搽( 2 1 5 )由第一节分析可得到该个体的状态。司以表不为：等l o o o + 1 0 0 1 ) + 萼l o l o ) + 扣) + 知州1 埘) + 知岫) 亿此个体取到1 0 0 0 ) 、1 0 0 1 ) 、1 0 1 0 ) 、1 0 11 ) 、l 1 0 0 ) 、1 1 0 1 ) 、1 1 1 0 ) 、1 1 11 ) 状态的概率分别为：三、上、三、三、。三、三、三、z 1 ，对忐于级典的二进制编码，上述8 1 w - 鬟w - - a s0 个状态分t 洲p j一、一、一、一、一、一、一、一， 1j兴口了一j z 巾v 钠闩，上地l 饥心y j1 61 61 61 61 61 61 61 6对应0 0 0 、0 0 1 、0 1 0 、0 1 1 、1 0 0 、1 0 l 、1 1 0 、1 1 1 ，代表8 个个体。在量子进化算法中，若干个量子染色体就构成了种群，第，代种群可表示为q ( f ) = k 。，g ：，一 吼 ，其中刀为种群规模，f 为进化代数，q 为第，代种群中第歹个量子染色体，具体形式可以描述为：g 二= 盼h 二；：i协m其中，m 表示量子比特的个数，即量子染色体的长度，户1 ，2 ，刀。由此可知，采用量子比特的编码方式，一个染色体可以表征任意的线性叠加态，而进化算法的编码方式只能表示一个具体的状态，所以q e a 比e a 更容易保持种群的多样性。浙江工业大学硕：i ：学位论文而且随着h 2 或例2 逐渐靠近。或l ，量子染色体逐渐收敛到单一的状态，种群的多样性也随之减小，算法收敛。( 2 ) 量子观测量子观测即对种群q ( t ) 中各个体的一次测量。量子理论指出，对一个处于任意叠加态的量子比特进行测量时，能使该量子比特以某一概率值( h 2 或i 剧2 ) 退化到状态“0 或“1 一上，因此量子观测能使每个个体从不确定状态转化为确定状态，即观测态尸( f ) 。观测态种群p ( f ) 的形式为：p o ) = p l t ，p 2 1 p 。“( 2 - 1 8 )其中，观测态个体p j 。( 户1 2 刀) 是长度为m 的二进制串( 而x 2 ) ，它是根据概率幅的取值情况构造而成。一般构造方法为：随机产生【o ，l 】之间的一个数吒( 芦l 2 历)( 岖吒s 1 ) ，若芝k 1 2 ，t 取l ，否则取0 ( 3 ) 量子评价量子评价即对观测态个体的优劣进行评价，个体的优劣一般用适应度表示，而量子评价过程就是根据问题的适应度函数计算个体的适应度值。通常应根据待求解问题的要求设计适应度函数，最直观的方法是直接将待求解问题的目标函数转化为适应度函数。一般地，适应度函数的设计应尽可能满足以下条件：条件l ：单值、连续、非负、最大化，这是设计适应度函数的基本条件。条件2 ：合理、一致性，即要求适应度函数能反映对应解的优劣程度。条件3 ：计算量小，即要求适应度函数应尽可能简单，这样可以减少计算时间和空间上的复杂性，降低成本。适应度是衡量个体优劣的标志，它是执行算法“优胜劣汰 的依据，也是驱使算法搜索寻优的动力。因此，适应度函数设计的好坏，将影响算法的收敛速度和寻优能力。( 4 ) 量子进化量子进化是指种群进化机制，通常包括量子更新、量子交叉、量子变异、个体选择等进化手段。目前，对这些进化手段在种群进化中的主次地位的划定还存在争议，大多数学者主张以量子更新为种群进化的主要手段，量子交叉、量子变异、个体选择为辅助进化手段。1 3浙江工业大学硕士学位论文a ) 量子更新量子更新是通过量子门的作用转换量子位状态的过程，即将量子门作用于量子叠加态或纠缠态的基态，使其相互干涉，相位发生改变，从而改变各基态的概率幅。量子更新操作的关键是设计合适的量子门，量子门的种类很多，q e a 中主要采用的是量子旋转门。为了计算方便，通常将问题转换为两态表示，即0 、l 编码问题，从而设计用旋转角度表示的简单量子旋转门，其矩阵形式表示如下：u c p d 嚣2 嚣泣其中，0 为旋转角度。染色体的更新通过量子位的更新来完成，过程如下：盼咿捌= p l s m 鸱c o , ；捌嘲( 2 圳其中，嘲为染色体中第z 个量子位，匮 为更新后染色体中第z 个量子位。b = s 屈) q ，在更新过程中，旋转角包的大小和符号起着关键作用，包的调整策略可以通过表2 1 得到。表2 - 1 旋转角通用调摧策略啦届)毛b e s t jf ( x ) f ( b e s t )a o ,c l i p 部风p 冈a , - - - op 部00f a l s e0o0o0oot r u eo000o0l脚0o00oolt r u eo 0 5 0 兀l士l士l0lo瑚0 0 1 0 兀- l+ l士l0l0t r u eo 0 2 5 死+ l- lo4 - 11lf 酊0 0 0 5 z+ llo士ll1u u eo 0 2 5 x+ ll0士1表2 - l 中，毛为当前染色体的第i 位；b e s t ，为当前最优染色体的第i 位；厂( 功为当前个体的适应度值；f ( b e s t ) 为当前最优个体的适应度值；s ( a ；届) 表示旋转的方向，保证算法1 4浙江工业大学硕士学位论文的收敛；a o , 表示旋转角度的步长，控制算法收敛的速度，该值太大容易使算法陷入局部最优解，反之则会使更新操作处于停滞状态，目前该值大小的设定缺乏理论上的指导，应根据具体问题通过实验取得，一般控制在0 0 0 1 兀- 0 0 5 z 之间为斟5 1 】，表2 1 中的a o , 值是目前常用的一组值。这种调整策略能够使算法收敛到具有更高适应度的染色体，我们可以通过一个直观的图形( 图2 - 1 ) 来说明：例如当毛= o ，b e s t j = l ，厂(