（控制理论与控制工程专业论文）基于混合量子进化算法的流水车间调度方法研究与应用.pdf

d i s s e r t a t i o ns u b m i t t e dt oz h e j i a n gu n i v e r s i t yo ft e c h n o l o g y f o rt h ed e g r e eo fm a s t e r r e s e a r c ha n d a p p l i c a t i o no f f l o w - - s h o ps c h e d u l i n gm e t h o d sb a s e do n h y b r i dq u a n t u m - i 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 m c a n d i d a t e ：w a n gx i a o q i n a d v i s o r ：w a n gw a n - - l i a n gx u x i n - l i c o l l e g eo fi n f o r m a t i o ne n g i n e e r i n g z h e j i a n gu n i v e r s i t yo ft e c h n o l o g y a p r i l2 0 0 9 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导! j i | j 的指导下，独立进行研 究工作所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包 含其他个人或集体已经发表或撰写过的研究成果，也不含为获得浙江工业大 学或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡献 的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律责任。 作者签名：扎芍日期如7 年，月刀日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权浙江工业大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本 学位论文。 本学位论文属于 1 、保密呀，在 1 年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“”) 作者签名： 互u ，并 j 鲕签名出了厶 日期：五田年r 月夕弓日 日期：声夕年r 月7 弓日 浙江工业大学硕士学位论文 基于混合量子进化算法的流水车间调度 方法研究与应用 摘要 车间调度有着很强的工程应用背景，是整个先进生产制造系统的核心内容和关键技术 之一。有效的调度方法和优化技术，是实现先进制造和提高生产效益的基础和关键。车间 调度问题是非常复杂的组合优化问题，已经被证明是n p 完全问题。对于n p 完全问题， 精确方法还不能有效地求得问题的最优解，通常是应用改进型启发式算法在可接受的时间 范围内求得问题的近优解。近几年新发展起来的量子进化算法，由于其特有的优化性能吸 引了众多研究者对其进行改进和应用研究。在车间调度领域，量子进化算法的应用还处于 起步阶段，还需要进一步拓展和深化。 本文主要研究了混合量子进化算法在流水车间调度问题中的应用，主要研究工作如 下： 1 针对置换流水车间调度问题，提出了一种根据概率幅信息确定工件排列的简单方 法；融合了遗传算法和量子进化算法的优点，提出了混合量子进化算法1 ；融合了差分进 化策略、变邻域搜索和量子进化算法的优点，提出了混合量子进化算法2 。实验结果表明， 混合量子进化算法可以很好地求解该类问题。 2 针对一般流水车间调度问题，提出了一种根据概率幅信息确定基于操作的工件排列 的简单方法。根据一般流水车间调度问题的编解码特点，对求解该问题的混合量子进化算 法的操作进行了改进，填补了量子进化算法在一般流水车间调度问题中的应用空白。实验 结果表明，混合量子进化算法可以较好地求解该类问题。 3 根据流程工业p v c 车间实际生产工艺的特点，建立了实际混合流程车间调度问题 模型，并应用混合量子进化算法l 求解了该问题，讨论了初始生产条件对调度结果的影响。 实验结果表明，混合量子进化算法l 可以较好的求解该类问题。 关键词：流水车间调度，量子进化算法，遗传算法，差分进化，变邻域搜索 浙江工业大学硕士学位论文 r es e a r c ha n da p p l i c a t i o no ff l o l s h o p s c h e d u l i n gm e t h o d sb a s e do nh y b i u d q u a n t u m i n s p i r e d e v o l u t i o n a r ya l g o r i t h m a b s t r a c t s h o ps c h e d u l i n gh a sas t r o n ge n g i n e e f i n gb a c k g r o u n d , a n di t i st h ec o r ec o n t e n to f a d v a n c e dm a n u f a c t u r i n gs y s t e ma n do n eo ft h ek e yt e c h n o l o g i e s e f f e c t i v es c h e d u l i n ga n d o p t i m i z a t i o nt e c h n i q u ei st h eb a s i ca n dk e yo fr e a l i z i n ga d v a n c e dm a n u f a c t u r i n ga n di m p r o v i n g t h e p r o d u c t i o ne f f i c i e n c y s h o ps c h e d u l i n gp r o b l e m i sav e r y c o m p l e x c o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m ，w h i c hh a sb e e np r o v e dt ob en p - c o m p l e t ep r o b l e m f o rn p - c o m p l e t e p r o b l e m , e x a c tm e t h o d sc a l ln o te f f e c t i v e l ya c h i e v et h eo p t i m a ls o l u t i o no ft h ep r o b l e m ，u s u a l l y t h ea p p l i c a t i o no fi m p r o v e dh e u r i s t i ca l g o r i t h ma c h i e v e ss e a l ? o p t i m a ls o l u t i o no ft h ep r o b l e ma t a c c e p t a b l et i m er a n g e i nr e c e n ty e a r s ，t h en e wd e v e l o p e dq u a n t u m - i n s p i r e de v o l u t i o n a r y a l g o r i t h m ( q e a ) h a sa t t r a c t e dm a n ys c h o l a r st os t u d yb e c a u s eo fi t su n i q u eo p t i m i z a t i o n p e r f o r m a n c e b u tt h ea p p l i c a t i o no fq e a i nt h ef i e l do fp r o d u c t i o ns c h e d u l i n gi ss t i l la ta i le a r l y s t a g e ，a n da l s or e q u i r e sb e i n ge x t e n d e da n ds t u d i e di n t e n s i v e l y t h i sp a p e rm a i n l ys t u d i e dt h ea p p l i c a t i o n so fh y b r i dq u a n t u m i n s p i r e de v o l u t i o n a r y a l g o r i t h m ( h q e a ) i nf l o w - s h o ps c h e d u l i n gp r o b l e m ，a n dt h em a i nr e s e a r c hw o r ki sa sf o l l o w s ： 1 f o rt h ep e r m u t a t i o nf l o w - s h o ps c h e d u l i n gp r o b l e m s ，p r o p o s e das i m p l ed e c o d i n gm e t h o d t od e t e r m i n ej o bs e q u e n c eb a s e do nj o b sp r o b a b i l i t ya m p l i t u d ei n f o r m a t i o n ；m e r g e dt h e a d v a n t a g e so fg e n e t i ca l g o r i t h ma n dq e aa n dt h e np r o p o s e dh q e a l ；m e r g e dt h ea d v a n t a g e s o fd i f f e r e n t i a le v o l u t i o ns t r a t e g y ，v a r i a b l en e i g h b o r h o o ds e a r c ha n dq e a ，t h e np r o p o s e d h q e a 2 t h ee x p e r i m e n t a lr e s u l t ss h o wt h a th q e ac a ns o l v es u c hp r o b l e mw e l l 2 f o rt h eg e n e r a lf l o w - s h o ps c h e d u l i n gp r o b l e m ( g f s p ) ，p r o p o s e das i m p l ed e c o d i n g m e t h o dt od e t e r m i n eo p e r a t i o n - b a s e dj o bs e q u e n c eb a s e do nj o b s p r o b a b i l i t ya m p l i t u d e i n f o r m a t i o n a c c o r d i n gt ot h ee n c o d i n ga n dd e c o d i n gc h a r a c t e r i s t i co fg f s p ，i m p r o v e ds o m e o p e r a t i o n so fh q e af o rs o l v i n gt h eg f s p ，f i l l e dt h ea p p l i c a t i o nb l a n ki ng f s p t h e e x p e r i m e n t a lr e s u l t ss h o wt h a th q e a c a ns o l v es u c hp r o b l e mb e t t e r 3 a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fa c t u a lp r o d u c t i o np r o c e s so fp v cs h o pi np r o c e s s i n d u s t r y ，b u i l th y b r i dp r o c e s ss h o ps c h e d u l i n gm o d e l ；a n ds o l v e dp v c - s h o ps c h e d u l i n gp r o b l e m a p p l y i n gw i t hh q e a i n ee x p e r i m e n t a lr e s u l t ss h o wt h a th q e a lc a ns o l v es u c hp r o b l e m b e t t e r i i 浙江工业大学硕士学位论文 k e yw o r d s ：f l o w - s h o ps c h e d u l i n g ，q u a n t u m i 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 m ，g e n e t i c a l g o r i t h m ，d i f f e r e n t i a le v o l u t i o n ，v a r i a b l en e i g h b o r h o o ds e a r c h 浙江工业大学硕士学位论文 目录 摘| 荽。i 第1 章绪论l 1 1 弓i 言1 1 2 流水车间调度问题研究现状。l 1 3 1 4 第2 章 2 1 2 2 2 3 2 4 2 5 第3 章 3 1 3 2 3 3 3 4 3 5 3 6 1 2 1 流水车间调度问题研究方法l 1 2 2 流水车间调度问题的研究发展2 量子进化算法研究综述4 1 3 1 量子计算4 1 3 2 基本量子进化算法6 1 3 3 量子进化算法的改进研究9 1 3 4 量子进化算法的应用研究1 l 1 3 5 量子进化算法研究展望。1 2 本文的主要工作和安排1 3 混合量子进化算法1 4 弓i 言1 z i 解的表达。1 4 混合量子进化算法l ( h q e a l ) 1 6 2 3 1 量子门旋转角策略1 6 2 3 2h q e a i 操作步骤1 8 混合量子进化算法2 ( h q e a 2 ) 21 2 4 1 差分进化策略2 l 2 4 2 变邻域搜索2 3 2 4 3 h q e a 2 操作步骤2 5 本章小结2 6 基于h q e a 的置换流水车间调度问题研究2 7 引言2 7 置换流水车间调度问题描述2 8 编码解码方案2 9 h q e a l 仿真实验与分析3 0 3 4 1q e a 与h q e a i 仿真实验与分析3 0 3 4 2h q e a i 不同终止条件仿真实验与分析。3 3 3 4 3 编码解码方案仿真实验与分析3 6 h q e a 2 仿真实验与分析3 9 3 5 1 实验设置3 9 3 5 2 参数的选择3 9 3 5 3 进化策略优化效果比较与分析4 0 3 5 4 仿真结果与分析4 l 本章小结4 4 浙江工业大学硕士学位论文 第4 章基于h q e a 的一般流水车间调度问题研究。4 5 4 1 弓i 言4 5 4 2 一般流水车间调度问题描述。4 5 4 3 编码解码方案4 6 4 4 h q e a 操作步骤4 9 4 4 1 h q e a i 操作步骤一4 9 4 4 2h q e a 2 操作步骤5 0 4 5 仿真实验与分析5 0 4 5 1 实验设置5 0 4 5 2 仿真结果与分析。5 0 4 6 本章小结5 3 第5 章基于h q e a l 的流程工业调度问题研究与应用5 4 5 1弓l 言5 z i 5 2p v c 车间问题描述及建模5 5 5 2 1 问题描述5 5 5 2 2 建模5 6 5 3 编码解码方案5 8 5 4 仿真实验与分析6 0 5 4 1 实验设置。6 l 5 4 2 仿真结果与分析。6 l 5 5 本章小结6 5 第6 章总结与展望6 6 6 1 总结6 6 6 2 展望6 7 参考文献6 8 致谢7 3 攻读学位期间参加的科研项目和成果7 4 浙江工业大学硕士学位论文 第1 章绪论 1 1引言 流水车间调度问题( f l o ws h o ps c h e d u l i n gp r o b l e m ，f s p ) 根据每台机器上各工件加工 顺序的不同可以分为置换流水车间调度问题( p e r m u t a t i o nf s p , p f s p ) 和一般流水车间调度 问题( g e n e r a lf s p , g f s p ) ，又称为非置换流水车间调度问题( n o np f s p ，n p f s p ) 。如果每 台机器上各工件的加工顺序相同，则称为置换流水车间调度问题。相反，如果每台机器上 各工件的加工顺序不同，则称为一般流水车间调度问题。尽管相对j o b s h o p 调度而言，f s p 的工艺约束比较简单，但它仍旧是一个非常复杂和困难的组合优化问题。g a r e y 等人【l 】已经 证明当求解目标是最小化最大完工时间时，大于2 台机器的问题就是n p 完全问题。对于 n p 完全问题，精确算法还不能有效地求得问题的最优解，通常是应用改进型启发式算法 在可接受的时间范围内求得问题的近优解。近几年，新发展起来的量子进化算法 ( q u a n t u m i 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 m ，q e a ) 由于其特有的量子比特表示方式及其计 算并行性的特点，吸引了众多研究者对其进行理论和应用研究，但是在车间调度领域的应 用研究还处于初期阶段，还需要进行拓展和深入。 1 2 流水车间调度问题研究现状 1 2 1流水车间调度问题研究方法 求解流水车间调度问题的方法一般分为精确方法、构造型启发式算法和改进型启发式 算法等。精确方法一般包括动态规划方法、分支定界方法、整数规划和穷举法等。其中整 数规划和分支定界技术是寻求流水车间调度问题最优解的常用方法，然而，难以在可接受 的时间范围内解决一些大规模甚至中等规模的调度问题，只适用于一些小规模调度问题。 因此，许多研究者提出了构造型启发式算法，如j o h n s o n 启发式算法、p a l m e r 启发式算法、 g u p t a 启发式算法、c d s 启发式算法、r a 启发式算法和n e h 启发式算法等。j o h n s o n 启 发式算法为后来的m 台机器问题的启发式算法提供了基础，几乎所有的启发式算法都用到 该算法1 2 。 改进型启发式算法通常是一些元启发式算法，即一类具有通用启发式策略的算法，如 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 、模拟退火( s i m u l a t e da n n e a l i n g ，s a ) 、禁忌搜索( t a b u 浙江工业大学硕士学位论文 s e a r c h , t s ) 、蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n , a c o ) 、粒子群优化算法( p a r t i c l e s w a r mo p t i m i z a t i o n ，p s o ) 、变邻域搜索算法( v a r i a b l en e i g h b o r h o o ds e a r c h , v n s ) 和迭代 局部搜索算法( r e r a t e dl o c a ls e a r c h , i l s ) 等。这类算法曾被称为现代启发式算法，而现 在广泛地被称为元启发式算法( m e t a - h e u r i s t i c ) 1 3 。元启发式算法还没有一个大家公认的 定义，但是可以简单地描述为1 4 j ：元启发式算法是一类算法概念的集合，它可以用来定义 应用于一个大范围内不同问题的各种启发式方法。换句话说，元启发式算法可以看作是一 种多用途的启发式算法，它用来指导潜在的与问题有关的启发式方法朝着可能有高质量解 的搜索空间进搜索。因此，元启发式算法是一种只需要较少修改就可以应用于不同优化问 题的算法框架。 1 2 2 流水车间调度问题的研究发展 自从j o h n s o n 5 1 9 5 4 年发表第一篇f s p 的文章以来，f s p 引起了许多学者的关注，各 领域的专家及学者对f s p 做了大量的研究。2 0 0 6 年g u p t a 等人f 6 】对过去5 0 年的研究作了 一个总结，并按时间将研究工作分为五个阶段。本节结合g u p t a 等人的划分方法，简要介 绍研究f s p 方法的发展过程，特别是以最小化最大完工时间为目标的f s p 研究方法。 ( 1 ) 第一阶段( 1 9 5 5 1 9 6 4 ) 在j o h n s o n 发表了他在两台机器的f s p 的研究成果后，这时期研究问题的目标是最小 化最大完工时间，研究模型扩展到了优台机器的模型及其它的几个模型上。早期研究的理 论性比较强，不少工作的研究目标是应用精确型方法求出问题的最优解，如数学规划方法 和仿真技术。 ( 2 ) 第二阶段( 1 9 6 5 1 9 7 4 ) 这一时期研究者提出了多种分支定界( b r a n c h & b o u n d ) 算法，目标函数也不仅限于最 小化最大完工时间。然而，除了极少数文献以最小化总流程时间为优化目标和考虑了时间 延迟的多目标优化外，其它仍然是以最小化最大完工时间为优化目标。这一时期，研究者 在用精确算法求解大规模问题的最优解时遇到了很多的困难，从而研究者转向开发和使用 构造型启发式算法来求解较大规模或者大规模f s p 的好解或近优解。这一时期提出的启发 式算法有p a l m e r 启发式算法( 1 9 6 5 ) 、g u p t a 启发式算法( 1 9 7 1 ) 和c d s 启发式算法( 1 9 7 0 ) 。 f r a m i n a n 等人 7 1 对这些启发式算法及其之后的启发式算法求解以最小化最大完工时间为目 标的置换流水车间调度问题进行了综述。k r o n e 等人【8 】对一般流水车间调度问题进行了研 究。 ( 3 ) 第三阶段( 1 9 7 5 - 1 9 8 4 ) 2 浙江工业大学硕士学位论文 n p 完全理论的出现对流水车间问题的研究方向产生了深刻的影响。期间，越来越多 的问题被证明是n p 完全问题；研究者提出了更多的构造型启发式算法，如r a 启发式算 法( 1 9 7 7 ) 和著名的n e h 启发式算法( 1 9 8 3 ) 等。问题模型更加多样化，如带准备时间 的流水车间问题、与交货期相关的目标函数和随机加工时间流水车间调度问题。r o c k 等人 【l o 】对一般流水车间调度问题进行了研究。 ( 4 ) 第四阶段( 1 9 8 5 1 9 9 4 ) 研究者开始研究柔性流水车间问题、多目标调度问题等，并且提出了多种元启发式算 法，如g a 、s a 和t s 等。期间，决策支持系统和专家系统等方法也开始应用到该领域。 h e j a z i 等人对以最小化最大完工时间为目标的f s p 进行了综述。r u i z 等人【1 2 1 对置换流水 车间调度问题的解决方法进行了综述和评价，特别是对优化效果较好的g a 、s a 、t s 和相 应的关键操作进行了陈述。 ( 5 ) 第五阶段( 1 9 9 5 2 0 0 4 ) 研究的问题更加广泛，对已有问题的研究也取得了很大的进展，很难找到一个有代表 性的、过去没有研究过的模型。然而，对多目标优化的讨论在这一时期显得很流行。同时， 新的元启发式算法也应用于流水车间调度问题中，如a c o 、免疫算法( i m m u n ea l g o r i t h m ， i a ) 等。p o r t s 等人1 1 3 】对置换流水车间调度问题和一般流水车间调度问题进行了比较分析。 j a i n 等人【1 4 1 提出了一种求解一般流水车间调度问题的算法框架。 ( 6 ) 近几年的发展( 2 0 0 5 一) 在构造型算法方面，k a l c z y n s k i 等人【1 5 1 改进了著名的n e h 算法，提出了算法n e h k k ； r a d 等人【1 6 j 提出了5 种新的构造型启发式算法。 研究者改进了多个元启发式算法的求解性能【1 7 。1 9 】求解流水车间调度问题；提出了一个 新的求解置换流水车间调度问题的优秀算法i g l 2 0 1 ( i t e r a t e dg r e e d y ) ；提出了一种求解以最 小化最大完工时间为目标的置换流水车间调度l a - j 题的量子遗传算法【2 1 1 ( 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 ，q g a ) ；提出了一种求解以最小化最大完工时间为目标的置换流水车间 调度问题的的差分进化算法【捌( d i f f e r e n t i a le v o l u t i o n , d e ) ：a g a t r w a l 等人团1 提出了自适应 学习算法求解流水车间调度问题。 研究者提出了多种混合算法【2 4 乏7 1 求解流水车间调度问题。l i a o 等【2 8 】对置换调度和非置 换调度进行了性能评价。l i n 等【2 9 1 提出了一种混合模拟退火和t a b u 搜索的方法求解般流 水车间调度问题。l i n 等【3 0 】提出了一种混合了s a 、g a 和t s 三种算法的混合元启发式算 法，求解带依赖于加工顺序的准备时间的一般流水车间调度问题。y i n g 等【3 l 】应用s a 对一 般流水车间调度问题和置换流水车间调度问题进行了仿真研究，对置换调度和一般调度给 3 浙江工业大学硕士学位论文 出了系统的优化性能评价。 综上所述，量子进化算法在车间调度领域中的应用还处于初始阶段，特别是在一般流 水车间调度问题中的应用，还属空白。在这方面的应用研究急需填补、扩展和深入。 1 3 量子进化算法研究综述 量子计算和量子信息的研究可以追溯到几十年前，然而直到2 0 世纪9 0 年代中期才真 正引起研究者的广泛关注。这期间发现了s h o r t 3 2 1 量子因子分解算法和g r o v e r p 3 1 量子搜索算 法，这两类算法展示了量子计算从根本上超越经典计算机计算能力的潜力及其在信息处理 方面的巨大优势p 引。量子计算相比于经典计算，最大的特点是计算的并行性。因此，量 子计算吸引了很多研究者的关注，并把量子计算中单位信息的特殊表达方式( 量子比特) 应用到经典计算机中，以期解决经典计算所不能解决的问题。 1 3 1 量子计算 利用微观粒子的状态表示的信息称为量子信息。信息一旦量子化，描述“原子水平上 的物质结构及其属性 的量子力学特性便成为描述信息行为的物理基础，在此基础上研究 信息的存储、传输和处理的一般规律的学科称为“量子信息学 。量子信息学是量子力学 与经典信息学结合的新兴学科，微观系统的量子特性为信息学带来许多令人耳目一新的现 象，在信息的表示、加工、处理和传输上生长出一些新的概念、原理和方法，量子信息与 量子通信将在未来的信息与通信的研究领域具有独特的不可替代功能，将发挥重要的作 用。 量子最早出现在光量子理论中，是微观系统中能量的一个力学单位。现代物理将微观 世晃中所有的微观粒子( 如光子、电子、原子等) 统称为量子。微观世界中量子具有宏观 世界无法解释的微观客体的许多特性，这些特性集中表现在量子的状态属性上。如量子态 的叠加性、量子态的纠缠、量子状态的不可克隆、量子的“波粒二象性以及量子客体的 测量将导致量子状态“波包塌缩 等现象。这些奇异的现象来自于微观世界中微观客体间 存在的相互干涉，即所谓的量子相干特性。利用微观粒子的量子态叠加及相干特性能够实 现未来计算机超高速并行计算；利用微观粒子的量子态纠缠、量子态不可克隆的力学特性 能够实现超高速的信息传送、实现不可破译不可窃听的保密通信。 在经典信息处理过程中，记述经典信息的二进制存储单元比特( b i t ) 由经典状态( 如 电压的高低) 1 和0 表示。相对于经典信息的基本存储单元比特，量子信息的基本存储单 元称为量子比特( q u b i t ) 。一个量子比特的状态是一个二维复数空间的向量，它的两个极 4 浙江工业大学硕士学位论文 化状态( 也称为基态) 为i o ) 和1 1 ) ，对应于经典状态的“0 ”和“1 。在量子力学中使用 迪拉克标记“( 1 “和“j ) ”表示量子态。英文中括号叫b r a c k e t ，迪拉克把符号“( l ) 拆成两半：b r a 和k e t ，分别用来称呼括号的左半“仁i 和右半“l y ) ，b r a 和k e t 在中文 中分别译作左矢( 左向量) 和右矢( 右向量) 。“( i 和“1 ) 是量子力学中表示量子 状态的标准标记。 i i ) 图i - i 布洛赫球 量子比特的重要特性在于一个量子比特可以连续地随机地存在于状态i o ) 和1 1 ) 的任意 叠加状态上。因此量子比特与经典比特的不同在于：一个量子比特能够处在既不是1 0 ) 也不 是1 1 ) 的状态上，而是处于状态i o ) 和1 1 ) 的一个线性组合的所谓中间状态之上，即处于状态 1 0 ) 和1 1 ) 的叠加态上，如式( 1 1 ) 所示。 i y ) = 历f o ) + 1 1 ) ( 1 - 1 ) 式l 一1 中口、为复数，称为概率幅，且必须满足归一化要求p 1 2 + pj 2 = 1 。h 2 表 示量子比特处于i o ) 态的概率，例2 表示量子比特处于i l 态的概率。处于两种状态1 0 ) 和1 1 ) 叠加态的粒子系统iy 就是量子信息的基本存储单元一量子比特。图1 1 所示的几何图形 为量子比特的可视化几何表示。因为p 1 2 + l p l 2 = l ，可以将等式1 1 改写成式1 _ 2 。 i 缈) s 扣扣 ( 1 2 ) 这里一j 秒石，一7 缈万，x = s i n s xc o s 缈，y = s i n 9 s i n 9 , ，z ：c o s 8 。显然秒 浙江工业大学硕士学位论文 由式1 - 1 可知，一个量子比特可以连续地、随机地存在于状态i o ) 和1 1 ) 的任意叠加态 上，直到它被某次测量退化为止( 量子物理指出测量粒子运动会导致“波包塌缩 ，使被 测量的量子比特状态以某一概率区间值退化到状态i o ) 或1 1 ) 上) 。例如一个量子比特能够 处在以下状态： 孚l o ) + 扣 3 ， 当测量这个量子比特时，测量的瞬间以o 7 5 c 陶2 ，的概率退化为l o ) ，或者- 以o 2 5 ( h 2 ) 的概率退化到1 1 ) 。 量子计算的一个主要原理就是使构成叠加态的各个基态通过量子门的作用发生干涉， 从而改变它们之间的相对相位。如一个叠加态量子比特l 如式1 3 所示，量子非门u 如 式1 4 所示。 u = 嘲 c - 4 ， 量子门u 作用在i 沙 上，那么结果为iy - i 11 1 ) + 孚i 。) ，可以看到量子比特的两个状 态的概率幅互相交换了。若量子系统ij f ， 处于基态的线性叠加的状态，我们称系统为相干 1 3 2 基本量子进化算法 量子进化算法( q e a ) 是一种进化算法，它是以一定数量的个体( 染色体) 组成的初 始种群为初始解，通过进化操作不断演化，知道最后收敛。和其它进化算法不同的是量子 进化算法独特的个体表示方式( 用量子比特表示个体) 和独特的进化操作。一个量子个体 由一串量子比特组成，然后利用量子比特的纠缠特性和相干特性对量子比特个体进行更新 演化。用量子比特表示个体的方法具有种群多样性好的特点，同时q e a 可以平衡粗搜索 ( e x p l o r a t i o n ) 和细搜索( e x p l o i t a t i o n ) 3 6 1 。尽管q e a 是基于量子计算的概念，但是它不 是量子算法，只是一种在经典计算机上运行的新的进化算法。 在量子进化算法中，染色体是由串量子比特表示的。一个长度为肌的量子染色体g 由脚个量子比特组成，表示成矩阵形式为： 6 浙江工业大学硕士学位论文 厂口l g - 瞄 其中| 口，1 2 + l p f = 1 ，i = l ，2 ，m 。 例如，一条长度为3 的量子染色体可以表示为 1 托 1 正 ( 1 - 5 ) 司以表不为： 一1 斗1 0 0 0 ) 一笪41 0 0 1 ) + 寺1 0 1 1 。) + 孚1 0 1 1 ) 一1 1 0 0 ) 一- - 4 - - - 订1 埘) + 石11 1 1 0 ) + 孚1 1 1 1 ) ( 1 - 6 ) 上述结果的意思是量子染色体处于状态i o o o ) 、1 0 0 1 ) 、l o l o ) 、1 0 11 ) 、1 1 0 0 ) 、i 1 0 1 ) 、 1 11 0 ) 和1 111 ) 的概率分别为而1 ，素，去，访3 ，话1 ，而3 ，话1 和话3 。在对这个长度为3 的 量子染色体进行测量的瞬间，其以相应概率退化为i o o o ) 、1 0 0 1 ) 、1 0 1 0 ) 、1 0 11 ) 、j 1 0 0 ) 、1 1 0 1 ) 、 1 1 1 0 ) 和1 1 1 1 ) 中的一种状态，例如以概率素退化为状态i l l l ) 。如上所述，长度为3 的量子 染色体可以包含8 个状态的信息。那z , ，长度为m 的量子染色体可以包含2 m 个状态的信 息。可见，用量子比特表示量子染色体的显著特点是种群的多样性，因为它可以概率地表 示线性叠加态。 由1 3 1 节可知，可以通过测量( 观察) 来得到量子比特的状态。每次测量量子比特， 量子比特就会以某一概率退化到状态l o ) 或1 1 ) 。那么，一个长度为m 的量子染色体通过某 种测量方法就可以得多j _ m - 进制表示的染色体，然后再转化为所求问题的解。 下面给出用于求解背包问题的基本量子进化算法的操作步骤。 步骤1 ：初始化阶段。设定运行代数r 卜0 。随机初始化量子种群q o = q o ，g o ，q o ( 甩 为种群规模) ，个体g ：l = g ? 。，g ：，q o ( m 为优化问题的维数) 为用两状态量子比特表 示的量子染色体。其中9 0 = k 0 ，耽r ，且k 1 2 + l 屈1 2 = l ，i = 1 ，2 ，m 。用式1 7 所示方 法观察q o 的状态生成二进制表示的种群p o = p o ，p o ，p o ，二进制个体 p ? = 【x ：l ，x 0 ，一，x ：肼】为所表征问题的解。评价p o ，并保存种群中每个个体和其当前解到 7 浙江工业大学硕士学位论文 b o = 【卵，b o ，醪】。其中矽= 【j ：。，屹，h b o 州】，8 艰0 表示相应个体的目标函数值。保存当 前种群中的最优个体及其目标函数值到b b e s t 。 也= 乜二缴一u ) | m 7 ， r or a n d ( j )【o ，l 】之间均匀分布的随机数。 步骤2 ：更新阶段。r 卜h 1 。由o 卜1 生成尸，。用上述方法观察q 卜1 并生成尸。评价 并保存较优解。式1 - 8 所示为量子更新门( 详见第二章) ，利用式1 - 9 对q 卜1 中每一个个体 g 一实施量子更新操作，即更新q 卜1 为q 。对尸。和b 卜1 中每个个体的目标函数执行一对一 的比较，并把较优个体及其目标函数值保存到b 。更新b b e s t ，即b ，中的最优个体及其目 标函数值保存到b b e s t 。 嘲，= 器蔷 m 8 ) u ( 磋，) 2 ls i l l 夏i | ；c o s ( ：研；。i q 。8 ) 吒训蚴嘲 m ” 步骤3 ：移民操作阶段。如果满足移民操作条件，那么按式l 一1 0 和1 1 1 执行局部移民 ( l m ，l o c a lm i g r a t i o n ) 和全局移民( g m ，g l o b a lm i g r a t i o n ) 操作。如果目标函数是求极小 值，那么局部移民采用式1 1 0 所示方法。如果满足全局移民的条件，那么用全局最优解替 代b r 中所有个体及其目标函数值。 6 f = m i n ( b ：_ 。，w ) ( 1 - 1 0 ) b = 吲，畦，k 】= b b e s t ，b b e s t ，b b e