（电路与系统专业论文）分布估计算法及其应用研究.pdf

中国科学技术大学硕：卜学位论文 摘要 分布估计算法及其应用研究 摘要 在当代科学技术的各个领域都存在各种各样的优化问题，形成的数学模型也 各不相同。近年来，进化计算在解决复杂优化问题方面取得了很大的成就。但是 在如何根据具体的问题设计有效的进化算法以提高计算速度及解决约束优化问 题等方面还有许多工作需要去做。遗传算法中的积木块假设使遗传算法具备了搜 索到全局最优解的能力，但遗传操作算子在解决一些问题时却会破坏积木块，使 它们无法有效重组，因此无法生成全局最优解。研究如何保护在搜索过程中获得 的优良模式( 即积木块) 不受遗传算子的破坏，并对它们有效重组，成为近年来 进化与遗传算法研究领域关注的一个重要课题。这导致了一类新的进化算法的出 现，即分布估计算法。本文对分布估计算法进行了研究，论文的主要工作和创新 之处有： ( 1 ) 提出了两种新的用于连续函数优化的分布估计算法，它们都是利用高 斯混合模型( g m m ) 对解空间中的优良解所在区域进行建模，分别采用 “b o o s t i n g 技术和贪心的e m 算法对g m m 进行学习，实现了模型结构和模型 参数的自动学习，消除了此前e d a s 对模型结构先验知识的依赖。 ( 2 ) 提出了一种基于高斯概率分布估计和一种基于边缘分布估计的多目标 优化算法，它们分别在每一进化代中通过估计较优个体的高斯概率分布和边缘概 率分布来引导各自对p a r e t o 最优解的搜索。通过与p a r e t o 排序、基于拥挤机制 的多样性保持等技术的有机结合，使得这两种算法在具有良好收敛性能的同时， 具有很好的维持群体多样性的能力。由于算法采用了概率模型比较简单，在进化 的过程中估计概率分布时不用学习变量间复杂的结构信息，因此它们的计算复杂 度较低、速度比较快。 ( 3 ) 提出了一种解决多目标背包问题的多目标优化算法，该算法通过估计 多个概率模型的边缘分布来保持群体的多样性，对于解决这种多目标的组合优化 问题具有很强的寻优能力，得到的结果可以非常逼近p a r e t o 前沿，而且分布范 围比较广。 关键词：分布估计算法；高斯混合模型：提升；贪心的e m 算法：多目标优化；p a r e t o 前沿 中国科学技术大学硕士学位论文 a b s t r a c t 分布估计算法及其应用研究 a b s t r a c t t h e r ea r ev a r i o u so p t i m i z a t i o np r o b l e m si na l if i e l d so fs c i e n c ea n d t e c h n o l o g yt o d a ya n dt h ec o r r e s p o n d i n gm a t h e m a t i c a lm o d e l sd i f f e rf r o me a c h o t h e r r e c e n t l y ，e v o l u t i o na l g o r i t h m ( e a ) p e r f o r mw e l li ns o l v i n gc o m p l i c a t e d o p t i m i z a t i o np r o b l e m h o w e v e r 。i tc o u l db ei m p r o v e di na s p e c t so fo f f e r i n g e f f i c i e n ta l g o r i t h mf o rt h eg i v e np r o b l e ma n ds o l v i n go p t i m i z a t i o np r o b l e mw i t h r e s t r i c t i o n s g e n e t i ca l g o r i t h m ( g a ) h a st h eg l o b a ls e a r c h i n gc a p a b i l i t yf o rt h e b u i l d i n gb l o c kh y p o t h e s i s h o w e v e rt h eg e n e t i co p e r a t o rm a yd e s t r o yt h e b u i l d i n gb l o c k s ，s ot h eb u i l d i n gb l o c k sc a n tb er e c o m b i n e de f f i c i e n t l y t h e r e f o r e t h eg l o b a io p t i m a ls o l u t i o nc a n 。tb eo b t a i n e d h o wt op r e s e r v et h e g o o ds c h e m a sw h i c ha r eg e n e r a t e di ns e a r c h i n gp r o c e s sf r o mn o tb e i n g d e s t r o y e da n dh o wt or e c o m b i n et h e me f f i c i e n t l yg e tm o r ea t t e n t i o n i n r e s e a r c ho fg ar e c e n t l y s oan e wk i n do fe a sh a sa p p e a r e d e s t i m a t i o no f d i s t r i b u t i o na l g o r i t h m s ( e d a s ) t h i sp a p e rf o c u s e so nt h ee d a sa n dt h em a i n w o r ka n dn o v e ip a r t so ft h i sd i s s e r t a t i o na r e ： ( 1 ) t w on e we 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 sf o rc o n t i n u o u sf u n c t i o n o p t i m i z a t i o na r ep r o p o s e d ，i nw h i c hg a u s s i a nm i x t u r em o d e i ( g m m ) i s a d o p t e dt om o d e lt h ep r o m i s i n ga r e ao fs o l u t i o ns p a c e ，t h eb o o s t i n gt e c h n i q u e a n dg r e e d ye ma l g o r i t h ma r ea d o p t e dt oe s t i m a t eg m m s oi th a st h ea b i l i t yo f l e a r n i n g t h em o d e is t r u c t u r ea n dp a r a m e t e r sa u t o m a t i c a l l yw i t h o u ta n y r e q u i r e m e n tf o rp r i o rk n o w l e d g e ( 2 ) an e wm u l t i 一0 b j e c t i v eo p t i m i z a t i o na l g o r i t h mb a s e do ng a u s s i a n d i s t r i b u t i o ne s t i m a t i o na n dan e wm u l t i o b j e c l i v eo p t i m i z a t i o na l g o r i t h mb a s e d o n m a r g i n a l d i s t r i b u t i o ne s t i m a t i o na r e p r o p o s e d ，i n w h i c hg a u s s i a n d i s t r i b u t i o na n d m a r g i n a lp r o b a b i l i t y d i s t r i b u t i o no ft h es e l e c t e db e t t e r i n d i v i d u a l sa r ee s t i m a t e da n da r eu s e dt og u i d et h es e a r c ho fp a r e t oo p t i m a l s o l u t i o n so ft h em u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m c o m b i n e dw i t hp a r e t o r a n k i n g ，d i v e r s i t yp r e s e r v i n gt e c h n i q u eb a s e do nc r o w d i n gm e c h a n i s me t c ，t h e a l g o r i t h m sa c h i e v eag o o db a l a n c eb e t w e e ng o o dc o n v e r g e n c ea n dd i v e r s i t y t h et w oa l g o r i t h m sd o n ti e a r nt h ec o m p l e xs t r u c t u r ei n f o r m a t i o nb e t w e e n v a r i a b l e so ne s t i m a t i n gp r o b a b i l i t yd i s t r i b u t i o ni ne v o l u t i o nb e c a u s eo fa d o p t i n g s i m p l ep r o b a b i l i t ym o d e l s ot h e i rc o m p u t a b i l i t yc o m p l e x i t yi sl o wa n ds p e e di s q u i c k ( 3 ) an e wm u l t i o b j e c t i v eo p t i m i z a t i o na l g o r i t h mf o rs o l v i n gm u l t i o b j e c t i v e k n a p s a c kp r o b l e mi sp r o p o s e d ，i nw h i c hm u l t i p r o b a b i l i t ym o d e l sm a r g i n a l p r o b a b i l i t yd i s t r i b u t i o no ft h es e l e c t e db e t l e ri n d i v i d u a l si se s t i m a t e da n dl s u s e dt op r e s e r v et h ed i v e r s i t yo fp o p u l a t i o n t h i sa l g o r i t h mh a st h ep o w e r a b i l i t yo fs e a r c h i n go p t i m a l t h er e s u l tc a nb ev e r yc l o s et op a r e t o f r o n t 。a n d s p r e a dw i d e r k e y w o r d ：e s t i a m a t i o no fd i s t r i b u t i o na i g o r i t h m s ，g a u s s i a nm i x t u r em o d e l ，b o o s t i n g ， g r e e d ye ma l g o r i t h m ，m u l t i o b j e c t i v eo p t i m i z a t i o n ，p a r e t o f r o n t 中国科学技术大学硕：l 学位论文 第一章绪论 分布估计算法及其应用研究 第一章绪论 在当代科学技术的各个领域都存在大量的优化问题，虽然优化方法有很多分 支且获得了许多成果，但是客观实际问题也是各种各样，形成的数学模型自然也 各不相同。因此要想以一种优化方法有效地解决所有的问题是不现实也是不可能 的。近年来，进化计算在解决复杂优化问题方面取得了振奋人心的成就。但是在 如何根据具体的问题设计有效的进化算法以提高计算速度及解决约束优化问题 等方面还有许多工作需要去做。进化计算包括遗传算法、进化规划和进化策略。 遗传算法是最早出现的一类进化算法。 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是模拟生物进化过程中优胜劣汰规则 与群体内部染色体信息交换机制的一类处理复杂优化问题的方法，它是一种基于 群体的启发式搜索算法n 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 s ，e d a s ) ， 这一类方法也叫做概率模型构造的遗传算法( p r o b a b i l i s t i cm o d e lb u i l d i n g g a s ，p m b g a s ) ，或迭代的密度估计算法( i t e r a t e dd e n s i t ye s t i m a t i o n a l g o r i t h m s ，i d e a s ) 。分布估计算法的基本思想是：利用概率模型对问题解空间 6 中国科学技术大学硕二卜学位论文 分布估计算法及其应用研究 第一章绪论 中有希望出现最优解的区域进行建模，然后利用该模型引导算法进行搜索嗨1 。与 其它演化算法( 如g a ) 不同，e d a s 用以下两个步骤来替换传统的遗传交叉和变 异操作伯1 ：( 1 ) 利用统计学习方法对较优解的概率分布进行估计；( 2 ) 根据估计 得到的概率分布模型对解空间重新采样，得到新的一组解。e d a s 已被用于组合 优化盯卜n 3 1 和连续优化n 4 h 1 8 3 两类主要优化问题的求解，结果表明e d a s 是一类新的 高效优化搜索算法。 1 1 传统遗传算法及其研究现状 1 1 1 遗传算法的基本思想 2 0 世纪6 0 年代中期，美国m i c h i g a n 大学的j o h nh o l l a n d 在a s f r a s e r 和h j b r e m e r m a n n 等工作的基础上提出了位串编码技术，这种编码既适合于变 异又适合交配( 即杂交) 操作，并且他强调将交配作为主要的遗传操作。随后， j h o l l a n d 将该算法用于自然和人工系统的自适应行为的研究之中，并于1 9 7 5 年出版其开创性的著作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 n 引。 后来，j h o l l a n d 与他的学生们将该算法加以推广并应用到优化及机器学习等问 题之中，而且正式定名为遗传算法。 1 1 2 遗传算法的一般结构 遗传算法的用伪代码可描述如下： b e g i n t = o ； 初始化p ( t ) ； 评估p ( t ) ； w h il e 不满足终止条件d o b e g i n 由p ( t ) 通过遗传操作形成新的群体p ( t + 1 ) ； 评估p ( t + 1 ) ； t = t + 1 ： e n d e n d 中国科学技术人学硕：卜学位论文 第一章绪论 分布估计算法及其应用研究 1 - 1 3 遗传算法的优点与不足 遗传算法模拟大自然生物演化的思想，具有很强的鲁棒性和适应性，广泛应 用在函数优化、参数估计、系统建模、组合优化和约束满足问题等等，解决了传 统优化方法难以解决的复杂优化问题，能在复杂空间内进行有效的搜索。但是 g a 在显示其巨大优越性的同时也暴露出一些局限性，一方面，遗传算法起关键 作用的两个算子都是发生在一定概率下，随机的、没有指导的迭代搜索，因此它 们在为种群中个体提供进化机会的同时，也无可避免的产生了退化的可能。在某 些情况下，这些退化还相当明显，特别是在接近全局最优解时，过早收敛，个体 的多样性很快减少，甚至陷入局部最优解等。另一方面，每一个待求的实际问题 都会有一些基本的、显而易见的特征信息或知识，然而遗传算法杂交和变异算子 却相对而言固定，在求解问题时，可变的灵活程度较小，这无疑对算法的通用性 是有益的，但却忽视了问题的特征信息对求解问题的帮助作用特别在求解一些复 杂问题时，这种“忽视”所带来的损失比较明显。 1 1 4 研究现状 最初，演化计算有遗传算法( g e n e t i ca l g o r i t h m ) 、演化规划( e v o l u t i o n a r y p r o g r a m m i n g ) 和演化策略( e v o l u t i o ns t r a t e g y ) 三个分支。2 0 世纪9 0 年代 初，在遗传算法的基础上又发展了一个分支：遗传规划( g e n e t i cp r o g r a m m i n g ) ， 它们虽然在算法的实现方面具有一些细微的差别，但它们都是借助生物演化的思 想和原理来解决实际问题。 演化计算在大型优化问题求解、机器学习、自适应控制、人工生命、神经网 络、经济预测等领域取得的成功，已引起了包括数学、物理学、化学、生物学、 计算机科学、社会科学、经济学及工程应用等领域科学家们的极大兴趣。自8 0 年代中期以来，世界上许多国家都掀起了演化计算的研究热潮。由于演化计算应 用范围广泛，从很多国际会议论文集中都可以看到有关演化计算应用方面的文 章。目前，有数种以演化计算为主题的国际会议在世界各地定期召开，包括“i e e e i n t e r n a t i o n a l c o n g r e s s o n e v o l u t i o n a r yc o m p u t a t i o n ( i c e c ) ”、 “i n t e r n a t i o n a lc o n f e r e n c eo ng e n e t i ca l g o r i t h m s ( i c g a ) ”、“g e n e t i ca n d 中国科学技术大学硕士学位论文分布估计算法及其应用研究 第一章绪论 e v o u t i o n a r yc o m p u t a t i o nc o n f e r e n c e ( g e c c o ) ”等。1 9 9 3 年由m i tp r e s s 出 版创刊了杂志“e v o l u t i o n a r yc o m p u t a t i o n ”，1 9 9 7 年又新创了杂志“i e e e t r a n s o ne v o l u t i o n a r yc o m p u t a t i o n ”，一些国际性期刊也相继出版以演化计算为主题 的专刊。 可以预见，随着演化计算理论研究的不断深入和应用领域的不断拓广，演化 计算必将取得更大的成功。 1 2 分布估计算法及其研究现状 1 - 2 1 概述 在遗传算法中有很多种不同的交叉与变异操作。在应用遗传算法时选择哪一 种交叉和变异操作依赖于使用者的经验，使用时根据对应用问题的分析和认识选 择适当的交叉和变异操作可以有效解决实际问题。但是，如果没有对于应用问题 的比较多的分析和认识，直接应用遗传算法就有盲目性。在实际操作中不合适的 算子往往会被使用。例如，当问题的基因块与编码没有紧密结合的时候选择单点 杂交是不合适的。这在先验知识未知的情况下尤为突出。因此了解无用积木块 ( b u i l d i n g b l o c k ) 的分布显得非常重要。而且分布的关联信息能被用来提升遗传 算法的效率。 在遗传算法中，基因之间的关系或连接( 也就是基因块) 起到了很大的作用， 各种遗传算子的作用是通过继承或改变基因之间的关系而实现的。可以注意到， 每一代群体的个体中都含有基因之间关系以及个体的适应度信息。因此，从机器 学习的角度看，当我们没有对于应用问题的先验知识的时候，可以从这些个体中 学习基因之间关系以及个体的适应度信息。利用这些学习到的信息可以生成性能 更好的下一代群体。研究如何保护在搜索过程中获得的优良模式( 即积木块) 不 受遗传算子的破坏，并对它们有效重组，成为近年来进化与遗传算法研究领域关 注的一个重要课题。这一思想引发了分布估计算法的研究。 1 2 2 分布估计算法的基本思想 分布估计算法的基本思想就是使用概率的方法描述和表示每一代群体。一个 中国科学技术大学硕：b 学位论文分布估计算法及其应用研究 第一章绪论 优化问题中每个自变量x 。被看作是一个随机变量( 也可以编码为遗传算法中的一 个基因) ，所有的随机变量构成一个随机向量x = ( x 1 ) x ：，x ，一，x ，) ( 同样对应 与遗传算法中的基因串) 。这时的一个个体就是该随机向量的一个取值，而一个 群体就对应于该随机向量的一个分布。随机向量的分布是群体性能的一个指标， 利用这个指标可以紧凑和整体地表示该群体。分布中包含了随机变量之间的概率 依赖关系，这种关系也是一种基因之间的关系，学习随机变量的分布就等于是在 学习基因之间的关系。在一个概率分布上的采样过程可以生成更有价值的群体和 个体。因此，分布估计算法利用每一代的个体，从中学习随机向量的分布，然后 在学习到的分布的基础上再生成下一代新个体，如此循环。算法的基本框架如下： 步骤1 ：初始化群体，并对每一个个体估值； 步骤2 ：从群体中选择个体； 步骤3 ：根据选择的个体估计概率分布； 步骤4 ：根据上一步估计出的概率分布，采样新一代个体，并对每一新个体 估值： 步骤5 ：如果某准则满足，则算法停止：否则，返回步骤2 。 1 2 3 研究现状 分布估计算法于1 9 9 6 年由m u h l e n b e i n 和p a a b 所提出，它的核心即是概率 图模型的生成及表示。应用于分布估计算法的概率图模型目前主要有两种，分别 是高斯网络( g a n s s i a nn e t w o r k s ) 和贝叶斯网路( b a y e s i a nn e t w o r k s ) 。分布估 计算法由于对于随机变量( 基因) 之间的依赖关系的假设不同瞳0 1 ，或其分布函数 的不同而产生了很多的算法，这些算法可以分成离散的和连续的两大类：如p b i l 算法、c g a 、u m d a 、m i m i c 算法、c o m i t 算法、b m d a 、e c g a 、b o a 、f d a 、i d e a 等 算法。具体介绍如下： ( 一) 离散的分布估计算法 在一个优化问题中，通常情况下有很多自变量。如果这些变量从有限数值集 合中取值，这时的分布估计算法就离散的分布估计算法。离散的分布估计算法计 算和实现都比较简单。一些连续的分布估计算法也通过离散化而使用离散的分布 l o 中国科学技术大学硕二b 学位论文分布估计算法及其应用研究 第一章绪论 估计算法。因此，离散的分布估计算法首先得到了研究和发展。 1 、变量独立假设下的算法 分布估计算法的最简单的情况是假设所有的随机变量都是独立的。也就是所 有基因之间没有关系，即 p ( x i x 2 x f ) = p ( x 1 ) p ( x 2 ) p ( x f ) ( 1 1 ) 先考虑如果每一个个体使用二进制编码方法时的状况，这时可以使用一个概 率向量描述每一代的群体。这个概率向量就确定了二进制串中每一位取值为1 的概率( 每一位取值为0 的概率等于1 减去取值为1 的概率) 。如果已经计算出 了概率向量，每一代的个体就可以从该概率向量中采样生成。 从群体中学习离散随机变量概率分布的算法比较简单，这是一个基于计数的 方法。离散随机变量x 取值为x 的概率为 眠：x ) ：螋 船 ( 1 2 ) 其中撑( 彳) 表示事件a 发生的次数，行为群体大小。可以证明，该估计是最大似 然估计。 在一个离散随机变量的分布上的采样不是一个困难的问题，这可以通过轮盘 赌的方式实现。 ( 1 ) p o p u l a ti o n b a s e di n c r e m e n t a ll e a r i n g ( p b i l ) 算法 步骤1 ：初始化群体，并对每一个个体估值； 步骤2 ：从群体中选择m 个最优个体； 步骤3 ：根据选择的个体估计随机向量的概率分布； 步骤4 ：根据上一步估计的分布，采样新一代个体，并对每一新个体估值； 步骤5 ：如果某准则满足，则算法停止；否则，返回步骤2 。 在算法步骤1 中，除了像遗传算法一样初始化一个群体，还可以通过令每一 个随机变量为均匀分布，然后在这些均匀分布的基础上再采样从而实现群体的初 始化。如果是二进制编码方法，可以初始化概率向量为( 0 5 ，o 5 ，0 5 ) 。 在步骤2 中，需要选择m 个最优个体。这m 个最优个体是群体中性能最好的 个体，它们代表了群体的进化的方向。因此，步骤3 的分布估计过程是在这m 中国科学披术大学硕：+ i i 学位论文分布估计算法及其应用研究 第一章绪论 个最优个体的基础上展开的。这时的一个特殊情况，就是m = l 。也就是说，群体 中最优秀的个体代表了整个群体的进化方向，它们指导了搜索的进行。 在步骤3 中，首先要对于每一个随机变量按照公式2 估计其分布，然后按照 下面的概率更新规则更新随机向量的分布： e 。= “( 1 0 一口) + 只。口 ( 1 3 ) 其中，只肼是随机变量在上一代的分布，只。是步骤2 中在选择的m 个最优个体 的基础上估计出的概率分布，口学习率，0 口1 。学习率参数口则控制了算法 的收敛速度。 步骤5 类似于标准遗传算法中的算法终止步骤。 因为由一个随机向量的一个分布所代表的群体是不唯一的，这有助于算法在 搜索中保持个体的多样性。该算法与标准的遗传算法一样都存在早熟的可能，即 收敛到局部最优。在p b i l 算法中，当随机变量取某数值的概率接近0 或l 时， 产生的向量的相似性会增加，这不利于算法在新的空间中搜索。因此，可以考虑 在算法中增加变异机制。 在p b i l 算法中，有两种变异方法，一种是直接在采样生成的解的基础上执 行变异操作，这一方法类似于标准遗传算法中的变异算子；另一种是在概率向量 的每一个分量上允许小的概率扰动。小的概率扰动，会使随机变量取某数值的概 率接近0 或1 时，生成的新的群体仍然能够保持多样性，因而可能避免收敛到局 部最优。 学习率参数口对于算法的收敛速度起到很大的作用，通过学习率参数能够控 制收敛速度，这是该算法的一个优点。学习率对于p b i l 算法的影响比对于标准 的遗传算法的竞争学习的影响要大。学习率影响了在下一代群体生成中，函数空 间的哪一部分的权重更大，当口比较小时，算法中原来的概率向量在新的向量中 占了更重要的位置，这时算法收敛较慢：当口比较大时，新估计的概率向量的作 用更大。它可以被看成是在全空间搜索能力和在已经搜索过的空间得到的信息之 间的一个折中。 口= 1 是该算法的一个特殊情况，这时，该算法更注重全空间的搜索能力。 这时的算法也被叫做单变量边缘分布算法( u n i v a r i a t em a r g i n a ld i s t r i b u t i o n a l g o r i t h m ，u m d a ) 。 中国科学技术大学硕= 卜学位论文分布估计算法及其应用研究 第一章绪论 ( 2 ) c o m p a c tg e n e t i ca l g o r i t h m ( c g a ) 步骤l ：初始化所有随机变量的分布为均匀分布； 步骤2 ：从分布中生成两个个体； 步骤3 ：根据选择的个体更新随机变量的分布； 步骤4 ：如果某准则满足，则算法停止；否则，返回步骤2 。 c g a 和p b i l 之间的主要差别在随机变量分布的更新规则上，也就是上面算 法的步骤3 中，在c g a 的步骤3 中，首先比较生成的两个个体，得到个体x 。和 x 胁然后对于每一个随机变量x j ，假设两个个体x 。，和x h 。，的随机变量取值 分别为x 和x 。，比较两个x 和x 。是否相同，如果相同，则什么都不做；如 果不同，则 只。( z ，：x ) ：埘( x ，：x ) + ! ( 1 4 ) 其中只埘是更新之前的分布，。是更新后的分布，n 是群体大小。在此步骤之 后，需要再对得到更新之后的分布做归一化，使之成为一个概率分布。 如果在步骤2 中同时生成了m 个体，可以对这m 个个体两两比较，依次完成 上式的分布更新。 c g a 最后的输出是概率分布p ，由于该算法的特殊性，它要求的存储量更小。 这类算法的概率模型可以用图1 1 表示，该表示借用了概率网络 ( p r o b a b i l i s t i cn e t w o r k s ) ，或称为图模型( g r a p h i c a lm o d e l ) 中的方法，这 种方法把每一随机变量用图中的一个节点表示，随机变量间的依赖关系或因果关 系用节点之间的边或有向弧表示。这样变量独立假设下的分布估计算法的模型可 以用图1 1 表示。由于变量之间是独立的，所以，所有节点之间没有边和弧连接， 可以把该图和后面概率模型的图相对照，从而比较其不同。 o o o o o o o 图1 1 变量独立假设下的e d a s 的图模型 2 、双变量概率依赖关系的算法 中国科学技术大学硕- | ：学位论文分布估计算法及其应用研究 第一章绪论 变量独立假设是一个太严格的假设，实际中这样的问题非常少，在更多的实 际问题中，变量之间是存在相互关系的，比变量独立假设宽松一点的要求是双变 量依赖假设，这一类算法假设随机变量的依赖性仅存在于两个变量之间。 ( 1 ) 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 ( m i m i c ) 假设优化问题的所有自变量构成的集合为x = x i , f 1 , 2 ，) 。这一组随机 变量的联合分布可以表示成 p ( x ) = p ( x jx 2 x ，) 尸( x 2x 3 x t ) p ( x f _ lx t ) 尸( x ，) ( 1 5 ) 由于群体大小的原因以及计算量的原因，得到所有随机变量之间的联合分布 和条件分布是困难的。因此，我们只考虑单变量的概率分布以及成对的随机变量 之间的联合分布和条件分布。在这种情况下，如果仅仅利用成对的随机变量的条 件分布p ( x iz ，) 以及随机变量的边缘分布p ( x ，) ，能否生成这样一些个体样本， 它们与从p ( x ) 中生成的个体样本具有相同的或近似的统计性质? 令乃是1 ，的一个排列7 r = i l i ：i l ，定义一类概率分布乓( x ) ： 鬈( x ) = p ( x x 。：) p ( x ，：h ) p ( x h ) 尸( ) ( 1 6 ) 其中7 t 决定了这个分布中使用哪些成对的条件概率，我们的目的就是选择一个排 列厅，使得概率分布群( x ) 与真实的概率分布p ( x ) 尽可能的接近。使用 k u l l b a c k l i e b l e r 散度d ( pi 巧) 来测量巧( x ) 和p ( x ) 之间的相似性，搜索所有 可能的万排序在计算上是很困难的，所以m i m i c 使用简单的贪心算法来寻找有最 优散度的排序万，然而用这种方法不一定能得到正确的模型。 m i m i c 算法的性能取决于两个因素：一个是有限数量的个体样本能否很好地 估计出模型的概率分布，这个因素是所有分布估计算法都面临的问题，另一个是 k u l l b a c k l i e b l e r 度量d ( pf 巧) 是否很小。只有当d ( pi 巧) 度量比较小的时 候，才说明概率模型与真实的分布非常接近。m i m i c 算法的模型可以用图1 2 表 示。 1 4 中国科学技术大学硕士学位论文 第一章绪论 分布估计算法及其应用研究 图1 2m i m i c 算法的图模型 ( 2 ) c o m b i n i n go p t i m i z e r sw i t hm u t u a li n f o r m a t i o nt r e e s ( c o m i t ) c o m i t 算法采用树形结构的概率分布模型，如下式： p ( x ) = 兀p ( x 小，) ( 1 7 ) 式中，表示i 的双亲位置。 c o m i t 使用最大加权跨度树( m 1 】l s t ) 算法来构造一个树结构，虽然这种模型 优于链形结构模型，但是树形结构不一定总是问题变量的真实结构。c o m i t 算法 的模型如图1 3 所示。 图1 3c o m i t 算法的图模型 ( 3 ) b i v a r i a t em a r g i n a ld i s t r i b u t i o na l g o r i t h m ( b m d a ) b m d a 算法是u m d a 算法的扩展，b m d a 比上面两种算法更加综合，它考虑到了 线性问题和变量间的成对相互关系，使用森林结构来表示概率模型。b m d a 使用 p e a r s o n 的z 2 统计方法来测量变量间的依赖关系，定义如下： zz ：y 丝竺型! 型丝垡 ( 1 8 ) 7 。 - e x p e c t e d 、 根据一元, u - 元边缘概率，变量位置f ，时，我们有： z 竺堕尘等掣型 ( 1 9 ) 几。x 厶i , x，) 尸( x ，)”7j n p ( x 如果z j 2 ， 3 8 4 ，我们就说变量f 和变量是9 5 不相关的。但是考虑双变量概率 模型的算法对于解决存在多变量间关联关系的问题来说仍然很不足够。b m d a 算 中国科学技术大学硕：i i 学位论文 第一章绪论 分布估计算法及其应用研究 法的模型如图1 4 所示。 图1 4b m d a 算法的图模型 3 、多变量概率依赖关系的算法 双变量概率依赖关系已经比较复杂，但有时仍不能满足实际应用的需求。因 此，需要考虑更复杂的概率模型，考虑三个以上随机变量之间概率关系的算法都 属于多变量分布估计算法。 多变量分布估计算法有两个重要问题需要解决，一个是有效构建概率模型的 问题，因为考虑的概率模型非常复杂，因此，要建立最优的概率模型计算量非常 大，通常采用贪心算法寻找次次优解：另一个问题就是如何判断两个随机变量之 间不存在概率依赖关系，这通常需要确定一个好的准则和一个好的阈值。 双变量分布估计算法在很多情况下会优于独立变量分布估计算法，这是因为 后者考虑的模型过于简单，沿此思路，需要考虑更多变量的相互依赖关系和研究 更复杂的概率模型。但是，考虑的变量数并不是越多越好。统计学习理论告诉我 们，简单的模型具有很好的泛化能力，但可能不具有很好的表示给定数据的能力。 复杂的模型能更准确地表示给定的数据，但泛化能力又比较差。因此，一个适当 复杂的模型，它对于数据的表示和泛化的综合能力最好。对于分布估计算法的模 型选择问题，可以利用统计学习理论作为指导。 ( 1 ) 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 i n ( e c g a ) e c g a 方法的思路是：首先把所有的变量划分成一些彼此独立的变量组，每 一组变量的边缘分布作为其联合概率分布。在每一组上使用c g a ，变量划分时， 使用了最小描述长度( 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 ) 准则作为一个变量组 的紧的度量。 在分布估计算法中，对于给定的一组样本，从中估计出的概率分布能力能够 比较好地表示这一组样本，但由于给定的样本是有限的，因此，需要考虑模型的 泛化能力。这需要在模型的简单性和准确性之间取一个折中，也就是说，我们的 目的是需要在能够很好地表示当前样本的模型中选择一个简单的模型。e c g a 算 1 6 中国科学技术大学硕士学位论文 第一章绪论 分布估计算法及其应用研究 法的模型如图1 5 所示，概率分布模型为： p ( x ) = p ( x 。) ( 1 1 0 ) c e f e c g a 算法： 步骤1 ：初始化群体，并对每一个个体估值； 步骤2 ：从群体中选择m 个最好的个体： 步骤3 ：用贪心搜索方法建立边缘乘积模型； 步骤4 ：对每一个变量子集生成一些新个体； 步骤5 ：根据构建的模型生成一些新个体： 步骤6 ：用新生成的个体构成新的群体： 步骤7 ：如果算法停止准则满足，则算法停止；否则，返回步骤2 。 图1 5e c g a 算法的图模型 ( 2 ) b a y e s j a no p t i m i z a t i o na 1 9 0 r i t h m ( b o a ) b o a 采用贝叶斯网络作为变量的概率模型。在b o a 中，有两个关键问题需要 解决，一个是选择一个合适的评分标准，另一个是搜索过程。 一个合适的评分标准是评价一个贝叶斯网络和一组样本数据之间吻合程度 的度量。在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 nl e n g t h ( m d l ) 。b o a 也使用贪心算法来搜索可能的网 络空间，所以b o a 也存在缺陷。b o a 算法的模型如图1 6 所示。 b o a 算法： 步骤1 ：初始化群体，并对每一个个体估值； 步骤2 ：从群体中选择m 个最优个体； 步骤3 ：使用选定的度量和限制构建贝叶斯网络； 步骤4 ：根据贝叶斯网络决定的概率分布生成一些新个体； 步骤5 ：用新生成的个体替换上一代中的一些比较差的个体； 中国科学技术人学坝：ij 学位论文分布估计算法及其应用研究 第一章绪论 步骤6 ：如果算法停止准则满足，则算法停止：否则，返回步骤2 。 图1 6b o a 算法的图模型 ( 二) 连续的分布估计算法 一般来说，连续变量情况下的建模更为困难，这时有两种思路可以使用。 一种是把连续随机变量离散化，然后使用上一节给出的各种分布估计算法。 离散的方法可以简化计算和减少存储要求，这在很多情况下是一个好的选择。离 散化的问题主要是由此而带来的误差太大。因此，另一种思路是直接对连续随机 变量建模。为简化问题，通常使用的概率模型是高斯模型。这样，建模的主要任 务就是计算模型的均值和方差( 或协方差矩阵) 。使用高斯模型有一些优点：容 易处理和实现，参数少。另外，在很多实际情况下变量的分布是高斯分布，或近 似高斯分布。 1 、变量独立假设下的算法 同离散分布估计算法一样，先讨论变量独立情况下的分布估计算法，这时有 p ( x l x 2 z ) = p ( x 1 ) p ( x 2 ) p ( x ，) ( 1 1 1 ) 可以假设p ( x ，) 服从正态分布： 尸( x 扣毒寺p 一帮叫r ( 1 1 2 ) 2 兀a ； 简记为p ( x i ) n ( u ，盯? ) 。当给定一组样本时，可以使用最大似然估计方法 估计分布的均值，和方差仃? ： p i = ! h 窆k =