（控制理论与控制工程专业论文）概率分析进化算法研究.pdf

摘要 f 进化计算利用进化过程中的计算模型作为关键技术，设计和实现以计算 机为基础的问题求解系统。进化过程中的计算模型统称为进化算法。进化算 法的共同特点是通过选择和重组过程模仿个体的进化过程。进化计算的主要 目的是研究快速、精确和可靠的胜任算法，以满足有效求解实际应用问题的 要求。进化计算不仅在基础理论、基本方法和手段上得到研究学者的重视， 而且在最优化、机器学习、信息挖掘和并行处理等许多领域得到广泛应用。 这些研究和应用工作为进化计算奠定了良好的理论基础：开辟了广阔的应用 前景 由h o l l a n d 首先提出的基本遗传算法( g a ) 是研究最为广泛的进化计算 算法之一，其基本理论依据是模式定理和“构造块”( b u i l d i n gb l o c k ) 假设 理论，但理论和应用表明g a 中的重组操作常造成构造块破坏，导致算法容 易早熟逼近局部。构造块破坏问题一般称为连锁( 1 i n k a g e ) 问题，具有识别 构造块的算法称为连锁学习算法。实际应用中也普遍存在连锁问题，因此需 要研究具有能够识别构造块的连锁学习算法，有效地求解实际应用中的问题； 一旷 本文从概率分布模型的角度研究连锁学习问题，探讨一类新型的概率分 析进化算法( p m e a ) 的原理、模型和算法：着重研究具有快速、精确和可靠 特性的“胜任”概率分析进化算法。 本文首先分析了g a 的模式定理，讨论了因为重组算子而导致模式定理存 在的缺陷：针对g a 难的欺骗问题进行了实验，验证了g a 算法不具备识别高 阶构造块的结论；文中还就构造块的并置和混合性能进行了理论分析，指出 构造块混合是比构造块并置更为有效的方法：研究也表明，只依靠增加选择 压强和减少交叉概率不能在本质上改善g a 算法的性能，因此必须研究新的机 制。 本文研究了概率分析进化算法的基本理论和方法；从概率理论的观点引 入了不使用交叉算子的模式定理；系统地分析了应用于进化计算的概率模型 和算法：讨论了概率分析进化算法的逼近性质在此基础上将p m e a 算法归纳 为一阶、二阶和高阶这几种类型的算法；并提出了p m e a 的一般框架算法。 本文重点研究了胜任概率分析进化算法，在分析了多种一阶概率分析进 化算法的基础上，提出了一种基于群体的基因学习算法：针对m i m i c 、依赖 树和b m d a 三种二阶概率模型，从图论的角度分析了算法的复杂性，提出了一 种通用的二阶快速p m e a 算法，实现了互信息、最小熵和x 平方统计三种概率 模型下的快速计算。 针对高阶构造块的连锁学习问题，本文对b a y e s 网络进行了深入研究， 从网络评价模型的复杂性讨论了基于b a y e s 网络概率模型的进化计算问题， 提出了采用最小描述长度( m d l ) 模型的b a y e s 网络进化算法；本文还从学习 网络结构的角度讨论了基于b a y e s 网络的快速计算问题，提出了一种快速计 算的b a y e s 进化算法，并结合爬山搜索技术算法实现了这种算法。文中结合 g a 难的a d f 测试函数对所提出的算法进行了性能评价，结果表明这些算法具 有胜任算法要求的快速、精确和可靠的性能。 基因表达遗传算法是将生物内部信息流模仿成关系搜索理论的进化算 法，本文结合基因表达遗传算法研究了进行连锁学习的另一类进化算法；分 析了这种算法不能明确地引导关系搜索的原因，在此基础上提出了一种模拟 退火基因表达遗传算法：对图划分和多约束背包n p 难问题的测试结果表明， 本文提出的算法求解这些n p 难问题比较其它几种有代表性的算法具有更好 的性能，体现了胜任算法的特点。广、7 一 关键词：进化计算；概率模型；遗传算法；j b a y e s 网络 a b s t r a c t e v o l u t i o n a r yc o m p u t a t i o nu s e sc o m p u t a t i o n a lm o d e l so fe v o l u t i o n a r yp r o c e s s e sa sk e ye l e m e n t si nt h ed e s i g na n di m p l e m e n t a t i o no f c o m p u t e r - b a s e dp r o b l e ms o l v i n gs y s t e m s t h e r ea r eav a r i e t yo fe v o l u t i o n a r yc o m p u t a t i o n a lm o d e l s t h a th a v eb e e np r o p o s e da n ds t u d i e d ，a l lo fw h i c ha r er e f e r r e dt oa se v o l u t i o n a r y a l g o r i t h m s e v o l u t i o n a r ya l g o r i t h m ss h a r eac o m m o nb e h a v i o ro fs i m u l a t i n gt h e e v o l u t i o no fi n d i v i d u a ls t r u c t u r ev i ap r o c e s s e so fs e l e c t i o na n dr e c o m b i n a t i o n t h em a i n p u r p o s eo fe v o l u t i o n a r yc o m p u t a t i o ni sr e s e a r c ho nt h ec o m p e t e n ta l g o r i t h m st os o l v et h ep r a c t i c a la p p l i c a t i o np r o b l e m sq u i c k l y , a c c u r a t e l ya n dr e l i a b l y e v o l u t i o n a r yc o m p u t a t i o nn o to n l ya t t r a c t st h er e s e a r c h e r s i n t e r e s ti ni t st h e o r y , m e t h o d sa n de x p e r i m e n t s ，b u ta l s op l a y sa ni n c r e a s i n gi m p o r t a n tr o l ei no p t i m i z a - t i o n ，m a c h i n el e a r n i n g ，i n f o r m a t i o nm i n i n ga n dp a r a l l e lp r o c e s s i n g a l lo ft h e s e r e s e a r c ha n da p p l i c a t i o ni n e v o l u t i o n a r yc o m p u t a t i o nh a v el a i dt h et h e o r e t i c a l f o u n d a t i o na n d e x p l o r e d aw i d e a p p l i c a t i o n a r e a g e n e t i ca l g o r i t h m s ( g a ) ，d e v e l o p e d b yh o l l a n d ，a r ca c l a s so f a l g o r i t h m s o fv e r yp o p u l a re v o l u t i o n a r ya l g o r i t h m s m o s to ft h e o r yo fg e n e t i ca l g o r i t h m s d e a l sw i t ht h es c h e m at h e o r e ma n dt h es o - c a l l e db u i l d i n gb l o c kh y p o t h e s i s b u t t h er e c o m b i n a t i o no p e r a t o r si ng ao f t e nd i s r u p tt h eb u i l d i n gb l o c k sa n dr e s u l ti n p r e m a t u r ec o n v e r g e n c et o t h e l o w q u a l i t y s o l u t i o n t h ep r o b l e mo fb u i l d i n g b l o c k sd i s r u p t i o ni so f t e nr e f e r r e dt o 弱t h e l i n k a g ep r o b l e m aa l g o r i t h mw h i c h c a l li d e n t i f yb u i l d i n gb l o c k si sc a l l e dt h el i n k a g el e a r n i n ga l g o r i t h m t h e r ea r e m a n yp r a c t i c a ll i n k a g ep r o b l e m s i ti sav e r yi m p o r t a n tt a s kt or e s e a r c ha n dd e v e l o p t h el i n k a g el e a r n i n ga l g o r i t h m st os o l v et h e p r o b l e m se f f i c i e n t l y t h i sd i s s e r t a t i o ns t u d i e st h el i n k a g el e a r n i n gp r o b l e m sb a s e do nt h ep r i n c i p l e o ft h ep r o b a b i l i t yt h e o r y ac l a s so fp r o b a b i l i s t i cm o d e l i n ge v o l u t i o n a r ya l g o - r i t h m s ( p m e a ) a r ee x p l o r e da n d t h e i rp r i n c i p l e s ，m o d e l sa n d a l g o r i t h m sa r es t u d - i e d t h ed i s s e r t a t i o ni s e m p h a s i s o nq u i c k , a c c u r a t ea n dr e l i a b l e c o m p e t e n t p m e a f i r s t l y , t h ea n a l y s i st ot h es c h e m at h e o r e mo fg ai sp e r f o r m e da n ds o m e ， f a i l u r eo f t h et h e o r e ma r ed i s c u s s e db ya n a l y s i st h eo p e r a t o r so f t h er e c o m b i n a t i o n t h ed i s s e r t a t i o np e r f o r m sa n a l y s i sa n de x p e r i m e n t so nas i m p l eg ac o n s i s t i n go f u n i f o r mc r o s s o v e ra n do n e p o i n tc r o s s o v e rb yf o c u s i n go ng a - h a r dd e c e p t i v e p r o b l e m s a se x p e c t e d ，t h er e s u l t ss h o wt h a tg a c a n n o ti d e n t i f yt h eh i g ho r d e r b u i l d i n gb l o c kp r o b l e m s a l s o ，t h ep r o b l e m f o rm i x i n ga n dj u x t a p o s i n go fb u i l d i n gb l o c k si sa n a l y z e d t h es t u d ys u g g e s t st h a ts i m p l es e l e c t i o na n d c r o s s o v e rr e 。 q u i r et h eh e l po f a d d i t i o n a lo p e r a t o r s i ff a s t ，e f f i c i e n tp r o c e s s i n gi sd e s i r e d t h i sd i s s e r t a t i o np e r f o r m sa n a l y s i so nt h et h e o r ya n dm o d e l so np r o b a b i l i s t i c m o d e l i n ge v o l u t i o n a r ya l g o r i t h m s as c h e m at h e o r e mf o rt h ea l g o r i t h m sr e m o v i n gt h eo p e r a t o ro f c r o s s o v e ri si n t r o d u c e db a s e do np r o b a b i l i t yt h e o r y t h ep r i m a r yp r o b a b i l i s t i em o d e l sa n da l g o r i t h m so fp m e a a r ee x a m i n e da n ds u r r u - f l a n z e d b a s e do f t h e s e ，t h ep r o b a b i l i s t i cm o d e l i n ge v o l u t i o n a r ya l g o r i t h m sa r ec l a s - s i f t e da sf i r s to r d e r s e c o n do r d e ra n dh i g ho r d e ra l g o r i t h m s e a c ho f t h e s ec l a s s e s i sa n a l y z e di nd e t a i l ac o n c e p tf r a m eo np m e a i sc o n s t r u c t e d t h ed i s s e r t a t i o ng i v e se m p h a s i so ns t u d y i n ga n dd e v e l o p i n gt h ec o m p e t e n t p m e a a l g o r i t h m s b a s e do na n a l y s i so f t h ef i r s to r d e rp m e a ，a p o p u l a t i o nb a s e d g e n el e a r n i n g ( p b g l ) a l g o r i t h mi sp r o p o s e d f o rt h es e c o n do r d e rp m e a ，t h e p r o b a b i l i s t i e m o d e l so fm i m i c ，d e p e n d e n c yt r e ea n db m d aa l g o r i t h m sa r e e x a m i n e d ，a n dag e n e r a lf a s ta l g o r i t h mf o rs e c o n do r d e rp m e a i sp r o p o s e d a n d t h ef a s ta l g o r i t h m sb a s e do nt h ep r o b a b i l i s t i cm o d e l so ft h em u t u a li n f o r m a t i o n ， t h el o w e s tu n c o n d i t i o n a l e n t r o p ya n d t h ec h i - s q u a r es t a t i s t i c sa r er e a l i z e d f o r h i g ho r d e rb u i l d i n gb l o c k sl e a r n i n gp r o b l e m s ，b a y e s i a n n e t w o r km o d e li s s t u d l e di nt h ed i s s e r t a t i o n t h es c o r em e t r i co ft h en e t w o r km o d e l si sd i s c u s s e d a n dab a y e s i a nn e t w o r ke v o l u t i o n a r ya l g o r i t h mb a s e do nt h em i n i m u md e s c r i p - t i o nl e n g t h ( m d l ) s c o r em e t r i ci sp r o p o s e d a l s o ，ag e n e r a lq u i c kp m e a i sp r o - p o s e df o rl e a r n i n gt h en e t w o r ks t r u c t u r e s aa l g o r i t h mc o m b i n i n gw i t hc l i m b i n g h i l ls e a r c ha n db a y e s i a nn e t w o r k m o d e li sr e a l i z e da c c o r d i n gt ot h eq u i c ka l g o r i t h m a l lo ft h e s ep r o p o s e da l g o r i t h m sa r et e s t e du s i n go a h a r da d f f u n c t i o n sa n dt h e i rp e r f o r m a n c ea r ee v a l u a t e d t h er e s u l t ss h o wt h a tt h e s ea l g o r i t h m s a r ea b l et os o l v et h ep r o b l e m sq u i c k l y , a c c u r a t e l ya n dr e l i a b l y , p r o v i d e dw i t ht h e 2 o r d e ro f t h e p r o b l e m s n o th i 【9 1 1 e rt h a nt h eo n eo f t h e a l g o r i t h m s t h ed i s s e r t a t i o np e r f o r m st h ea n a l y s i st os o - c a l l e dg e n ee x p r e s s i o ng e n e t i c a l g o r i t h m s ( g e g a ) w h i c h a r ea n o t h e rc l a s so fe v o l u t i o n a r ya l g o r i t h m sa t t e m p t i n gt os o l v et h el i n k a g ep r o b l e m g e g aa l g o r i t h m ss i m u l a t et h ep r o c e s so f t h e i n f o r m a t i o nf l o wo f t h ei n t r a c e l l u l a ri nt h en a t u r a le v o l u t i o n ，a n dm a pi ti n t or e l a t i o ns e a r c hp r o b l e m b u tt h i sc l a s so fa l g o r i t h m s c a n n o ti d e n t i f yt h ed e p e n d e n c e b e t w e e nt h eg e n e si na ni n d i v i d u a lb e c a u s et h e r ei sn od e f i n i t eg u i d ef o rs e a r c h i n g t h eg o o dr e l a t i o n t oi m p r o v et h eq u a l i t yo fg e g a ，as i m u l a t e da n n e a l i n gg e n e e x p r e s s i o ng e n e t i ca l g o r i t h mi sp r o p o s e d t w oe x p e r i m e n t a lc a s ew i t ht h eg r a p h p a r t i t i o na n d m u l t i - c o n s t r a i n t sk n a p s a c kn p - h a r dp r o b l e m sa r et e s t e du s i n gs e v - e r a le v o l u t i o n a r ya l g o r i t h m s t h er e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h mh a s b e s tp e r f o r m a n c ea m o n gt h e s ea l g o r i t h m s k e y w o r d s ：e v o l u t i o n a r yc o m p u t a t i o n ；p r o b a b i l i s t i cm o d e l g e n e t i ca l g o r i t h m ；b a y e s i a nn e t w o r k 3 第一章绪论 第一章绪论 早在2 0 世纪5 0 年代，分析自然进化过程进化算法便作为优化手段提出来。 关于进化算法所研究的内容我们可以用b r e m e r m a n n 。”1 的杰出论文中的一段话给 予描述：“该项工作的主要目的是研究基因型进化过程中，变异、配对和选择等行 为在线性适应函数中的效果。由于涉及的数学理论十分困难，引入了和理论分析 结合的计算机实验手段。在一系列新的实验中，我们发现了逼近非常好的进化模 型，但不知道这些方案在生物界是否同样有效”。本文开篇引用b r e m e r m a n n 的 论述作为对进化算法的解释，原因是要理解进化算法研究方法的内涵。进化算法 研究者应该由自然启示获取灵感，但不只是简单地复制自然中的某些现象，其目的 是要研究有效的方法求解现实中的优化难题。这种研究应该是自然启示、计算机 实验手段和数学理论的有效结合，以达到分析求解优化问题的目的。本文研究概 率分析进化算法实质上是将基于自然的传统进化算法、强有力的计算机实验方法 和概率理论结合的进化算法。 本章简要介绍进化算法的概念，着重介绍概率分析进化算法研究背景和发展 概况，在此基础上引入本文所做工作。 1 1 进化计算和进化算法概念 进化计算( e v o l u t i o n a r yc o m p u t a t i o n ，简称e c ) 是一种基于群体构造和模 拟生物进化操作的一类随机搜索计算。e c 以进化过程中的计算模型为核心，设计 和实现基于计算机的问题求解系统。e c 中的计算模型通常称为进化算法 ( e v o l u t i o n a r ya l g o r i t h m s ，简称为e a ) 。进化算法的研究起源至少可以追朔到 2 0 世纪5 0 年代“，最具代表性的e a 主要有进化规划( e v o l u t i o n a r y p r o g r a m m i n g ，简称e p ) 、进化策略( e v o l u t i o n a r ys t r a t e g y ，简称e s ) 和遗传 算法( g e n e t i ca l g o r i t h m ，简称g a ) 。进化规划首先由l j f o g e l 等人提出”1 ， d b f o g e l 对之进行了完善。1 ；进化策略首先由r e c h e n b e r g 提出卿，s c h w e f e l 在其基础上提出更一般的( ，u ) 和( + u ) 模型啊1 ；g a 则由h o l l a n d 提出”， g o l d b e r g ，d j o n g 等人又进行了改进“。这三种进化算法的共同特点是通过选择 ( 确定或随机的) 和重组( 变异( m u t a t i o n ) 或交叉( c r o s s o v e r ) ) 等操作，模 拟由个体组成的群体的进化过程，使群体一代一代地进化，逼近搜索空间中的最 湖南大学控制理论与控制工样博士学位论文 优解。它们的不同点主要表现在进化操作的原则，e p 和e s 把变异作为主要的进 化操作：g a 则是强调交叉的作用，变异只是它的次要功能。另一方面，e p 和e s 的选择是确定的，而g a 一般则是采用随机选择。借用生物学的术语，e s 利用变 异和选择分析自然进化，属于一类无性繁魑算法：g a 的思想则主要是利用重组双 亲的基因生成后代，属于有性繁殖算法。在e s 中，交叉和自适应变异结合具有重 要作用。 进化计算不仅在基础理论、基本方法和手段上得到研究学者的重视，如国际上 权威刊物的“e v o l u t i o n a r yc o m p u t a t i o n ”，”i e e e t r a n s o r l e v o l u t i o n a r y c o m p u t a t i o i l ”的设立；每年一次的“国际进化计算会议”即i c e c 的举办等。而且 在最优化机器学习和并行处理等许多领域得到广泛应用。国内在进化计算领域 也做了许多理论和应用方面的工作“”“，这些理论研究和应用工作为进化计算奠 定了良好的理论基础，开辟了广阔的应用前景。 另一方面，我们也看到前述三类进化算法( 不包含( ，“) - e s ) 的全局收 敛( 以概率1 ) 性质尽管在文献上都有证明“，但这些证明一般都是在算法上 加以许多约束条件简化而得到的，而且前提都是采用保留最优个体( e l i t i s m ：即 一旦找到一个最优解，这个解就不会丢失。) 的选择机制。而关于进化算法中变 异和交叉的作用，以及随机和确定选择机制的利弊，更是引起了不同学派间的许 多争论r ”2 ”“1 然而这些争论的依据主要是基于不完备的实验结果，缺少令人 信服的理论证明，而在理论上进行这种证明又不是一件容易的事情。因此，一些 学者选择了设计新的更具有理论依据的进化算法的研究路线。结合本文的研究内 容，下面将详细介绍这方面的研究进展。 1 2 概率分析进壬的i 法研究现状 近年来，一些研究者从统计学的观点出发，将构造性模型引入进化算法的研 究，形成一类基于概率分析的进化算法。这类算法最早被称为分布评价算法 ( 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 m e a ( p r o b a b i l i s t i cn o d e l i n ge v o l u t i o n a r y a l g o r i t h m s ) 。p f 2 d a 算法在许多方面表现了很好的性能，因此引起许多研究人员 的研究兴趣，第一次关于这类算法的专题国际会议已于今年在美国召开，这也说 明p m 队在进化计算领域中开辟了新的研究方向。 2 第一章绪论 由h o l l a n d 首先提出的基本遗传算法( g a ) ，是基于自然选择、交叉、变异和 重组等操作构成的一种优化方法。g a 和e s 都是在七十年代独立地提出的两种不 同进化算法，r e c h e n b e r g 主要研究很小群体中变异算子在连续参数优化中的作 用；而h o l l a n d 则利用g a 研究离散领域的决策理论，强调的是大群体中交叉算子 的重要性。g a 的基本理论依据是模式定理和“构造块”( b u i l d i n gb l o c k ) 假设 理论”。”，构造块指的是群体中高于平均适应度、低阶、短距离的模式，也就是构 成问题解的基本部分。模式定理预测在采用比例选择机制下，通过交叉和变异算 子的作用，可以再生和混合更多好的构造块，最后逼近解。然而，交叉和变异算 子不仅具有建立构造块的功能，也存在损坏构造块的问题，这就是常说的没有免 费午餐定理* 。本质上，g a 缺少足够的进化导向作用，而且模式定理也缺少评价 其生成好解的概率理论。实际的重组操作常造成构造块破坏，导致算法容易逼近 局部最优或者早熟。构造块破坏问题一般称为连锁( 1 i n k a g e ) 问题9 1 ，具有识别 构造块的算法称为连锁学习( 1 i n k a g el e a r n i n g ) 算法。 实际应用中也普遍存在连锁问题，如背包问题，图划分问题，计算机网络的 路由等问题。因此需要研究具有能识别构造块的连锁学习算法，有效地求解上述 具有普遍意义的连锁问题。然而这是一个具有挑战性的难题不少研究者指出 ”1 ”1 ，如果可以研制有效的连锁学习算法，将会在进化算法的研究上取得重大 进展。因此研究有效的连锁学习算法一直是人们关注的研究课题”“。针对 g a 存在的连锁问题，文献提出了许多改进重组算子的方法“，目前代表性的研 究方法主要有两类：一类方法是改变算法中解的表示，通过基因级而不是染色体 一级的重组操作改善连锁问题“：最近的一些研究表明“，此类算法具有的连 锁学习能力不足以解决复杂的优化问题：另一类方法则是改变重组操作的基本原 理，即从当前群体中选取部分有前途的优选解作为产生新解的依据，利用概率分 布模型分析这些解，在此基础上通过概率分布构造新的群体，最后逼近最优解 c a - 4 , 6 , ”11 9 - a t i 。本文着重研究后一种方法，我们称利用这种方法产生的算法为概率 分析进化算法。本文也将研究前一种方法和模拟退火算法的结合问题，讨论这些 算法求解n p 难问题的性能。 1 2 1 一阶概率分析进化算法 为了克服g a 因交叉重组导致的连锁问题，人们提出是否可以不使用重组操作 。- ”，而是通过从优选的解集合中提取信息，然后利用这种信息的分布概率产生新 湖南大学控制理论与控制工程博士学位论文 的解，由此实现算法的连锁学习。这种将构造性概率模型引入进化算法的思想形 成概率分析进化算法的理论依据。 p m e a 算法的概念最早可以追溯到a c k l e y 于1 9 8 7 年提出的一个学习算法， 在此算法中他引入了一个具有重要意义的数据结构即基因向量，通过来自群体的 萨负反馈信息操作此向量。文中有一个直观的比拟，即把长度为l 的基因向量比 作由l 个成员组成的政府，群体数据比作选民的投票结果，依据此结果评判群体 ( 选民) 对向量( 政府) 的满意程度。这一算法的意义是首次应用了群体中基因 的概率分布分析和评价解的质量。 s y s w e r d a 在文献。中提出了“基于基因位的模拟交叉”( b i t b a s e d s i m u l a t e dc r o s s ，简称b s c ) 操作来产生新群体的思想。b s c 操作利用群体级的 统计方法替代g a 的交叉重组，其基本思想描述如下：对于当前群体，统计染色体 中第i 个基因位为l 的个体数量；同样也统计第i 个基因位为0 的个体数量。对 这些数据和适应度函数值加权统计，作为产生后代的依据，即按照统计值概率分 配新个体的基因位值为l 或0 。b s c 实际上把g a 的选择和交叉结合成一个操作， 其创新意义是利用样点边缘概率分布计算取代g a 的重组操作来产生新的群体。 b a l u j a “巧妙地结合上述两者的思想，构思了利用一个概率向量表示群体的 染色体，并用它记录群体在结构中每一基因位置为“l ”或为0 的比例，初始 概率向量的每一位值为0 5 ( 表示该基因位为0 和1 的概率均等) ，通过搜索过程 逐步朝向0 或1 逼近。并利用此向量产生新的个体，再依据这些新个体的适应度 值修改概率向量，使之最后逼近最优解。这种称为“基于群体的增量学习” ( p o p u l a r i o n b a s e di n c r e a s e dl e a r n i n g ，简称p b i l ) 的算法，尽管此文并没 有进行理论分析，但本质上是利用了概率分布模型生成新的群体，而且在选择机 制上也利用了人工育种的方法，因此一般被认为是概率分析进化算法的原型，它 对p m e a 的研究和发展具有重要意义。 p b i l 算法给人的另一个启发是可以用一个概率向量压缩群体规模。若染色体 长度l ，群体规模为n ，则g a 存储群体的空间为n * l 位，而用概率向量表示群体 时，存储量只需l * l o g ：n 位，明显地节省了存储空间根据这一思想，h a r i k 叫 等人提出了压缩遗传算法( c o m p a c tg e n e t i ca l g o r i t h m ，简称c g a ) 的概念。 文献2 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 ) ，则是基于对群体进行处理的算法。在每一代迭代时，算 法首先用块选择1 ( b l o c ks e l e c t i o n ，也称切断选择) 机制从当前群体选择若干 ( 如5 0 ) 最好的解，算法对染色体的每一基因位统计优选出的群体子集中个体 第一章绪论 的数目( 边缘概率分布) ，然后利用这些统计值生成新的解，并替换群体中原来的 解。如此反复，直到满足终止条件。对u m d a 算法的理论分析很好地吻合其实验结 果和p b i l 算法一样，u m d a 实际上也是采用了人工育种的选择机制。 以p b i l 为代表的上述算法，实际上是通过人工育种的选择机制抽取优选解的 整体信息，然后评价它们的分布，再利用这种分布产生新的群体。但这种评价的 前提是假定变量( 基因) 间相互独立。因此，它们在求解线性问题( 如o n e m a x 问题) 或一阶构造块问题时，具有和g a 相当甚至更好的性能“2 “，且易于实现。 但对于变量间具有相互影响( 一种连锁关系) 的高阶构造块问题，这些算法由于 不具备连锁学习的功能，求解效果较差。基于这些原因，本文将其归纳为一阶概 率分析进化算法。由于一阶p m e a 不能处理连锁问题，因此需要寻找更好的分布评 价方法达到连锁学习的目的。 1 2 2 二阶概率分析进化算法 p m e a 算法中的一个重要的问题是连锁学习即如何识别和混合高阶的构造块， 这一问题引出跚卧中建立分布和学习分布的两个基本问题。首先研究并提出高阶 连锁学习的p m e a 算法是称为“相互信息最大输入聚合”的算法( m u t u a l i n f o r m a t i o nm 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 算法) ”1 。和m i m i c 类似的另一个基于双变量边缘分布的p m e a 算法是用树结构表示分布的算法”1 ；这 种称为相关树( d e p e n d e n c yt r e e ) 的结构使得树中父子结点的相关信息最大。树 中根结点的值首先利用单变量边缘分布产生，树中其他的叶结点的值则依据其父 结点的条件概率产生。事实上，链是一种特殊的树，因此比较m i m i c 的链式分布， 树型结构分布的精确度更高二次边缘分布算法( b i v a r i a t em a r g i n a l d i s t r i b u t i o na l g o r i t h m ，简称b m d a ) 。1 采用森林结构表示分布，为了确定变量 ( 结点) 的连接，算法采用计算双变量边缘分布的p e a r s o n 汹1j - 平方统计计算方 法，这种计算方法也用于辩识其余变量的相关关系算法采用最大生成树类似的搜 索算法构造并搜索最后的模型。由于链，树都属于森林的特殊情况，b m d a 具有更 一般的意义和更好的精确度。 上述三个算法都涉及到两个以上变量的相关性，这些算法本质上是通过不同 的方法计算染色体中两两基因间的边缘分布，构造和搜索最好的相关图，然后利 用这种图生成新的解本文因此将其归纳为二阶概率分析进化算法。这些算法具 有低阶构造块的连锁学习功能，可以有效地再生和混合二阶构造块，因此在求解 湖南人学控制理论与控制工程 尊七学位论文 线性和二次问题时具有很好的性能，但其实现上比一阶p m e a 引入了更多的计算。 1 2 3 高阶概率分析进化算法 从耵面的讨论我们知道p m e a 的关键在于选择好评价分布和学习分布产生新 的后代。如果用图表示分布模型，我们发现，一阶p m e a 是一个边集为0 的图：而 二阶p m e a 则对应有向链，有向树和有向森林，它们的共同特点是结点( 变量) 的 入度不超过l 。自然地，人们想到可以用更为复杂的图结构来表示多变量间的相 关性，以求解高阶问题。b a y e s 优化算法。”( b a y e sj a no p t i m a la l g o r i t h m ，简称 b o a ) 便是在这种背景下产生的p m e a 算法。下面简要介绍b o a 算法。 b a y e s 网络是一无环有向图，它即可以对所给的数据进行描述，又可以产生 与所给定数据性质相同的数据，因此常用于对离散或连续变量的多项式数据建模 d2 - i ：l 1 利用b a y e s 网络求解问题的关键在于学 - 3 网络，学习网络指的是找到一个 网络，使之在约定的评价标准下，最好地匹配现有训练数据集“。网络的评价标 准浣明网络所分析的数据的好坏程度，也就是对网络质量的评价；搜索过程则是 要寻找具有最高评价标准值的网络。 b o a 算法利用b d 评价标准“。”1 和贪婪算法建立和搜索网络研究表明 2 2 4 - 2 5 , 2 7 b o a 算法求解许多测试函数，包含高阶构造快问题都得到了很好的优化结 果，但算法的复杂程度也随之增加。由于b a y e s 网络的应用特点，近年来相关理论 和应用研究很多“”，因此与b o a 算法相关的研究领域会更宽。 扩展压缩遗传算法( e x t e n d e dc o m p a c t e da l g o r i t h m ，简称为e c g a ) “”，是另一 种支持多变量相关的高阶概率分析进化算法和b o a 不同，e c g a 的基本思想是将 多个变量按照某种评价尺度聚合( c l u s t e r i n g ) ，作为单个变量对待，然后类似前述 的u m d a 算法进行计算为了区别好的聚合( 本质上是寻找构造块) ，e c g a 利用“最 小描述长度”( m i n i m u md e s c r i p t i o nm o d e l ，简称为m d l ) 啪1 的评价模型分析样点， 并采用贪婪算法搜索最好的模型m d l 是偏向高压缩率数据的数据分析模型，因此 具有计算简单的优点e c g a 的特点是把多变量相关关系转化成单变量边缘分布计 算问题，对于一些可分离计算的高阶问题，其求解性能很好，且易于实现但对于 现实中许多构造块重叠的问题，e c g a 难以搜索到个好的模型，因