（电路与系统专业论文）面向特定对象的量子演化模型研究及应用.pdf

删 u n i v e r s i t yo fs c i e n c ea n dt e c h n o l o g yo fc h i n a adi s s e r t a t i o nf o rm a s t e r sd e g r e e r e s e a r c ho nq u a n t u m e v o lu t i o nmq d e i t h e o d ef o rt h e i s p e c i f i co b j e c t a n di t s a p p l i c a t i o n a u t h o r sn a m e ： s p e c i a l i t y ： 一 s u p e r v i s o r ： 1 n fi n i s h e dt i m e ： s i t o n gc a o c i r c u i t sa n ds y s t e m s a s s o c i a t ep r o f x i a n f uc h e n j u n e1 0 m ，2 0 1 2 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名：鱼塾闼生：签字日期：垒垒! ! ! ! 查 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入中 国学位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内 容相一致。 保密的学位论文在解密后也遵守此规定。 口开口保密( 年) 作者签名：萤塞衄刍： 导师签名： 签字日期：望里! ! ! ! 冬签字日期： 摘要 摘要 量子衍生计算以其“叠态 与“纠缠 特性而被广泛运用于复杂智能信息 处理领域，以期提高组合优化算法性能。由于物理机制机理不同，量子计算存在 物理模拟十分困难等不足之处。背包问题是经典组合优化n p 类问题，实际应用 中往往因其多维约束与多目标优化而使问题变得更趋复杂。本文针对从实际应用 课题中抽取的特殊背包问题，旨在研究设计一种高性能的量子演化算法模型，并 在此基础上进行相关实验研究与应用研究，所做的主要研究工作成果如下： ( 1 ) 提出一种从数理角度模拟“叠态”、“塌缩”与“纠缠特性的量子 衍生演化算法模型。以高斯随机过程虚拟量子计算的叠态与塌缩特性，以遗传交 配等操作模拟量子计算的纠缠特性。理论分析与实验结果均显示本文提出的新型 量子遗传算法具有种群多样性维护性能较好、时空算法复杂度适中、优化质量较 高等特点。 ( 2 ) 针对多维背包约束问题，本文提出了一种新的修复策略。针对算法遗 传演化过程中产生的超出约束条件的非法可行解，本文研究设计了一种基于线性 松弛问题求解的染色体修复方案。将该修复策略与所建量子衍生遗传优化算法结 合，应用于处理多维背包约束问题，实验结果验证了该方法的有效性与实用性。 ( 3 ) 针对遗传算法局域搜索性能较差和遗传隐匿问题，本文研究了一种基 于邻域混沌扰动的“量子演化+ 调和算法混合模型特性，以期综合利用遗传算 法的并行分布式全局搜索优势与基于邻域混沌扰动的调和算法局部优化性能。函 数优化的部分实验结果显示，该混合模型表现了良好的优化性能。将该模型应用 于求解多维背包问题的实验结果显示，在处理特长染色体优化方面，该算法模型 效果较优。 。 ( 4 ) 将本文提出的量子遗传算法应用于9 2 1 计划子项目一货物装载布局优 化软件研制，已成功验收，并获航天相关部门验收鉴定专家较高评价。 关键词：量子计算遗传算法高斯噪声多维背包问题和声搜索混沌 摘要 a b s t r a c t a b s t r a c t t h ec h a r a c t e r i s t i c so ft h es u p e r p o s i t i o n ，e n t a n g l e m e n to fq u a n t u mi n s p i r e d c o m p u t a t i o na rew i d e l yu s e di nc o m p l e xi 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 , i no r d e r t oi m p r o v et h ep e r f o r m a n c eo ft h ea l g o r i t h mt os o l v ec o m b i n a t o r i a lo p t i m i z a t i o n a l g o r i t h m d u et ot h ed i f f e r e n c eo ft h ep h y s i c a lm e c h a n i s m ，t h ep h y s i c a ls i m u l a t i o n o fq u a n t u mc o m p u t a t i o ni sv e r yd i f f i c u l t k n a p s a c kp r o b l e mi sac l a s s i c a ln p p r o b l e mo fc o m b i n a t o r i a lo p t i m i z a t i o n b e c a u s eo fs o m ek n a p s a c kp r o b l e m sh a v e m u l t i - d i m e n s i o n a lc o n s t r a i n t sa n ds o m eh a v em u l t i d i m e n s i o n a lo b j e c t s ，t h es o l v i n g o ft h e s ep r o b l e m sb e c o m em o r ea n dm o r ec o m p l e x i nv i e wo ft h ep r a c t i c a l a p p l i c a t i o no fs p e c i a lk n a p s a c kp r o b l e m ，ah i g hp e r f o r m a n c eq u a n t u me v o l u t i o n a r y a l g o r i t h mm o d e lh a v eb e e np r o p o s e di nt h i sp a p e r a n ds o m ee x p e r i m e n t a lr e s e a r c h a n da p p l i c a t i o nr e s e a r c hh a v eb e e nc a r r i e do u to nt h eb a s i so ft h i sm o d e l ，t h em a i n r e s e a r c hr e s u l t sa r ea sf o l l o w s ： ( 1 ) an e wq 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 mm o d e li sp r o p o s e di nt h i s p a p e r t h es i m u l a t i o no ft h e c h a r a c t e r i s t i c so ft h es u p e r p o s i t i o n , c o l l a p s e ，a n d e n t a n g l e m e n to fq u a n t u mc o m p u t a t i o ni sc a r r i e do u tf r o mm a t h e m a t i c a la s p e c t g a u s ss t o c h a s t i cp r o c e s si su s e dt os i m u l a t et h es u p e r p o s i t i o n ，c o l l a p s eo fq u a n t u m c o m p u t a t i o n g e n e t i co p e r a t i o ni su s e dt os i m u l a t et h ee n t a n g l e m e n to fq u a n t u m c o m p u t a t i o n t h e o r e t i c a la n a l y s i sa n de x p e r i m e n t a ld a t as h o wt h a tt h en o v e l q u a n t u mg e n e t i ca l g o r i t h mp r o p o s e di nt h i sp a p e rh a sb e t t e rp o p u l a t i o nd i v e r s i t y m a i n t e n a n c ep e r f o r m a n c e ，t e m p o r a la n ds p a t i a lc o m p l e x i t y , a n db e t t e ro p t i m i z a t i o n ( 2 ) i no r d e rt os o l v et h ec o n s t r a i n t so f 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 ，a n e wr e p a i rs t r a t e g yi sp r o p o s e d f o rt h ei l l e g a lf e a s i b l es o l u t i o n st h a te x c e e dt h e c o n s t r a i n t si nt h ep r o c e s s i n go ft h ea l g o r i t h m ，t h el i n e a rr e l a x a t i o no ft h ep r o b l e mi s s o l v e dt or e p a i rt h ei l l e g a ls o l u t i o n 硼1 er e p a i rs t r a t e g ya n dt h eq 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 mh a v eb e e nc o m b i n e dt op r o c e s st h em u l t i d i m e n s i o n a lk n a p s a c k p r o b l e m ，t h ee x p e r i m e n t a lr e s u l t sv e n f yt h ee f f e c t i v e n e s sa n dp r a c t i c a b i l i t yo ft h e m e t h o d ( 3 ) a i m i n ga tt h ep o o rp e r f o r m a n c eo ft h el o c a ls e a r c ho fg e n e t i ca l g o r i t h ma n d t h eg e n e t i cl a t e n tp r o b l e m s ，am o d e lb a s e do nt h ec h a o sd i s t u r b a n c eo fn e i g h b o r h o o d h a v eb e e nu s e di nt h e q u a n t u me v o l u t i o na l g o r i t h m + h a r m o n ys e a r c h ”i nt h i s i i i p a p e r i tc o m p r e h e n s i v eu t i l i z a t e st h ea b i l i t yi np a r a l l e la n dd i s t r i b u t e dr g o b a ls e a r c h o fg e n e t i ca l g o r i t h ma n dl o c a lo p t i m i z a t i o np e r f o r m a n c eo fh a r m o n ys e a r c h a l g o r i t h mb a s e do i lc h a o t i c t h ee x p e r i m e n t a lr e s u l t so ff u n c t i o no p t i m i z a t i o ns h o w 1 a t , t h em o d e lh a v eag o o do p t i m i z a t i o np e r f o r m a n c e t h em o d e li su s e dt os o l v e m u l t i d i m e n s i o n a l k n a p s a c kp r o b l e m e x p e r i m e n t a l r e s u l t s s h o w 廿l a t ，i n t h e p r o c e s s i n go fl o n gc h r o m o s o m eo p t i m i z a t i o n , t h ea l g o r i t h mm o d e li sb e t t e r ( 4 ) t h eq u a n t u mg e n e t i ca l g o r i t h mi sa p p l i e dt ot h e9 2 1 p l a n - - c a r g ol o a d i n g l a y o u to p t i m i z a t i o ns o f t w a r ed e v e l o p m e n t , a n di ti ss u c c e s s f u la c c e p t e d k e yw o r d s ：q u a n t u mc o m p u t a t i o ng e n e t i ca l g o r i t h mg a u s s i a nn o i s e 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 mh a r m o n ys e a r c hc h a o t i c i v 目录 目录 摘要i a b s t r a c t i i i 目录v 图表目录i x 第1 章绪论i 1 1 引言1 1 2 研究背景i 1 2 1 组合优化问题1 1 2 2 组合优化算法2 1 3 发展历史及研究现状5 1 3 1 遗传算法5 1 3 2 量子进化算法6 1 4 本文主要工作及结构安排9 1 4 1 本文的主要研究工作9 1 4 2 论文结构安排9 第2 章理论概述i i 2 1 遗传算法概述i l 2 1 1 遗传算法定义1 1 2 1 2 遗传算法基本要素l l 2 2 量子计算概述1 4 2 2 1 量子比特1 4 2 2 2 量子逻辑门15 2 2 3 量子优化算法15 2 3 量子遗传算法概述1 6 v 目录 2 3 1 编码方式1 6 2 3 2 量子遗传算法流程1 7 2 4 背包问题概述1 7 2 4 1 经典背包问题概述。1 7 2 4 2 其它背包问题概述1 8 2 5 函数优化问题概述。l9 2 5 1 函数优化问题描述l9 2 5 2b e n c h m a r k 函数1 9 2 6 本章小结2 3 第3 章基于随机干扰的量子遗传算法2 5 3 1 引言2 5 3 2 基于随机干扰的量子遗传算法2 5 3 2 1 几种重要的随机变量分布2 5 3 2 2 算法模型2 7 3 2 3 算法流程3 0 3 3 量子遗传算法解决函数优化3 l 3 3 1 求解方式及步骤31 3 3 2 实验结果及性能分析3 4 3 4 量子遗传算法求解多维背包问题。4 6 3 4 1 求解方法及步骤4 6 3 4 2 实验结果及性能分析4 9 3 5 量子优化模拟及多维背包问题修复算子的改进5 2 3 5 1 量子优化5 2 3 5 2 修复算子改进5 3 3 5 3 实验结果及性能分析5 8 3 6 本章小结6 0 第4 章混合量子遗传算法6 3 4 1 引言6 3 4 2 和声搜索算法简介。6 3 4 2 1 和声搜索算法概述6 3 4 2 2 和声搜索算法处理步骤“ 目录 4 2 3 和声搜索算法特点6 7 4 3 混合量子遗传算法6 7 4 3 1 算法提出6 7 4 3 2 算法模型6 8 4 4 函数优化中的应用6 8 4 4 1 求解方式以及算法流程6 8 4 4 2 实验结果及性能分析6 9 4 5 新个体产生方式改进7 4 4 5 1 混沌优化方法。7 4 4 5 2 改进方法。7 5 4 5 3 算法流程7 5 4 5 4 实验结果及性能分析7 6 4 6 多维背包问题求解8 2 4 6 1 和声搜索算法在二进制编码中的应用8 2 4 6 2 算法模型8 3 4 6 3 实验结果及性能分析8 3 4 7 本章小结8 5 第5 章面向特定对象的量子演化模型8 7 5 1 引言8 7 5 2 系统设计需求及总体架构8 7 5 2 1 系统设计需求。8 7 5 2 2 系统总体架构8 7 5 3 运行环境8 8 5 3 1 硬件环境8 8 5 3 2 硬件环境8 8 5 4 系统设计及实现8 8 5 4 1 数据管理子系统8 8 5 4 2 布局优化子系统8 9 5 4 3 视景显示子系统9 0 5 5 本章小结9l 第6 章总结与展望9 3 v i l 一 旦茎 一 一一 6 1 总结9 3 6 2 工作展望9 3 参考文献9 5 致谢9 9 在读期间参与的科研项目与研究成果1 0 1 图表目录 图表目录 图1 1 种群结构分类7 图2 1z 函数图2 0 图2 2 五函数图2 0 图2 3 石函数图2 l 图2 4 正函数图2 l 图2 5z 函数图2 2 图2 6 五函数图2 2 图2 7 石函数图2 3 图2 8 石函数图2 3 图3 1 高斯分布概率密度函数2 6 图3 2 均匀分布概率密度函数2 6 图3 3 指数分布概率密度函数2 7 图3 4 个体叠态模拟图2 9 图3 5q g a 流程图3l 图3 6 测量父代个体l 模拟图3 3 图3 7 测量父代个体2 模拟图3 3 图3 8 子代个体1 叠态模拟图3 4 图3 9 子代个体2 叠态模拟图3 4 图3 1 0s g a 与q g a 求解函数彳最优个体3 6 图3 11s g a 与q g a 求解函数正最优个体3 6 图3 1 2s g a 与q g a 求解函数石最优个体3 7 i x 图表目录 图3 1 3s g a 与q g a 求解函数六最优个体3 7 图3 1 4s g a 与q g a 求解函数六最优个体3 8 图3 1 5s g a 与q g a 求解函数五最优个体3 8 图3 1 6s g a 与q g a 求解函数 最优个体3 9 图3 1 7s g a 与q g a 求解函数正最优个体3 9 图3 1 8 函数z 基因多样性分布图4 1 图3 1 9 函数五基因多样性分布图4 2 图3 2 0 函数五基因多样性分布图4 3 图3 2 1 函数正基因多样性分布图4 4 图3 2 2 函数六基因多样性分布图4 5 图3 2 3 量子优化模拟图5 3 图3 2 4 量子变异模拟图5 3 图4 1 和声记忆库结构图“ 图4 2 和声搜索算法流程图。6 6 图4 3 函数z 最优个体函数图7 0 图4 4 函数五最优个体函数图7 0 图4 5 函数六最优个体函数图7 1 图4 6 函数六最优个体函数图7 l 图4 7 函数六最优个体函数图7 2 图4 8 函数五最优个体函数图7 2 x 图表目录 图4 9 函数厶最优个体函数图7 3 图4 1o 函数石最优个体函数图7 3 图4 1 l 基于混沌的和声搜索流程图7 6 图4 1 2 函数石最优个体函数图7 8 图4 13 函数石最优个体函数图7 8 图4 1 4 函数六最优个体函数图。7 9 图4 1 5 函数五最优个体函数图7 9 图4 16 函数石最优个体函数图8 0 图4 1 7 函数五最优个体函数图8 0 图4 1 8 函数工最优个体函数图8 l 图4 1 9 函数石最优个体函数图8 1 图5 1 货物装载布局优化软件组成图8 8 图5 2 数据管理子系统界面8 9 图5 3 布局优化子系统界面8 9 图5 4 布局结果平面显示9 0 图5 5 布局结果三维显示。9 l 表3 1s g a 与q g a 对比实验3 5 表3 2 交叉算子选择4 9 表3 3 染色体长度为1 0 0 时仃与解的关系。5 0 表3 4 染色体长度为2 5 0 时盯与解的关系5 0 表3 5s g a 与n q g a 演化结果5 l 表3 6 不可行解修复方法对比实验5 8 表4 1 音乐演奏与优化问题类比6 3 表4 2o g a 与h o g a 演化结果6 9 x i 图表目录 表4 3 随机与混沌扰动实验7 7 表4 4 基于和声搜索的量子遗传算法求解m k p 8 4 第1 章绪论 1 1引言 第1 章绪论 本章首先介绍了本课题的研究背景，给出本文最终的应用方向一背包问题， 针对可用于求解背包问题的算法进行分析。经过比较，选择量子遗传算法作为本 文研究方向。本章还讨论了遗传算法和量子遗传算法的研究现状。最后给出本文 的组织结构。 1 2 研究背景 1 2 1 组合优化问题 组合优化( c o m b i n a t o r i a lo p t i m i z a t i o n ) 学科作为应用数学的一个重要分 支，需要在复杂且庞大的搜索空间中找寻最优解或近似最优解。组合优化问题在 管理科学、工程技术、自然科学等领域中大量存在。随着其规模的不断增大，时 间复杂度也急速提高。若要有效的找到可行解，就必须尽力缩小搜索范围，否则 将会产生搜索空间的组合爆炸。因此，解决这一难题是现在的一个热点研究问题。 在算法研究过程中，很多学者致力于解决一类复杂问题非确定型多项式 ( n o n d e t e r m i n i s t i cp o l y n o m i a l ，n p ) 问题。1 9 7 1 年库克( s c o o k ) 发表了“t h e c o m p l e x i t yo ft h e o r e mp r o v i n gp r o c e d u r e s 1 和1 9 7 2 年卡普( r k a r p ) 发 表的“r e d u c i b i l i t ya m o n gc o m b i n a t o r i a lp r o b l e m s 2 两篇著名的论文奠定 了n p 完备理论的基础。在n p 问题中，最难的问题为n p 完全问题( n pc o m p l e t e ， 简记为n p c ) 。 背包问题( k n a p s a c kp r o b l e m ，k p ) 作为一类组合优化的经典n p 完全问题 2 ，经常出现在工商业、物流业、组合数学、计算复杂性理论、密码学等领域 中。背包问题的研究无论在理论上还是实际生活中都具有重大意义。但随着背包 问题约束数量的增加，问题的愈加复杂化，使得背包问题的求解愈加困难。如何 选取合适的解决办法也成为一个难点问题。 本论文课题来源于9 2 1 计划，主要研究的是一种适用于航天的背包问题，也 即本文题中的“特定对象 。该问题具有强约束的特点，主要包含：几何约束、 第1 章绪论 结构约束、容量约束、动态平衡等相关技术参数约束等。鉴于课题的最终应用， 若对该问题的优化结果有些微改进，都将取得巨大的社会及经济效益。 1 2 2 组合优化算法 1 2 1 1 局域搜索优化算法 常见的贪婪算法、爬山法、神经网络方法等都属于局域搜索优化算法。 贪心算法( 又称贪婪算法) 是指，在对问题求解时，总是做出在当前看来是 最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义 上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当 广泛的、规模相对较小的许多问题还是可能会产生全局最优解或高质量次优解。 爬山法跟贪心算法相近，在对问题求解优化时，总是向着更优的方向前进。 算法复杂度很低，但一般得到的只是局部极值。 神经网络方法也是典型的局部寻优算法，这个特点使得神经网络方法常用于 联想记忆等领域。优化领域，除非有硬件支持，一般较少采用。 1 2 1 2 穷举法与分枝界限法 穷举法即对整个状态空间进行穷举，自然可以获得全局最优解。但对那些计 算复杂度出现组合爆炸类问题，显然无能为力。 分枝定界法是一个用途十分广泛的算法，由查理德卡普( r i c h a r dm k a r p ) 在2 0 世纪6 0 年代发明，是一种全局优化方法。运用这种算法的技巧性很强，不 同类型的问题解法也各不相同。分支定界法的基本思想是对有约束条件的最优化 问题的所有可行解( 数目有限) 空间进行搜索。该算法在具体执行时，把全部可 行解空间不断分割为越来越小的子集( 称为分支) ，并为每个子集内的解的值计 算一个下界或上界( 称为定界) 。在每次分支后，对凡是界限超出已知可行解值 的子集不再做进一步分支。这样，解的许多子集( 即搜索树上的许多结点) 就可 以不予考虑，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可 行解的值不大于任何子集的界限。 分支定界法可应用于大量组合优化问题。其关键技术在于各结点权值如何估 计，可以说分支定界法的求解效率由上下界限决定。若界限估计不好，在极端情 况下将与穷举搜索没多大区别。 1 2 1 3 模拟退火算法 模拟退火算法( s i m u l a t e da n n e a li n g ，s a ) 最早由k i r k p a t r i c k 等应用于组 合优化领域。它是基于m e n t e - c a r l o 迭代求解策略的一种随机寻优算法，其出发 2 第l 章绪论 点是基于金属热处理的退火过程与一般组合优化问题之间的相似性。模拟退火算 法是一种通用的优化算法，理论上具有概率的全局优化性能。目前已在工程中得 到了广泛应用，诸如v l s i 、生产调度、控制工程、机器学习、神经网络、信号 处理等领域。 模拟退火算法优化效果依赖于缓慢降温过程与“分子 的充分运动，优化速 度相对较慢，但优化质量较高。另外，规模敏感性方面性能表现良好。 1 2 1 4 集群智能优化算法 当前流行的集群智能优化方法主要包括蚁群算法、鱼群算法和鸟群算法( 粒 子群算法) 。 1 蚁群算法 蚁群算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) ，又称蚂蚁算法，是一种用来在 图中寻找优化路径的机率型算法。它由m a r c od o r i g o 于1 9 9 2 年提出，其灵感来 源于蚂蚁在寻找食物过程中发现路径的行为。 蚂蚁之所以具有智能行为，完全归功于它的简单行为规则，而这些规则综合 起来具有下面两个方面的特点：多样性与正反馈。 多样性保证了蚂蚁在觅食的时候不置走进死胡同而无限循环，正反馈机制则 保证了相对优良的信息能够被保存下来。我们可以把多样性看成是一种创造能 力，而正反馈是一种学习强化能力。正反馈的力量也可以比喻成权威的意见，而 多样性是打破权威体现的创造性，正是这两点小心翼翼的巧妙结合才使得智能行 为涌现出来。 2 鱼群算法 人工鱼群算法也是一种基于动物行为的群体智能优化算法，与蚁群算法大同 小异。 3 粒子群算法 粒子群优化算法( 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 ) 也是起源于对简单社 会系统的模拟。最初设想是模拟鸟群觅食的过程。所有的鸟都不知道食物在哪里， 但是它们知道当前的位置离食物还有多远。最简单有效的找到食物的最优策略是 就是搜寻目前离食物最近的鸟的周围区域。 p s o 从这种模型中得到启示并用于解决优化问题。p s o 中，每个优化问题的 解对应搜索空间中的一只鸟，我们称之为“粒子 。所有的粒子都有一个由被优 化的函数决定的适应值( f i t n e s sv a l u e ) ，每个粒子还有一个速度决定他们飞翔 的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。 1 2 1 5 基因遗传演化算法 第1 章绪论 这类典型算法包括遗传算法、演化策略等等。遗传算法( g e n e t i ca l g o r i t h m ， g a ) 是模拟生物自然选择原理和基因遗传机理的计算模型，是一种通过模拟自然 进化过程搜索最优解的方法。它最初由美国m i c h i g a n 大学j h o l l a n d 教授首先 提出，并出版了颇有影响的专著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 l s y s t e m s ，g a 这个名称才逐渐为人所知。 基因遗传算法以本质并行性、高鲁棒性与高可移植性著称，在函数优化与搭 积木式的组合优化等领域表现了异常良好的优化性能。不足之处在于系统多样性 难以长期维持。因此，很多改善多样性维持能力的方法不断被提出，其中包括以 下几种：( 1 ) 增大变异概率。此种方法实现简单，计算复杂度低。但缺点在于， 变异概率若取的过大，可能会导致丢失最优解。( 2 ) 引入小生境思想。该方法的 难点主要在于难以实现基因型聚类。( 3 ) 自适应技术。该方法在演化过程中需时 时对种群多样性进行分析，以获取恰当参数值，从而导致增大时空复杂度及软件 开销。因此，在g a 的研究过程中，如何维持种群多样性成为一个难点问题，也 是一个急需解决的问题。 1 2 1 6 量子计算 在经典信息理论中，信息量的基本单位是比特( b i t ) ，一个比特是给出经典 二值系统一个取值的信息量。在量子信息理论中，量子信息的基本单元是量子比 特，通常用q u b i t 表示。 一般的，n 个量子比特的态张起一个2 “维h i l b e r t 空间，存在2 ”个互相正交 的态。正是由于量子态可以处于各基态的叠加态中，因此对于n 个量子比特构成 的态，量子算法可以同时操纵2 “个基态。在经典信息中，对于相同比特长度的 信息来说，虽然也可以构成2 “个状态，但经典算法或者经典信息处理系统只能 处理其中的一个状态。这就是说量子系统具有很高的并行性。 由此还可知，量子系统是一个概率意义下的随机系统。因为它处于基态的叠 加态中，对其进行测量，它就会塌缩到其中的一个基态，每次观测的结果都不一 定相同。这个思想对于增强演化算法的群体多样性有很大的启发。 由于量子计算具有上述优点，因此将量子计算与g a ，p s o 等优化算法相结合， 成为目前的一个主流研究动向。 综上所述，背包问题为本文最终待求解问题。它是一种基因相似型问题，即 每一个背包可对应于染色体上的一位基因。考虑到最终实际应用时编码的便利 性，本文决定采用遗传算法作为本文研究方向。鉴于g a 的多样性维持能力较弱 的问题，本文旨在研究将量子计算的特性引入g a 以期改善种群多样性，从而提 高优化质量。 4 第l 章绪论 1 3 发展历史及研究现状 1 3 1遗传算法 1 3 1 1 发展过程 遗传算法由h o l l a n d 教授于2 0 世纪6 0 年代创立，它模拟了达尔文的“优胜 劣汰”自然选择机理和孟德尔的遗传机理。其主要特点是群体搜索策略和群体中 个体之间的信息交换，搜索不依赖于目标函数的梯度信息，进化过程具有有向随 机性，简单通用、鲁棒。主要的操作算子包括：选择、交叉、变异。其优化过程 可以简单描述为：用一群染色体串编码求解问题的候选解，通过个体配对、交叉、 变异进行基因重组。然后评估新个体的优劣，从父代群体和子代群体中以特定策 略选择出下一代的候选个体。如此循环往复，直到群体收敛为止。其主要发展简 史如下： 2 0 世纪5 0 年代末到6