（系统工程专业论文）量子遗传算法改进算法研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 量子遗传算法是将量子计算与遗传算法相结合的一种崭新的优化方法， 具有很大的生命力和研究价值。量子算法中融入了量子力学的许多基本特 性，极大地提高了计算的效率，已逐步成为一种崭新的计算模式，将它与遗 传算法相结合，将会大大提高遗传算法的效率，和弥补遗传算法的不足，使 优化方法应用更加广泛。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 d g e n e t i ca l g o r i t h m ”文中提出了量子遗传的概念，k h h a n ，k h p a r k ， c h l e e j h k i m 将量子遗传算法用于求解组合优化问题，取得了较 好的效果。但有研究结果表明qga 不适于用来求解连续函数的优化问题 特别是多峰连续函数的优化问题为了能将量予计算的强并行性用到实际的 优化问题中，本文对此作了进一步的研究，使量子遗传算法的性能进一步提 高，应用更加广泛。 论文共分六章。第一章为绪论，简要介绍了现代优化方法以及量子计算 和量子遗传算法方面的研究。通过讨论量子计算及曩子遗传算法的优点，分 析了量子遗传算法得以迅速发展的原因。第二章简要介绍遗传算法，介绍了 遗传算法的适应度函数，遗传操作的数学基础，及它的遗传操作。 第三章 简要介绍量子遗传算法，介绍了量子力学基础知识，量子逻辑门，量子位的 基本表示方法，量子遗传操作更新，及量子遗传算法流程。第四章提出分组 量子遗传算法，通过将个体分层、分组，并将每层按类进行不同的量子计算， 对解的空间作了各方试探，保证了染色体的多样性也就保证了解的多样性。 第五章提出了基于混沌的量子遗传算法，混沌能不重复地历经一定范围内的 所有状态，具有遍历性，同时它的随机性和规律性，使它具有丰富的时空动 态。而且它对初值变化具有强烈的敏感性，这使它在搜索过程中避免陷入 局部极值。这恰弥补了量子遗传算法的不足与缺陷。本文从这个角度提出一 种基于混沌的量子遗传算法，介绍了混沌的概念，混沌的算法和混沌最予 遗传算法。第六章提出了基于模糊决策的量子遗传算法，量子遗传算法主要 是通过旋转量子门的更新来进化，其中旋转角的大小直接影响优化结果和进 化速度。本文将旋转角优化规则模糊化，提出种基于模糊决策的量子遗传 算法。介绍了模糊控制基本知识，模糊量子遗传算法，和基于模糊控制求取 旋转角。 关键词：优化：量子遗传算法；分层量子遗传算法；混沌量子遗传算法 模糊量子遗传算法； 西南交通大学硕士研究生学位论文 第1 i 页 _ _ _ _ _ l _ _ _ _ _ _ _ _ - _ - _ _ _ - _ _ _ _ _ _ _ _ - _ _ _ _ _ _ - _ _ _ _ - - - _ _ _ - _ _ i _ 一 a b s t r a c t q u a n t u mg e n e t i ca l g o r i t h m si san e wo p t i m u mm e t h o dt h a tc o m b i n e s q u a n t u mc o m p u t a t i o nw i t hg e n e t i ca l g o r i t h m s ，i ta d p e a r ss t r o n gl i f e f o r c ea n d b ev a l u a b l e f o r r e s e a r c h q u a n t u mc o m p u t a t i o na b s o r b e dm a n ye s s e n t i a l c h a r a c t e r so fq u a n t u mm e c h a n i c s ，w h i c hi m p r o v e dt h ec o m p u t a t i o ne 币c i e n c y , a n db e c o m eab r a n dn e wm o d e lo f c o m p u t a t i o n a n a r a y a n a n & m m o o r e p u tf o r w a r dt h ec o n c e p to fq u a n t u mg e n e t i ci nh i sa r t i c l e q u a n t u m 。i n s p i r e d g e n e t i ca l g o r i t h m ，k h h a r t ，k h p a r k ，c h l e e & j h ，k i ma p p j i e d q u a n t u m g e n e t i c a l g o r i t h m s t os o l v et h e p r o b l e m o fc o m b i n a t i o n a l o p t i m i z a t i o na n d h a v e g o t ag o o de f f e c t b u ts o m er e s e a r c hi n d i c a t et h a tq g a i s n o tf i tt os o l v et h eo p t i m i z a t i o np r o b l e m so fc o n t i n u o u s f u n c t i o n ，e s p e c i a l l yt h e o p t i m i z a t i o np r o b l e m so fm u f f - p e a k e dc o n t i n u o u sf u n c t i o n s s os o m ei m p r o v e d q u a n t u mg e n e t i ca l g o r i t h m sa r ep u tf o r w a r d ，t h ep e r f o r m a n c eo ft h ea l g o r i t h m s a r eb e t t e r t h i sd i s s e r t a t i o ni n c l u d e ss i xc h a p t e r s t h ef i r s tc h a p t e ri si n t r o d u c t i o n ，i t b r i e f l yi n t r o d u c e st h ec u r r e n td e v e l o p m e n t o f t h em o d e m o p t i m i z e dm e t h o d a n d q u a n t u mc o m p u t a t i o na n dq u a r l t u mg e n e t i ca l g o r i t h m s t h r o u g ha n a l y s i n gt h e e x c e l l e n c eo fq u a n t u m c o m p u t a t i o n a n d q u a n t u m g e n e t i c a l g o r i t h m s ，l t i n t r o d u c e st h eq u i c kd e v e l o p m e n tr e a s o no fq u a n t u mg e n e t i ca l g o r i t h m s t h e s e c o n d c h a p t e rb r i e f l y i n t r o d u c e s q u a n t u mc o m p u t a t i o n ，f i t n e s s f u n c f i o no f q u a n t u mc o m p u t a t i o n g e n e t i co p e r a t i o n o fq u a n t u mc o m p u t a t i o n t h et i l i r d c h a p t e rb r i e f l yi n t r o d u c e sq u a n t u m g e n e t i ca l g o r i t h m s ，t h eb a s i ck n o w l e d g eo f q u a n t u mm e c h a n i c s ，q u a n t u ml o g i c a lg a t e ，t h e b a s i c e x p r e s s i n g m e t h o do f q u a n t u mb i t o p e r a t i o nr e n e w f l l o fq u a n t u mg a t e ，a n df l o wc h a r to fq u a n t u m g e n e t i c a l g o r i t h m s t h e f o u r t h c h a p t e rp r e s e n t s b l o c k q u a n t u m g e n e t i c a l g o r i t h m s ，b yl a y e r i n g a n db l o c k i n gt h ei n d i v i d u a l s ，a n de v e r yl a y e ru s e s d i f f e r e n tq u a n t u mc o m p u t a t i o n ，a n dt r y i n gt h es o l u t i o ns p a c et h r o u g hd i f f e r e n t w a y s ，b yu s i n g t h em e t h o d ss u c ha s l a y e r i n g a n db l o c k i n g ，g u a r a n t e e st h e d i v e r s i t yo fc h r o m o s o m e a n dk e e p st h ed i v e r s i t yo fs o l u t i o n t o o t h ef i 觚 c h a p t e rp r e s e n t so u a n t u mg e n e t i ca l g o r i t h m sb a s e do nc h a o s ，c h a o sc a np a s s t h r o u g h a l lt h es t a t e sw i t h o u t r e p e t i t i o n s o i th a st h ec h a r a c t e r i s t i c so f e r g o d i c i t ya n dr a n d o m n e s sa n dr e g u l a r i t y ，i t ss e n s i t i v i t yt oi n i t i a lv a l u em a k e s i t s s e a r c ha v o i dd r o p p i n gi n t ol o c a lo p t i m u m s ot h ei n t e g r a t eo ft w oa l g o r i t h m s c a nb e h a v eb e t t e r t h es i x t hc h a p t e rp r e s e n t sq u a n t u mg e n e t i ca l g o r i t h mb a s e d 西南交通大学硕士研究生学位论文第1 i i o n f u z z yr u l e s q u a n t u mg e n e t i ca l g o r i t h me v o l v eb yq u a n t m n r o t a t i o ng a t e t h e m a g n i t u d eo ft h ea n g l ep a r a m e t e rh a sa ne r i e c to nt h es p e e da n dt h eq u a l i t yo f c o n v e r g e n c e s oaf u z z yq u a n t u mg e n e t i ca l g o r i t h mb a s e do n t h eo p t i m i z a t i o no f f u z z yr u l e sa r ep r o p o s e d t h er e s u l t sf r o mt y p i c a lf u n c t i o n t e s td e m o n s t r a t et h a ti t i sb e t t e r k e yw o r d s ： g e n e t i ca l g o r i t h m ；q u a n t u mg e n e t i ca l g o r i t h m ；o p t i m i z a t i o n c h a o t i cg e n e t i ca l g o r i t h m ；f u z z yg e n e t i ca l g o r i t h m 西南交通大学硕士研究生学位论文 第l 页 第1 章绪论 量子遗传算法是新发展起来的一种基于量子计算原理i l 2 l 的概率优化方 法它以量子计算的一些概念和理论为基础，用量子位编码来表示染色体，通过 量予门的旋转来完成进化搜索+ 具有种群规模小、收敛速度较快，全局寻优 能力强的特点文献【l 3 分别提出了量子遗传算法、并行量子遗传算法，并用 来求解组合优化问题，结果表明，qga 的性能大大优于传统遗传算法。有分 析表明，qga 不适于用来求解连续函数的优化问题，特别是多峰连续函数 的优化问题扣j 为了能将量子计算的强并行性应用到实际的优化问题中，探索 新的量子算法是非常有必要的因此，本文提出几种具有广泛适用性的新量子 遗传算法 1 1 现代优化方法的回顾 现代优化算法包括禁忌搜索( t a b us e a r c h ) 、模拟退火( s i m u l a t e d a n n e a l i n g ) 、遗传算法( g e n e t i ca l g o r i t h m s ) 、神经网络( n e u r a ln e t w o r k s ) 和 拉格朗日松弛等算法。这些算法涉及生物进化、人工智能、数学和物理科学、 神经系统和统计力学等概念，都是以一定的直观基础构造的算法，称之为 肩发式算法。启发式算法的兴起与计算复杂性理论的形成有密切的联系。当 人们不满足常规算法求解复杂问题时现代优化算法开始体现其作用【4 8 】。 禁忌搜索算法( t a b us e a r c h ) 是局部邻域搜索算法的推广，是人工智能 存组合优化算法中的一个成功应用。g l o v e r 在1 9 8 6 年首次提出这一概念， 进而形成一套完整算法，禁忌搜索算法的特点是采用了禁忌技术，所谓禁忌 就是禁止重复前面的工作。为了回避局部邻域搜索陷入局部最优的主要不 足，禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点，在下一次 搜索中，利用禁忌表中的信息不再或有选择的搜索这些点，以此来跳出局部 最优点。 遗传算法( g e n e t i ca l g o r i t h m s ) 是7 0 年代初期由美国密执根大学的 i t o l l a n d 教授发展起来的。遗传算法是一种借鉴生物界自然选择和进化机制 发展起来的高度并行、随机、自适应搜索算法。它使用了群体搜索技术，将 种群代表一组问题解，通过对当前种群施加选择、交叉和变异等一系列遗传 西南交通大学硕士研究生学位论文第2 页 操作，从而产生新一代种群，并逐步使种群进化到包含近似最优解的状态。 由于其思想简单、易于实现以及表现出来的健壮性，遗传算法赢得了许多应 用领域，特别是问题求解、优化和搜索、机器学习、智能控制、模式识别和 人工搜索等领域。但它在实际应用中也存在不足和局限性，表现在迭代次数 多，收敛速度慢，易陷入局部极值和过早的收敛等。 人工神经网络的早期工作可以追溯到1 9 4 3 年m c c u l l o c h 和p i t t s 建立的 第一个模型，后被扩展为“认知”模型。人工神经网络有较强的学习能力 和自适应性，且具有大规模的平行计算能力，且它的发展也较成熟，但它仍 然受到计算机发展的限制。 l - 2 量子遗传算法 量子遗传算法是基于量子计算原理的一种遗传算法，将量子计算与遗传 算法相结合的量子遗传算法是种崭新的优化方法，具有很大的生命力和研 究价值。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 h h a n ，k h p a r k ，c h l e e & j h k i m 在“p a r a l l e lq 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 mf o rc o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e m s ”一文中，将量子遗传算法用于求解组合优化问题，取得了较好的 效果。 量子遗传算法也引起了国内越来越多学者的注意，已有一批学者对量子 遗传算法的改进算法作了一些研究。 目前，有关量子计算的研究在国际上十分活跃。美国、欧洲、日本和以 色列等各国政府都已将其列入重点发展的高科技项目之一大力扶持。美国的 国家标准化技术研究所、l o sa l a m o s 国家实验室以及国际著名高校u n i v e r s i t y o f o x f o r d 、m i t 等，有关量子计算的研究也在如火如荼的进行。在我国虽然 这门新兴高科技的发展处在起步阶段，但是在某些方面的研究已达到世界先 进水平。例如，中国科技大学量子通信和量子计算开放实验室露前已经推出 了3 项重大原创性成果：在国际上首次提出概率量子克隆原理；在国际上首 次建立量子避错编码理论；提出了一种克服消相干的新型量子处理器；另外， 我国的量子计算的理论在国际上亦有特色。中科院武汉物理和数学研究所 在苯分子上实现了两个量子比特的量子算法。中科院大量子通信与量子计算 研究小组研制成功两量子比特的核磁共振量子逻辑门和三量子比特核磁共 振量子t o f f o l i 门。在丙氨酸分子上成功实现四量子比特核磁共振量子计算操 作，使我国具备研究了多量子比特核磁共振量子计算机的能力，从而为我国 西南交通大学硕士研究生学位论文第3 丽 的量子信息科学跻身国际前沿做出了重要贡献。我国对这新兴重要领域十 分重视，量子信息处理技术的突破在使信号和信息处理技术再一次飞跃的 同刊，不仅将对计算机科学、密码学、通信技术以及国家安全和商业应用等 众多领域产生巨大的推动作用，而且也将对人类生活的方方面面产生重大的 影响【1 7 1 。 1 3 本文结构与主要工作 本文主要是对量子遗传算法的改进算法进行了分析和研究。论文共分六 章，分别介绍如下： 第一章为绪论，简要介绍了现代优化方法以及量予计算和量子遗传算法 方面的研究现状。通过讨论量子计算及量子遗传算法的优点，分析了量子遗 传算法得以迅速发展的原因。 第二章简要介绍遗传算法，介绍了遗传算法的适应度函数，遗传操作的 数学基础，及它的遗传操作。 第三章简要介绍量子遗传算法，介绍了量子力学基础知识，量子逻辑门， 餐了位的基本表示方法，量子遗传操作更新，及量子遗传算法流程。 第四章提出一种分组量子遗传算法，它通过将个体分层、分组，并将 每层按类进行不同的量子计算，对解的空间作了各方试探，通过分层、分组 等方法、保证了染色体的多样性也就保持了解的多样性。 第五章提出一种基于混沌的量子遗传算法，混沌能不重复地历经一定范 围内的所有状态，具有遍历性，同时它的随机性和规律性，使它具有丰富的 时空动态。而且它对初值变化具有强烈的敏感性，这使它在搜索过程中避 免陷入局部极值。这恰弥补了量子遗传算法的不足与缺陷。本章从这个角度 提出一种基于混沌的量子遗传算法，介绍了混沌的概念，混沌的算法和混 沌量子遗传算法。 第六章提出了一种基于模糊控制的量子遗传算法，量子遗传算法主要 是通过旋转量子门的更新来进化，其中旋转角的大小直接影响优化结果和进 化速度，本文将旋转角优化规则模糊化，提出一种基于模糊决策的量子遗传 算法。介绍了模糊控制基本知识，模糊量子遗传算法，和基于模糊控制求取 旋转角。 西南交通大学硕士研究生学位论文 第4 页 第2 章遗传算法简介 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 是以自然选择和遗传理论为基础， 模拟自然界生物进化过程与机制求解问题的一类自组织与自适应的人工智 能技术，已广泛应用于计算机科学、人工智能、信息技术及工程实践。 遗传算法( g e n e t i ca l g o r i t h m s ) 是7 0 年代初期由美国密执根大学的 h o l l a n d 教授发展起来的。遗传算法是一种借鉴生物界自然选择和进化机制 发展起来的高度并行、随机、自适应搜索算法。它使用了群体搜索技术，将 种群代表一组问题解。通过对当前种群施加选择、交叉和变异等一系列遗传 操作，从而产生新一代种群，并逐步使种群进化到包含近似最优解的状态。 由于其思想简单、易于实现以及表现出来的健壮性，遗传算法赢得了许多应 用领域，特别是问题求解、优化和搜索、机器学习、智能控制、模式识别和 人工搜索等领域。但它在实际应用中也存在不足和局限性，表现在迭代次数 多，收敛遽度慢，易陷入局部极值和过早的收敛等【2 0 1 。 其具体操作过程如图2 - 1 所示： 2 1 遗传算法的特点 遗传算法之所以广泛应用是因为它利用了生物进化和遗传的思想，与传 统优化算法有许多不同的特点： ( 1 ) 自组织、自适应性和自学习性( 智能性) 。应用遗传算法求解问题 时，在编码方案、适应度函数及遗传算子确定后，算法将利用进化过程中获 得的信息自行组织搜索。自然选择消除了算法设计过程中一个最大的障碍， 即需要事先描述问题的全部特点，并要说明针对问题的不同特点算法应采取 的措施。因此，利用遗传算法的方法，我们可以解决那些复杂的非结构化问 题。 ( 2 ) 遗传算法的本质并行性。遗传算法按并行方式搜索一个种群数目 的点，而不是单点。 ( 3 ) 遗传算法不需要求导或其他辅助知识，而只需要影响搜索方向的 目标函数和相应的适应度函数。 ( 4 ) 遗传算法强调概率转换规则而不是确定的转换规则。 ( 5 ) 遗传算法可以更加直接地应用。 西南交通大学硕士研究生学位论文 第5 页 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 一- 1 r - _ 图2 - 1 遗传算法操作过程 2 2 遗传算法求解中的一些细节问题 2 2 1g a 的编码方法 g a 中的编码在许多问题的求解中，对算法的性能有很重要的影响。简 单二进制编码的采用得到了h o l l a n d 早期理论结果的支持它使用的编码符 号集由二进制符号0 和l 组成的，因此实际的遗传基因型是一个= 进制符号 串，其优点在于编码、解码操作简单，交叉、变异等遗传操作便于实现，而 且便于利用模式定理进行理论分析等：其缺点在于，不便于反映所求问题的 特定知识，对于一些连续函数的优化问题等，也由于遗传算法的随机特性而 西南交通大学硕士研究生学位论文第6 页 使其局部搜索能力较差，对于一些多维、高精度要求的连续函数优化，二 进制编码存在着连续函数离散化时的映射误差，个体编码串较短时，可能达 不到精度要求：而个体编码串的长度较长时，虽然能提高精度，但却会使算 法的搜索空间急剧扩大 后来许多学者对遗传算法的编码方法进行了多种改进，例如，为了提高 遗传算法的局部搜索能力，提出了格雷码编码；为改善遗传算法的计算复杂 性、提高运算效率，提出浮点数编码、符号编码等方法等。为便于利用求解 问题的专门知识，便于相关近似算法之间的混合使用，提出了符号编码法； 此外还有多参数级联编码和交叉编码方法。 2 2 2 几种常见的适应度函数 适应度函数基本上有以下三种： 直接以待求解的目标函数的转化为适应度函数，即 若目标函数为最大化问题f i t ( f ( x ) ) = f ( x ) 若目标函数为最小化问题f i t ( f ( x ) ) = f ( x ) 0 若目标函数为最小问题，则 f i t ( f ( x ) ) = c m 弧- f ( x )f ( x ) c 。i 。 ( 2 4 ) 这种方法是对第一种方法的改进，可以称为”界限构造法”，但有时存在界 限值预先估计困难、不可能精确的问题。 0 若目标函数为最小问题 f i t ( f ( x ) ) = 1 ( 1 + c + f ( x ) ) c = o ，c + f ( x ) = o ( 2 - 5 ) 若目标函数为最大问题 f i t ( f ( x ) ) = 1 ( 1 + c f ( x ) ) c = 0 ，c - f 【x ) = 0( 2 6 ) 这种方法与第二种方法类似，c 为目标的保守估计值。 2 2 3 适应度函数的设计 适应度函数设计主要满足以下条件： ( 1 ) 单值、连续、非负、最大化 这个条件很容易理解和实现 ( 2 ) 合理、一致性要求适应度反映对应解的优劣程度，这个条件的 话南交通大学硕士研究生学位论文 筮7 亟 达成往往难以衡量。 ( 3 ) 计算量小适应度函数设计应尽可能简单，这样可以减少计算时 间和空间上的复杂性，降低成本。 ( 4 ) 通用性强适应度对菜类具体问题，应尽可能通用，最好无需使用 者改变适应度函数中的参数。 2 2 4g a 参数的选择 g a 的参数选择包括群体规模、收敛判据、杂交概率和变异概率等。这 些参数的选择关系到g a 的精度、可靠性、和计算时间等诸多因素，并且影 响到结果的质量和系统性能。 一般说来，选择较大数目的初始群体可以处理更多的解，因而容易找到 全局最优解，其缺点是增加了每次迭代的时间，一般取2 0 1 0 0 。 交叉率的选择决定了交叉操作的频率，频率越高，可以越快地收敛到最 有希望的最优解区域，因此一般选取较大的交叉率，但太高的频率也可能导 致过早收敛，一般取值0 4 0 9 。 变异率的选取一般受到种群大小、染色体长度等因素影响，通常选取很 小的值，一般取0 0 0 1 0 1 。若选取高的变异率，虽然增加样本模式的多样性， 但可能会引起不稳定。种群大小及染色体长度越大，变异率选取越小。 染色体长度主要决定于问题求解精度的要求，精度越高，染色体长度越 长，搜索空间越大，相应地要求种群大小设置大一些。最大进化代数作为一 种模拟终止条件，一般视具体问题而定，取1 0 0 - - 5 0 0 代。对于具体问题而言， 衡量参数设置恰当与否，要依据多次运行的收敛情况和解的质量来判断。 2 3 遗传算法的数学基础 2 3 1 模式定理 模式定理：在遗传算予选择、交叉、变异的作用下，具有低阶、短定义 距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。 模式定理的一般数学表达式如下，是指在考虑选择、交叉和变异操作的 作用下，一个特定模式在下一代中期望出现的数目可以近似表示为： m ( 日，+ 1 ) m ( 日，) 上等尘i1 - - p c ! ；：掣一d ( ) p 。i ( 2 7 ) _ ，l l j j m ( h ，t + 1 ) 表示在t + 1 代种群中存在模式h 的个体数目。 西南交通大学硕士研究生学位论文 第8 页 m ( h ，t ) 表示在t 代种群中存在模式h 的个体数目： f ( h ) 表示在t 代种群中包含模式h 的个体平均适应度 ，表示在t 代种群中所有个体的平均适应度； l 表示个体的长度； p 。表示交叉概率； p 。表示变异概率； 模式定理是遗传算法的基本理论，它浣明高适应值、长度短、阶数低的 模式在后代中至少一指数增长包含该模式的串h 的数目。而简单的交换操作 不易破坏长度短、阶数低的模式，而变异概率很小，一般不会影响这些重要 模式。 用这种方法处理相似性，g a 减少了问题的复杂性，在某种意义上这些 高适应值、长度短、低阶的模式成了问题的部分解( 又叫积木块) 。g a 足 从父代最好的部分解中构造出越来越好的串，而不是去实验每个可能的组 合。长度短、低阶的、高适应值的模式通过遗传操作再生，交换、变异，再 再生、再交换、再变异的逐渐进化。形成潜在的适应值较高的串，这就是积 木假说。g a 通过积木块的并置，寻找接近最优的特征。 2 3 2 遗传算法收敛判据 收敛判据：o a 是一种反复迭代的搜索方法，它通过多次进化逐渐逼近 最优解而不是恰好等于最优解，因此需要确定收敛判据。目前采用收敛判据 有多种。如规定遗传迭代的代数所确定的判据：或根据解的质量确定的判据 如连续几次得到的最优个体的适应值没有变化或变化很小时，则认为g a 收 敛了：或种群中最优个体的适应值与平均适应值之差与平均适应值的百分数 之比小于某一给定允许值等等。为评价g a 的收敛性能，定义离线性能函数 p ( c ) _ 喜f t ， ( 2 - 8 ) 其中f 。为第i 代的最大个体适应值，p ( t ) 是第t 代的离线性能值。 在早期搜索中，p ( t ) 将迅速增长；在后期搜索中，p ( t ) 的增长将平缓下 来，并最终趋向于收敛值( 2 6 】。 西南交通大学硕士研究生学位论文 第9 页 2 4 小结 本章主要介绍了遗传算法，并对遗传算法作了一定的分析。 1 ) 介绍了遗传算法和遗传算法的特点。遗传算法比较突出的特点是它 的本质并行性、自组织、自适应性和自学习性( 智能性) 。 2 ) 对遗传算法的一些细节问题作了介绍。主要介绍了遗传算法的编码 问题、适应度函数设计问题、以及遗传算法参数的选择问题。 3 ) 给出了遗传算法的收敛判据和它的数学基础。着重介绍了遗传算法 基本理论基础模式定理。 西南交通大学硕士研究生学位论文 第1 0 页 第3 章量子遗传算法 量子遗传算法( q u a n t u mg e n e t i ca l g o r i t h m ，q g a ) 是将量子计算和遗传 算法相结合的一种算法。 在分析量子计算的特点之前，我们先简单了解一下量子计算的一个重要 理论基础，即量子力学原理其实，对量子计算以及量子算法的研究，并不 一定要去系统地学习量子力学，只需要理解与量子计算有关的量子态的基本 特性就可以了就如同了解常规计算机时不一定需要系统学习半导体物理一 样 3 1 量子计算基础知识 1 光的波粒二象性 光的波动性早在十七世纪就已发现，光的干涉和衍射现象以及光的电磁 理论从实验和理论两方面充分肯定了光的波动性 虽然光的波动性有大量实验事实和光的电磁理论的支持，但本世纪切所 发现的黑体辐射，光电效应等现象却揭示了把光看作波动的局限性 普朗克在1 9 0 0 年引进量子概念解决了黑体辐射的问题，而第个完全肯 定光除了波动性之外还具有微粒性的是爱因斯坦。他认为电磁辐射不仅在被 发射和吸收时以h v 的微粒形式出现，而且以这种形式以速度c 在空间运动， 用这个观点，爱因斯坦成功地解释了光电效应。这样，光就具有微粒和波动的 双重性质，这种性质称为波粒二象性。 2 微粒的波粒二象性 1 9 2 4 年德不罗意在光有波粒二象性的启示下，提出微粒也具有波粒二象 性的假说。他把粒子和波通过下面的关系联系起来：粒子的能量e 和动量p 与波的频率v 和波长九之间的关系 e = h v = h c o p = h n x = h ( 3 1 ) ( 3 2 ) 西南交通大学硕士研究生学位论文 第1 1 页 这个公式称为德布罗意关系式 自由粒子的动量和能量都是常量 f 联系的波，它的频率和波矢都不变 3 波函数 所以由德布罗意关系可知：与自由粒 即它是一个平面波。 如果粒子受到随时间或位置变化的力场的作_ j ，它的动量和能量不再是 常量，这时粒子就不能用平面波来描写，而必须用较复杂的波来描写。在一 股情况下，我们用一个函数表示描写粒子的波，并称这个函数为波函数。它 是一个复数。 为人们所普遍接受的对于波函数的解释，是由波恩先提出的。他提出的 是波函数的统计解释，即：波函数在空间中某一点的强度和在该点找到粒 子的几率成比例。按这种解释，描写粒子的波乃几率波。 由于粒子必定要在空间中的某一点出现，所以粒子在空间各点出现的几 率总和等于1 ，因而粒子在空间各点出现的几率只决定于波函数在空间各点 的相对强度，而不决定于强度的绝对大小。 4 态迭加原理 以粒子的双狭缝衍射实验为例。用l 表示粒子穿过上面狭缝到达屏b 的状态，用凯表示粒子穿过下面狭缝到达屏b 的状态，再用甲表示粒子穿 过两个狭缝到达屏b 的状态。那么甲可以写成甲l 和甲2 的线性叠加，即 。p = c l v i + c z i l ，2( 3 - 3 ) 式中，c 。和c 。是复数，对于一般的情况，如果v ，和掣：是体系的可能状 态，那么，它的线形迭加 l p = c l t l t | + c 2 l i d 2 ( 3 - 4 ) 也是这个体系的一个可能状态，这就是量子力学中的态迭加原理 态迭加原理还有下面的含义：当粒子处于态和态掣。的线性迭加态 时，粒子是既处在态v ，又处在态掣：。 这表示量子计算机可以同时表征经典计算机中的许多态，使得大规模量 子并行存储和计算成为可能。 5 薛定谔方程 西南交通大学硕士研究生学位论文第1 2 页 在经典力学中，当质点在某时刻的状态为己知时，由质点的运动方程 就可以求出以后任一时刻质点的状态。在量子力学中情况也是这样，当微观 粒子在某一时刻的状态为已知时，以后时刻粒子所处的状态也要由一个方程 柬决定。所不同的是，在经典力学中，质点的状态用质点的坐标和速度来描 写，质点的运动方程就是我们熟知的牛顿运动方程；而在量子力学中，微观 粒子的状态则用波函数来描写，决定粒子状态变化的方程不再是牛顿运动方 程，而是我们要建立的薛定谔方程。 i a 警一等v 2 v + u ( 咖 ( 3 _ s ) a 【 2 u 、 式中v 一波函数u ( r ) 一粒子在力场中的势能 6 纠缠 v = i 杀+ j 熹+ t 旦a z叙。甜 若复合系统的一个纯态( p u r es t a t e ) 不能写成两个子系统纯态的直积，就 称之为纠缠态。这说明一个处于纠缠态的完整量子系统的一些确定态和予系 统的确定态并不对应，各子系统之间存有关联。量子纠缠现象是量子力学特 有的不同于经典物理的最奇特现象。 3 2 量子遗传算法简介 量子遗传算法是新发展起来的种基于量子计算原理的概率优化方法 它以量子计算的一些概念和理论为基础，用量子位编码来表示染色体，通过 量子门旋转更新来完成进化搜索，种群规模小，且不影响算法性能，同时兼 有“勘探”和“开采”的能力、收敛速度也较快。 西南交通大学硕士研究生学位论文 第1 3 页 3 2 1 量子逻辑门 量子计算是通过一系列么正算子实现的，么正算子保证了独立性和可逆 性对量子位最基本的么正操作就是逻辑门逻辑门的作用和经典计算机 样可以由真值表给出d a v i dd e u t s c h 定义了一个通用量子逻辑门，由 这个通用逻辑门可以实现任何量子门操作在经典可逆计算中已经证明，最 简单的通用逻辑门是三位f 7 ( - - 位输入三位输出) t o f f o l i 门和f l e d k i n 门都 可以作为实现量子计算的通用逻辑门 在t o 行o l i 门中，两个输入量子位( 控制位) 控制第三个量子位( 目标位) 的 状态，两控制位不随门操作而改变。当两控制位同时为1 时目标位改变，否 则保持不变表l 是t 0 f f o l i 门的真值表。 在f l e d k i n 门的三个输入位中，一个位是控制位，其他两个位是目标 位控制位不发生变化，当控制位为“l ”时，两目标位的值交换，否则， 保持不变。表2 给出了f l e d k i n 门的真值表。 表1 t o f f o l i 门真值表 【n p u tb i t s0 u y p u tb r r s abcabc 控制控制目标控制控制目标 0o000o olo010 l0o10 0 llo1ll o0loo1 01101l 1o1101 111l1o 西南交通大学硕士研究生学位论文 第1 4 页 _ _ _ _ _ _ _ _ _ _ _ - _ _ - _ _ _ _ _ _ _ - _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ - _ _ _ - _ _ - _ _ _ _ _ _ - - - 一1 i t _ _ 表2f l e d k i n 门真值表 i n p u t b i t so u t p u tb i t s i abcabc 目标目标控制目标目标控制 o o0o0o 0 loolo 1 o01o o l l01 10 o0l 00l o lll o1 l o1o l1 1 l1l l1 3 2 2 量子位表示方法 在q g a 中，染色体不是用确定性的值( 如二进制数、浮点数或符号等) 表示，而是用量子位表示，或者i 既是阐随机概率方式表示。一个量子位不仅 仅表示0 或l 两种状态而且同时表示这睡个状态之间的任意中间态。般 地，用n 个量子位就可以同时表示2 “个状态，因而，对于相同的优化问题， q g a 的种群大小可比传统g a 小很多； 在q g a 中，一个量子位可能处于i1 ) 或lo ) ，或者处于i1 ) 和io ) 之间的中间态，即f1 ) 和f0 ) 的不同叠加态，因此一个量子位的状态可表 示为： l 掣) = ql0 ) + bi1 )( 3 7 ) 其中。和b 可以是复数。表示相应状态的概率幅，且满足下列归一化条 件： i a l2 + ibf2 = l( 3 8 ) 在上式中， a l2 表示io ) 的概率，lbi2 表示l1 ) 的概率。 由此可知，对于位数相同的量子位，n 个量子比特可同时表示2 “个状态。 其中任一状态可表示为： 翌童窑翌查兰堡圭i 研l li i 究生学位论文i第 1 5 夏m - - - _ _ _ _ _ _ - _ _ _ _ - _ _ _ - - _ 一 - r 掣) = c , t s 。 ( 3 9 ) = t 在( 3 。9 ) 式中，c k 为第k 个状态的概率幅，且满足归一化条件fc 1i2 + i c 2i2 + 十i l 2 1 i2 = l ，其中，i 掣j ) 是一个2 ”维h i l b c r t 空间中的个单位 矢量。它所在空间的维数是随n 呈指数型增长，这明显区别于传统g a 中随 n 呈线性增长的态空间。例如： 1ll 瓜瓶2 i1 坯 垭冱2 ( 3 1 0 ) 表示： 扣0 ) + 知岫) + 铷t ) + + 知，) + 扣) + 扣) 即它代表状态 i o o o ) ，i o o i ) ，1 0 1 0 ，| o 】1 ) ，i 1 0 0 ) ，i l o i ，1 11 0 ，i l1 1 ) 冉勺概率分别为 1313l3l3 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 它用三个量子比特代表了8 种状态。 3 2 3 量子遗传操作更新 在q g a 中，由于染色体处于叠加或纠缠状态。因而q g a 的遗传操作不 能采用传统g a 的选择、交叉和变异等操作方式，而采用将量子门分别作用 于各叠加态和纠缠态的方式；子代个体的产生不是由父代群体决定，而是由 父代的最优个体及其状态的概率幅决定。遗传操作主要是将构造的量子门作 用于量子叠加态或纠缠态的基态，使其相互干涉，相位发生改变，从而改变 要童奎鎏查兰堡主竺室生兰竺堡奎 墓i 曼区 各基态的概率幅。因此，量子门的构造既是量子遗传操作要解决的主璺i 司题， 也是q g a 的关键问题，因为它直接关系到q g a 的性能好坏。在q g a 中， 主要采用量子旋转门，即： u _ c o s 口q 洒1= i i l s i n o c o s 0 j ( 3 1 1 ) 在( 3 - 1 1 ) 式中。o 为旋转角。 量子位的更新是通过量子门的更新来完成的，其过程如下： 咖c o s ( a o , m ) - 啦s i n ( 甜a o , 嘲 在更新的过程中，0 的大小和符号起关键作用 0 的幅度影响收敛速