（信号与信息处理专业论文）实数型pmbga的实现与改进.pdf

实数型p m b g a 的实现与改进 摘要 概率模型遗传算法( p m b g a ) 是在遗传算法基础上发展起来的一类新算法， 它将统计学的有关理论引入到遗传算法中，以群体的概率统计学习实现进化操 作，利用个体的概率分布分析每一代群体的学习结果并作为新群体形成的依据， 最终逼近于形成最优或近似最优个体的概率分布。本论文主要研究实数型概率模 型遗传算法。在分析运行参数对算法计算质量和效率影响的基础上，获得提高算 法搜索效率的方法，并且通过仿真实验进行比较验证。 论文首先讨论了实数型p m b g a 算法流程，分析了p m b g a 与g a 的不同， 通过计算实例表明，在进化质量稳定性和收敛效率方面p m b g a 都优于遗传算 法。 在算法的参数选择问题上，通过实际测试发现，种群规模，概率模型的调整 规则，算法的停止条件，以及使用不同分布构造概率模型等参数会对算法性能带 来不同程度的影响。种群规模小，方差学习率大都会导致算法不容易收敛，停止 条件则对运行世代数有直接的影响。 通过对实数型p m b g a 运行参数的分析，发现在进化后期出现大量的相似个 体同时方差下降缓慢，影响算法的收敛。因而设计了自适应的实数型p m b g a ， 随进化代数自适应地调整种群规模和方差学习率，提高了算法的收敛速度。 为了准确地提取搜索空间有效的和潜在的信息，提出了概率模型的加权统计 算法，在进化群体的统计评估过程中加入选择的优良个体适应度的影响因子。典 型测试函数计算实验表明，应用加权统计的概率模型遗传算法可以有效地获得进 化群体中的有用信息，普遍提高进化的收敛质量和效率。 将改进的实数型p m b g a 用于i i r 滤波器设计的应用实例中，计算结果表明 这种优化设计方法是有效的，其特点是通过构造优化准则作为算法的适应度函 数，实现直接设计。 关键词：p m b g a 概率模型，自适应，加权统计，实数编码 实数型p m b g a 的实现与改进 a b s tr a c t p m b g ai san e wa l g o r i t h md e r i v e df r o mg a i ti n t r o d u c e ss o m ec o n c e p t so f s t a t i s t i c si n t og a ，a n du s e st h es t a t i s t i c a l l e a r n i n go fp o p u l a t i o n t om a k ef u r t h e r e v o l u t i o na n du s e st h ed i s t r i b u t i o no fi n d i v i d u a l st oa n a l y z et h el e a r n i n gr e s u l to f p o p u l a t i o na c c o r d i n gt o t h en e wg e n e r a t e dp o p u l a t i o n t h e r e f o r eg r a d u a l l yi t g o t c l o s e dt ob et h eb e s t r e a l c o d e dp m b g ai ss t u d i e di nt h i sp a p e r s o m ei m p r o v i n g m e t h o d sa r ep r o p o s e da n dt e s t e da f t e rt h ef r a m eo fp m b g a a n dt h es e l e c t i o no f p a r a m e t e r s a r ea n a l y z e d t h ea l g o r i t h mf l o wi sd i s c u s s e df i r s ta n dt h e nt h ed i f f e r e n c eb e t w e e np m b g a a n dg a ，a n dt h e i rc o m p a r i s o na r ea n a l y z e d p m b g ai sv a l i d a t e dt ob eb e t t e ro nt h e e v o l u t i o nq u a l i t ya n d c o n v e r g ee f f i c i e n c y p o p u l m i o ns i z e ，t h ec h a n g i n gr u l e so fp r o b a b i l i s t i cm o d e l ，p r o b a b i l i s t i cm o d e l w i t hd i f f e rd i s t r i b u t i o n s ，s t o pc o n d i t i o n sa r ct e s t e dt oh a v ee f f e c to nt h ep e r f o r m a n c e o fr e a l - c o d e dp m b g a as m a l lp o p u l a t i o ns i z ea n dab i gl e a r n i n gr a t ec a nc a u s eb a d c o n v e r g e n c e b a s e do na n a l y s i so fp a r a m e t e r s ，as e l f - a d a p t e dp m b g ai sp r o p o s e dw i t ha f l e x i b l ep o p u l a t i o ns i z ea n da l e a r n i n gr a t et oa c c e l e r a t ec o n v e r g i n gs p e e da n d r e d u c e t i m ec o n s u m p t i o n an e wm o d e lo fw e i g h t e ds e l e c t e di n d i v i d u a l si sp r o p o s e di no r d e rt os e a r c hm o r e u s e f u li n f o r m a t i o n f i t n e s sf a c t o ri sa d d e di n t ot h ep r o c e s so fs t a t i s t i ce v a l u a t i o n t h i s i m p r o v e m e n t i sv a l i d a t e dt ob eb e t t e rc o n v e r g i n gq u a l i t ya n dm o r e e f f i c i e n t 。 f i n a l l y , p m b g a i su s e df o rd i r e c td e s i g no fi i rd i g i t a lf i l t e ra n dt h ee x p e r i m e n t a l s os h o w sf e a s i b i l i t yo ft h i sm e t h o d k e y w o r d s ：p m b g a p r o h a b il is t ic m o d e i s e i f - a d a p t i o n ，w e ；g h t e ds t a t is t i c r e ai c o d e d 实数型p m b g a 的实现与改进 1 1 概率模型遗传算法 第1 章绪论 遗传算法是在计算机上模拟生物进化机制而发展起来的一种全局最优并行 搜索算法，遗传算法模拟了生物的进化过程，也使用了同样的生物学的概念与术 语。由于采用了类似物种进化过程中基因的选择、交叉和变异等操作手段，使得 遗传算法在本质上成为一类非确定性算法，具有全局搜索能力，特别适用于多峰 值函数的最优解问题。基因重组和交叉生成新的个体，变异则使得遗传算法得以 保持种群的多样性，以防止出现非成熟收敛，因此交叉和变异算子成为遗传算法 最重要的特征。 遗传算法的有效性可以由模式定理来解释，。模式定理认为在交叉和变异等 遗传算予的作用下，低阶，短距，平均适应度高的模式( 即积木块) 在子代中呈 指数增长。也就是说遗传算法是通过在子代中保留优秀的模式而逐渐趋近最优解 的。 遗传算法在上一代进化群体的基础上，使用交叉和变异等遗传算子构造新群 体，在优胜劣汰的选择策略下逐渐逼近最优模型。但是由于有限的群体规模和进 化代数，不可避免地产生取样误差，使进化轨迹偏离问题的最优解方向。另外交 叉操作可能会破坏原有个体的优良模式，使部分个体的适应值恶化。在实际的运 行中表现为算法过早地失去群体的多样性，导致算法逼近局部最优或者早熟。 遗传群体只是搜索空间中的有限个体，交叉操作是根据具体的群体交换彼此 的编码，变异操作也只是对当前解空间进行有限的局部搜索。近年来一些研究者 从统计学的观点出发，提出一类新的算法，使用一个概率模型来保存被选择的优 秀个体的模式的某些统计特征，而子代的产生不再使用交叉和变异算子，而是由 概率模型取样产生一部分个体取代种群中适应度较差的个体。统计方法提耿进化 群体内的有用信息，将其浓缩为编码的概率分布模型，可以描述当前进化群体所 表示的搜索空间。 不同的研究者在研究这个新算法的时候，使用了不同的名称，本文为了称呼 实数型p m b g a 的实现与改进 方便，把这类算法统称为概率模型遗传算法( p r o b a b i l i s l i cm o d e l b u i l d i n gg e n e t i c a l g o r i t h m ( p m b g a ) ) “。 p m b g a 开始于产生一个大小为九的初始种群，同时建立一个概率模型，然后 在种群中选择个个体。依照被选择个体的集合估计概率的分布，依此修正概率 模型，然后由概率模型取样产生下一个种群。 基本的p m b g a 流程伪代码如下： p r o c e d u r e p m b g a b e g i n i n i t i a l i z ep o p u l a t i o n ( ) ； i n i t i a l i z ep r o b a b i l i s t i cm o d e ； w h i l e ( n o te n dc o n d i t i o n ) d o b e g i n s e l e c tu i n d i v i d u a l s ； e s t i m a t ed i s t r i b u t i o no fu i n d i v i d u a l s ； m o d i f yp r o b a b f l i s t i cm o d e l ； s a m p l e i n d i v i d u a l sf r o m p r o b a b i l i s t i cm o d d ； g e n e r a t en e x tp o p u l a t i o n ； e n d e n d 在产生子代个体过程中没有交叉也不经过变异，依靠概率模型更新种群全部 或者一部分。与g a 中的隐含积木块相反，此处的处理过程中，优秀个体的模式 比劣等个体的模式以更大的概率体现在概率模型上，并经过概率模型取样，在子 代中得到充分体现。 p m b g a 算法的成功与否完全依赖于使用的概率模型，概率模型的好坏是p m b g a 表现的决定性的因素。概率模型越准确，算法越能有效避免重要的积木块破裂“。 与g a 相比，p m b g a 有以下的优势： 1 g a 对于多变量的问题，没有而且也很难研究变量之间的相关关系： p m b g a 在建立概率模型的时候可以建立变量之间的相关关系参数，而且可以使 用此参数改善算法的性能。 实数型p m b g a 的实现与改进 2 g a 使用了积木块的假设，然而积木块在算法过程中不能够体现出来， 它是隐含的；在p m b g a 中使用一个概率模型保存优秀的个体概率分布的估计， 在这里不仅可以看到模式的发展，还可以很清晰地看到每个变量取某个特定值的 概率。 1 2 国内外研究现状 1 9 9 4 年b a l u j a 构思了利用一个概率向量表示群体的染色体，向量的元素用 于表示群体在结构中每一个基因位置为1 或0 的比例，称之为p o p u l a t i o nb a s e d i n c r e m e n t a ll e a r n i n g ( p b i l ) 并首先提出了此类算法的一个最简单的形式【1 】o 随 后许多研究者开始关注这个算法并且提出了各种各样的的模型，并由研究者给予 各自名字，表1 1 列出- r - 进制编码领域p m b g a 算法的一些典型的模型。 表1 1 二进制编码领域典型的算法 大部分早期的p m b g a 集中研究二进制编码表示的优化问题，即离散问题， b a l u j a l 9 9 4 年提出的p b i l 只是使用一个变量，不过算法很快扩展到多变量的情 形。对于多变量的情形，使用概率模型不仅可以表达变量本身的发展趋势，而且 还可以设计用来研究变量之间的各种关系。实际上，对于二进制编码的p m b g a 算 法，后来的研究大多倾向于考虑变量之问的关系，在表1 1 所列的算法中，按照 研究的变量的数目不同，算法分成了几个类别【2 l ： 1 变量之间互不相关 3 实数型p m b g a 的实现与改进 2 变量之间两两相关 3 多变量之间相关 第一类包括p b i l ，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 m ( u m d a ) 【5 】，c o m p a c tg e n e t i ca l g o r i t h m ( c g a ) f 4 】。 u m d a 计算选择的个体的边缘概率p ( x ；) ，然后依照概率p o ) 2 n p ( x i ) 产生新 的个体代替父母。 c g a 只产生二个个体，竞争它们，使用胜利个体中的与失败个体不同的基因 值更新概率向量，胜利个体与失败个体相同的基因位则不改变。 第二类包括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 tc l u s t e r i n g ( m a m i c ) 1 6 】， c o m b i n i n go p t i m i z e r s w 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 r d 1 7 1 , b i v a f i m e m 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 i v l d a ) 【8 】。 m i m i c 使用概率分布的链式结构，c o m r r 使用一个树结构的概率模型，相比 链和树结构，b m d 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 ( e c g a ) 1 9 1 。f a c t o r i z e d d i s t r i b u t i o na l g o r i t h m ( f d a ) 【，b a y e s i a no p t i m i z a t i o na l g o r i t h m ( b o a ) 【1 0 1 1 1 1 l e a r n i n gf a c t o r i s e dd i s t r i b u t i o na l g o r i t h m ( l f d a ) m l ，e s t i m a t i o n o f b a y e s j a nn e t w o r k ( e b n a ) 1 2 1 1 。 此类算法考虑两个变数以上的互相关，反映相互关系的概率网络明显变得复 杂，计算时间增长，几乎不能搜寻所有的可能模型。由于简化的原因，大部分本 类算法使用贪婪和启发搜寻一个好模型，然而贪婪的启发搜索不总是保证准确 性。许多目前p m b g a s 研究把重心集中在发现好的启发式接索上【3 】。 以上的研究都是基于二进制编码。二进制编码的优点在于编码、解码操作简 单，二进制p m b g a 算法的统计学习，采用概率矩阵表示各个编码位取1 的概率， 分析、计算比较简单；但是对于一些多维、高精度要求的连续函数优化，二进制 编码存在着连续函数离散化时的映射误差，个体编码串较短时，可能达不到要求： 个体编码串的长度较长时，会使算法的搜索空间急剧增大，造成算法的性能降低。 实数编码则可以克服以上二迸制编码的缺点，而目在p m b g a 中采用实数编码进 行统计学习时，是建立一个基于变量分布函数的连续概率模型，比二进制编码有 更多的灵活性。这种采用实数编码的p m b g a 算法在本文中称之为实数型 实数型p m b g a 的实现与改进 p m b g a 。 许多研究者后来把p m b g a 应用到实数域，这其中包括使用高斯分布的连续 p b i l 【12 1 ，使用重复区间更新的实值编码p b i l 1 3 】，使用一个有限的自适应高斯混 合概率模型的p b i l 。u m d a 和m i m i c 后来也被扩展到实数域。l a r r a n a g a 则提 出一个高斯网络学习估计父代多变量高斯分布【1 4 1 ，b o s m a n 使用了两个概率估计 模型，高斯分布和柱状图分布1 1 ”，还介绍了一个正态混合模型处理非线性相关 【1 7 】，t s u t s u i 也发表了一个连续域的使用边缘柱状图模型的算法【1 8 】。 国内也已经有学者展开对此类算法的研究，浙江师范大学金炳尧结合p b i l 和自私基因算法提出基因学习算法并且介绍了其在图论和时间表问题中应用 2 6 】【2 7 】【2 8 1 ，湖南大学林亚平归纳了概率分析算法的几个类型并对算法存在的问题 和研究作了展望【2 9 1 。国内的这些研究都是基于二进带0 编码，并没有涉及到实数 编码的情况，因此本文对实数型p m b g a 算法进行深入研究。 1 4 本文的内容安排 本文构造了一个实数型p m b g a 算法，在算法的基本框架下尝试了不同的分 布模型和不同的参数选择对算法性能带来的影响并提出了相应的改善措施。 各章节安排如下： 第二章阐述实数型p m b g a 算法的基本原理和结构框架，并对p m b g a 和g a 算法作了一个简单的比较。 第三章分析算法中各个参数对收敛的影响并提出相应的改善措施，本章分别 用高斯分布，柯西分布和均匀分布建立概率模型，并且使用种群中的一个或多个 最优个体的不同统计特征去更改概率模型，以验证算法在各种条件下的性能，并 提出自适应改变参数的模型。 第四章提出对选择出的优秀个体加权统计，使用加权后的统计参数来改变算 法的概率模型；加权模型表现出更好的性能。 第五章是本算法的一个工程实际应用。使用p m b g a 算法实现i i r 滤波器的直 接设计。 第六章是全文总结。 5 实数型p m b g a 的实现与改进 第2 章实数型概率模型逮传算法 g a 作为一个日渐成熟的算法，由于使用简单，不需要先验知识，并行计算等 特点而得到广泛应用，g a 通过种群中个体之间的交叉和变异，使个体中的优秀 基因得以传播和遗传下去，但是基因的传播和遗传的过程不是直接表现出来的， 而是隐含的，p i v i b g a 算法则改善了g a 的这一问题，通过建立一个概率模型表现 被选择的个体的基因模式，使优秀个体的发展模式充分表现，而且这个模式通过 采样传递到下一代。 p m b g a 是进化计算领域一种新的有效的算法，和g a 的不同之处在于g a 使用交 叉和变异算子作为必要的工具和手段来产生下一代种群，而p m b g a 则是估计和分 析被选择的个体的概率分布，利用概率分布精化当前的搜索空间，充分地获取进 化群体中的潜在信息，逐渐增加有效个体的概率，促进搜索解空间以寻找到那些 可能的最优区域。算法的性能得到显著的改善，最终获得精度更好的结果。 p m b g a 算法的中心之处在于如何估计分析和利用被选择的个体的概率分布， 就是如何建立一个概率模型，模型的好坏是算法表现的根本。 2 1 总体框架 在p m b g a 中，不使用交叉和遗传算子，用以下方法取代： 1 ) 建立一个概率模型 2 ) 根据概率模型采样产生新的个体 从种群中选择优秀的个体，估计其概率的分布，估计的结果用来更改概率模 型，所以概率模型代表的是种群中优秀个体的模式变化；在这里，优秀模式被显 式地表达出来。 基本p m b g a 算法流程如下： ( 1 1 产生初始种群，初始化概率模型 f 2 1 选择优秀个体 f 3 ) 估计被选择个体的概率分布，更改概率模型 6 实数型p m b g a 的实现与改进 ( 4 ) 根据概率模型取样产生新的个体 ( 5 ) 新的个体与原先的种群结合产生新的种群 ( 6 ) 没有达到收敛条件则转2 图2 1 p m b g a 算法流程方框图 概率模型的好坏是p m b g a 表现的决定性的因素，也是区别不同算法的依据。 2 2 基本算法 二进制编码的p m b g a 使用概率向量来表达优秀个体的统计模式，概率模型向 量的各个位显示的是个体相应的二迸制编码位取1 的概率。在实数领域研究者使 用概率密度函数代替离散概率矩阵：或者将连续空间离散化。然后使用二进制编 码的算法。 在构造算法之前，需要解决三个问题： 1 ) 使用什么样的概率密度函数去构造概率模型 2 ) 概率模型如何随世代变化 3 ) 种群怎样由概率密度函数采样产生 实数型p m b g a 的实现与改进 2 2 1 初始概率模型 本文最初选择了高斯密度函数n ( 肛，口) 来构造概率模型： 脚：志一等) ) 限- ， 许多研究者已经选择了使用高斯分布去构建概率模型i 1 2 1 1 4 】f 1 5 】1 1 7 】，选择这个 函数的原因一般有两个： 许多实际问题符合高斯分布 高斯分布分析计算方便 从高斯分布密度表达式中可以看到，参数肛，盯决定了概率密度，所以算法只 须要确定p ，口就可以完全确定概率分布。 2 2 2 群体生成 在p m b g a 中，种群由概率模型全部或部分采样产生，高斯分布概率模型产生 种群方法如下： 1 ) 首先生成一个服从( 0 1 ) 的随机数r a n d 2 ) 那么a ：竺型二竺就服从( p ，仃) 分布 3 ) 假设变量的取值范围为 1 k ，u k ，如果a e 1 k ，u k ，保留，否则舍弃 4 ) 重复以上步骤直到种群完全产生 2 2 3 适应度函数 轮盘赌是g a 常用的选择方法，但是轮盘赌要求适应度不能为负，所以适应 度经常需要经过变换。p m b g a 般选择的都是最优个体，只需要适应度比较雨不 管正负，所咀不需要适应度转换，计算上会节省很多时间。 2 2 4 选择 最优个体的选择有多种方法： 1 ) 只选择单个最优个体 2 ) 选择多个最优个体 实数型p m b g a 的实现与改进 其中单个最优个体还分两种情况： 1 ) 本世代最优个体 2 ) 从初始到本世代的历代最优个体 2 2 5 概率模型的修正 概率模型是种群的优秀模式的表现，随着算法的进行而逐步修正，这是算法 的核心。对于高斯分布概率模型来讲，主要修正的参数是弘，c r ，算法希望是这样 进行的，初始“在搜索区间中央，盯相当大使得整个搜索区间都有足够的概率被 搜索到，当世代t 逐渐增大的时候，逐渐靠近极值点，而盯逐渐变小，理想情 况是t 一。时，- - - 0 ，口一m i n ( f ( x ) ) 或者m a x ( f ( x ) ) ，如下图所示： 图2 2 概率分布随算法进行的变化 ( a ) 初始分布( b ) 算法演化至某一世代时的概率分布 因此这里使用如f 的概翠密度模型更改规则： 1 产生大小为a 的神群，种群中的所有个体服从( p ，j ) 分布 2 每一世代选择卢个最优个体y l , y ：，y 。 3 更改概率模型 ( f + 1 ) 2 ( 1 瑚) 肛o ) 删( 善y ，一肛( f ) ) ( 2 2 ) 9 一烈 实数型p m b g a 的实现与改进 a ( t + 1 ) = 仃( f ) + l r 2 ( 1 f y ；一弘( r ) i o o ) ) ( 2 3 ) “ 对于式( 2 4 ) ，有的研究者采用更简单的做法【3 0 】： o ( t + 1 ) 一a ( o + y 0 r 1 ( 2 4 ) 对比起来，式( 2 3 ) 包含了最优个体的信息，幕q 用最优个体的不同的统计 特征可以控制盯的变化，比式( 2 4 ) 更灵活。 2 2 6 终止条件 高斯分布p m b g a 的终止条件有两个： 1 ) 最大运行世代数 2 ) d ( es 为问题的精度要求 至此，我们可以列出高斯分布p m b g a 的结构流程： 1 ) 初始化似( o ) ，口( 0 ”，t = 0 2 ) 按照正态分布似o ) ，a o ) 产生种群 3 ) 计算适应度，选择最优个体 4 ) 改变概率分布参数弘，盯 5 ) 收敛条件判断，不收敛则t = t + l ，转2 ) 6 ) 结果处理 2 3 计算实例 使用b r a i nr c o s 函数来测试上面的算法： ，( ) = 口( x2 一b x ? + c x l 一d ) 2 + p ( 1 一) c o s ( xj ) + e ( 2 5 ) 其中一5 妄x 】s 1 0 ，0 s x 2e 1 5 且删扣若胪i 5 小船- 1 0 ，- 壶 此函数有3 个全局最小值点 1 0 实数型p m b g a 的实现与改进 图2 3b r a i nr c o s 函数的三维图形 因为b r a i n 函数有两个变量，所以算法建立两个变量的高斯概率分布： ( 盹，q ) ( 卢2 ，盯2 ) ，z l ( 肛1 ，盯1 ) ，x 2 舡2 ，仃2 ) 初始化芦。( 0 ) 一2 , 5 ，仃。( o ) = 7 5 ，芦2 ( o ) 一7 5 ，口：( o ) 一7 , 5 ，i r l = l r 2 一o 0 1 ，种群 大小为1 0 0 ，每一世代只取一个最优个体用来修改概率模型，修改按照式( 2 2 ) 和( 2 3 ) 进行，下面是算法运行了1 0 次的结果： 表2 1b r a i n 函数运行1 0 次的结果 实数型p m b g a 的实现与改进 可以看到每一次运行虽佳适应度基本稳定收敛，都收敛到了最小值点，3 个 最小值点也被找到，分别在( 一3 1 4 ，1 2 2 7 ) ，( 9 4 2 ，2 4 7 ) ，( 3 1 4 ，2 2 7 ) 附近，运行世 代数范围【5 3 6 ，7 1 4 ，变化幅度不大。卢，肛：很快就到达最优点附近，口。，盯： 则沿着类似负指数曲线的轨迹下降： 圈2 4 单次运行卢1 ，p 2 随世代变化的曲线 图2 , 5 单次运行盯。、盯2 随世代变化的曲线 2 4 与g a 的比较 由图2 4 和图2 ，5 ，可以清楚看到概率分布随世代变化的曲线，概率分布的 变化是由每代选择的优秀个体的统计特征决定的，所以概率分布的变化代表每一 世代优秀个体的变化，而经典遗传算法对优秀个体的模式表达是隐含的，无法清 晰表达出来。 除此之外，p m b g a 算法还可以研究多变量问题的变量之间的关系，本文不涉 实数型p m b g a 的实现与改进 及变量相关这个问题。 下面比较p 她g a 和g a 在相同的情况下的运行效果。 2 4 1 g a 算法参数及流程 1 ) 编码方式：浮点数编码 种群大小1 5 0 3 1 轮盘赌选择 适应度函数修正 因为目标函数有负值，不适合直接应用轮盘赌，为此需要对目标函数进行修 正，设种群的目标函数为f o ，y ) 取负变为极大值问题，为了保证适应度为正， 在每一世代中，求出种群中个体的最小目标函数值m i n ( f 0 ，y ) ) ，其余个体的目 标函数值减去此最小值，作为适应度，o ，_ ) ，) ： ，0 ，_ ) ，) 一- ( f o ，y ) 一m i n ( fx ，) ，) ) )( 2 6 ) 5 ) 交叉操作 o f f s p r i n g p a r e n t l - c t + ( p a r e n t 2 一p a r e n t l )a ( 一l o ) ( 2 7 ) 6 ) 变异操作：使用非均匀变异“，具体定义如下： 如果s ：= p ，。) 为一个染色体，且基因h t 被选择变异( v 七的域为 【k ，“。】) ，则结果变为向量s = v ，v ：，一。) 其中k 1 ，n v ：2 v k + a ( t , u k - v k 翥委篆震萋凳：) c z s ， 这旱，函数0 ，y ) 返回【o ，y 】里的一个值，以使a ( t ，y ) 靠近0 的概率随t 的增 加而增加。这一性质使该算子在初始阶段均匀地搜索空间( 当t 很小时) ，而在 后面阶段非常地局部化。a ( t ，y 1 使用了下面的函数： a(t,y)；y+(1一ro-ra(ty 6 )( 2 9 ) =+ ( 1 一r 。) ( 2 9 ) 这里r 为一个在 o ，1 里的随机数，t 为最大代数，b 为决定非均匀度的系 实数型p m b g a 的实现与改进 统参数，这里b = 5 。 7 ) 最优个体保留到下一代 8 ) 运行2 0 0 0 代 2 4 2 测试函数 我们使用s h u b e r t 函数 f ( x ，y ) = 荟c o s 瓣+ 1 虹十】 善c o s 孵+ 1 ) y + 】 + o 5 【( x + 1 4 2 5 1 3 ) 2 + ( y + 0 8 0 0 3 2 ) 2 】 ( - 1 0 x ，y 1 0 )( 2 1 0 ) 作为测试比较函数，此函数有7 6 0 个局部极小值点，其中只有一个 ( 一1 4 2 5 1 3 0 8 0 0 3 2 ) 为全局最小，最小值为i 8 6 7 3 0 9 。此函数极易陷入局部极 小值一1 8 6 3 4 。 2 4 3 结果分析 比较按照3 个标准进行； 进化质量一每次运行是否收敛到极值点 进化代数运行世代数 g a 中，除了总世代数限制外，没有具体的收敛条件，所以在这里世代数 的比较是收敛到极值点时的世代数的比较，因此定义适应度小于1 8 6 ，7 3 为到达极值点，称之为有效收敛。 算法复杂度 表2 2g a 和p i d b g a 各自运行1 0 次的比较结果 实数型p m b g a 的实现与改进 图2 6 g a 和p n 3 g a 各自运行1 0 次的收敛结果 图2 7 g a 和p 蛐, g a 各自运行1 0 次的运行世代数 进化质量上p m b g a l 0 0 的收敛，而g a 只有3 0 ；进化代数上，g a 平均 有效世代数是p m b g a 的1 4 倍；同时p m b g a 不需要适应度转换，选择次数大 大小于g a ，概率模型采样比选择、交叉和变异要简单的多。 p m b g a 算法继承了g a 的许多特点，比如种群和进化的概念，不需要先验 知识等，但是p m b g a 有与g a 不同的许多特点： 1 不使用交叉和变异算子，使用概率矩阵或者概率模型 2 概率模型表达了种群中优秀个体的模式，并可以利用此特点研究变量之间的 宴数型p m b g a 的实现与改进 各种相关关系 2 5 本章小结 本章阐述了实数型p m b g a 的基本算法，计算了一个实例并且与g a 进行了 比较。比较的结果显示： 1 ) 进化质量上p m b g a 优于g a 2 ) 进化代数上p m b g a 优于g a 3 ) 算法复杂度p m b g a 比g a 简单 实数型p m b g a 的实现与改进 第3 章运行参数对p m b g a 的影响及改进 算法的结构确定之后，算法要稳定准确地运行，还需要对算法所涉及的参数 精心选择并确定其最佳取值范围。 种群的染色体总数即种群规模，对算法的效率有明显的影响，规模太小得不 到进化，而规模太大将导致程序运行时问长，对不同的问题可能有各自适合的种 群规模。所以为了算法的有效运行，首先要确定种群的大小。本文的算法设计， 随着世代进行，搜索空间会逐渐变小，一个小的搜索空间可以使用一个相对较小 的种群，本章探讨了种群大小依搜索空间变化的可能。 当搜索空间会逐渐变小时，一部分搜索空间不免被舍弃，为了避免陷入局部 极小值，保持个体的多样性，种群中增加了一部分在整个搜索空间内均匀分布的 个体，这部分个体在种群中应该占到多大的比例，才能不影响算法性能，又能够 有效避免局部极值点，是需要确定的。 算法收敛的判定除了最大运行代数的限定外，基本上是由高斯分布参数。来 确定的，当。小于某个f 圉值e 时，算法停止：显然e 的大小对收敛世代数有明显 的的影响。 算法的高斯分布概率模型中，分布参数岸，盯的变化公式中的变化率系数 l r l ，l r 2 的大小对收敛快慢，收敛精度也产生影响。 算法最初使用高斯分布，本章也分析了使用其他分布：柯西分布和均匀分布 构造概率模型后算法的性能。 综上所述，本章需要测试的参数有： 1 ) 种群大小 2 ) 种群中服从随机分知的个体的个数 3 1 收敛条件 4 1 最优个体的选择方式：当代最优个体或者历代最优个体 5 1 变化率系数l r 6 1 其它分布模型 实数型p m b g a 的实现与改进 3 1 测试函数 本章选择s h o k e ls q r n 5 函数作为测试函数 s 。1 ，工2 ，z ”工4 ) ；一套寿 。1 ) 其中0 s z 。s 1 0 j a l ia 2 ia 3 ia ic i 14 04 04 04 0 0 1 21 o1 01 01 oo 2 38 o8 o8 o8 oo 2 46 06 06 06 00 4 53 o7 03 ，07 oo 6 此函数有一个全局最小值，最小值m i n ( s ) _ 一1 0 。1 5 3 2 基本运行条件： 1 ) 种群大小1 0 9 2 ) 每世代选择一个最优个体y 去更改概率模型 3 ) 种群中随机个体所占的比例为2 0 4 ) 口的变化规则 肛( f + 1 ) 一卢( f ) + 扣1 y p o ) ( 3 2 ) f ，1 0 0 1 5 ) 口的变化规则： 盯o + 1 ) = a 0 ) + 扣2 0 y 一卢( f ) i 一仃o ) ( 3 3 ) 肛2 = o 0 1 6 ) 收敛条件： 世代数大于1 5 0 0 或小于0 0 5 测试的标准： 1 ) 收敛质量一能否收敛到最优值，对于s h o k e ls q r n 5 函数，最优值为 1 8 实数型p m b g a 的实现与改进 1 0 1 5 3 2 ，到达一1 0 1 5 认为有效收敛。 2 ) 运行世代数的大小。 3 2 运行参数的影晌 3 2 t 种群规模 种群的规模要适当，种群规模太小，种群中就没有充分的多样性，不利于适 应度值高的染色体的进化，致使算法得不到满意的解。种群规模大有利于种群的 进化，种群健壮发展，但染色体多，每进行一轮进化花费的机器时间就多，致使 算法的效率低。 种群规模过大，并不会带来过多的好处。对于遗传算法的实践而言，初始群 体规模一般是由算法仿真实验确定。 种群大小分几个档次来测试，5 0 ，1 0 0 ，1 5 0 ，2 0 0 ，每一档次都运行1 0 遍。 表3 1 不同的种群大小的运行结果 就本算法而言，当种群大小在1 0 0 及以下的时候，算法有效收敛率为5 0 到 8 0 ，平均运行世代数9 3 0 9 4 0 ，当种群大小增大到1 5 0 时，最优适应度值稳定 在最小值附近，算法1 0 0 收敛，而且运行世代数则有稍微下降，种群继续增大 之后，运行世代数呈下降趋势。 1 9 实数型p m b g a 的实现与改进 b o - t 0 4 $ $ o51 0 靳 ( a ) 种靠h 蜘 兰厮 乒咔一 剧f 盘撤 图3 1 不同的种群大小的运行结果 ( a ) 不同的种群大小的收敛结果( b ) 不同的种群大小运行世代数 3 2 2 种群中的服从随机分布的个体数目 算法运行过程中，高斯分布参数。是逐渐减少的，种群中的个体集中在以p 为中心，3o 的范围内，随着算法的进行，搜索区间逐渐变小，部分区间搜索不 到了，为了增加个体多样性，我们在种群中增加一部分在整个搜索空间服从随机 分布的个体，下面钡4 试这部分个体的数目带来的影响。 随机个体的数目分为o ，2 0 ，6 0 个，分别运行算法l o 次。 表3 2 种群中随机分布个体数目的测试结果 根据测试结果来说，随机个体数目的大小对有效收敛和运行世代数的多少似 乎没有明显影响。这可以归因于每一世代最优个体的选择，目前的算法设计每一 世代只有一个毒优个体能够对概率模型产生影响，其他的个体都被忽略，如果随 机产生的个体竞争不到最优的位置，那么就被忽略，起不到什么作用。 。一 恤 豳 蜘 啪 瑚 实数型p m b g a 的实现与改进 t 4 鼍 龟 1 0 庙帆十悻叶 051 00 鼢 051 0 耐诎救 啊帆十 # 叶瞬帆十体如 培忭赢撤 ( a ) ( b ) 图3 2 种群中不同随机分布个体数目的测试结果 ( a ) 不同随机个体数目的收敛结果( b ) 不同随机个体数目的运行世代数 3 2 3 停止条件 g a 停止条件与解的质量有关系，由于所要解决的问题的最优解预先不知道， 停止条件就成了一个值得研究的方面。如果按预设的进化代数作停止条件，由于 不同的问题的复杂度不同，而且对同一问题构造的遗传操作不同其算法性能不 同，因此很难合理地预设一个进化停止代数。另一个常用的停止条件是种群中的 最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时，这 是一个比较合理的方式，但可能由于构造的算法在进化机制上存在不合理因素， 出现进化进程缓慢，或者个别个体早熟，导致过早结束运行，得到一个质量很差 的解。 本算法由于结构的不同，除了按预设的进化代数作停止条件以外，还可以增 加一个停止条件，就是 h i cs( 3 4 ) 当。很小的时候，搜索空间已经很小，没有继续搜索的必要了，那么。什么 时候算作很小呢，下面测试不同e 值对有效收敛和运行世代数的影响。 取几个值：0 5 ，0 0 5 ，0 0 2 ，0 0 1 ，算法同样运行1 0 遍。 实数型p m b g a 的实现与改进 当e 比较大的时候，搜索空间还相当大，显然无法保证收敛到极值，当e 变 小的时候，收敛的次数增加，当e 继续变小的时候，并不能保证每次运行有效收 敛，同时运行世代数有明显增加。视具体问题而论e 应有不同的取值。 # 嚆捌帆5幢捌请蛳惦黼i 方期m 5崎捌帅皓 阳 ，；圳 a 粘撇 t 圈 口 j 譬* t 算 加 05 f l 自觏遵概m 铀b 矗期缸懒瑚根0 埘 彗f & 女 ( a )( b ) 图33 不同e 值的测试结果 ( a ) 不同e 值的收敛结果( b ) 不同值的运行世代数 3 2 4 最优个体的选择方法 在只选择一个最优个体的情况下。有两种选择方法：当代的最优个体y 和历 代的最优个体y + ，选择的最优个体分别去修改概率模型参数u 和o ，下面列出四 种情况： 1 ) 用y 修改u ，用y 修改o 2 ) 用y 修改，用y 修改o 2 2 实数型p m b g a 的实现与改进 3 ) 用y 修改u ，用y + 修改o 4 ) 用y + 修改p ，用y + 修改。 每一种情况运行1 0 次，下表是收敛和运行世代数的变化 表34 选择历代和当代最优个体的运行结果 图3 4 不同最优个体的测试结果 ( a ) 不同最优个体的收敛结果( b ) 不同最优个体的运行世代数 选用历代最优个体还是当代最优个体区别不是很大，选用历代最优个体时， 收敛精度稍微有提高，运行世代数没有明显变化。 3 2 ，5 概率模型学习系数l r 选择好最优个体之后，用来修改概率模型，那么最优个体对概率模型的影响 的大小，由系数l r 来体现，下面是不同l r 数值分别对u ，o 所带来的影响： 1 ) “学习率l r l 的影响 实数型p m b g a 的实现与改进 按照式( 3 2 ) ，i r l 表示高斯分布参数u 靠近最优个体的速度，i r l 大， u 以较大的步长迅速靠近最优个体，i r l 小，则使用较小的步长。当l r l = l 的时 候，u 就等于每代所选出的最优个体。 表3 5 不同l r l 的运行结果 试验结果表明l r l 增大或减少对收敛和运行世代数并没有特别的影响，最优 个体每一代都变，当算法后期，最优个体比较固定的时候，i r l 的大小只要保证 在要求代数内接近最优个体就可以了。 h 目0 1i n 却岱 h