（电路与系统专业论文）量子进化算法中信息共享机制研究.pdf

摘要 摘要 量子进化算法是一类新颖的分布估计算法，通过多个量子概率模型协同进化 来引导算法实施搜索。目前的分布估计算法具有好的收敛速度，但是在求解复杂 优化问题时，算法的持续探索能力欠佳。本文基于量子进化算法的多概率模型结 构，研究其中的信息共享机制，以及算法收敛能力和探索能力的平衡等问题，进 而研究新的、更为高效的量子进化算法。这些问题是当前进化计算领域的热点问 题，对它们的研究具有重要的学术价值和应用前景。 论文的主要工作和创新之处如下： 1 ) 基于大规模o 1 背包问题和n kf i t n e s sl a n d s c a p em o d e l ，对量子进化算法几 种主要的信息共享机制进行了实验分析，结果表明，信息共享机制对量子进 化算法性能有着重要的影响；有信息共享机制的算法相比没有信息共享机制 的算法，在寻找最优解能力方面具有明显优势；随机全面的信息共享机制比 固定邻域结构的信息共享机制更有利于算法处理复杂的大规模优化问题。 2 ) 提出了一种基于全面学习的量子进化算法( c l q e a ) 。该算法基于全面学习 的思想，实现了以量子比特为单位的、更为充分的信息交换。实验结果表明， 该算法能够在保持较好探索能力的同时，有效提高针对大规模复杂问题的优 化性能。 3 ) 提出了一种基于生态地理学模型的量子进化算法( q b o ) 。该算法通过模拟 多个“生态岛屿 之间物种的迁徙行为，以一种更为自然的方式实现量子个 体问全面充分的信息交换。实验结果表明，该算法能够以一种更高效的方式 快速共享有意义的信息：因此，在处理大规模、复杂优化问题时，在具有更 快收敛速度的同时，能够获得更高质量的解。 本文的工作有利于人们更深入地认识量子进化算法的优化机理，进而帮助人 们设计出更为有效的量子进化算法。此外，本文所提出的量子进化算法可用于求 解多种实际工程和科学应用中的大规模、复杂优化问题。 关键词：量子进化算法信息共享机制 全面学习生态地理学模型n k 模型 0 1 背包问题 a b s t r a c t a b s t r a c t 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 i e a ) i san e wt y p eo fe s t i m a t i o n o fd i s t r i b u t i o na l g o r i t h m s ( e d a s ) ，w h i c hu t i l i z e sm u l t i p l ec o - e v o l v e dq u a n t u m p r o b a b i l i t ym o d e l st og u i d et h es e a r c ho ft h ea l g o r i t h m m o s to fp r e v i o u se d a sh a v e s h o w np r e t t yg o o dc o n v e r g e n c es p e e d ，b u tt h ee x p l o r a t i o na b i l i t yo ft h e mi sn o t s a t i s f y i n gw h e na p p l i e do nc o m p l e xm u l t i m o d a lo p t i m i z a t i o np r o b l e m s b a s eo nt h e m u l t i m o d e ls t r u c t u r eo fq i e a ，t h i sd i s s e r t a t i o ns t u d i e st h ei n f o r m a t i o ns h a r i n g m e c h a n i s mi nq i e a ，t h ei s s u eo f b a l a n c i n gt h ec o n v e r g e n c ea n de x p l o r a t i o na b i l i t yo f q i e a ，a n dt h e ns t u d i e sn e w a n dm o r ee f f i c i e n tq i e a s t h et o p i c so ft h i sd i s s e r t a t i o n a r ei n t e n s i v e l yc o n c e r n e di nt h ef i e l do fe v o l u t i o n a r yc o m p u t a t i o n ，t h e r e f o r eh a v e i m p o r t a n tr e s e a r c hv a l u ea n dp r o m i s i n ga p p l i c a t i o np e r s p e c t i v e t h em a j o rw o r k sa n dc o n t r i b u t i o n so f t h i sd i s s e r t a t i o ni n c l u d e ： 1 ) s e v e r a li n f o r m a t i o ns h a r i n gm e c h a n i s m so fq i e a sa r ee x p e r i m e n t a l l ya n a l y z e d b a s e do nl a r g es c a l eo 一1k n a p s a c kp r o b l e m sa n dn kf i t n e s sl a n d s c a p em o d e l t h e r e s u l t ss h o wt h a tt h ei n f o r m a t i o n s h a r i n g h a si m p o r t a n ti n f l u e n c eo nt h e p e r f o r m a n c eo fq i e a s t h ea b i l i t yo ff i n d i n go p t i m a ls o l u t i o n so fq i e a sw i m i n f o r m a t i o ns h a r i n gi so b v i o u s l yb e t t e rt h a nt h a tw i t h o u ti n f o r m a t i o ns h a r i n g s t o c h a s t i ca n d c o m p r e h e n s i v ei n f o r m a t i o ns h a r i n gi sb e a e rf o rq i e a t od e a lw i t h c o m p l e xl a r g es c a l eo p t i m i z a t i o np r o b l e m st h a ni n f o r m a t i o ns h a r i n gb a s e do nt h e f i x e dn e i g h b o r h o o ds t r u c t u r e 2 ) a n e w q i e a ( c l q e a ) b a s e do nc o m p r e h e n s i v el e a r n i n gi sp r o p o s e d ，i nw h i c ha c o m p r e h e n s i v e ，b i t - b i ti n f o r m a t i o ns h a r i n gm e c h a n i s mi si m p l e m e n t e db a s e do n t h ei d e ao fc o m p r e h e n s i v el e a r n i n g e x p e r i m e n t a lr e s u l t ss h o wt h a tc l q e ah a s b e t t e rp e r f o r m a n c eo nl a r g es c a l ec o m p l i c a t e do p t i m i z a t i o np r o b l e m s ，w h i l ea l s o h a sg o o de x p l o r a t i o na b i l i t y 3 ) a n e wq i e a ( q b o ) b a s e do nt h eb i o g e o g r a p h ym o d e li s p r o p o s e d ，i nw h i c h c o m p r e h e n s i v ei n f o r m a t i o ns h a r i n gm e c h a n i s ma m o n gq u a n t u mi n d i v i d u a l si s i m p l e m e n t e di nam o r en a t u r a lw a yv i as i m u l a t i n gt h em i g r a t i o nb e h a v i o ra m o n g m u l t i p l eh a b i t a t s e x p e r i m e n t a lr e s u l t ss h o wt h a tq b oc a ns h a r eg o o dk n o w l e d g e a m o n gm o d e l si na m o r ee f f i c i e n tw a y , w h i c hh e l p sq b ot of i n db e a e rs o l u t i o n s w i t hr e l a t i v e l yl o w e rc o m p u t a t i o n a lc o s t t h ew o r ko ft h i sd i s s e r t a t i o nw i l lb eh e l p f u lt or e v e a lt h ep r i n c i p l eo fq i e a si n m o r ed e p t h ，a n dt h e r e f o r eb eh e l p f u lt od e s i g nm o r ee f f e c t i v eq i e a s b e s i d e s ，t h e i l a b s t r a c t n e wq i e a sp r o p o s e da r ea p p l i c a b l et om a n yc o m p l e xa n dl a r g es c a l eo p t i m i z a t i o n p r o b l e m si nr e a le n g i n e e r i n ga n ds c i e n t i f i ca p p l i c a t i o n s k e yw o r d s ：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 ；i n f o r m a t i o ns h a r i n g m e c h a n i s m ；c o m p r e h e n s i v el e a r n i n g ；b i o g e o g r a p h ym o d e l ；n kf i t n e s s l a n d s c a p em o d e l ；0 - 1k n a p s a c kp r o b l e m i i l 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：签字日期： 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入中国学 位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 一公开口保密( 年) 作者签名： 签字日期： 导师签名： 签字日期： 第l 章绪论 1 1 选题背景与意义 第1 章绪论 进化算法是一类受自然界生物进化和行为规律启发而发展出来的启发式搜 索算法，擅长于求解各类复杂的优化问题。近年来，在各种应用需求的驱动下， 关于进化算法的研究在许多方面都取得了重要的进展，其中，以下几方面的进展 尤其引人关注。 1 ) 一些新的算法模型相继提出，如遗传规划( g e n e t i cp r o g r a m m i n g ) ( k o z a , 1 9 9 2 ) ，粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t i o n ) ( k e n n e d y , 1 9 9 5 ) ， 差分进化( d i f f e r e n t i a le v o l u t i o n ) ( s t o r e ，1 9 9 5 ) ，蚁群算法( a n tc o l o n y o p t i m i z a t i o n ) ( d o n g o ，19 9 9 ) ，人工免疫系统( a r t i f i c i a li m m u n es y s t e m s ) ( d a s g u p t a ，2 0 0 2 ) ，文化算法( c u l t u r ea l g o r i t h m ) ( r e y n o l d s ，1 9 9 4 ) ，量子进化 算法( q 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 m s ) ( h a r t ，2 0 0 2 ) ，分布估计算法 ( 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 s ) ( m n h l e n b e i n ，19 9 8 ) ，等等。关于这些新 算法模型的研究，极大地丰富了进化计算的内容，同时也扩展了人们对于进化计 算的理解和认识。 2 ) 涌现出一批针对复杂优化问题的新技术，使得进化算法的问题求解能力 得到进一步提高。例如，( a ) 在多目标优化领域，涌现出诸如p a r e t o 排序( d e b ， 2 0 0 0 ) 、a c h i e v e ( k n o w l e s ，19 9 9 ) 、h y p e r - v o l u m e ( e m m e r i c h ，2 0 0 5 ) 、以及各类 多样性保持技术( k n o w l e s ，1 9 9 9 ) ( f o n s e e a ，1 9 9 3 ) 等新技术；( b ) 在大规模优 化领域，提出了合作协同进化( c o o p e r a t i v ec o e v o l u f i o n ) ( m i t c h e l l ，2 0 0 0 ) 的思 想，并且发展出了多个实现技术( j a n s e n ，2 0 0 3 ) ( b e r g h ，2 0 0 4 ) ( y a n g ，2 0 0 8 ) ； 提出了基于多智能体的优化技术；出现了多策略集成的设计思想，也发展出了多 个实现技术( d u ，2 0 0 8 ) ( w a n g ，2 0 1 0 ) ( v r u g t ，2 0 0 9 ) ；( c ) 在动态优化领域，出 现了m u l t i s w a r r n ( b l a c k w e l l ，2 0 0 6 ) 、m e m o r y ( b r a n k e ，1 9 9 9 ) 等多种技术( j i n ， 2 0 0 5 ) ；( d ) 在约束优化领域，出现了s 约束法( t a k a h a m a ，2 0 0 5 ) 等新技术。 3 ) 应用领域进一步扩展。近年来进化算法在生物信息处理领域( f o g e l ， 2 0 0 3 ) 、数据挖掘领域( f r e i t a s ，2 0 0 2 ) 、机器学习领域( f o g e l ，2 0 0 6 ) 、工业设计 领域( o d u g u w a ，2 0 0 5 ) 、路径规划领域等都有不俗的表现。 4 ) 关于进化算法的分析方法的研究也取得了一些重要进展。一些新的分析 方法的出现使得人们有可能对进化算法的内在行为和优化能力进行更为有效和 深入的考察。例如，通过漂移分析( d r i f ta n a l y s i s ) 方法( h e ，2 0 0 4 ) ，我们可以 第l 章绪论 分析进化算法在处理各类优化问题时的收敛性质；通过f i t n e s sl a n d s c a p e a n a l y s i s 技术( m e r z ，2 0 0 4 ) ，我们可以直观地通过实验观察到不同策略对不同性 质问题的性能表现；通过实验分析技术( e x p e r i m e n t a la n a l y s i s ) ( c z a r n ，2 0 0 4 ) ， 我们可以对算法的性能进行更为客观、全面的评估，等等。 在上述研究进展中，分布估计算法( e d a ) 的出现和快速发展对进化计算的 发展起到了重要的影响作用。分布估计算法是近1 0 年发展起来的一类新的进化 算法，最初是为了解决在遗传算法中存在的优良模式保护问题，即如何保护在搜 索过程中获得的优良模式不受遗传算子( 如交叉和变异算子) 的破坏，同时对它 们进行有效地利用，而提出的一种策略。分布估计算法核心思想是( p e l i k a n ， 1 9 9 9 ) ：利用概率模型对解空间中有希望出现最优解的区域进行建模和估计，再 利用该模型引导算法对解空间展开搜索，使其快速向最优解收敛。 在分布估计算法的研究中，概率模型的选择与学习是最受学者们关注的核心 问题之一，因为它直接决定了分布估计算法的计算效率和优化性能。目前采用的 概率模型主要有三种类型( p e l i k a n ，1 9 9 9 ) ：单变量模型，双变量模型和多变量模 型。单变量模型( 如c g a 、p b i l 等采用概率矢量模型( h a r i k ，1 9 9 9 ) ( b a l u j a , 1 9 9 4 ) ) 结构简单，各变量统计独立，模型的学习也比较简单，因而基于它的分布估计算 法的整体复杂度较低。但是，由于单变量模型无法描述变量之间的相关性，即联 结( l i n k a g e ) 关系，使得算法对复杂优化问题的优化能力有限。多变量模型( 如 b o a 等采用的b a y e s 网络( p e l i k a n ，1 9 9 9 ) ( e t x e b e r r i a ，1 9 9 9 ) ) 可以很好地描述 变量间的联结关系，但是，学习多变量模型的计算代价高昂，需要维持的群体规 模庞大，当所求解问题的规模增大时，算法的计算复杂性会显著增加，目前一般 都是采用贪心算法来实现模型的学习。双变量模型( 如m i m i c 等( b o n e r , 1 9 9 7 ) ( b a l u j a ，1 9 9 7 ) ( p e l i k a n ，1 9 9 9 ) ) 的表达能力和复杂性介于上述两种模型之间。 此前的分布估计算法基本上都采用与模型相匹配的统计学习方法来学习概 率模型，这使得分布估计算法的收敛性一般都比较很好。但是，当被用于处理复 杂的优化问题时，如多模态优化问题、多目标优化问题、动态优化问题，分布估 计算法对解空间的持续探索能力往往不能令人满意了。 量子进化算法( 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 s ) ( h a n ，2 0 0 2 ) ( b i n ， 2 0 0 2 ) 是一类特殊的分布估计算法，其特殊性主要体现在以下几个方面： 1 ) 引入了量子物理中的一些概念和模型，如量子态的叠加、量子旋转门、 量子概率模型等，这使得量子进化算法具有了与经典进化算法不同的特色。 2 ) 采用量子概率模型对解空间中可能的优良解区域进行建模和估计，通过 量子概率模型学习和记忆搜索过程中得到的优良解信息，引导算法对解空间进行 有效的搜索。 2 第1 章绪论 3 ) 采用多个量子概率模型的算法结构，多个模型之间通过交换或共享信息 来实现协同进化。这一特点又使得量子进化算法有别于大多数的分布估计算法。 经过十年左右的发展，量子进化算法取得一些重要的进展，尤其是k h h a n 等人的工作( b i n ，2 0 0 3 ) ( b i n ，2 0 0 3 ) ( f a n ，2 0 0 8 a ) 让人们看到了量子进化算法 的特殊魅力和应用潜力。但是，关于量子进化算法的细致的分析工作还比较少， 尤其是对不同信息共享策略下量子进化算法的行为研究还非常缺乏，这使得目前 量子进化算法的研究进入到一个相对停滞的瓶颈期。 此前研究表明，分布估计算法具有很好的收敛性，但是缺乏灵活、有效的机 制来保持算法的持续探索能力，这使得分布估计算法在处理复杂的多模态数值优 化和组合优化问题时容易陷入局部最优。量子进化算法采用多个量子概率模型并 行搜索的框架结构，通过多个概率模型之间的信息共享和协同进化，实现对复杂 优化问题的求解。这启发我们基于量子进化算法的多概率模型结构，研究多概率 模型间有效的信息共享与协同进化机制，进而研究有效提高分布估计算法持续探 索能力的新方法。 1 2 分布估计算法 量子进化算法是一类特殊的分布估计算法。因此，在介绍量子进化算法的研 究现状之前，我们有必要先介绍一下分布估计算法的基本原理及其研究现状。 1 2 1 分布估计算法的产生背景 遗传算法是受达尔文进化论和孟德尔基因学说启发而产生的一种模拟生物 界自然进化过程的启发式搜索算法，通过对每一代种群中的优良个体进行选择和 重组来构造和发现更好的解。大量研究与应用成果表明，对于许多复杂问题，遗 传算法是一种高效、稳健的优化搜索算法( 陈国良，1 9 9 6 ) 。但是，随着研究的深 入，遗传算法的局限与不足也逐渐显露出来：1 ) 群体规模难以确定。遗传算法 是一种基于群体的搜索算法，群体规模的大小很难确定。群体规模小( 1 0 0 左右) 将限制算法对长阶模式( s c h e m a ) 的考察，进而影响算法的全局搜索能力( w h i t l e y , 2 0 0 1 ) ；而群体规模大则又会导致算法的计算复杂度升高。2 ) 固定的、与问题无 关的交叉算子常常会频繁破坏已获得的优良模式( 又称“积木块b u i l d i n g b l o c k ”) ，或者无法将它们有效重组。遗传算法对那些积木块在编码个体中排列 紧密的问题工作很好，而对于那些积木块在整个解空间中分散分布的问题，则效 果不佳( p e l i k a n ，1 9 9 ) 。 因此，研究如何保护在搜索过程中获得的优良模式( 积木块) 不受遗传算子 第1 章绪论 的破坏，同时对它们进行有效重组，就成为近二十年来遗传算法研究领域关注的 一个重要课题。这导致出现了一类新的优化搜索算法一一分布估计算法 ( e s t i m a t i o no f d i s t r i b u t i o n a l g o r i t h m s - - e d a ) ( m i l h l e n b e i n ，1 9 9 8 ) 。该类算法核 心思想是：利用概率分布模型对解空间中有希望出现最优解的区域进行建模和估 计，再利用该模型引导算法快速向全局最优解收敛。分布估计算法有效地避免了 遗传算法存在的群体规模难设定、以及交叉、变异对优良模式的破坏作用等问题。 已有的研究成果表明，对许多问题，分布估计算法具有与标准遗传算法相近的效 果，但是，其计算复杂度比传统遗传算法有较大幅度的降低。 现实世界中的许多优化问题都存在一个内在的、复杂的结构，在数学上可以 描述为多个决策变量之间的依赖关系( d e p e n d e n c e ) 。如果优化算法能够对这一 内在结构进行有效地学习和利用，将有助于优化问题的快速求解。传统进化算法， 包括遗传算法，对这种存在内在依赖关系的优化问题的求解能力非常有限。其根 本原因就在于传统进化算法一般都假设问题的变量是相互独立的，绝大多数进化 算子都是基于单个变量的操作，缺乏有效的方法对变量之间的依赖关系进行学习 和利用。分布估计算法的出现为学习和利用优化问题的内在结构关系提供了一种 新的研究思路。由于此前在统计学习领域已经有了许多关于多变量统计模型方面 的研究成果，随着这些成果逐渐被引入分布估计算法，分布估计算法有可能对存 在内在依赖关系的优化问题实施有效的求解。 1 2 2 分布估计算法的基本原理 分布估计算法的基本思想是：利用概率模型来估计和描述解空间中各个可行 解为最优解的概率分布，再利用该概率模型引导启发式搜索。利用统计学习的方 法对概率模型进行更新进化，使得高概率区间逐渐收缩到真实最优解附近，进而 引导算法搜索到真实最优解。 在分布估计算法中，优化问题的每个决策变量x ，被定义为一个随机变量，全 部随机变量的排列构成了一个随机向量x = ( 而，x ：，x 一，x ，) 。问题的解是该随 机向量的一个取值，而一个群体就对应于该随机向量取值分布的一个近似。因此， 随机向量的取值分布是群体的一种紧凑而完整的表示。根据学习得到的概率分布 对解空间实施采样，有可能获得更高质量的群体和个体。分布估计算法正是利用 每一代个体所提供的、不尽完整的、关于解空间中好解与坏解的分布信息，学习 随机向量的取值分布，然后再利用学习得到的关于优良解的分布信息指导算法对 解空间的采样。分布估计算法的基本流程如下： 1 ) 按照某一种概率分布初始化产生由心个个体组成的第一代种群，评估每 一个个体的适应度值； 4 第1 章绪论 2 ) 按照适应度，采用某种选择策略，从当前群体中选择k 船个较优个体； 3 ) 根据所选择的比脚个个体，估计并更新概率模型： 4 ) 按照更新后的概率模型再对解空间实施采样，得到新一代种群，评估每 一个体的适应度值； 5 ) 如果满足终止条件，算法停止；否则，返回步骤2 。 1 2 3 分布估计算法的研究现状 分布估计算法( 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 ) 这一称法最早是由 m i 缸 d e n b e i n 和p a a b 提出( m i i h l e n b e i n ，1 9 9 8 ) 的。经过近1 5 年的发展，目前已 产生出多个算法模型。这些算法或者对随机变量之间的依赖关系的假设不同 ( p e l i k a n ，1 9 9 9 a ) ，或者所采用的概率模型不同，大体可以分为两大类：离散优 化分布估计算法和连续优化分布估计算法。 ( 一) 离散优化分布估计算法 如果随机变量从有限数值集合中取值，这时的分布估计算法就是离散的分布 估计算法。离散的分布估计算法计算和实现都比较简单。因此，离散的分布估计 算法首先得到了研究和发展。 1 ) 基于单变量模型的分布估计算法 单变量模型假设所有随机变量都是统计独立的，因此各变量联合概率分布的 计算可以简化为各变量的取值概率的乘积，即 p ( x l x 2 x ，) = p ( x 1 ) p ( x 2 ) p ( x ，) ( 1 - 1 对于采用二值编码的进化算法，可以用一个概率向量来描述每一代的群体。 该概率向量中的每一个变量描述了二值串中每一位取值为1 或0 的概率。按照该 概率向量对二值解空间进行采样，就可以得到每一代群体。 单变量概率模型的学习方法比较简单。随机变量x ，取值为x 的概率为 尸( 鼍：x ) ：f r q ( x , = x ) 一 万 ( 1 2 ) 其中f r q ( x j = x ) 表示第f 个随机变量毛取值为x 的次数，以为群体大小。 基于单变量概率模型对解空间进行采样可以通过模拟轮盘赌来实现，即根据 离散变量各个值的取值概率的大小对【0 ，1 ) 区间进行分段，一个取值对应一个分 段，然后通过一个 0 ，1 ) 区间均匀分布的随机数发生器实现采样。 2 ) 基于双变量概率模型的分布估计算法 第1 章绪论 变量独立假设是一个过于苛刻的假设，实际应用中满足这样假设的问题非常 少。在更多情况下，变量之间是存在相互依赖关系的。比变量独立假设宽松一点 的是双变量依赖假设，双变量概率模型假设随机变量的依赖关系仅存在于两个变 量之间。典型的基于双变量概率模型的分布估计算法有m i m i c ( b o n e t ，1 9 9 7 ) 、 c o m i t ( b a l u j a ，1 9 9 7 ) 和b m d a ( p e l i k a n ，1 9 9 9 c ) 等。下面我们以m i m i c ( m u t u a l i n f o r m a t i o n m a x i m i z i n gi n p u tc l u s t e r i n g ) ( b o n e t ，19 9 7 ) 算法为例来介 绍基于双变量概率模型的分布估计算法。 设优化问题的所有自变量的集合为x = z ，f = 1 , 2 ，) ，其联合概率分布可 表示如下： p ( x ) = p ( x lix 2 x t ) 尸 2ix 3 ) 尸( x hfx ，) e ( x ，) ( 1 3 ) 精确计算多个变量的联合概率分布是一个非常困难的任务。一方面要求样本 的分布和数量必须足够大，另一方面，计算的代价也非常高。在有些情况下，我 们可以对任务进行简化，上述单变量模型就是对联合概率分布的一种最简单的近 似。我们也可以将联合概率分布的计算简化为仅考虑多个变量之间串行依赖关系 的形式。 令疗是1 ，的一个排列万= i t i 2 ，定义一类概率分布巧( x ) ： 群( z ) = p ( x ix 如) 尸( x ，2x ) 尸( x 1x ) 尸( x ) ( 】4 ) 其中万决定了这个分布中变量之间依赖关系及其条件概率。我们需要找到一 个最优的排列万，使得概率分布巧( x ) 与真实的联合概率分布p ( x ) 尽可能地相 似。m i m i c 算法采用k u l l b a c k l i e b l e r 散度d ( plg ) 来度量男( x ) 和p ( z ) 之间的 相似性。为降低模型学习的计算代价，采用贪心算法来最优排序万。 3 ) 基于多变量概率模型的分布估计算法 双变量概率模型有时仍然不能满足描述实际应用问题复杂内在结构的需求。 这时，就要考虑采用更为复杂的概率模型，如能描述三个以上变量之间依赖关系 的多变量概率模型。统计学习理论告诉我们，简单模型一般具有较好的泛化能力， 但是可能对给定数据的描述能力较弱：复杂模型一般能更准确地描述给定的数 据，但是泛化能力往往又比较差。因此，我们需要有办法选择一个复杂度适中的 模型，使其在数据描述精度和泛化能力两方面有一个较好的折中。 多变量概率模型的学习需要解决两个重要问题，一是找到一种高效的模型学 习方法，以有限的计算代价获得概率分布的一个较优估计。由于多变量概率模型 学习本身是一类复杂度很高的问题，同时对样本数量的要求也很大，因此，一般 采用贪心算法来实现近似估计：另一个问题是找到一种有效的模型约简方法，以 6 第l 章绪论 提高模型的泛化能力，这通常需要确定一个好的准则。典型的基于多变量概率模 型的分布估计算法有e c g a ( s a s t r y , 2 0 0 0 ) 、b o a ( p e l i k a n ，1 9 9 9 b ) 等。 在e c g a ( e x t e n d e dc o m p a c tg e n e t i ca l g o r i t h m ) 中，首先对所有变量进行分 组，采用最小描述长度( m i n i m u md e s c r i p t i o nl e n g t h ，m d l ) 准则作为组的紧 致度量，采用一种贪心策略来实现分组优化；对每一组变量使用c g a 策略估计 其边缘概率分布。 b o a ( b a y e s i a no p t i m i z a t i o n a l g o r i t h m ) 采用贝叶斯网络作为变量的概率模 型。在b o a 中，需要解决两个关键问题，选择一个合适的模型质量评价准则， 和一个高效的模型学习方法。 模型质量评价准则是关于贝叶斯网络模型与一组样本数据之间吻合程度的 一种度量，理论上可以采用任何一个已有的合理准则。b o a 采用 b a y e s i a n d i r i c h l e t ( b d ) 准则，也有算法采用其它的规则，如m i n i m a ld e s c r i p t i o n l e n g t h ( m d l ) 。关于模型的学习，b o a 采用了一种贪心算法以实现模型的快速学 习。 ( 二) 连续优化分布估计算法 所谓连续优化问题是指该问题的自变量在连续的实数空间取值。可以通过两 种途径实现连续优化问题的求解：一种是把连续问题离散化，即将连续变量的取 值离散化，用离散变量来近似描述连续变量，然后直接采用上一节的离散优化分 布估计算法实现问题的求解。另一种途径是直接对连续变量建模。经常采用的概 率模型是高斯模型，这是因为，一方面高斯模型比较简单，已有许多有效的模型 学习算法；另一方面，现实应用中的许多分布都可以用高斯分布加以近似。高斯 模型学习包括模型结构学习和参数学习两部分。模型结构学习就是要确定高斯分 量的个数，这个问题在假设各变量相关的高斯混合模型的学习时会面临，而对于 变量独立假设下的高斯模型，则不存在结构学习的问题；参数学习就是根据给定 样本数据估计模型的均值和方差( 或协方差矩阵) 。 1 ) 基于单变量模型的分布估计算法 同离散分布估计算法一样，我们先讨论在变量独立假设下的分布估计算法， 此时，各变量的联合概率分布可以用它们各自的边缘概率分布的乘积来近似，如 下式所示( s e b a g ，1 9 9 8 ) 。 p ( x l x 2 x f ) = p ( x 1 ) 尸( x 2 ) p ( x ，) ( 】8 ) 假设p ( x ，) 服从高斯分布： 7 第1 章绪论 即扣南p 南”川2 记为p ( x ，) 一( ，盯? ) 。当给定一组样本时， 和方差仃0 加去弘 ( 1 - 9 ) 可以按下式估计分布的均值， ( 1 1 0 ) 班去鼢删 m 其中，是变量x ，的第后个样本，声，和钟分别为肛和砰的估计。 基于单变量高斯模型的分布估计算法的一般流程如下： 1 ) 按照一定的初始分布采样产生初始群体； 2 ) 评估每一个个体的适应度值； 3 ) 采用某种选择策略，从群体中选择前m 个较优个体； 4 ) 根据选择的m 个体，学习单变量高斯模型； 5 ) 根据新学习得到的单变量高斯模型，采样产生新一代群体，并评估每一 新个体的适应度； 6 ) 如果满足终止条件，则停止算法；否则，返回步骤3 ) 。 在基于单变量高斯模型的分布估计算法中，模型参数的更新可以采用两种策 略：一种是逐渐更新策略，即高斯模型的均值和方差以一定的比率逐渐更新，以 体现新知识的引入和旧知识的记忆，其形式如下式所示( s e b a g ，1 9 9 8 ) 。 。2 。甜( 1 一口) + 口。优 ( 1 1 2 ) 吒2 。= 口乞( 1 一口) + 彦乙口 ( 1 1 3 ) 其中，。材是随机变量在上一代的均值，p 。伽是当前代新估计出的均值， 口( 0 口1 ) 是学习率，控制着算法的收敛速度。 另一种更新策略是完全更新，即每一代都是以新学习的均值和方差完成取代 前一代的均值和方差，其形式如下式所示( g o n z a l e z ，2 0 0 2 ) 。 = k ( 1 1 4 ) = 威。 ( 1 一l5 ) 此外，在基于单变量高斯模型的分布估计算法中，高斯模型常常又被看成是 8 第l 章绪论 变量的邻域函数，用于引导变异。此时，高斯模型的方差就是决定变异步长的重 要参数，因此，除了式( 1 4 ) 和( 1 6 ) 的更新策略外，还可以考虑采用其它几种 更新方法： ( 1 ) 方差保持一个常数c ，不随时间而改变。 ( 2 ) 按照一个固定的衰减策略，逐渐减小方差的值，以控制算法的收敛， 如下式： 仃乙= 仃勃 ( 1 1 6 ) 其中：0 ( 口，夕) 为两个复常数，满足条件 口| 2 + | 1 2 = 1 其中i o 和1 1 分别表示两个不同的量子基本态。 l o 和1 1 两个态的信息。 ( 1 2 7 ) ( 1 2 8 ) 一个量子比特可以同时存储 若干个量子比特的集合构成一个量子寄存器。一个两比特量子寄存器有4 个独立的状态1 0 0 ，1 0 1 ，1 1 0 ，1 1 l ，张起一个四维的矢量空间，该量子寄存器 可以同时存储这4 个态的迭加态，因此可以同时包含这4 个态的信息。类似地， 三比特量子寄存器的态矢量可以张起一个8 维矢量空间，一个三位量子寄存器的 态矢量可以张起一个2 维矢量空间，因而可以存贮2 厶个不同的状态信息。 量子计算机对量子寄存器进行处理，即同时对其中存储的各个迭加态进行计 算，这就是所谓的“量子并行 ，量子计算机具有超出经典计算机的信息处理能 力，就源于它的这种高度并行计算。 1 3 2 量子进化算法的研究进展 ( 一) 量子进化算法模型研究 将量子理论与遗传算法相结合的尝试开始于二十世纪九十年代后期，1 9 9 5 年，a j i tn a r a y a n a n 和m a r km o o r e 率先将量子力学的概念与模型引入进化计算 ( n a r a y a n a m ，1 9 9 6 ) 。他们将量子力学中的“多宇宙 假设引入遗传算法，提出 了一个量子启发遗传算法( 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 中， 群体被分成若干个相同大小的子群体，每个子群体模拟一个“量子宇宙”，各个 子群体采用相同的遗传策略独立进化。在每一代进化操作结束后，各子群体之间 通过作者定义的联合交叉算子交换信息，以实现联合进化。作者将量子启发遗传 算法用于求解旅行商问题( t s p ) ，取得了较好的效果。q i g a 的成功表明，将量 子力学中的概念和模型引入进化计算是可行和有效的。 2 0 0 0 年，k h h a n 等提出遗传量子算法( g e n e t i cq u a n t u ma l g o r i t h m ) ( h a n ， 2 0 0 0 ) 。在g q a 中，首次引入量子比特的概率幅来表示基因，用量子比特串来 编码个体。引入量子力学中的“测量 操作来实现量子概率向量到实际解向量的 映射。引入量子计算中的“旋转门( r o t a t i o ng a t e ) ”来实现量子比特概率幅的更 新。作者定义了一种算法结构，即多个量子概率向量构成一个量子种群，每个量 子个体通过测量、评估、更新等一系列操作实现进化，全部量子个体之间通过共 享全局最优解而实现协同进化。作者通过0 1 背包问题对g q a 的性能进行了验 1 2 第1 章绪论 证。 2 0 0 2 年，k h h a r t 等对g q a 进行了扩展，提出了量子启发进化算法 ( 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 ) ( h a n ，2 0 0 2 ) 。在q e a 中，引入了局 部迁移操作，以改善g q a 由于收敛过快而容易陷入局部最优的不足。q e a 可以 认为是量子概念与进化计算的最好的结合，也是迄今关于量子进化算法最为重要 的工作之一。此后，h a r t 等还对q e a 的参数设定问题进行了研究( h a n ，2 0 0 4 ) ， 并尝试将q e a 应用于人脸识别( j a n g ，2 0 0 4 ) 、金融数据分析( f a n , 2 0 0 8 a ) 等实 际工程问题的求解，也取得了较好的效果。 随着n a r a y a n a n 和h a n 等人研究成果的发表，在进化计算领域掀起了一股量 子进化算法研究的热潮。2 0 0 2 年，李斌等人提出了一种基于量子概率表达的遗 传算法( g e n e t i ca l g o r i t h mb a s e d o i lq u a n t u mp r o b a b i l i t yr e p r e s e n t a t i o n ，g a q p r ) ( l i ，2 0 0 2 ) ，将量子编码个体看成是遗传算法中的染色体，根据量子概率向量更 新的特点，提出了一种量子交叉操作，取代q e a 中的迁移操作，实现个体间的 协同进化。同时提出了一种基于量子非门