（计算机应用技术专业论文）量子克隆进化算法研究.pdf

摘要 摘要 人类已步入信息时代，物质、能量、信息是人类赖以生存的三大资源。以计 算机为核心的现代信息处理和以数字化通信为特征的现代信息传输正在紧密地结 合起来，将人类带入到未来崭新的信息时代。作为智能信息科学发展中有生命活 力的一个研究方向，计算智能已经引起了广泛的关注。近年来普遍认为：计算智 能是在神经网络、模糊系统、进化计算三个分支发展相对成熟的基础上，相互融 合而形成的一种新的计算方法。事实上，“计算智能”( 或“智能计算”) 是一个 内蕴相当丰富的概念，长期以来，分布于世界各地的计算机科研人员都在因循不 同的方向、通过各异的途径来设法接近这一概念的实质。实际上，计算智能是一 门跨越包括物理学、数学、计算机科学、通讯、生理学、进化理论和心理学等学 科在内的深奥科学。因此，引入各领域的有效知识对它进行研究，就能为建立一 种更统一的智能系统设计和优化方法提供基础，也是计算智能一个必然的发展趋 势。本文研究了一种将量子理论运用到进化计算当中并结合人工免疫系统中的克 隆选择学说的量子克隆进化算法，提出了它的理论框架，证明了其收敛性，并讨 论了它的应用。理论分析和仿真结果证明：量子克隆进化算法是全局收敛的，且 具有快速进化求优的能力。本文主要内容概括如下： ( 1 ) 本文将量子理论与人工免疫系统中的克隆选择学说思想相结合提出了 一种新颖的学习算法量子克隆进化算法，证明了该算法收敛性， 仿真试验表明：该算法是可行有效的。给出了克隆算子的具体实现方 法： ( 2 ) 在分析进化算法的不足和瓶颈问题后，提出了量子克隆进化计算的理 论框架，其中包括：量子克隆遗传算法、量子克隆进化策略、量子克 隆进化规划。 关键词：量子染色体概率克隆算子混沌变异全局收敛 a b s t r a c t a b s t r a c t t h e2 0 “c e n t u r yi sa r e s p l e n d e n ta g e w i t l la na l l t i m ed e v e l o p m e n t o f t e c h n o l o g ya n d c i v i l i z a t i o n m a t t e r , e n e r g ya n dc o m m u n i c a t i o n i st h r e ek e y t o p i c s c o m p u t e r sc e n t e r e d m o d e mi n f o r m a t i o n p r o c e s s i n g a n d d i g i t a l i n f o r m a t i o nc h a r a c t e r i z e dm o d e m i n f o r m a t i o nt r a n s m i s s i o na r ei n p r o c e s s o ft h e i rc l o s ec o m b i n a t i o n a sa na c t i v e r e s e a r c hd i r e c t i o no f i n t e l l i g e n ti n f o r m a t i o np r o c e s s i n g ，c o m p u t a t i o n a li n t e l l i g e n c e ( c i ) h a sa t t r a c t e dm a n ys c i e n t i s t s a t t e n t i o n i nr e c e n ty e a r s ，c ii sg e n e r a l l yc o n s i d e r e da sa n e w c o m p u t a t i o n a lm e t h o d b a s e do nt h ef u l ld e v e l o p m e n to fi t st h r e eb r a n c h e s - - n e u r a l n e t w o r k ( n n ) ，f u z z ys y s t e m ( f s ) a n de v o l u t i o n a r yc o m p u t a t i o n ( e c ) i nf a c t ，c i i n c l u d e sa b u n d a n ti m p l i c a t i o n s o v e ral o n gp e r i o d ，t h ew o r l d w i d er e s e a r c h e r sa r e g o i n gi nd i f f e r e n td i r e c t i o n sa n du s i n g v a r i o u sm e t h o d st oa p p r o a c ht h ee s s e n c eo fc i n a t u r a l l y , c ii sa na b s t r a c ts u b j e c ts p a n n i n gp h y s i c s ，m a t h e m a t i c s ，c o m p u t e rs c i e n c e ， c o m m u n i c a t i o n ，p h y s i o l o g y , e v o l u t i o n a n d p s y c h o l o g y a c c o r d i n g l y , u s i n g t h e e x t r a c t e dk n o w l e d g eo ft h e s es u b j e c t sc a nm a k ead e e p e r i n v e s t i g a t i o ni n t oc ia n dg i v e ab a s i sf o rt h eo p t i m i z a t i o n ，a l s oh e l pt ob u i l du pam o r eu n i f o r m l yi n t e l l i g e n tm e t h o d o fs y s t e md e s i g n i nt h i sp a p e r , af r a m eo fq u a n t u mc l o n a le v o l u t i o n a r ya l g o r i t h mi s p r e s e n t e db yt h ec o m b i n i n go fq u a n t u mt h e o r y w i t l lt h ec l o n a ls e l e c t i o n t h e o r yi n a r t i f i c i a li m m u n e s y s t e m ( a i s ) i t sa l g o r i t h m sa r eg i v e n i nd e t a i la n dt h e i rc o n v e r g e n c e s a r ep r o v e d b o t ht h et h e o r ya n a l y s i sa n ds i m u l a t i o n sp r o v ei t ss u p e r i o r i t y t h ec o n t e n t o f t h i sp a p e ri n c l u d e s ： 夺t h ec l o n a ls e l e c t i o nt h e o r yi na i sa n dt h ea p p l i c a t i o no f t h ec l o n eo p e r a t o ra r e p r e s e n ti nd e t a i li nt h i sp a p e r 夺b a s e do nt h e a n a l y s i s o ft h eb o t t l e n e c ko ft h e e v o l u t i o n a r ya l g o r i t h m ，t h e q u a n t u mc l o n a le v o l u t i o n a r ya l g o r i t h mi sp r e s e n t e d i ti n c l u d e st h r e ep a r t s ：t h eq u a n t u m c l o n a lg e n e t i ca l g o r i t h m s ，t h eq u a n t u mc l o n a le v o l u t i o n a r ys t r a t e g i e sa n dt h eq u a n t u m c l o n a le v o l u t i o n a r yp r o g r a m m i n g k e y w o r d ：q u a n t u mc h r o m o s o m ep r o b a b i l i t y c l o n a lo p e r a t o r c h a o sm u t a t i o nt h e g l o b a lc o n v e r g e n c e 创新性声明 y 5 8 3 3 1 0 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：连妞翅日期兰塑竺! ：主 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文( 与学位论文相关) 工作成果时署名单位仍然为 西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学 校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保 存论文。( 保密的论文在解密后遵守此规定) 本人授权西安电子科技大学图书馆保存学位论文，本学位论文属于( 保密 级别) ，在年樱密后适用本授权书，并同意将论文在互联网上发布。 本人签名：礁塑翅 日期三煎业：i ：互 导师签名： 垒i 互。日期生! 至! ! ：二 第一章绪论 第一章绪论 计算是人类思维能力的最重要的方面之一，计算能力的提高与人类文明进步 息息相关。从古老的算盘到现代的超级计算机，人类的计算技术实现了革命性的 突破。综观当今，计算机的广泛应用已经并且仍在继续改变着我们的世界。一方 面，人们为计算机的神奇能力所倾倒。另一方面，人们也为它无力完全满足实际 的需要而烦恼。因此，加速计算机的运算速度已提高计算机的运算能力成为计算 机科学的中心任务之一。 如何加快计算机的运算能力呢? 这一问题大体可以从两个方面着手解决。一 是制造更为先进的计算机硬件，另- - n 是设计恰当的计算机运算流程，后者可以 称之为“算法”。智能计算的提出为我们寻找快速算法提供了新思路。近年来普遍 认为：计算智能( c o m p u t a t i o n a li n t e l l i g e n c e - - c i ) 是在神经网络( n e p a ln e t w o r k n n ) 、模糊系统( f u z z ys y s t e m - - f s ) 、进化计算( e v o l u t i o n a r yc o m p u t a t i o n - - e c ) 三个分支发展相对成熟的基础上，相互融合而形成的一种新的计算方法。事实上， “计算智能”( 或“智能计算”) 是一个内蕴相当丰富的概念，长期以来，分布于世 界各地的计算机科研人员都在因循不同的方向、通过各异的途径来设法接近这一 概念的实质。实际上，计算智能是一门跨越包括物理学、数学、计算机科学、电 子机械、通讯、生理学、进化理论和心理学等学科在内的深奥科学。因此，将各 领域的知识有效的引入到计算智能中研究，就能为建立一种更统一的智能系统设 计和优化方法提供基础，因此也是计算智能一个必然的发展趋势。 量子计算( q u a n t u mc o m p u t a t i o n - - q c ) 的研究开始于1 9 8 2 年计算首先被诺 贝尔物理学奖获得者r i c h a r df e y n m a n 看成是一个物理过程之后，现在它已经成为 当今世界各国紧密跟踪的前沿学科之一。量子计算的并行性、指数级存储容量和 指数加速特征展示了其强大的运算能力1 2 j l ”，1 9 9 4 年p e t e rs h o r 就提出了分解大数 质因子的量子算法，它仅需几分钟就可以完成用1 6 0 0 台经典计算机需要2 5 0 天才 能完成的r s a 一1 2 9 问题( 一种公钥密码系统) ，使当前公认为最安全的、经典计 算机不能破译的公钥系统r s a 可以用量子计算机容易的破译【4 】：1 9 9 6 年，g r o v e r 提出量子搜索算法，证明量子计算机在穷尽搜索问题中比经典计算机有d f ) 的 加速【5 】j 用此算法，可以仅用2 亿步代替经典计算机的大约3 5 1 0 “步，破译广泛 使用的5 6 位数据编码标准d e s ( 一种被用于保护银行间和其他方面金融事务的标 准) 。目前量子计算已经在保密通信、密码系统、数据库搜索等领域得到成功的应 用。美国早在1 9 9 9 年就研制出量子计算机运算器的雏形两l ，计算专家们更是预言， 随着量子计算研究中一个个难题的解决，本世纪将出现并运用比现在的电子计算 2量子克隆进化算法研究 机的运算器速度快1 0 0 0 倍以上的量子计算机。 虽然建造量子计算机理论上和原则上没有根本的障碍，但在实际上和技术上 仍然是个巨大的挑战，尤其是实用的、具备一定规模的量子计算实现尚在探索之 中1 7 ”，然而关于量子计算的更为永恒和令人激动的理由是它所导致的思考物理学 基本定律的心得，以及它为其他科学技术所带来的有创见的方法。例如，计算智 能的研究也可以建立在一个物理的基础之上，量子机理和特性会为计算智能的研 究另辟蹊径，有效利用量子理论的原理和概念，将会在应用中取得明显优于传统 智能计算模型的结果1 9 j 。因此量子计算智能( q u a n t u mc o m p u t a t i o n a li n t e l l i g e n c e - q c i ) 的出现结合了量子计算和传统智能计算各自的优势，具有很高的理论价值 和发展潜力。 1 1 量子计算原理 1 1 1 量子算法 量子计算机的研究是当前信息领域的一个很活跃的课题，量子算法作为控制 量子计算机运行的程序，与经典的计算机程序到底有什么区别昵? 量子算法是相对于经典算法而言的，它最本质的特征就是利用了量子态的叠 加性和相干性，以及量子比特之间的纠缠性，是量子力学直接进入算法领域的产 物，它和其他经典算法最本质的区别就在于它具有量子并行性。我们也可以从 概率算法去认识量子算法，在概率算法中，系统不再处于一个固定的状态，而是 对应于各个可能状态有一个几率，即状态几率矢量。如果知道初始状态几率矢量 和状态转移矩阵，通过状态几率矢量和状态转移矩阵相乘可以得到任何时刻的几 率矢量】。量子算法与此类似，只不过需要考虑量子态的几率幅，因为它们是平 方归一的，所以几率幅度相对于经典几率有倍的放大，状态转移矩阵则用 w a l s h - - h a d a m a r d 变换、旋转相位操作等酉正变换实现【1 2 1 。量子算法得以实现的 前提在于用量子位( q u b i t ) 代替了经典的位( b i t ) 。在量子信息论中，信息的载体 是一个一般的二态量子体系，这个二态的量子体系，可以是一个二能级的原子或 粒子，也可以是一个自旋为以的粒子或具有两个偏振方向的光子，所有这些体系， g - 均被称为量子比特即量子位；区别于经典比特，在量子体系中，一位的信息位是 由两个本征态的任意叠加态所构成即量子比特，例如个h 位二进制的串在量子体 系中就可同时表示2 “个信息，而量子计算机对每个叠加分量( 本征态) 实现的变换 相当于一种经典计算，所有这些经典计算同时完成，并按一定的概率振幅叠加起来， 给出量子计算的结果，这种计算称之为量子并行计算。下面给出详细的定义。 第一章绪论 1 1 2 叠加性 在经典数字计算机中，信息被编码为位( b i t ) 链，1 比特信息就是两种可能情 况中的一种，0 或1 ，假或真，对或错。例如，电容器的板极间的电压可以代表1 比特信息：带电的电容表示1 ，而放电的电容表示0 。在量子计算机中，基本的存 储单元是一个量子位( q u b i t ) ，一个简单的量子位是一个双态系统，例如半自旋或 两能级原子：自旋向上表示0 ，向下表示l ；或者基态代表0 ，激发态代表1 。不 同于经典比特，量子比特不仅可以处于0 或l 的两个状态之一，而且更一般的可 以处于两个状态的任意叠加形式。一个n 位的普通寄存器处于唯一的状态中，而 由量子力学的基本假设，一个n 位的量子寄存器可处于2 ”个基态的相干叠加态i ) 中，即可以同时表示2 ”个数。叠加态和基态的关系可以表示为： 庐) = c ，i 谚) ( 1 1 ) j 式中q 为状态i 谚) 的概率幅，川2 表示妒在受到量子计算机系统和纠缠的测量仪器 观测时坍塌到基态i 西) 的概率，即对应得到结果为i 的概率，因此有： zic,12=1(1-2) 1 1 3 相干性 量子计算的一个主要原理就是：使构成叠加态的各个基态通过量子门的作用 发生干涉，从而改变它们之间的相对相位。如一个叠加态为 = 万2 l o ) + 去1 1 ) = 去( ；) ，设量子门d = 击( ：! 。) 作用其上，则两者的作用 结果是陟) 2 而3 | o ) + 面1 1 1 ) ，可以看到，基态i o ) 的概率幅增大，而1 1 ) 的概率幅 减小。若量子系统| 庐) 处于基态的线性叠加的状态，我们称系统为相干的，当一个 相干的系统和它周围的环境发生相互作用( 测量) 时，线性叠加就会消失，具体 坍塌到某个基态j 而) 的概率由i c f l 2 决定，如对上述渺) 进行测量，其坍塌到l o ) 的概 率为0 9 ，这个过程称之为消相干。g r o v e r 等量子算法主要利用了这一量子机制 1 1 3 1 1 4 量子克隆进化算法研究 1 1 4 纠缠性 量子计算另一个重要的机制是量子纠缠态，它违背我们的直觉。对于发生相 互作用的两个子系统中所存在的一些态，若不能表示成两个子系统态的张量积， 这样的态就称为纠缠态。对处于纠缠态的量子位的某几位进行操作，不但会改变 这些量子位的状态，还会改变与它们相纠缠的其他量子位的状态。在s h o r 算法中 得到量子傅立叶变换所需要的状态时，就用到了这经典量子力学特性【15 1 。量子 计算能够充分实现，也是利用了量子态的纠缠特性。 1 1 5 并行性 在经典计算机中，信息的处理是通过逻辑门进行的。量子寄存器中的量子态 则是通过量子门的作用进行演化，量子门的作用与逻辑电路门类似，在指定基态 的条件下，量子门可以由作用于希尔伯特空间中向量的矩阵来描述，由于量子门 的线性约束，量予门对希尔伯特空间中量子状态的作用将同时作用于所有基态上， 对应到 位量子计算机模型中，相当于同时对2 ”个数进行运算，而任何经典计算 机为了完成相同的任务必须重复2 1 次相同的计算，或者必须使用2 ”个不同的并行 工作的处理器，这就是量子并行性。换言之，量子计算机利用了量子信息的叠加 和纠缠的性质，在使用相同时间和存储量的计算资源时提供了巨大的增益。在s h o r 算法中充分利用了这一点。 1 1 6 研究重点 到目前为止，量子计算机还没有走出实验室的大门。在这种情况下，深入研 究量子算法及其它和其他科学技术之间的相互作用，不断产生具有重要意义的概 念和方法。并形成良好的工具就成为量子信息处理领域的主要发展方向。致力于 经典信息处理研究的科技工作者们也应该开阔思维，量子计算是一种与经典计算 完全不同的全新的计算模式，它所包含的特殊性质正在不断应用到传统理论中去， 成为近年来科学界研究的热点【i “。因此目前的工作可以从以下方面展开： ( 1 ) 深刻领悟现有量子算法的本质，运用到传统算法中去，通过对传统的表示 作一些调整使其具有量子理论的优点，从而实现更为有效的算法。 ( 2 ) 现有的有效的量子算法是很有限的，我们应以现有的量子算法为基础，着 手研究新的应用更广的量子算法来进行信息处理。 ( 3 ) 利用现有的计算条件，尽量模拟量子计算机的真实运算环境，用来验证和 开发新的算法。为以后真正实际的量子计算机的开发和研制提供基础保 障。但是由于量子计算特点所决定的时间空间耗费巨大的问题，现在只能 第一章绪论 模拟有限规模的量子计算。 1 2 量子计算智能的研究进展 量子计算理论用于计算智能早在前几年就已出现，量子计算首先在简单的专 家系统中得到应用，现在它已经应用到更多的方面，例如量子联想记忆，人工神 经网络，模糊逻辑等等。下面我们就详细作一介绍。 1 2 1 基于量子特性的优化算法 o r o v e r 算法是最能体现量子并行性的算法，也是搜索算法中最快的算法。利 用量子计算巨大的并行性它可以很容易的实现对所有可能状态的穷尽搜索，解 决所有“求解困难而验证容易”的n p 问题。 遍历搜索的目的是从一个杂乱无序的集合中找到满足某种要求的元素，要验 证一个元素满足要求容易，但反过来，查找合乎要求的元素则往往要大费周折， 因为这些元素可能并没有按照这种要求有序的进行排列，并且这些元素的数目又 很大，在经典算法中，我们只有逐个的试下去，这也正是“遍历搜索”这一名称 的由来。显然，在经典算法中，运算步骤和被搜索集合元素数成正比。若该集 合中只有一个元素符合要求，为使搜索成功率达到1 0 0 ，一般说来步骤数要接近 ；而在g r o v e r 算法中，搜索成功的运算步骤只与成正比，它对状态空间的快 速搜索是通过概率幅的求反放大实现的。由此可以设想，它对优化问题也能构成 快速搜索。使用改进的g r o v e r 算法可以使它不仅可以解简单的决策问题，而且可 以在并行计算函数值的同时使高函数值状态凸现出来，即解决优化问题，而算法 的参数可以用经典算法学习。 1 2 2 量子人工神经网络 从神经元的m p 模型首先提出至今，人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k a n n ) 的研究已在各个领域得到广泛的应用。几十年来a n n 取得了很大的进展， 但也暴露出了不少问题，主要是因为它是建立在极其简化的神经元模型基础之上 的，随着信息量和信息复杂度的增加，它已无法适应。因此在新的世纪，构建更 加外向的神经网络理论，将神经网络理论赋予更强的数学基础、生物学特征乃至 物理特征是a n n 研究中面临的巨大挑战，也是它发展的最大机会。 一些人提出：正像生物神经系统的研究激发了a n n 的研究工作那样，量子效 应在人类认知领域中也起着重要的作用。从9 0 年代开始，直至目前的一些研究成 果均表明：人脑信息处理的过程可能与量子现象有关。英国o x f o r d 大学p e n r o s e 6量子克隆进化算法研究 教授对量子理论和人脑意识的研究证明了人体内的某些细胞对单个量子敏感，因 此大脑中可能存在量子力学效应；1 9 9 4 年美国a r i z o n a 大学h a m e r o f f 教授指出： 在神经元细胞内架的微管之中或周围，意识是作为一个宏观量子态由量子级事件 相干的一个临界极突现出来的：1 9 9 6 年p e r u s 博士提出：量子波函数的坍塌十分 类似于人脑记忆中的模式重构现象等等【l ”。所有研究结果均表明：量子系统是所 有物理过程的微观系统基础，同样也应该是生物和心理过程的基础：量子系统具 有和生物神经网络相似的动力学特征，因而将a n n 和量子理论结合起来会更好的 模拟人脑的信息处理过程。 量子计算与神经网络的结合是当前人工神经网络理论发展的一个前沿课题， 虽然量子神经网络( q t m n t u mn e u r a ln e t w o r k - - q n n ) 的发展才刚刚起步，但也初露 峥嵘。从p e r u s 最先发表了对量子形式和n n 理论数学相似性的评述开始，目前在 国内外已有不少有关q r c n 的研究成果。m e n n e e r 和n a r a y a n a n 提出了一种将量子 机理中的“多宇宙”论引入网络训练，对应训练集中的每一个样本都有一个神经 网络与之对应，最后得出的网络是这些网络的叠加：b e h r m a n 等人也提出了用量子 点实现q n n 的方法对于每个输入它采用一个量子点，系统按量子机理进行时间 进化，观察则在固定的时问间隔，不同的时间切片作为n n 中隐层的神经元一越 多的时间切片，则越多的隐层单元。q n n 研究主要的代表人物有美国q n n 研究 的权威文图拉博士和马丁内斯、现在巴西的中国学者李伟钢博士和中国科学技术 大学的解光军博士：当前研究的方向大致可分为： ( 1 )量子联想记忆【”l ( 2 )量子竞争学习1 1 9 1 ( 3 )使用量子点的神经网络1 2 0 j ( 4 )具有量子特性的传递函数的传统神经网络【2 1 】 ( 5 )量子h o p f i e l d 网络【2 2 1 1 2 3 基于量子染色体的进化算法 进化算法( e v o l u t i o n a r ya l g o r i t h m - - e a ) 是解决优化问题的种有效方法，包括 遗传算法( g e n e t i c a l g o r i t h m - - g a ) 1 2 ”，进化策略( e v o l u t i o n a r ys t r a t e g y - - e s ) 和进 化规划( e v o l u t i o n a r y p r o g r a m m i n g - - e p ) 。理论上已经证明：它们均能从概率的意 义上以随机的方式寻求到问题的最优解；但是由于自然进化和生命现象的不可知 性，导致了进化算法的本质缺陷。e a 最明显的缺点就是它的收敛问题，包括收敛 速度慢和未成熟收敛，虽然已有很多算法对它进行了改进，但很难有本质上的突 破。e a 之所以能使个体得到进化，首先是采用选择操作尽量选出比较好的若干个 体，保证下一代个体一般不差于前代，使个体趋于最优解，同时采用进化操作一 第一章绪论 交叉和变异( e p 中没有用交叉) ，通过它们的破坏性影响产生新的个体，从而生成 更好的个体，更重要的是可以维持群体的多样性。 分析进化算法可以看出：虽然在进化过程中，e a 尽量维持个体多样性和群体 收敛性之间的平衡；但是它没有利用进化中未成熟优良子群体所提供的信息，因 此收敛速度很慢。如果能在进化中引入记忆和定向学习的机制，增强算法的智能 性，则可以大大提高搜索效率，解决进化算法中的早熟和收敛速度问题。基于以 上考虑，本论文将进化算法和量子理论结合并借鉴了人工免疫系统中的克隆选择 算法，提出一种量子克隆进化理论及其学习算法，详细内容见后几章。 1 2 ，4 量子退火算法 解n p 完全或n p 难问题需要大量的计算时间，模拟退火( s i m u l a t e a n n e a l i n g s a ) 算法首先作为解优化问题的一种通用方法而被提出，它可以在有限的时间 内求得有限精度的解一近似最优解，基本思想就是利用热力学扰动使系统逃离代 价函数的局部极小值，是使系统在适当的退火方法下达到全局最优解。 在s a 中引入热力学扰动，可以在一个大的搜索空间中找到全局最小值。因此， 如果其他状态转移的机理可以得到更好的收敛性，我们同样也可以采纳。这样的 一个可能性就是t s a l l i s 广义转移概率，它是一种广义的用于m o n t ec a r l o 模拟的传 统b o l t z m a n n 型转移概率。在此方法中，系统在温度降低中收敛到最优状态，它的 过程要快于s a ，然而广义的转移概率不满足详细的平衡条件。因此，我们使用 另一种用量子隧道效应进行状态转移的概率一称之为量子退火。分析表明：量子 隧道效应可以有效的达到全局最小，并其呈现比温度驱动的s a 好的性能。有人提 出利用这种量子隧道效应解组合优化问题，这就是利用量子隧道效应引起状态间 的变化的量子退火算法( q u a n t u ma n n e a l i n ga l g o r i t h m - - q a a ) 。量子退火的过程对 应于s a 中的热力学转移，它可以利用两种方法来研究一时问度量的s c h r o d i n g e r 等式和量子m o n t ec a r l o 原理，这两个动力系统实际上是等效的，但是这两个方法 都可以找到最优解，而且速度均比s a 方法快，找到最优解的概率要远大于s a 。 1 2 5 量子模式识别算法 f e y n m a n 首先将应用量子系统的连续特性而构造的量子计算机与使用仅有两 个状态的晶体管构造的数字电子计算机进行了比较。研究结果表明：几乎没有使 用经典物理实现先进的信息处理的例子，而基于统计物理模型的算法却可以广泛 应用于数据分析，图像识别，神经网络的学习等。这是因为量子算法远远快于传 统算法，如黑箱的问题、s h o r 算法和g r o v e r 算法等，因此利用量子机理的模式识 别方法和它的传统对应物也是指数加速的。 量子克隆进化算法研究 模式识别是人工智能( a r t i f i c i a li n t e l l 垃e n c e a i ) 中一个基本的问题，除了模 式的检测和定位外，模板的匹配也是一个有意义的方向，它通常要用特定的分类 器实现。有人就以用量子系统执行图像分析中的模板匹配的任务为例，讨论了量 子模式识别的实现，它需要根据问题，使用量子系统构造对应的模型，选取同量 子定理一致的算法模型，其中要用到一些在联想记忆、图象识别和并行分布式处 理都要用到的线性操作和矢量空间的概念，由于量子系统高维的状态存储空间， 以及能够模拟计算中数据分析不同的线性模型的能力，量子模式识别可以不需要 大量的量子位数，无需将完全模式集存储到一个量子存储器中，就能实现快速的 图像匹配的算法。 1 2 7 量子聚类算法 聚类分析是研究如何用数学的方法将一组样品( 对象、指标、属性) 进行分 类的方法。聚类算法包括统计算法，机器学习方法，神经网络方法和面向数据库 的方法等。聚类是模式识别中一个重要的问题，目前我们常用的聚类方法是基于 距离的分割聚类算法，它仅仅根据数据间的几何相似性进行分类，是一种无监督 的学习方法，所以一般说来，它的效果并不如入意；而且在现有的聚类算法中， 聚类数目一般需要事先指定，如k o h e n o n 白组织算法，k 均值算法，模糊c 均值 聚类算法等。然而，类别数在很多情况下是不可知的，而且各类聚类算法的结果 一般都要依赖于初值，即使类别数目保持不变，聚类的结果也相差很大。 受到物理学中量子机理和特性的启发，我们可以利用量子理论解决此类问题， 一个很好的例子就是基于相关点的p o t t 自旋和统计机理提出的量子聚类模型，它 把聚类闯题看作一个物理系统，通过求解一系列随温度变化的自由能函数的全局 极小来得到聚类问题的最优解。许多算例均表明：对传统聚类算法无能为力的几 种聚类问题，该算法都得到了比较满意的结果。 1 2 8 量子小波与小波包算法 子波分析( w a v e l e ta n a l y s i s ) 是门既有坚实数理论基础，又有广泛实际应 用背景的新学科。1 9 9 0 年以后，子波分析同时朝着几个方向发展。1 9 9 2 年， w i c h e r h a u s e r 和c o i f m a n 等人沿着频带划分的思想，用一个尺度函数生成一组包括 子波函数在内的“子波包”，实现了全频域的渐细估计，为信号的自适应频带划分 提供了工具。最近，a n d r e a sk l a p p e n e c k e r 通过研究指出：在量子计算机上可以实 现周期化的小波包变换和小波变换，而且实现周期化的小波包变换要比实现小波 变换容易，并且还给出了具体的量子电路的实现方法。 假设信号可以用刀个量子比特表示，n = 2 ”为输入信号的长度，在经典计算 第一章绪论 机上我们需要0 ( ) 步运算来实现小波变换，o ( n l o g n ) 步来实现小波包变换。在 量子计算机上，则只需要o ( 1 0 9 2 ) 个基本量子门运算来实现小波与小波包变换， 而且实现小波包算法比小波算法需要更少的计算量。 1 2 9 其他 b a v e s i a l l 网络是一种表示一组变量间概率关系的图模型，它能够容易地处理不 完整数据：学习因果关系等。从上个世纪9 0 年代以来，它已发展成为专家系统中 编码不确定专家知识的一种通用方式。2 0 0 1 年，r o b e r tr t u c c i 提出了一种量子 b a y e s i a n 网络，它提出的方法的特别之处就是对于每一个网络都给出了一个非常有 用的密度矩阵，称之为网络的m e t a 密度矩阵，详见文献 2 4 1 。 另外还有人考虑了将量子计算和传统机器学习的结合，它讨论了能描述成标 准分离形式( d n f ) 的学习函数问题，提出了一种从随机样本中，利用基于f o u r i e r 机理的量子学习算法【25 1 。除此之外，还有人利用量子计算的指数加速的能力点研 究了用量子计算进行决策树估计的算法【2 。 目前量子智能计算的概念形成不久，其内涵正在不断扩充，各种计算模型也 相继出现。实际上，我们现在更关心的是量子智能计算对传统信息处理方式的改 进，本论文的工作就是围绕这个目的展开的。 1 3 本文的主要内容 鉴于以上讨论，我们在本文中提出了种新颖的学习算法一基于量子机理的 克隆选择算法。我们会在以后的章节里详细介绍人工免疫系统中的克隆选择算法。 在e a 中，算法的多样性和收敛速度一直是一对矛盾，我们提出的算法通过一种新 颖的量子染色体表示( 它实质上定义了个体的出现概率) 来增加种群的多样性， 并且设计量子变异算子和克隆选择算子来充分利用种群当代的信息，简单方便的 引导进化，克服过早收敛，在一定程度上缓和了e a 早熟和收敛速度的矛盾。对应 于进化理论体系，该算法体系包括三个方面，即量子克隆遗传算法，量子克隆进 化规划和量子克隆进化策略。我们分别给出了相应算法并证明了其全局收敛性。 理论分析和许多仿真实验结果都表明，与e a 相比，量子克隆进化算法不仅是有效 的，也是可行的，可以较好地解决已有算法中可能出现的早熟现象，并且使收敛 速度有显著提高。在材料的组织与编排方面： 我们首先在第二章简要介绍了进化算法的基本原理、步骤及意义，并概述了 进化算法的发展现状分析了其瓶颈问题。而针对其不足之处引入了人工免疫系统 i o量子克隆进化算法研究 中的克隆算子，综述了人工免疫系统中的发展现状，比较其与神经网络、进化计 算以及一般的确定性优化算法的异同并给出本文中所涉及到的克隆选择算予的具 体步骤。 第三章中，我们通过上述的讨论与总结，将量子理论运用到进化计算当中并 结合克隆算子提出了量子克隆进化算法，并详细地对量子克隆进化理论中所涉及 到的三个算法进行了介绍与分析，给出了仿真结果。 第二章进化计算与人工免疫系统 第二章进化计算与人工免疫系统 进化计算( e v o l u t i o n a r ya l g o r i t h m - - e a ) 是一类模拟生物进化过程与机制求解 问题的自组织、自适应人工智能技术。依照达尔文的自然选择和孟德尔的遗传变 异理论，生物的进化是通过繁殖、变异、竞争、选择来实现的，进化算法就是建 立在上述生物模型基础上的随机搜索技术。它起源于6 0 年代对于机器学习问题发 展的遗传算法( g e n e t i c a l g o r i t h m s - - g a ) ，l j 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 ) 以及i r e c h e n b e r g 和h e s c h w e f e l 用于数 值优化问题的进化策略( e v o l u t i o n a r ys t r a t e g i e s - - e s ) 。我们所熟悉的g a 是一种 更为宏观意义上的仿生算法。它通过模拟达尔文的“优胜劣汰，适者生存”的原 理鼓励好的个体，通过模拟孟德尔的遗传变异理论在进化过程中保持好的个体， 同时寻找更好的个体，由此来模仿一切生命与进化过程。进化策略和进化规划与 遗传算法类似，它们都以自然界中的进化过程为自适应全局优化搜索过程的借鉴 对象，并在利用生物进化机制提高计算机求解问题能力的目标和基本思路上是一 致的但是在具体做法上有所差别：g a 强调染色体的操作【2 7 】【2 8 】，e p 强调种群极 上的行为变化【2 ，e s 强调个体极上的行为变化。随着各种算法之间相互交流的深 入，对它们的区分也不那么严格了。那么我们下面以遗传算法为例分析其机理和 性能。 遗传算法有其自身的特点：智能性与本质并行性。遗传算法的智能性包括自 组织、自适应和自学习等，应用遗传算法求解问题时，在确定了编码方案、适应 值函数及遗传算子后，算法将应用演化过程中获得的信息进行自组织搜索，适者 生存的选择策略赋予了遗传算法自适应的能力，同时也赋予了它根据环境的变化 自动发现环境的特征和规律的能力；遗传算法的本质并行性表现在两个方面：一 是遗传算法的内在并行性，即其本身非常适合大规模并行，二是遗传算法的内含 并行性，即它可以同时搜索解空间内的多个区域，并且相互之间进行信息交流， 这种搜索方式使得遗传算法可以以较少的计算获得较大的收益。这些特点使得遗 传算法广泛应用于控制、规划、设计、组合优化、图像处理、信号处理、机器人、 人工生命等多个领域。本章介绍了分析了遗传算法的基本机理，并给出进化算法 的瓶颈问题，在改进其算法中进入了克隆算子，在下节将详细介绍了人工免疫系 统中的克隆选择算法。 量子克隆进化算法研究 2 1 遗传算法简介 遗传算法的基本思想是基于d a r w i n 进化论和m e n d e l 的遗传学说的。 g a 把问题的解表示成“染色体”，在算法中也就是二进制编码的串。并且， 在执行遗传算法之前，给出一群“染色体”，也就是假设解。然后，把这些假设解 置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色 体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。 这样，一代一代的进化，最后就会收敛到最适应环境的一个“染色体”上，它就 是问题的最优解。很明显，遗传算法是一种群体并行的最优化方法，它通过进化 和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定 的串b ，处，即求出最优解。下面给出遗传算法的步骤和意义。 长度为三的”个二进制串玩( f = 1 ，2 ，n ) 组成了遗传算法的初始解群，也 称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。 1 初始化 选择一个群体，即选择一个串或个体的集合b ，i = i ，2 ，n 。这个初始的群 体也就是问题假设解的集合。一般取h = 3 0 1 6 0 。 通常以随机方法产生串或个体的集合b ，i - - - - - 1 ，2 ，疗。问题的最优解将通过 这些初始假设解进化而求出。 2 选择 根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适 应度准则体现了适者生存，不适应者淘汰的自然法则。 给出目标函数，n a b ，) 称为个体b i 的适应度。以公式( 2 1 ) p 选中b i ) = 掣 ( 2 1 ) ：f ( b j ) 万 为选中6 i 为下一代个体的次数。 显然，从上式可知： ( 1 ) 适应度较高的个体，繁殖下一代的数目较多。 ( 2 ) 适应度较小的个体，繁殖下一代的数目较少，甚至被淘汰。 这样，就产生了对环境适应能力较强的后代。从问题求解角度来讲，就是选 择出和最优解较接近的中间解。 3 交叉 对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉 概率，。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新 第二章进化计算与人工免疫系统 一撼拄 ，变异为9 李窑西 ，变异为9(三一李螫器 1 4量子克隆进化算法研究 根据进化术语，标准遗传算法所包括的三种遗传操作具体如下： 1 选择( s e l e c t i o n ) 这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。 故有时也称这一操作为再生( r e p r o d u c t i o n ) 。由于在选择用于繁殖下一代的个体 时，是根据个体对环境的适应度来决定其繁殖量的，故而有时也称为非均匀再生 ( d i f f e r e n t i a lr e p r o d u c t i o n ) 。 2 交叉( c r o s s o v e r ) 这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因 进行交换，从而产生新的个体。交叉算子示意如图2 2 。 父串l 父串2 父串1 父串2 i 交叉点i 交换 i i 目q _ _ l _ h 自目目- 黼 j 交叉点lj 交换交叉，卣 ， 黼瀚黼隧懑黼酬 后代串1 单点交叉 两点交叉 后代串2 后代串1 后代串2 l l曩暖霹隰 豳麟豳黼 黼黼蕊 图2 2 交叉算子示意图