（计算数学专业论文）基于进化规划的分布估计算法.pdf

硕士论文基于进化规划的分布估计算法 摘要 进化规划是一种随机优化方法，它是通过进化达到行为智能化。进化规划算法从 一组随机产生的个体开始进行搜索，通过变异、选择等操作使个体向着搜索空间中越 来越靠近全局最优值的区域进化。但是进化规划算法很容易早熟收敛，因此，避免早熟 收敛，均衡算法的探索和执行能力，已成为进化规划研究的主要内容之一。分布估计 算法通过将统计学习理论与进化算法结合，形成一种全新的进化模式，是进化计算领 域的研究热点。 本文所做的主要工作有对分布估计算法和进化规划进行了的相关知识进行概括 总结，弄清分布估计算法和进化规划的主要思想、步骤、收敛性和算法的优缺点。在 此基础上提出了新算法，基于进化规划的分布估计算法，分布估计算法可以利用进化 规划在进化过程中产生的种群进行概率分布估计来预测最优个体，为进化规划提供搜 索方向，加快其收敛。然后证明了新算法的收敛性，最后通过将新算法应用到函数优 化问题中对算法的性能进行检验，本文选择了8 个标准测试函数测试算法求解不同类 型问题的能力。 关键词：进化规划，分布估计算法，基于进化规划的分布估计算法，收敛性 硕士论文 a b s t r a c t e v o l u t i o n a r yp r o g r a m m i n gi s ak i n d o fs t o c h a s t i co p t i m i z a t i o na l g o r i t h m e p a l g o r i t h m sa r eb a s e do na na r b i t r a r i l yi n i t i a l i z e dp o p u l a t i o no fs e a r c hp o i n t sw h i c he v o l v e s t o w a r d sb e t t e ra n db e t t e rr e g i o n si nt h es e a r c hs p a c eb ym e a n so fr a n d o m i z e dp r o c e s so f m u t a t i o na n ds e l e c t i o n p r e m a t u r ec o n v e r g e n c ei sa l s oab i gp r o b l e mo fe v o l u t i o n a r y p r o g r a m m i n g s oa v o i d i n gp r e m a t u r ec o n v e r g e n c ea n db a l a n c i n gt h ea b i l i t yo fe x p l o r a t i o n a n de x p l o i t a t i o nh a sb e c o m eo n eo ft h ei m p o r t a n ta s p e c t so fe p ss t u d y 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 mi san e wc l a s so fe v o l u t i o n a r ya l g o r i t h m s ，w h i c hc o m b i n e st h es t a t i s t i c t h e o r yw i t l le v o l u t i o n a r ys c h e m e s t h em a j o rw o r k si nt h i sp a p e ra r e ：t h i sp a p e rp r e s e n t sab r i e fo v e r v i e wo fe v o l u t i o n a r y p r o g r a m m i n ga n de 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 ，a n dc l e a r st h em a i ni d e a s ，p l a n n i n g ， c o n v e r g e n c ea n dt h ea d v a n t a g e sa n dd i s a d v a n t a g e so fe v o l u t i o n a r yp r o g r a m m i n ga n d 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 b a s e do nt h i s ，a d v a n c e san e w a l g o r i t h m ，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 sb a s e de v o l u t i o n a r yp r o g r a m m i n g ，e d ac a nu s et h ee pi n t h e e v o l u t i o n a r yp r o c e s so fp o p u l a t i o n sw e r ee s t i m a t e dp r o b a b i l i t yd i s t r i b u t i o nt op r e d i c tt h e o p t i m a li n d i v i d u a l s ，p r o v i d et h es e a r c hd i r e c t i o nf o rt h ee p , a c c e l e r a t et h ec o n v e r g e n c e t h e n i t sc o n v e r g e n c ei sp r o v e d f i n a l l yw eu s et h en e w a l g o r i t h mt os o l v eo p t i m i z a t i o np r o b l e m s ， a n de i g h tb e n c h m a r k sa r ec h o s e ni no u re x p e r i m e n t s k e yw o r d ：e v o l u t i o n a r yp r o g r a m m i n g ，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 ，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 sb a s e de v o l u t i o n a r yp r o g r a m m i n g ，c o n v e r g e n c e 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本学 位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或公布 过的研究成果，也不包含我为获得任何教育机构的学位或学历而使用过的 材料。与我一同工作的同事对本学位论文做出的贡献均已在论文中作了明 确的说明。 研究生签名：圭丑丑 砂口年莎月2 多日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或上 网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并授权 其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密论文， 按保密的有关规定和程序处理。 研究生签名：翻丑 j l d 扣年6 月2 弓日 硕士论文基于进化规划的分布估计算法 1 绪论 1 1 研究背景 随着计算机技术的飞速发展，计算机渗透到社会生活的各个领域中，人类步入了一 个科学技术迅猛发展的时代。计算机科学与其他学科的交叉产生了许多新的学科，推动 着科学技术向更广阔的领域发展，对人类社会产生了深远的影响。而现实中的许多问题 都可以归结为求解优化问题，因此优化方法受到广泛关注，从经典的求解方法发展到智 能的方法，已经解决了大量的问题，特别是进化算法的研究与发展更是开启了优化方法 的新领域，进化计算主要由遗传算法、进化策略和进化规划等组成。尽管这三类算法之 间很相似，但在历史上，它们是彼此独立发展起来的。再从遗传算法到分布估计算法， 将概率模型和概率分布理论引入进化算法，进一步推动了优化方法的发展。 在二十世纪四五十年代，为了提出更好的解决优化问题的方法，一些具有创新精神 的科学家独立开始了模拟生物进化机制的研究。但是在之后的三十年内，这些研究并未 被人们知道。这在很大程度上是因为当时缺乏足够强大的计算机平台，也与当时的理论 存在逻辑方法上的缺陷有关 1 1 。直到二十世纪七十年代，h o l l a n d ，r e c h e n b e r g ，s c h w e f e l 和f o g e l 等人所做的工作改变了这一状况【2 】。在随后的几十年中，在达尔文生物进化思 想和后达尔文主义进化思想的启迪下，以遗传算法、进化策略、进化规划等为代表的启 发式随机搜索算法，在理论和应用两个方面都取得了长足的发展。进化计算作为一个新 兴的交叉学科，逐渐成为人工智能领域的一个重要分支，相关的学术会议和出版物的数 量不断增长，与此相关的一个科学领域诞生了。 根据不断研究和应用清楚的表明，模拟自然进化的搜索方法可以产生非常鲁棒的计 算机算法。进化计算就是基于这种思想发展起来的一类随机搜索计算方法。随着科学技 术的迅速发展，工程技术、社会经济以及科学计算领域中出现了越来越多的复杂性计算 问题，这些问题表现出高度非线性、不可导、不连续等特性，复杂度相当之高，使得传 统的优化算法在这些问题面前显得比较苍白无力。而进化计算的出现为解决这类问题开 辟了一条崭新的途径。 1 2 进化规划算法和分布估计算法的发展历程 1 2 1 进化规划算法的发展历程 进化规划是进化计算的一个分支，是一种随机优化方法，是由美国的l j f o g e l 等 在二十世纪六十年代提出的。进化规划是通过进化达到行为智能化。l j f o g e l 在有限 状态机的研究中发现，早期的神经网络方法和启发式算法无法满足系统不断提高性能的 i 绪论 硕士论文 要求，他希望通过系统的自适应机制来达到这一要求，l j f o g e l 等借用进化的思想对 一群有限态自动机进行进化以获得较好的有限态自动机，他们将此方法应用到数据诊 断、模式识别和分类以及控制系统的设计等问题之中，并取得了较好的效果。1 9 6 6 年 l j f o g e l 、o w e n s 和w a l s h 合著了基于模拟进化的人工智能一书。该书系统地阐述 了进化规划的基本思想，在进化规划的发展过程中具有重要的意义。f o g e l 提出的方法 与遗传算法有许多相同之处，但不像遗传算法那样注重父代与子代在基因及其遗传操作 上的联系，而是把侧重点放在父代与子代表现行为的联系上。在最初的发展中，进化规 划并没有得到足够的重视。直n - 十世纪九十年代，d b f o g e l 将进化规划思想拓展到 实数空间，使其能够用来求解实数空间中的优化计算问题，并在变异运算中引入正态分 布技术，从而使进化规划成为一种优化搜索算法，并作为进化计算的一个分支在实际领 域中得到了广泛的应用。进化规划可应用于求解组合优化问题和复杂的非线性优化问 题，它只要求所求问题是可计算的，使用范围比较广。d b f o g e l 使用进化规划解决旅 行商问题( t s p 问题) 【3 1 ，改善了求解性能；他将进化规划应用于实数空间的连续参数 优化问题领域，扩大了进化规划的适用范围，增强了进化规划的影响力。在此期间，进 化规划不断扩展其应用领域，取得了相当丰富的成果。进化规划作为进化中的学习算法， 提高了优化方法的性能；进化规划中的自适应机制，不但提高了其自身的性能，而且被 广泛应用于进化计算的各个方向。1 9 9 2 年，第一届进化规划会议在美国举办，该会议每 年举办一届，迅速吸引了各行业如学术、商业和军事等的大批研究人员和工程技术人员。 后来b a c k 和s c h w e f e l 提出了带有自适应的进化规划算法，实验表明该算法要优于不 带有自适应的进化规划算法。1 9 9 9 年，姚新等利用柯西分布代替进化规划中的正态分布， 提出了快速进化规划算法。后来，姚新等将l e v y - t y p e 分布应用在进化规划中， m 1 w a n m a t s u 利用l e v y - t y p e 分布代替正态分布，提出了推广进化规划算法。2 0 0 3 年，计 明军提出单点变异进化规划算法，在每次迭代中只对父代的一个分量进行变异，使算法 的精度有了数量级的提高。2 0 0 5 年，董宏斌提出了混合策略进化规划算法，综合了几种 进化规划算法的优点进一步提高了算法的精度这些改进的算法在求解高维以及具有多 个极小全局优化问题具有较好的效果。 1 2 2 分布估计算法的发展历程 遗传算法是一种借鉴生物界自然遗传机制的高度并行和自适应的全局优化随机搜 索算法，具有功能强、鲁棒性好、计算简单、对搜索空间无限等特点。然而，遗传算法 本身还存在一些问题。首先，遗传算法的关键是处理进化过程中的积木块，然而交叉算 2 硕士论文基于进化规划的分布估计算法 子和变异算子不具有学习和识别基因之间连锁关系的能力，所以实际的重组操作经常造 成积木块的破坏，从而导致算法逼近局部最优解或早熟：另外，遗传算法中操作参数的 选择依赖性强，甚至参数选择本身就是一个优化问题；第三，遗传算法的理论基础还比 较薄弱1 4 1 。 为了解决遗传算法的这些问题，更好地解决各种难解优化问题，各种改进遗传算法 不断出现。概率分布估计算法是为了避免传统遗传算法中的基因块的破坏产生的影响而 提出的算法。为了解决遗传算法的这些问题对传统遗传算法有代表性的改进方法是改 变重组操作的基本原理，将遗传算法中基因的交叉和变异操作改进为学习优良解集中种 群的概率分布，其基本思想是从当前种群中选取部分优良解，并利用这些优良解估计和 学习种群的分布模型，然后采样该分布模型产生新的种群。逐次迭代，最后逼近最优解。 基于这种由分布模型改进进化算法的思想形成的一类新型优化算法称为分布估计算法。 分布估计算法最早是由m u h l e n b e i n ，h p a a b 于1 9 9 6 年提出的1 5 1 。作为一类在遗 传算法基础上发展起来的新型进化优化算法，分布估计算法也采用了选择和繁殖的群体 进化策略，但由于利用构建概率图模型和采样概率图模型的进化方法，由优良解集的概 率分布来引导进化搜索的前进方向，避免了传统遗传算法中交叉算子和变异算子带来的 盲目性和随机性，有效地提高了进化搜索效率。在2 0 0 0 年前后分布估计算法迅速发展， 成为当前进化计算领域前沿的研究内容，近年来国际上进化计算领域的各大学术会议都 将分布估计算法作为重要专题予以讨论。 1 3 本文的主要研究内容 本文回顾了进化规划算法的相关知识，概述了研究背景和研究现状，对进化算法的 收敛性进行了介绍，对进化规划算法进行学习研究，分析算法的性能及存在的问题，重 点介绍分布估计算法的研究背景和和基本思想，研究了分布估计算法的收敛性，在分布 估计算法中引入了进化规划算法，并对基于进化规划的分布估计算法进行了理论证明和 数值验证。 论文各个部分的主要内容如下： 第一章绪论。主要介绍了论文研究的背景、研究现状和研究意义。对进化算法产生、 发展、理论基础等进行了介绍，并对进化计算的收敛性研究进行了说明，比较了进化算 法与普通搜索算法的异同，总结了进化算法的特点以及应用现状。另外详细描述了分布 估计算法的背景、研究现状和发展趋势。 第二章进化规划。主要介绍了进化规划算法的基本思想和步骤，研究了进化规划算 法的收敛性，最后介绍了进化规划的特点及其应用和发展前景。 第三章分布估计算法。描述了分布估计算法的基本框架、类别和理论研究，以及有 i 绪论硕士论文 限群体模型下分布估计算法的收敛性。通过在期望分布基础上引入一个误差量，给出有 限规模群体中个体分布的表示方式，然后在三种不同的常用选择策略下对e d a s 的收敛性 进行证明。结果显示在有限群体模型下，在文中所述误差范围内分布估计算法具有良好 的全局收敛性。 第四章基于进化规划的分布估计算法。首先分析了进化规划和分布估计的优缺点， 对新算法的基本思想做出了论述，描述了新算法的基本步骤，并对其做出了理论证明， 最后对基于进化规划的分布估计算法进行了数值验证。 第五章小结。分析了分布估计算法的不足之处，并对分布估计算法算法为未来的发 展可能方向做了一个小结。 4 硕士论文基于进化规划的分布估计算法 2 进化规划 2 1 进化规划算法的构成 进化规划被广泛应用于各种优化问题 m i n f ( x ) i x q c r ” 其中f ( x ) c o n s t ，f ( x ) o ， 坛q 且有有限个极值点引。 用x ( f ) = o ) ，x 2 ( f ) ，j o ) ) 表示e p 的第t 代种群它是一个随机过程，其状态为r 州 中的一个点，状态空间为q n 。本文中r 啪中的点用符号x = x 1x 2 ，j ) ( x r ”，i = l ，2 ，) 表示，称x 为的第i 个分向量。容易看出x ( r ) = x 1 ( ，) ，x 2 0 ) ，j o ) ) 无后效性，是一个过程从第t 步到第t + l 步的操作过程可简单地描述为： x ( ，) 竺屿x 竺型马x o + 1 ) 其中x ( f ) = x 7 1 0 ) ，x 2 0 ) ，( f ) ) - - x + 1 0 ) ，x + 2 ( f ) ，j 2 ( r ) 是变异的结果。竞争 就是在x ( t ) u x 7 0 ) 中按步5 确定新一代种群x ( t + 1 ) 9 1 。 设s ，x er 槲，从s 与x 的并中选取n 个分向量作无重复的排列，可以组成p = 碡个新 向量，用u ( s ，x ) = n ，“娩，u 七) ( k = l ，2 ，e ) 表示之。 令q ( u ( s ，x ) ) = p x ( t + 1 ) = ( u 。( s ，x ) ix ( t ) = x ，x ( ，) = s ) 。q ( u 。( s ，x ) ) 描述了的竞争规 则，完全由竞争规则确定。 定理1 假设g ( u 。( s ，x ) ) ( k = 1 ，2 ，e ) ， = ) 关于( s ，x ) 是区域q n q n 上的连续函数， 且假设a 成立。贝l jx ( t ) 的联合密度函数只( x ) 是区域q n 上的连续函数，并且 m ( 加，鹰占。一叭蹦) ) q ( u 砸，瑚肌，吡 ) d s d x 黼 妒尊岛e 卅窆j 业2 c r ；， ，司洲妁场， 仃f = 仃n 仃f 2 o k ，i - - 1 ，2 ，n ，j = 1 ，2 ，n ，6 ( x ) 是珂维d i r a c 函数。 6 硕士论文基于进化规划的分布估计算法 证明：当t = 。时，p o ( x ) = i 两1 ，j l l ( g ) 表示区域q 的l e b e s g u r e 测度，一( f = 1 ，2 ， ，= 1 ，2 ，n ) 之间相互独立。所以在x ( o ) = 0 条件下，x ( 0 ) 的条件分布密度为： 以d 舢k 。，= 尊冉 _ 荔寿孑e 冲卜；n 兰zi 丢产ix 2 】) = r c s 另外， e p x l x , x ( y ，l l s ，0 ；x ，o ) = 8 ( y - u ( s ，x ) ) q ( u o ，x ) ) 则局o ) = ，办卅z ，i ij ，o ；x , o ) p o ( x ) a x 心砂 = ，窆艿一u ( 蹦) ) q ( u ( 蹦) ) r ( s ，x ) p o ( x ) d r o r 州t l 根据假设a ，可证明q ( u 。( s ，x ) ) r ( s ，x ) p o ( x ) 关于x 一致有界。结合留( 扩( j ，x ) ) 的连续性， 可得a o ) = ， 、 g ( 扩( s ，x ) ) r ( s , x ) p o ( x ) 一：，一；，一；，广d s 口+ 1 d s 出1 d x 4 从 q m 。 而岛 ) 在q 内连续。 当t o 时，同上可证。 定理2 若q ( u 七( s ，x ) ) ( k = 1 ，2 ，e ) 关于( s ，x ) 是( s ，x ) 上的连续函数，那么 x ( t ) i ，= 0 ，1 ，) 是齐次m a r k o v x 立_ 程1 0 1 。 证明：对于任意的t o ，有办l x ( y ，f + 1x , t ) = ，窆6 ( y u ( s ，x ) ) g ( 扩( s ，x ) ) r ( s , x ) d s 在被积函数中r ( s ，x ) ，q ( u ( 以x ) ) 均与t 无关，所以办1 z ( y ，t + l i x ，f ) 与无关，即 x ( t ) if = 0 ，1 ，) 是齐次m a r k o v 过程，证毕。 2 2 1 进化规划的收敛分析 q ( u ( s ，x ) ) 连续意味着适应性差别不大的个体参与竞争时，它们获胜的可能性也差 别不大因而一般来说，当适应性函数连续时，所给竞争规则能保h y _ q ( u ( s ，x ) ) 的连续性 设f ( x ) = m i n f ( x 1 ) ，f ( x 2 ) ，f ( x ) ) ，x q ，g 为包含点集 2 进化规划硕士论文 k = x q if ( x ) = f = m i n f ( y ) ly q ) 中q 区域，其l e b e s g u e 钡l j 度记为j l l ( g ) 定理3 设q ( u ( s ，x ) ) ( k = l ，2 ，e ) ，关于( s ，x ) 是区域q n x f 2 n 上的连续函数， o p ( g ) o ，使得当t t 时， fp , ( x ) d x = 1 。 证明：v 占 0 ，取g = x q i f ( x ) 一f 。l s 贝i jp if ( x ) 一厂l ) ：尸( r ) q 一g ) ： f 只( x ) 出堡型 d g b o 即p l i m f ( x ( t ) ) = f ) = 1 定理5 设q ( u ( s ，x ) ) ( k = 1 ，2 ，e ) ，关于( s ，x ) 是区域q n x t 2 n 上的连续函数，且假设a 成立，则对任意正整数r ，1 i me l 厂( x ( f ) ) 】7 = ( f ) 7 。 证明：根据假设a ，f ( y ) 在q n 上连续，所以有正数m 。使得( 厂( y ) ) 7 一u 。) 7 m ， 又因为，所以v s 0 ，可取g 使得当x g 时，u ( y ) ) 7 一u ) 7 s ， 从而e 【厂( x ( f ) ) 】7 一u ) 7 = f 【厂( x ( f ) ) 】7 一( 厂+ ) 7 p , ( x ) d x 毋 = 卜， ( 厂( 彳) ) 7 - ( f ) 7 协( x ) 出g + m ，只o ) d x 掣- g_ g 结合定理3 即得。 定理6 设q ( u ( j ，x ) ) ( k = l ，2 ，e ) ，关于( s ，x ) 是区域q nx f 2 n 上的连续函数，且假设a 成立，则对任意正整数r ，则随机序y l j f ( x ( t ) ) r 阶收敛于f + ，即l i m e if ( x ( t ) ) - f 1 7 = 0 。 证明：由定理4 和定理5 知定理6 显然成立。 2 3 进化规划的特点与应用 进化规划能适应于不同的环境、不同的问题，并且在大多数情况下都能得到比较有 效的解。与遗传算法和进化策略相比，进化规划主要具有下面几个特点【1 1 1 ： ( 1 ) 进化规划直接以问题的可行解作为个体的表现形式，无需再对个体进行编码处理， 也无需再考虑随机扰动因素对个体的影响，更便于进化规划在实际中的应用。 8 硕士论文基于进化规划的分布估计算法 ( 2 ) 进化规划中的选择运算着重于群体中各个个体之间的竞争选择，但当竞争数目较 大时，这种选择也就类似于进化策略中的确定选择过程。 ( 3 ) 进化规划以n 维实数空间上的优化问题为主要处理对象，对生物进化过程的模拟主 要着眼于物种的进化过程，所以它不使用交叉算子等个体重组方面的操作算子。 与常规搜索算法相比较，进化规划具有以下一些优点【1 2 1 ： ( 1 ) 智能性：确定进化方案之后，算法将利用进化过程中得到的信息自行组织搜索； 基于自然选择策略，优胜劣汰；具备根据环境的变化自动发现环境的特征和规律的能力， 不需要事先描述问题的全部特征，可用来解决未知结构的复杂问题。也就是说，算法具 有自组织、自适应、自学习等智能特性。 ( 2 ) 多解性：在每次迭代过程中都保留一群侯选解，从而有较大的机会摆脱局部极值 点，可求得多个全局最优解。 ( 3 ) 并行性：具有并行处理特性，易于并行实现。一方面算法本身非常适合大规模并 行计算，各种群分别独立进化，不需要相互之间进行信息交换；另一方面，进化规划算 法可以同时搜索解空间的多个区域并相互交流信息，使得算法能以较少的代价获得较大 的收益。除此之外，进化规划的优点还包括过程性、不确定性、非定向性、内在学习性、 整体优化、稳健性等多个方面。 进化规划的一些缺点： 进化规划算法一般是采取基于排序的选择方式，即在父代和子代组成的集合中选择 前几个最优个体组成新一代种群，这在一定程度上会导致算法过早收敛及算法后期种群 搜索范围变窄，易于陷于局部最优。 进化规划的应用： 在最近几年中，进化规划的研究及应用都得到了高度重视，在无线电通信系统，树 型网络设计以及电力系统等领域都取得了丰硕的成果f 1 3 】： ( 1 ) 在直接序列扩频通信中，用传统的非线性优化方法解决信号滤波问题时，对 某些干扰的处理达不到较好的效果，稳定性也不理想，因而如何利用全局技术进一步提 高滤波性能，更好的抑制窄带干扰的影响是一个急待解决的问题。利用进化规划的方法 解决信号滤波问题可以明显的提高滤波性能，特别是对于极点靠近单位圆的干扰和高输 入噪比的干扰有较好的效果，并且能够较好的抑制窄带干扰的影响。 ( 2 ) 目前无线通讯系统中，盲均衡和盲辨识法的研究已经引起了越来越多的研究 者的注意，一些学者利用进化规划算法识别系统参数，取得了很好的结论。 ( 3 ) 设计树型网络中提出的基本问题，是解决其他网络设计问题的出发点，一般 是通过启发式算法不断加减边来逼近最优解，但当拓扑结构受限制为树时，启发算法不 再有效。有学者将进化规划的方法引入连接空间任意两节点，同时断开由此形成的回路 9 2 进化规划硕士论文 上的一条边的变异方式，得到了满意的结果，并同时指出了基于遗传算法求解o c s t 问题 的不足。这表明了进化规划作为进化计算的一个分支，在不同的优化问题上有自己的优 越性。进化规划侧重于群体层次的进化，通过变异改变性能，这个特点使得进化规划在 解决结构不固定的优化问题时，具有一定的优势。 1 0 硕士论文基于进化规划的分布估计算法 3 分布估计算法 3 1 背景 分布估计算法最早是在1 9 9 6 年提出，在两千年前后迅速发展，成为当前智能算法 熟点讨论的内容，最近几年来国际上与智能算法有关的各大学术会议都将分布估计算法 作为热点讨论【1 4 】。分布估计算法是一种基于概率模型的智能算法，它通过对当前优秀个 体建立概率模型来指导算法的下一步搜索，并从所获得的较优解的概率分布函数中抽样 产生新的个体。由于这类算法在本质上改变了简单遗传算法通过重组操作产生群体的途 径，因此改善了简单遗传算法中存在的欺骗问题和连锁问题。 3 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 ，e d a s ) e d a s 算法伪代码为： d 。卜随机产生m 个个体作为初始群体 重复f o ri = i ，2 ，直到终止准则达到 d 三卜根据某个选择法从d ，_ 中选择m 个个体作为优秀群体 p ，( 力= 烈x i d 三) 卜估计被选个体的联合概率分布 d ，卜从p ，( c ) 中采样m 次，得到新的种群 3 3 分布估计算法分类 分布估计算法是基于种群的搜索算法，它根据当前种群中一定数量的好个体集合 进行概率分布估计而产生新的种群为了知道所选择个体的概率分布，因而要建立概 率模型。根据概率模型所描述变量的离散或连续性质，分布估计算法首先可以分为离散 分布估计算法和连续分布估计算法。再根据模型的复杂度，分布估计算法分成假定向量 的各维分量的概率分布是独立的、假定向量的各维分量两两具有依赖性和考虑多维分量 间的依赖性三类。 3 分布估计算法硕士论文 3 3 1 离散分布估计算法 3 3 1 1 变量无关的分布估计算法 在分布估计算法的研究中，最简单的情况是变量之间无关在这种情况下，一般的 可以通过一个简单的概率向量表示解的分布，变量之间关系可以用图表示设定待解决 问题为n 维问题，变量无关性使得任意解的概率可表示为n 个一维且独立的概率分布的 积： p ，( x 。，x ：，x 。) = 兀p ，( 咒) 当然这在一个困难的优化问题中是不行的，那里变量存在依赖性。 3 3 1 1 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 na l g o r i t h mb t l d a ) 由 德国学者_ a , a i h l e n b e i n 在1 9 9 6 年提出，算法的伪代码如下1 5 】： d 。卜随机产生m 个个体作为初始群体 重复f o ri = 1 ，2 ，直到终止准则达到 院卜根据选择法从d q 中选择m 个个体作为优势群体 。6 ，( x ，= 咒i d 三) p ，( 功2p ( xd l _ 三) 2 珥p ，b ，) 2 马【型丙一卜估计被选个体的联合概率分布 d ，卜从p ，( x ) 中采样m 次，得到新的种群 从算法的伪代码中看出在每一代模型被选个体的联合分布估计p ( x ) 是尽可能简单 的。它被因子分解为n 个一维边际分布的积：p l ( x ) = p o i d 三) = 兀p ，( x ，) 6 ，( x ，= x 。i d 三) 每一个一维边际分布从边际频率中估计：p ，( x ) = 上l j 厂一，其中 孙肿别确= b 警辩价钟，x i - - x i 3 3 1 1 2 基于群体的增量学习算法 在基于群体的增量学习算法( p o p u l a t i o nb a s e di n c r e m e n t a ll e a r n i n g ，p b i l ) 中，函数定义在二进位空间q = o ，1 打中，在每一代，种群由一个n 维概率向量 1 2 硕士论文基于进化规划的分布估计算法 p ，( x ) = ( p ，( x 。) ，p ，( x ，p ，( x 。) ) 表示。其中p ，( x ，) 表示在d ，第j 个分量取1 的概 率，也就是二进制表示的解集中第i 位取1 的概率。d ，表示第1 次生成的种群。在每一 代中，使用概率向量p ，( x ) 得到m 个个体。m 个个体被评估并选出n 个最好的个体，记他们 为x ：村，x l ，村，x l 村，新种群产生的方法是更新概率向量肿1 ： p m ) = ( 1 + a ) p ，( x ) + a 专k = l x 乙，其中a 为学习率，口( o ，1 】 p b i l 算法的伪代码为： 得到一个初始概率向量p 。( x ) w h i l e 不收敛d o b e g i n 用概率向量p ，( x ) 得到m 个个体：x l 1 ，x 1 ，x 吖l 评估并排序x ：，- ，x 0 ，x m i 选择n ( m ) 个最好的个体：x 1 。村，x 乙，x 0 射 更新概率向量p m ( x ) = ( p m ( x 。) ，p m ( x 。) ) f o ri = 1 ，nd o p i + i ( x ，) = ( 1 一a ) p ，( x ，) + a 专善x ：村 e n d 在p b i l 中，如果a = l ，则与u m d a 相同，因此可以把u m d a 看作p b i l 的一个特例。 3 3 1 1 3 紧致遗传算法 与p b i l 类似，在紧致遗传算法( c o m p a c tg e n e t i ca l g o r i t h m ，c g a ) 中种群由一 个概率向量表示。在c g a 算法中，由概率向量表示各个解的概率分布，它与p b i l 算法和 u m d a 算法的不同不仅在于概率模型的更新算法，而且群体规模很小，只需要很小的存 储空间算法中，每次仅由概率向量随机产生两个个体，然后对两个个体进行比较，按照 一定的策略对概率向量更新。下面是c g a 算法的伪代码【1 7 】： 1 初始化概率向量p 。( x ) = p 。( x l ，x f ，x 。) = ( p 。( x 。) ，p 。( x ，p 。( 溉) ) 2 ( 0 5 ，0 5 ，0 5 ) 2 1 = 1 + 1 ，两个个体随即产生：x 。i ，x ： 1 3 3 分布估计算法硕士论文 3 评估并排列x ：，x i ：获得：x 1 。：( 两个中最好的) 和x ：两个中最差的) 4 更新概率向量p ，( x ) 使其朝着x ：的方向改变 f o ri = lt on ifx ：2 x ：2t h e n 1 i f x l i ：22 1 t h e n p ，( x i ) 2p ，1 ( x t ) + 玄 i f x ：= 22 0t h e np ，( x t ) 2p ，- l ( x t ) 一壶 5 检查概率向量p ，( x ) 是否收敛 f o ri = lt on i f p 肛i ) oa n dp 胁i ) lt h e n r e t u r n2 6 p ( x ) 表示最后的解 3 3 1 2 基于双变量依赖模型的分布估计算法 各变量相互独立是一个非常苛刻的条件假设，能够满足这一条件的优化问题非常 少。在绝大多数实际问题中，各变量之间都存在一定的相互联系。本节中的几种算法就 假设两个变量之间存在相互依赖关系。此时，在算法中除了需要确定参数以外，还要对 模型的结构进行学习 1 5 1 。 3 3 1 2 1输入聚类最大互信息算法 输入聚类最大互信息算法( m u t u a li n f o r m a t i o nm a x i m i z a t i o nf o ri n p u t c l u s t e r i n g ，m i m i c ) 概率模型可以表示至多两个变量之间的关系算法，是由美国人工 智能实验室的等人于年提出的一种启发式优化算法。在算法中，把所有的随机变量之间 的相互关系假设成了一个链连接关系，在n 个随机变量组成的链中，只有相邻节点之间 存在相互联系【1 9 】。 在每一代，m i m i c 搜索一个变量之间的最优排列p ? ( x ) ，使被选择优良解集的概率 分布p p ) 与该排列定义的概率分布( ) p ? ( x ) 最接近。其中： p ，( x ) 2p ，( x 订ix ，：) p ，( x ，：ix ，) p ，( x 加一，ix 加) p ，( x 加) 万= ( j l ，f 2 ，) 表示序号1 ，2 ，n 的一个排列。两个概率分布( p ；( x ) 与p ，( x ) 之间的 接近程度用k u l l b a c k l i e b l e r 度量来表示： 1 4 研( x ) = 岛( 瓦) + 岛( 蜀1 + ，) ，其中 = l 硕士论文基于进化规划的分布估计算法 办( x ) = 一p ( x = x ) l o gp ( x = x ) 表示x 变量的香农熵， h ( xy ) = 一h ( xl 】，= j ，汩( 】，= y ) ，其中 y h ( x i 】，= y ) = 一p ( x = x l y = y ) l o g p ( x = x 】，= y ) 表示x 在y 的均值不确定度。 m i m i c 算法在每一代中要根据选择后的优势群体构造最优的概率图模型矽? ( x ) ，也就是 搜索最优的排列7 r 使k l 距离研( x ) 最小化。为了避免穷举所有n ! 个可能排列，在d o b o n e t 的文章中，提出了一种贪心算法，搜索变量的近似最优排列 这个思想是去选择有最小估计熵的变量瓦，在下面的每一步，从没有被选中的变量集 中挑选一个变量，使得他关于前一步被选变量的平均条件熵是最小的。 下面是用m i m i c 算法执行联合概率分布估计的伪代码 2 0 1 ： 1 - 选择= a r g m i n ，岛( x ，) 2 f o rk = n 一1 ，1 选择t = a r g m i n ，岛( x jij 0 + 1 ) ，j & “， 3 矸( x ) = a ( t lx j 2 ) 易( 薯2i 薯3 ) p a x , - 1i ) p a x ) 3 3 1 2 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 ) 算法是p b i l 算法的提出者b a l u j a 于1 9 9 7 年提出的，用于解决双变量相关的优化 问题。c o m i t 算法是p b i l 算法的最大不同在于c o m i t 算法的概率模型是树状结构，而p b i l 是链式结构。 c o m i t 算法的伪代码是： d 。卜随机产生m 个个体作为初始群体 重复f o r1 = 1 ，2 ，直到终止准则达到 d 三卜根据某种选择法从d 一。中选择m 个个体作为优秀群体 p ，( 功= 贴id 三) = i - p ，( x ， x j ( o ) - - i n c h o w 和l i u 的m w s t ( 最大加权生成树) 算法估计被 选个体的概率分布 苈卜从p ，( x ) 中抽样m 个个体 d 尸卜以d 尹中的最好的个体作为快速搜索的初始点，用快速搜索选择m n 个个体 1 5 3 分布估计算法 硕士论文 d ，卜d ，u d 三 3 3 1 2 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 肋a ) 假 设待求解问题的概率模型是一组树结构( 或称为森林结构) 。 在b 肋a 中，节点之间是否存在依赖关系采用p e a s o n 的z 2 统计，对于两个随机变 量的z 2 统计量，如果z 2 ，鼍厂、置= a 。e c g a 使用的这种概率模型称为 c 6 q 边缘乘积模型。 在划分变量组时，e c g a 采用了最小描述长度准则( m d l ) ，算法利用压缩群体的复 杂度和模型复杂度之和来定义边缘乘积模型的组合复杂度。 压缩群体的复杂度用边际分布的熵定义： 1 6 硕士论文基于进化规划的分布估计算法 j l z ( 丘) = 一p ( 丘= t ) 1 0 印( 五= t ) ；模型复杂度考虑到模型的维数： c e qc e q l o g n d i i l l 五，其中m m t 表示参数的个数。边缘乘积模型的组合复杂度为： c c t 一p ( 置= 艺) l o 印( 置= x 。) + l o g n d i i n 置为了减少计算量，e c g a 采用了贪婪算 c e q c e q 法进行变量组的划分。 首先假设每个变量作为一组，然后算法将变量组两两组合，并选取使模型组合复杂 度最小的一种组合方式进行合并，构成一个新组，算法一直进行这种合并，直到没有变 量组可以合并为止。 下面是e c g a 的伪代码： 穰卜随机产生m 个个体作为初始群体 重复f o r1 = 1 ，2 ，直到终止准则达到 磁卜用竞赛图选择法从口d 中选择n m 个个体作为优势群体 p a x ) = p ( x l 硝) = 兀易阮i 说) 卜依靠边际乘积模型估计被选个体的概率分布。模型搜 c e | 索使用最深上升搜索，最小化一p (