（控制理论与控制工程专业论文）遗传算法和量子遗传算法在物流系统优化中的应用.pdf

摘要 物流优化成为大型物流企业利润增长的突破点，也是打破物流系统开发瓶颈的 有效。f 段。k 久以来，依抛数据分析和运篇学的思想，为物流系统的运作和执行提 出建设性的意见、方案和依掘，整合物流环节、优化流程管理，成为成功物流管理 中的- 一个重要因素物流优化。凼此无论从管理的角度还是工程的角度，物流优 化都存在很大的经济利益和发展潜力，对管理人员和工程技术人员提出了巨大的挑 战。 本文研究的主要内容是：遗传算法和量子遗传算法在运输指派问题、二次分配 问题( q a p ) 、以及配送方案优化和物流决策的多选择背包问题的应用与实现。 令文共分为六章。第一章绪论，阐述了物流系统的发展趋势和物流优化方法； 第二章遗传算法，介绍该算法的流程和理论基础，以及改进遗传算法；第三章量 子遗传算法，介绍量子计算的概念，对量了遗传算法的进化机理和改进算法进行总 结归纳；第四章遗传算法在运输最优化指派问题l 的实现，运用改进遗传算法，不 断扩大研究规模；通过实例分析，说明改进遗传算法在指派问题和q a p 问题上的有 效性；第五章量子遗传算法在物流配送系统的应用，根据量子编码的特性，提出新 的量子配送模型和配送策略，实现量子遗传算法在配送领域的首次应用。在此基础 上提 h 派型量子更新门思想，对量予遗传操作进行改进；第六章量子遗传算法在物 流决策支持方面的研究，以多选择背包问题为研究对象，实现了量子遗传算法在该 领域的应用，其中对约束问题的处理，以及对非法解处理的思路上，较为新颖，对 同类约束问题的处理具有借鉴意义。 通过量予遗传算法或遗传算法建模是优化过程中的关键，本文基于大量的研究 和试验，成功地将算法与具体的物流问题相结合，实现物流系统中若干环节的整合 和优化，有很高的应用价值，其潜在的经济效益不容忽视。 关键词：物流系统优化，量子遗传算法，遗传算法，指派问题，物流配送 多选择背包 a b s t r a c t t h eo p t i m i z a t i o nt ot h el o g i s t i cs y s t e m sh a sb e c o m et h ek e yp o i n tt or a i s et h e c o m p e t i t i o na n d t h en e w i n c r e a s i n gi nt h ep r o f i tf o rt h el a r g ea n dp o w e r f u ll o g i s t i c s e n t e r p r i s e s 。m e a n w h i l e i ta l s oh a sb e c o m et h en e ws o l u t i o nt op r o m o t et h ef u r t h e r d e v e l o p m e n tf o rl o g i s t i c ss y s t e m s b a s e do nt h eo p e r a t i o nr e s e a r c ha n dd a t a a n a l y s i s ，t op r o v i d ep l a n n i n g ，s u g g e s t i o n sa n de x e c u t i v es u p p o r t i n gs t r a t e g i e sf o r t h es u p p l yc h a i nh a sb e e no n eo ft h em o s ti m p o r t a n tf a c t o r sf o rt h es u c c e s s f u l l o g i s t i c sm a n a g e m e n t ，t or e a l i z et h ei n t e g r a t i o na n do p t i m i z a t i o ni nt h ew h o l e s u p p l yc h a i n s w h a t e v e ri nt h ee n g i n e e r i n gf i e l do rt h em a n a g e m e n tf i e l d ，t h e o p t i m i z a t i o n f o r l o g i s t i cs y s t e m sh a sg r e a ts p a c e t or a i s et h e e c o n o m y d e v e l o p m e n t 。a ts a m et i m ei ta l s ob e c o m e sag r e a tc h a l l e n g eb o t ht om a n a g i n g e x p e r t sa n d t ot h ee n g i n e e r si nt h i sf i e l d t h em a i nc o n t e n t si nt h i st h e s i sa r ei n c l u d e d ：t h ea s s i g n m e n tp r o b l e mi n l o g i s t i c s ，q u a d r a t i ca s s i g n m e n tp r o b l e m ，d i s t r i b u t i o no p t i m i z a t i o na n dt h e m u l t i p l e - c h o i c ek n a p s a c kp r o b l e m sr e a l i z a t i o na n da p p l i c a t i o nb yu s i n gt h e g e n e t i ca l g o r i t h ma n dq u a n t u mg e n e t i ca l g o r i t h m 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 ti nl o g i s t i c sa n dt h ea d v a n c e do p t i m i z i n g m e t h o d s t h es e c o n dc h a p t e ri sg e n e t i ca l g o r i t h m ，b r i e f l yi n t r o d u c i n gg e n e t i c a l g o r i t h mo p e r a t i o na n db a s i sk n o w l e d g e ，a n dt h en o n s t a n d a r dg e n e t i co p e r a t o r s t h et h i r dc h a p t e ri sq u a n t u mg e n e t i c a l g o r i t h m ，i n t r o d u c i n g t h eq u a n t u m m e c h a n i c sa n dt h eb a s i ce x p r e s s i n gm e t h o do fq u a n t u mb i t ，a n do p e r a t i o n r e n e w a lo fq u a n t u mg a t e t h ef o u r t hc h a p t e rp r e s e n t st h er e a l i z a t i o ni nl o g i s t i c s t r a n s p o r t a t i o no p t i m i z a t i o nt h ea s s i g n m e n tp r o b l e mb a s e do ng a 。b yal o to f e x p e r i e n c e s ，i tp r o v e dt h ec h a r a c t e r i s t i c so fg a a n dt h ei m p r o v e ds t r a t e g yi ng ai s e f f e c t i v ea n da v a i l a b l e t h ef 砒hc h a p t e ri sa b o u tt h eq u a n t u mg e n e t i ca l g o n t h m s a p p l i c a t i o ni nd i s t r i b u t i o np l a n n i n g t ob u i l dt h eq u a n t u mm o d e la n dd i s t r i b u t i o n s t r a t e g i e sa r et h ec o r eo ft h ec o u r s ei nt h i st h e o r y , t h e nc o n t i n u et op r o p o s e r e n e w a lq u a n t u mg a t e t h es i x t hc h a p t e ri st h er e s e a r c hi nl o g i s t i c sd e c i s i o n m a k i n gb yu s i n gt h eq u a n t u mg e n e t i ca l g o r i t h m t h eo b j e c ti sm u l t i p l e c h o i c e k n a p s a c ki n c o m b i n a t o r i a lo p t i m i z a t i o n 。t h ei n n o v a t i o ni st h ec o r r e c t i o nf o rt h e i l l e g a l s o l u t i o na n dt h er e s t r i c tc o n d i t i o n s ，p r o v i d i n gan e ww a yt oc o v e rt h i s p r o b l e m t h em o d e l i n gb yg ao rq g ai st h ek e yp o i n tf o rt h eo p t i m i z a t i o n t h e c o n n e c t i o nb e t w e e na l g o r i t h ma n dp r a c t i c ep r o b l e mt or e a l i z et h ei n t e g r a t i o na n d o p t i m i z a t i o nh a sg r e a tv a l u ef o rt h ef u r t h e rr e s e a r c hi nt h i sf i e l d ，b a s e do nt h e g r o a te x p e r i e n c e sa n dt e s t s m e a n w h i l et h eb e n e f i ti tb r i n g sc a nn o tb en e g l e c t e d y a n gy i n g ( c o n t r o lt h e o r ya n dc o n t r o le n g i n e e r i n g ) d i r e c t e db y w a n qx i h u a i k e y w o r d ：l o g i s t i cs y s t e mo p t i m i z a t i o n ，q u a n t u mg e n e t i ca l g o r i t h m 。a s s i g n m e n t p r o b l e m ，q a p , l o g i s t i c sd i s t r i b u t i o n ，m u l t i p l e c h o i c ek n a p s a c k i 论文独创性声明 本论丈是我个人在导师指导卜进行的研究_ 1 _ i 作及取得的研究成果。 论文中除了特别加以标注和致谢的地方外，不包括其他人或其他机构已 经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均 已在论文中作了明确的说明并表示了谢意。 诈：哲签名：盐羹日期：2 卿：坐 论文使用授权声明 本人同意上海海事大学有关保留、使用学位论文的规定，即：学校 有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以上网公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文。保密的论文在解密后遵守此规定。 作者签名：盎堇导师签名：墨址日期：2 1 掣 第1 章绪论 物流产业在国际上被喻为促进经济发展的“加速器”，亦如著名的管理学权威e f 德鲁克( p e t e red r u c k e r ) 在“黑大陆”说中所提到的：“流通是经济领域的黑暗大 陆”。消费者所支付的商品价格中，约5 0 是与商品流通活动有关的费用，因此物流 将是降低成本的最后领域。丽中国物流产业的发展必将对2 1 世纪中国经济的发展产 生积极的影响和贡献。在这一发展的关键时期，对物流系统进行优化。整体改善国 民经济的运行效率，直接提高社会经济效益，有其深远的意义。 1 1 物流发展 我国从2 0 世纪7 0 年代末从国外引入“物流”概念。到舳年代开展物流启蒙和宣 传普及，9 0 年代物流发展起步，到本世纪初物流“热”开始升温，从我困物流发展历 史及其现状和趋势来看，可以说我国的物流已经从起步阶段转向发展阶段。现代物 流基础设施初具规模，物流技术和管理水平不断提高；与之同步的物流理论研究工 作，无论是在广度还是深度上。基本已与国际接轨。虽然我国的物流技术装备j f 在 日新月异地进步，但与蓬勃发展的物流市场需求相比，无论是从量上还是质上都不 能满足要求。特别是物流器具的标准配套、各种运输方式的有效衔接以及配送、分 拣系统的有机组合等都还存在巨大差距。应该看到，物流实际操作的硬件上确实存 在着很多欠缺，但是这些硬件设施的更新和改进是可以通过加大投资，引进国外 资源等措施得到解决的。目前软件物流技术的研究的深度和广度远不及硬件设施 的改进步伐，而物流发展趋势迫切要求，有更多的学者和专家，从运筹学和工程优 化的角度来研究物流，优化物流。而且现代物流系统在借助计算机网络技术己迈入 综合化阶段，电子商务的提出，为物流企业提供了新的更完善的技术平台和市场环 境，这些外在条件的发展和成熟，将促使物流整合优化不仅仅是对企业内部的物流 过程做出调整，而且对供应链的诸多环节都要进行综合考虑。对其庞大的系统进行 优化的复杂性已不言而喻。随着我国物流理论研究的不断深入和对物流重要性认识 的逐步提高，物流业界越来越注重实践，注重技术，注重管理。 物流发展趋势： 1 物流技术现代化与综合化 现代物流服务拥有强大的“硬件”，先进的技术、装备，计算机技术、通信技术 在物流中得到广泛地应用。g p s ( 全球卫星定位系统) 与e m ( 电子地图) 等最先进 的设备应用，以及集装箱、卡车等，实现物流服务的自动化、机械化、无纸化和智 能化。同时，“软件”也与时俱进，众多先进物流管理理念推陈出新，在实践中接受 考验，不断完善。 2 物流服务系列化与专业细化 物流已超出传统意义上的分工。在传统的存储、运输、包装、流通加工之外， 衍生出市场调查、预测、采购及订单处理，以及配送、物流咨询、物流方案的设计 与选择、库存控制等更多有利于做出决策的系统系列化服务。与此同时，专业的细 化分工，出现物流外包、第三方物流、第四方物流的概念。更多的专业咨询公司为 企业提出更具有现实意义的物流方案，这一趋势将成为未来物流人才发展的一方广 阔空间。 3 物流与商流之间信息一体化 现代物流服务侧重于将物流与供应链的各个环节整合在一起，为此，信息瓶颈 必须打破。其中很多发达国家中，集商流与物流为一体的配送中心的成立，不失为 打破瓶颈的一种有效方法，极大提高物流运作的效率。 4 物流最优化 运筹学在物流系统的优化方面提供了原始的动力，现代进化算法及启发式算法 等，在量化方面为实现物流系统最优化，又提供了一把利器。很多供应链管理软件 的生成，都是以应用和物流最优化为指导方向，不断完善和发展中。可以说物流最 优化将成为未来几十年物流发展的最明显的趋势之一，将从量上和质上，给物流发 展注入强劲的动力。 5 物流响应快速化 物流服务提供者对物流配送需求的响应速度越来越快，不仅仅是商品周转次数 的加快，配送过程的简化是一明显的特征。 2 1 2 物流系统优化方法 首先，优化问题普遍存在于各个研究领域，物流系统也不例外。随着人们对优 化技术研究的逐步深入，解析算法和智能优化算法已成为常用的解决最优问题的两 种主要方法。 例如，1 9 4 9 年d a n t z i g 在提出了著名的求解线性规划问题的单纯形法之后，发 现线性规划是可以用来解决整数规划中的运输问题的；1 9 5 8 年g o m o r y 提出著名的 割平面法求解线性规划，随后l a n d 和d o i n g 于1 9 6 0 年开发了分支定界法，1 9 6 0 年 b a l a s 也提出隐枚举法求解0 - 1 整数规划，随后的动态规划是一种类似隐枚举法的一 种方法l 。这些方法都属于解析方法，能通过对模型的解析，求出最优解。应该说 解析方法是一种最有说服力的一种分析技术，当条件变化时能对所求解进行灵敏度 分析，这是其优点：但是面对复杂的现实问题，仅用解析法往往不足以表现物流活 动的全貌；此外，为了分析和求解的方便，在建模时往往做出了一些假设，有可能 影响到结果的准确性。 智能优化算法( 又称启发式算法) ，该类算法能对现实问题进行较为全面的描 述，在有效的时间里得到满意解，但不能保证是最优解。目前该类常用的三种启发 式算法有模拟退火法( s a ) ，禁忌搜索法( t s ) 和遗传算法( g a ) 。启发式算法具 有很好的可操作性，并且由于启发式原则符合人们的思维，很容易被决策者接受。 它的稳定性和通用性成为关注的焦点，对于解的评价虽不是百分百的最优，只能是 堪称满意解。 当今物流系统优化的方法很多，但仍需要得到更加科学化的模型的支持，以及 在具体问题上更贴切实际、更合理的方法和思路的提出。这将是不单单要求优化方 法上的改进，还包括更合理、更完善的模型的提出和发展。 1 3 遗传算法 遗传算法最早是由美国密执根( m i c h i g a n ) 大学j h h o l l a n d 教授提出，在他的 著作中，提出以二进制数字串为基础的基因模式理论及基本原理，为遗传算法奠定 了峰实的理论基础。经过几十年的努力，遗传算法己经成为一种成熟的具有极高鲁 棒性和广泛适用性的优化方法。 3 遗传算法是以自然选择和遗传理论为基础，通过模拟自然界的生物进化过程， 将所求解问题的解，用编码串( 也称为“染色体”) 来加以表示，并形成一组代表该优化 问题的一些可能解的集合，我们称为种群，然后利用相应的遗传算子( 选择，交叉， 变异) 作用于种群中的各个染色体，即按照“适者生存，优胜劣汰”的原则，生成新的 种群，反复迭代，最终达到包含问题最优解染色体的优良种群，达到优化的目的。 g a 摒弃了传统的搜索方式，将生物进化过程中适者生存规则与群体内部染色 体的随机信息交换机制相结合，进行高效的全局寻优搜索。自1 9 7 5 年j o h nh h o l l a n d 教授出版关于g a 的经典之作( a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s 1 2 l 以来，g a 作为一种通用的、与求解问题无关的广谱优化算法，在生物技术、计算 机辅助设计、数据分析、模式识别、人工智能、生产调度、微电子学、售货服务系 统等领域都得到应用，成为求解全局优化问题得最得力的工具之一。 1 4 量子遗传算法 量子遗传算法属于量子信息的范畴。量子信息是信息科学和量子力学相结合的 新兴交叉科学。量子信息科学采用量子态作为信息单元，一旦用量子态来表示信 息，就实现了信息的量子化。于是，无论从信息的传递还是提取都必须服从量子的 物理原理。特别值得一提的是信息的量子处理，就是对该信息实施幺正变换，信息 的提取就是对信息系统进行量子测量1 3 1 。 量子信息领域的权威b e n n e t t 和d i v i n c c n z o 在自然杂志撰文对量子信息做 了总结性的评价：从经典信息到量子信息的推广，就像从实数到复数的推广一样。 量子计算正是利用了量子理论中有关量子态的叠加、纠缠和干涉等特性，通过量子 并行计算有可能解决经典计算中的n p 问题。尤其1 9 9 4 年s h o r 提出第一个量子算 法，用来求解大数质因子分解的经典计算难题。1 9 9 6 年g r o v e r 提出随机数据库搜索 的量子算法，在量子计算机上可实现对未加整理数据库数量级的加速搜索。从 此，量子计算以其独特的计算性能引起了广泛瞩目，迅速成为研究的热点。量子遗 传算法是量子计算与遗传算法相结合的产物，它将量子的多态性、叠加性、纠缠性 等与遗传算法的全局寻优能力结合起来，因而具有比传统的遗传算法更高的效率。 4 1 5 内容和结构安排 本课题的研究得到上海市重点学科“物流管理与工程”( t 0 6 0 2 ) 项目，以及上 海市教委科研项f 1 ( 0 5 f 7 _ 0 6 ) “群智能理论及其在多目标优化中的应用”的支持。 论文共分为6 章，分别介绍如下： 第一章绪论，阐述了物流优化的意义及其发展趋势，对遗传算法和量子遗传算 法作了简单介绍： 第二章遗传算法，介绍该算法的发展过程和理论基础，对一些改进遗传算法进 行讨论： 第三章量子遗传算法，简要介绍了量子遗传算法的进化机理，量子更新策略是 本章的重点； 第四章遗传算法在运输最优化指派问题上的实现，包括物流指派模型和二次分 配问题，随着问题规模的扩大，改进遗传算法的有效性和局限性也进一步体现； 第五章量子遗传算法在物流配送系统的应用，根据量子编码的特性，提出新的 量子配送模型和配送策略，并在此基础上对量子遗传操作进行改进，提出新的派型 量子门更新，使量子遗传算法在配送领域的应用得以实现； 第六章量子遗传算法在物流决策支持方面的研究，以组合优化问题中的多选择 背包问题为研究对象，实现量子遗传算法在该领域的应用，其中对约束问题的处 理，以及对非法解处理的思路上，有所侧重。 5 2 1 遗传算法概述 第2 章遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 是一种基于生物遗传和进化机制的适 合于复杂系统优化的自适应概率优化技术。作为一种实用、高效、鲁棒性强的优化 技术，从7 0 年代兴起，8 0 年代发展到9 0 年代的高潮，国内外的专家和学者做出了 很大贡献。1 9 6 7 年，h o l l a n d 的学生b a g l e y 在博士论文中首次提出“遗传算法”一 词，又发展了复制、交叉，变异、显性、倒位等遗传算子。h o l l a n d 教授提出了遗传 算法的基本定理模式定理( s c h e m at h e o r e m ) ，8 0 年代实现了第一个基于遗传 算法的机器学习系统，开创了遗传算法机器学习的新概念；d ej o n g 基于大量的纯数 值函数优化试验，建立了该算法的工作框架；1 9 8 9 年，g o l d b e r g 出版了g e n e t i c a l g o r i t h mi ns e a r c h ，o p t i m i z a t i o na n dm a c h i n el e a r n i n g 一书1 4 j ，系统总结了遗传算法 的主要研究结果，全面介绍了遗传算法的基本原理及其应用。1 9 9 1 年，d a v i s 出版 了h a n d b o o ko fg e n e t i ca l g o r i t h m s 一书，介绍了遗传算法在科学计算、工程技术和 社会经济中的大量实验；1 9 9 2 年k o z a 将遗传算法用于计算机程序优化及其自动生 成，提出遗传编程概念( g e n e t i cp r o g r a m m i n g ) 。此外m i s t u og e n 教授及其学生程润 伟编著的g e n e t i ca l g o r i t h m sa n de n g i n e e r i n gd e s i g n 推动遗传算法的普及和研究成果 在实践应用上的转化1 列，还有很多国内外著名的学者专家在该领域进行深入的研 究，使遗传算法成为进化技术领域中众所周知的一种仿生算法。 作为强有力且应用广泛的随机搜索和优化方法，遗传算法可能是当今影响最广 泛的进化计算方法之一。目前，遗传算法迅速发展，广泛应用于系统优化、参数估 计，机器学习、过程控制、模式识别、人工智能、故障诊断以及计算机技术等领 域，取得了良好的效果。随着遗传算法的基本原理、方法及其应用技巧的深入研 究，其应用范围也越来越广泛，尤其在工程领域内发展迅速。 6 2 2 遗传算法的理论基础 遗传算法有效性的理论依据是模式定理和积木块假设。h o l l a n d 的模式定理通过 计算有用相似性，即模式( p a t t e n ) ，奠定了遗传算法的数学基础，是该算法的t 要 定理，在一定程度上解释了该算法的机理、数学特性及计算能力。 模式定理保证了较优的模式( 或较优解) 的样本呈指数级增长，从而满足了寻 找最优解的必要条件，即遗传算法存在着寻找到全局最优解的可能性。而积木块假 设指出，遗传算法具备寻找到全局最优解的能力，即具有低阶、短距、高平均适应 度的模式，在遗传算子的作用下，相互结合，能生成高阶、长距、高平均适应度的 模式，最终生成全局最优解1 6 j 。 2 3 遗传算法过程 遗传算法的一般结构可以描述如下： b e g i n t 一0 初始化p ( t ) 评价p ( t ) w h i l e ( 终止条件不满足) d o b e g i n 重组p ( o 以产生c 0 ) 评价c ( t ) 从p ( t ) 矛l lc ( t ) 中选择e ( t + o t t + 1 e n d e n d 其他遗传算法过程与上述过程基本类似，例如混合遗传算法的一般结构，是在 重组r 0 ) 产生c 0 ) 之后，添加了一步“对c 0 ) 进行局部爬山”。原则上，遗传算法提供 了一种在复杂解空间上进行有向随机搜索的方法。 7 2 4 改进遗传算法 虽然遗传算法与传统的优化方法比较，具有相当多的优点，如：g a 不受问题 本身的性质、优化准则形式、模型结构形式、被优化参数数目和有无约束等的限 制，仅用目标函数在概率准则引导下进行并行全局自适用搜索，能够处理传统优化 方法难以解决的复杂问题，具有极高的鲁棒性和广泛适用性。但是遗传算法存在的 问题仍是不可忽视的，例如早熟现象，收敛较慢，以及适应度标定方式的多样性 等。很多的专家学者在不断的研究中，提出各种变形的遗传算法。 改进遗传算法的基本途径主要有以下几方面： 1 、改进编码方式；这是建模过程中的第一步，也是最关键的一步，初始编 码方式的优劣，可能成为影响问题求解质量和速度的一个重大因素； 2 、混合遗传算法( h y b r i dg e n e t i ca l g o r i t h m ) ；包括遗传算法与最速下降法 相结合的混合遗传算法，以及与模拟退火法( s i m u l a t e da n n e a l i n g ) 相 结合的混合遗传算法； 3 、采用动态自适应技术，控制进化过程中的控制参数和编码精度； 4 、采用非标准的遗传操作算子； 5 、采用并行算法； 很多改进的遗传算法的侧重点仍然是交叉、变异和选择，下面介绍最近提出的几种 改进遗传算法的研究成果。 2 4 1 编码方式的改进 基本遗传算法使用固定长度的二进制符号串来表示群体的个体，其等位基因由 二值 o ，1 所组成。初始群体中的各个个体的基因可用均匀分布的随机数来生成。 鉴于二进制编码方式有其自身的局限性，又提出了实数编码，实数序列编码方式， 带优先权重的编码方式，量子编码方式等。m a s a t o s h is a k a w a 和k o s u k ek a t o 提出 了使用双串的遗传算法( g e n e t i ca l g o r i t h mw i t hd o u b l es t r i n g s ，即g a d s ) 【4 2 l ，它把 染色体编码为一种叫做双串( d o u b l es t r i n g s ) 的结构，通过特定的解码后产生的总 是可行解。文献 4 3 1 中采用了该思想对0 - 1 背包问题进行了编码和解码过程。使得遗 传算法的改进更趋于合理化和科学化。 同时在编码长度上也出现了可变长度的序列编码方式等，针对早熟收敛和后期 8 搜索迟钝的解决方案，可以采用种群规模和进化代数进一步加大，最新的还有引入 主群和属群的概念等，这些都是在编码方式上对遗传算法进行改进。 2 4 2 遗传算子的改进 在改进的遗传算法中，最多的是对遗传算予的改进。以交叉方式的改进为例， 描述如下： 参数：交叉概率p ，种群规模n ，最大运行代数m a x g e mg 为进化代数，交叉次 数p cn u m b e r 。 s t e p i ：种群复制，p o p 2 = p o p l ，将原种群p o p l 复制给p o p 2 ； s t e p 2 ：i fr a n d = pc 。( g m a x g e n ) 随机产生父本和母本； f o rn = 1 ：1 ：p c _ n u m b e r 按照交叉方式进行交叉； e n d e n d s t e p 3 ：从子代中返回给p o p 2 ： 其中，种群的复制，保证原种群中最优个体不变，为以后的选择提供条件； 动态确定交叉概率，既可防止优良基因因为交叉而遭破坏，又可在陷入局优解时为 种群引入新的基因；交叉方式可以采用单点交叉多点交叉、树交叉、部分匹配交 叉、以及中值交叉等； p c _ n u m b e r 的确定与种群规模有关，规模越大，远亲交叉的机会就越多，带来意外 的最优解的概率也就越大。 2 5 本章小结 本章通过了解遗传算法发展过程、数学理论基础以及进化流程，进一步探讨了 改进的遗传算法，包括编码方式的改进和遗传算子的改进，其中对遗传算子的改进 主要讨论了交叉算子。 9 第3 章量子遗传算法 量子汁铮足2 0t l = 纪的一大奇迹，它的概念直到l o 多年前爿j l 叶：现。量- 了计算成 功地利用了量子理论中态的迭加( s u p e r p o s i t i o n ) 、纠缠( e n t a n g l e m e n t ) 、坍塌 ( c o l l a p s e ) 等概念，使计算取得了质的突破，使得一些传统意义上的n p c o m p l e t e 问题在量子计算层面上有了多项式级求解的可能性。同时量子计算及量子 理论已经与计算机科学、信息科学等相互交叉，产生了诸如量子计算机、量子通 信、量子编码、量子信息处理等新的研究领域，为传统理论的发展提供了全新的思 路和研究方法。 3 1 量子遗传算法简介 3 1 1 量子遗传算法概述 首先将量子计算理论和进化算法相结合进行研究的是英图e x t e r 大学计算机科 学系的a j i tn a r a y a n a n 和m a r km o o r e ，并于1 9 9 6 年提出了量子遗传算法的概念1 7 1 ， 1 9 9 5 年n a r a y a n a n 等人利用量子理论中“多宇宙”( m a n yu n i v e r s e s ) 的观点，重新设 计了染色体的群体机构和遗传策略，提出一个多宇宙量子衍生遗传算法( q l g a ) ， 在求解t s p 问题上得到较好的结果。从形式上看它很像是一种隔离小生境遗传算 法，由于该算法基于传统遗传算法对量子多宇宙思想进行模拟，因而存在计算复杂 度较高的问题。1 9 9 9 年s p e c t o r 等人利用遗传编程技术( g p ) 产生了一个量子与或 算法，其性能优于经典算法。此后，在2 0 0 0 年k u k h y u nh a n 等人将量子遗传算法 进一步完善，并首次将其应用于组合优化问题中；国内，中国科学技术大学的杨俊 安博士在改进量子遗传算法的基础上，提出了一种新的量子遗传算法并从理论上证 明了算法的全局收剑性，同时提出了基于量子遗传算法与独立分量分析算法相结合 的盲源分离新算法，进一步发展了量子遗传算法。目前，量子遗传算法已经受到人 们的密切关注，并且成为某些学科和领域的研究热点1 8 j 。传统的g a 最明显的缺点 是它的收敛问题，其中包括收敛速度慢和未成熟收敛。而在进化中未成熟的优良子 群体所提供的信息并没有充分利用，因此，在进化中导入良好的引导机制可以增强 算法的智能性，提高搜索效率，使问题更趋向于实际工程。 目前，这一领域的研究成果主要体现在两类模型上：其一、基于量子多宇宙特 征的多宇宙量子衍生遗传算法( q u a n t u mi n s p i r e dg e n e t i ca l g o r i t h m ，q i g a ) 。其 二、基于量子比特和量子态叠加特性的遗传量子算法( g e n e t i cq u a n t u ma l g o r i t h m ， g q a ) 1 9 l 。在q i g a ，i ，多宇宙是通过多个种群模拟获得的，并没有利j j 量f 的念 叠加表达，因而仍属于常规遗传算法1 1 3 】。 o g a 和g q a 本质上都属于概率演化算法，在算法中采用了类似w i n n e rt a k e s a u ? 的贪心策略来实现个体的演化，因此，对于一些复杂的优化问题，该算法容易 陷入局部最优。 3 1 2 量子遗传算法特点 首先，遗传算法作为一种模拟生物界自然进化过程的启发式搜索算法，大量研 究与应用成果表明它是高效、稳健的优化算法。但是，随着研究的深入，遗传算法 的局限与不足也逐渐突现出来： 1 ) 计算复杂度较高，g a 是一种基于群体的搜索算法，群体规模小( 1 0 0 个左 右) 将限制算法对长阶模式( s c h e m a ) 的考察，而群体规模大则会导致算法的计算 复杂度升高； 2 ) 固定的、与问题无关的交叉算予常常会频繁地破坏积木块( b u i l d i n g b l o c k ) ，或无法将他们有效重组； 3 ) 遗传算法对那螳积木块在编码个体中排列紧密的问题工作很好，而对那些积 木块在整个解空问中分散问题的处理，则效果不佳。 针对这些不足，近年来人们开始探索一些新的遗传算法模型，其中一类基于概 率模型的遗传算法如e d a ( 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 ) 逐渐引起关注。该 类算法利用概率模型对解空间中有希望出现最优解的区域进行建模，再利用该模型 引导遗传算法快速向全局最优解收敛，与传统遗传算法相比，该类算法的计算复杂 度有较大的降低，但是，这类算法存在的不足主要在于概率模型的选择上。 量子遗传算法作为两种算法的结合，提供了一种更自然简洁和灵活的模型表达 方式，并存在支持其演化的丰富的算子集合。 与传统的遗传算法相比较，量子遗传算法能够以更小的种群规模，在更短的时 间里找到问题的最优解。该算法采用的染色体编码方式不是传统的二进制编码、实 数编码或符号编码等方式，而是量子位染色体编码方式。并且对父代的操作也不是 1 1 采用传统的复制、交叉和变异等操作，而是利用量子门作用完成更新父代个体，从 而产生新的子代个体。同时量子位是量子遗传算法中最小的信息存储单元。在量子 遗传算法中，采用的量子念的基本特性就是量子叠加态，并且是对量子概率幅进行 操作。 量子遗传算法与其他遗传算法相比较，具有以下优点： 1 1 量子遗传算法中的种群规模可以很小，但是并不影响算法的性能，仍能保持 种群中个体的多样性。 在量子遗传算法中，采用量子位的编码方式，一个量子位染色体能够表示叠 加的状态，因此与传统的遗传算法比较，它具有更好的种群多样性。 3 ) 2 子遗传算法具有较高的搜索效率，广泛的适应性，迅速的收敛性。 4 1 量子遗传算法具有良好的全局搜索能力，同时由于量子位的概率表示，它能 够用一个量子位同时表示出所有的线性叠加状态，这样就大大地减少了染色体的个 数，并且每个量子位都是由当前最优解和其概率决定的，这样每个个体之间的联系 性就比较弱。因此，它比传统的遗传算法更适于并行结构的实现。 5 1 量子遗传算法同时兼有数据探索和数据挖掘的能力，这得益于量子遗传算法 本身的算法结构。 3 1 3 量子遗传算法目前的应用 世界上对量子遗传算法的研究较少，其代表性研究如下：a j i tn a r a y a n a n 和m a r k m o o r e 等人在1 9 9 6 年将量子多宇宙的概念引入遗传算法，提出了量子衍生遗传算法 ( 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 s ) ，并成功地用它解决了t s p 问题。基于多宇宙 概念的量子衍生遗传算法，利用多个种群的并行搜索，增大搜索的范围，利用种群 之间的联合交叉，实现种群之间信息的交流，将多个种群各自分散的搜索联系起 来，从整体上提高算法搜索的效率。基于量子多宇宙概念的遗传算法本质上仍属于 常规遗传算法的范畴，它并没有用到量子计算中的一些概念，如叠加态的应用，所 以说它与量子计算的差距还很大。 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 m a l g o r i t b m q g a ) 。他将量子的态矢量表达引入遗传编码，利用量子旋转门实现染 色体基因的调整，使得该算法将来在量子计算机上执行成为可能，并且给出了一种 基因调整策略，并以此实现了0 1 背包问题的求解，结果其性能要优于传统的遗传 算法。k u k h y u nh a n 的遗传量子算法( g q a ) 实际上是一种概率演化算法，在算法中 没有采用任何遗传操作，因为他认为该算法染色体的多态性表达，已经能够保证算 法具有足够的多样性，同时具有开发能力和探索能力。因而，不再需要有交叉和变 异。但是对于一些多峰函数优化问题，浚算法仍然容易陷入局部最优，针对该问题 国内很多学者提出了很多改进的q g a 。例如引入的小生境协同进化策略，使得该算 法能更好地处理多变量多峰函数优化问题，提出了r c q g a ( r e a lc o d e dc h a o t i c 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 ) 提供了解决复杂函数优化问题的一条思路。在 解决实际组合优化问题上，量子遗传算法也有新的突破。如熊焰等人，针对0 1 背 包问题对该算法和传统遗传算法进行了对比试验，证明了该算法在解决组合优化问 题上的有效性l r 丌。 3 2 量子遗传算法中的基本概念 3 2 1 量子比特 比特( b i t ) 是经典计算和经典信息的基本概念，量子计算与量子信息建立在类 似的概念基础上，诞生了量子比特( q u a n t u mb i t 或q u b i t ) 1 3 1 。该节比照经典比特介 绍单量子比特和多量子比特的属性。 在量子信息论中，信息的载体是一个一般的二态量子体系。这个二态的量子体 系，可以是一个二能级的原子或离子，也可以是一自旋为1 2 的粒子或具有两个偏 振方向的光子，所有这些体系，均被称为量子比特即量子位。区别与经典比特，量 子比特可以处于0 ，1 两个本征态的任意叠加状态，而且对于量子比特的操作过程 中，两态的叠加振幅可以相互干涉。基于这一点在下面的编码过程中，充分利用了 量子的相干性。 3 2 2 量子编码 当采用量子比特编码时，遗传个体如下： p 倒：慨一= 】 定义；只( o ) 一k 1 2 ，v , 0 ) - 旧1 2 表示第i 个量子比特耿值分别为一0 和1 的概率，则整个个体坍缩到某个特定解s 的 概率p ( s ) 为：p ( s ) = 日b ，) x 只g ：) 日蛳。b 脚。一。) b mj ， s o ，1 是解s 的第i 个分量。因此，当采用晕子比特的概率幅对进行编码时，个 体所表达的就是解空间中解的取值概率分布。 因此，针对上述量子编码，需要设计新的交叉和变异算子。在遗传算法中，交 叉算子的目的是实现两个个体间结构信息的互换，在q c g a 中最能体现各个个体结 构信息的是各个个体的演化目标。因此我们可以设计一种新的交叉算子，随机选 择两个个体，暂时交换它们的演化目标，并以新的目标演化一次。经过一次交叉操 作，两个个体所表达的解的概率分布都会做出相应修改，这相当于将一个个体所获 得的关于解空间分布的知识传递给另一个个体。 变异的作用是( 轻微地) “打乱”某个个体当前的演化状态，以增强个体的局部 寻优能力。我们定义了一个单量子比特变异算子，其思想可进一步推广到多量子比 特的情形。通过将量子比特的概率幅对的位置对调，改变该量子比特态叠加的状 态，同时也改