（计算机软件与理论专业论文）并行思维进化计算的性能分析.pdf

太原理二r 大学硕士研究生学位论文 y6 2 0 3 22 并行思维进化计算的性能分析 摘要 2 0 世纪6 0 年代，美国m i c h i g a n 大学的j h o l l a n d 教授首先 提出j ，遗传算法( g e n e t i c a l g o r i t h m ，缩写为g a ) ，它是模拟达尔 文的遗传选择和优胜劣汰的生物进化过程的计算模型。经过三 十多年的发展，无论在算法的改进方面，还是理论以及应用研 究方面，都已取得了很大的进步和成功。但是遗传算法中仍然 存在许多问题，如建筑块假设、早熟收敛和进化时间长等问题。 思维进化计算( m i n de v o l u t i o n a r yc o m p u t a t i o n ，缩写为m e c ) 是孙承意教授于1 9 9 8 年提出的一种新的进化计算( e v o l u t i o n a r y c o m p u t a t i o n ，缩写为e c ) 方法。它是根据对g a 存在问题的思 考以及对人类思维进步的分析，模仿人类社会中存在的趋同和 异化现象提出来的。 m e c 固有的并行性和大规模并行机的快速发展，促使我们 开始研究m e c 的并行化问题。m e c 与并行计算机的结合，能 把并行机的高速性和m e c 固有的并行性二者的长处结合起来， 从而促进m e c 的研究与发展。 水文在对进化计算、思维进化计算和并行遗传算法( p a r a l l e l g e n e t i ca l g o r i t h m ，缩写为p g a ) 这些背景知识的回顾和了解基 础上，对影响p m e c 的主要因素进行了理论分析，且通过实验 验证了理论分析的正确性。这些理论分析和实验结果况明m e c 具有很好的并行性。进一步丰富了由孙承意教授于1 9 9 8 年提出 的m e c 框架。论文中的创新点如下： 1 ) 将主从式p m e c 与主从p g a 和粗粒度p g a 进行了比 i 太原理工大学硕士研究生学位论文 惦 1 义o 2 ) 从理论上分析了影响p m e c 性能的主要因素，并通过实 验进行了验证。结果表明：m e c 适合并行计算，当选取适当的 参数( 如子群体尺寸，从处理器数目等) 时，p m e c 能获得较好的 并行性能。 关键词：进化计算，遗传算法， 并行进化算法，并行遗传算法， 机 i i 思维进化计算，趋同，异化， 并行思维进化计算，集群计算 太原理工大学硕士研究生学位论文 p e r f o r m a n c ea n a l y s i s0 f p a r a l l e lm i n de v o l u t i o n a r y c o m p u i 、a t i o n a b s t r a c t g e n e t i ca l g o r i t h m ( g a ) w a sf i r s t l yp r o p o s e di n19 6 0 s b yp r o f e s s o rh o l l a n dw h oc a m ef r o mm i c h i g a ns t a t eu n i v e r s i t y i t i sac o m p u t a t i o n a lm o d e lt h a ts i m u l a t e se v o l u t i o n a r yp r o c e s si n n a t u r e d u r i n gt h ep a s s e d3 0y e a r s ，t h et h e o r e t i c a ls t u d ya n d a p p l i c a t i o no fg a h a sb e e nm o s ta c t i v e ，a n dh a sr a p i d l yb e c o m ea h i g h l i g h ti nt h ef i e l d so fi n t e r n a t i o n a la c a d e m y h o w e v e r ，t h e r ea r e m a n ys h o r t c o m i n g si ng a ，w h i c hs h o u l dn o tb en e g l e c t e d i nt h e e a r l ys t a g e ，r e s e a r c h e r s h a v en o t i c e dt h e p r o b l e m o fg a s p r e m a t u r e l y ，a n o t h e rc r u c i a lp r o b l e mi sc o m p u t i n ge f f i c i e n c yo f g a d u et on o n d i r e c t i o n a l i t yo fi t se v o l u t i o n a r ym e c h a n i s m m i n de v o l u t i o n a r y c o m p u t a t i o n ( m e c ) i s an e w a p p r o a c ho fe v o l u t i o n a r yc o m p u t a t i o n ( e c ) p r o p o s e db yc h e n g y i s u ni n 19 9 8 i tc o m e sf r o mt h ec o n s i d e r a t i o no ft h e e x i s t i n g p r o b l e m so fg e n e t i ca l g o r i t h m ( g a ) a n dt h ea n a l y s i so ft h em i n d p r o g r e s so f h u m a n i t y i ti m i t a t e st w op h e n o m e n ao f h u m a ns o c i e t y s j i n i l a r t a x i sa n dd i s s j m i l a t i o n m e ci so f p a r a l l e l i t y i n h e r e n ta n dd e v e l o p m e n to f l a r g e s c a l ep a r a l l e lc o m p u t e ri sr a p i d l y t h e s em a k eh sb e g i nt o s t u d yp a r a l l e lp r o b l e mo fm e c m e ci n t e g r a t e s w i t h p a r a l l e l c o l n p u t e rc a np r o m o t er e s e a r c ha n dd e v e l o p m e n to fm e c i i i 太原理工大学硕士研究生学位论文 i nt h i st h e s i s b a s e do nt h er e v i e wo fe c ，m e ca n d p a r a l l e lg e n e t i ca l g o r i t h m sf p g a s ) ，w ea n a l y z em a n yf a c t o r so f a f f e c t i n gp e r f o r m a n c eo fp m e c t h et h e o r e t i ca n a l y s i sa n d e x p e r i m e n t a l r e s u l t ss h o wt h a tp m e ch a s g o o dp a r a l l e l p e r f o r m a n c e t h i s e n r i c h e st h ef r a m e w o r ko fm e c t h e o r n a l i t i e si nt h i st h e s i sa g ea sf o l l o w s ： f i r s t l y , w ec o m p a r ep a r a l l e lm i n de v o l u t i o na l g o r i t h m s w i t hm a s t e rs l a v ep a r a l l e lg e n e t i ca l g o r i t h m sa n dc o a r s ep a r a l l e l g e n e t i ca l g o r i t h m s s e c o n d l y ，m a n y f a c t o r so fa f f e c t i n g p e r f o r m a n c eo f p m e ca r ea n a l y z e di nt h e o r y w ec o n d u c te x p e r i m e n t si no r d e rt o v e r i f yt h ea n a l y s i s s t u d i e so ni t st h e o r ya n de x p e r i m e n ts h o wt h a t m e ci ss u i t a b l et op a r a l l e l i n g k e yw o r d s ：g e n e t i ca l g o r i t h m s ( g a ) ，m i n d e v o l u t i o n a r y c o m p u t a t i o n ( m e c ) ，e v o l u t i o n a r yc o m p u t a t i o n ( e c ) ，s i m i l a r t a x i s ， d i s s i m i l a t i o n ，p a r a l l e lg e n e t i ca l g o r i t h m ( p g a ) ，p a r a l l e lm i n d e v o l u t i o n a r yc o m p u t a t i o n ( p m e c ) ，c l u s t e ro fw o r k s t a t i o n s ( c o w ) 太原理工大学硕士研究生学位论文 1 引言 第一章绪论 2 0 世纪6 0 年代，美国m i c h i g a n 大学的j h o l l m a d 教授首先提出了遗传 算法 1 ( g e n e t i ca l g o r i t h m ，缩写为g a ) ，它是模拟达尔文的遗传选择和优 胜劣汰的生物进化过程的计算模型。经过三十多年的发展，无论在算法的 改进方面，还是在理论以及应用研究方面都取得了很大的进步。但是遗传 算法中仍然存在许多问题，如早熟收敛，进化时间长等问题。 基于对g a 存在问题的思考以及对人类思维进步的分析，模仿人类社 会中存在的趋同和异化现象，孙承意教授于1 9 9 8 年8 月提出了思维进化 计算( m i n de v o l u t i o n a r yc o m p u t a t i o n ，缩写为m e c ) 2 。 经过多年的理论和实验研究表明：m e c 的计算效率和收敛性能比标准 g a 及其它进化算法一般要高5 0 以上，说明m e c 是一种高效的算法。 已经进行了m e c 收敛性证明，开发了一些趋同和异化策略，成功地解决 了一。些非数值优化问题。此外，还将m e c 应用于图像分析中，并取得了 较好的结果。所有这些工作已经为m e c 建立了一个初步完整的体系。 2 本文的主要内容 经过几年来的理论和实验研究，目前思维进化计算在理论上已经有了 很大的发展，同时也广泛应用于一些实际问题。m e c 固有的并行性和大 规模并行机的快速发展，促使我们开始研究m e c 的并行化问题。m e c 与 并行计算机的结合，能把并行机的高速性和m e c 固有的并行性二者的长 处结合起来，从而促进m e c 的研究与发展。本文主要从这个方面来进 步丰富m e c 框架。这一部分内容主要在论文的第六章。 太原理工大学硕士研究生学位论文 本文中的章节安排如下： 在第二章中给出了进化计算的概述。叙述了进化计算的四火分支：遗 传算法，进化策略，进化规划和遗传程序设计，以及它们的基本原理和发 展历史。 第三章概述了并行遗传算法。叙述了四类典型的并行遗传算法：全局 并行遗传算法、粗粒度并行遗传算法、细粒度并行遗传算法和混合并行遗 传算法及其发展现状。 第四章概述了思维进化计算。叙述了思维进化计算的提出以及实现， 思维进化计算的三个实现机制和目前的一些研究成果，所有这些工作已经 为m e c 建立了一个初步完整的体系。 第五章简单介绍了一下并行程序设计的基础。主要包括：并行计算机、 并行编程模型与并行语言、m p i 的简单介绍。 第六章主要包括下面几方面的内容：1 ) 并行思维进化计算的框架。 详细地介绍了框架中各组成部分，并将p m e c 与主从式p g a 和粗粒度p g a 进行了比较。2 ) 并行思维进化计算的算法描述。3 ) 对并行思维进化计算 的算法性能进行了分析。这部分内容主要从理论上分析了子群体尺寸、个 体评价时间和从处理器数目对算法性能的影响，为了验证理论分析的正确 性我们做了一些实验，理论分析和实验结果表明：思维进化计算适合并行 订算，且当选取适当的参数( 如，子群体尺寸，从处理器数目等) 时，p m e c 能获得较好的并行性能。 第七章简单的总结了本文的主要内容。 3 思维进化计算的研究进展 m e c 自从1 9 9 8 年由孙承意教授提出以来，已经建立了一个初步完整 的理论体系，下面分别从几个不同的方面来详细介绍m e c 已经取得的迸 展： 2 太原理工大学硕士研究生学位论文 思维进化计算的结构框架 孙承意教授于1 9 9 8 年8 月提出了思维进化计算的理论框架。以后所 有的工作都是在这个框架下来完成的。第四章将专门介绍m e c 框架及实 现方法。 m e c 收敛性能和计算效率的实验研究 自从m e c 提出以来，已经就数值优化问题，采用大景g a 文献i w 门 常用函数，实验证明了m e c 算法的高效性，甚至对一个搜索空间为 2 如；1 0 7 1 0 9 ，峰的数量约为5 1 5 1 0 6 ，但全局峰的数量仅为3 2 的强欺骗 多峰函数而言，m e c 的平均评价次数也仅仅是小生境g a 的1 5 7 以下， 充分说明m e c 是一种高效的算法。 m e c 与g a 机制的比较 m e c 能够显著提高计算效率和收敛性能主要是由于机制上的原因。这 些机制包括定向机制、记忆机制、勘探与开采的协调机制，第三章中详细 给出了m e c 和g a 在这些机制上的不同。 m e c 收敛性证明 对于有限离散搜索空间和有界连续搜索空f 闭，分别用确限状念空问扣 的马尔可夫链理论和连续状态空削中的马尔可夫链理论进行了收敛性证 明。 采用m e c 求解多目标优化问题 丌发了求解多目标优化的m e c 算法 3 】 4 ：p a r e t o m e c 和s p m e c ( s c o r e dp a r e t om e c ) 。这两个算法根据m e c 和p a r e t o 的原理求解多目标优 化问题。采用多目标优化领域常用的函数进行性能测试，与当前世界公认 的最好的多目标优化算法s p e a ( s t r e n g t hp a r e t oe v o l u t i o n a r ya l g o r i t h m s ) 相 比较，对于凸的，非凸的，离散的测试函数，这两个算法与s p e a 性能大 体相当；而对于非均匀的测试函数，这两个算法的性能明显优于s p e a 。 3 太原理工大学硕士研究生学位论文 m e c 用于非数值优化问题 采用m e c 已经成功地解决了一些非数值优化问题，如t s p 5 、 j o b s h o p 6 、系统的动态建模问题、图的最大团问题 7 】等。其中在求解图 | 0 展人团问题巾丌发了m c p m e c l 算法。聚_ r j 困1 轫7 7 n 纵“离敝数哥+ j 川! 沧竹机4 i ：| 学( d i s c r e t em a t h e n r i t i c s & 7 | l h e o l - c l i c a l ( o i l l l ：, t l l c l s c i o n 吡 d i m a c s ) ”提供的3 0 多个标准测试图形进行测试，测试结果表明： m c p m e c l 算法的性能明显优于其它许多算法，如启发式遗传算法，煺火 复制启发算法。 m e c 的应用研究 m e c 自从提出以来，已经成功应用到了很多领域，包括在图像分析、 经济预测系统的构建、自动控制方向上的应用。 4 太原理工大学硕士研究生学位论文 第二章进化计算概述 进化计算( e v o l u t i o n a r yc o m p u t a t i o n ，简称e c ) 是模拟生物进化过程与 机制来求解问题的一类随机优化计算模型。自从8 0 年代中期以来，世界 上许多国家都掀起了进化计算的研究热潮。当前的进化计算领域正处于飞 速发展时期，目前有许多以进化计算为主题的国际会议在世界各地定期召 开，国际互联网上也有许多相关文献。而且由于进化计算应用之广泛，从 一些杂志及国际会议论文中都比较容易看到有关进化计算应用方面的文 章。现在已经出版了两种专门关于进化计算的新杂志“e v o l u t i o n a r y c o m p u t a t i o n ”和“i e e et r a n s a c t i o n so i le v o l u t i o n a r yc o m p u t a t i o n ”，并且一 些国际性的期刊也竞相推出以进化计算为主题的专刊。 在这一章中我们首先了解一下进化计算的历史及其发展现状。接下来 重点介绍进化计算中的几个主要发展方向。 1 进化计算的发展史 早在3 0 多年前，一些分别在美国和欧洲不同地方的研究者们同时产生 了模拟生物进化的思想，这样就出：现了各种用于优化问题的算法。三十多 年来的研究和应用证明了这些算法的鲁棒性和有效性。这一类基于生物进 化机制的随机搜索算法就是进化算法( e v o l u t i o n a r ya l g o r i t h m s ，简称e a s ) 。 ，依历史发展与不同的应用侧重，进化计算历史上有四个主要的分支： 遗传算法、进化策略、进化程序设计和遗传程序设计，它们是这一领域许 多活动的基础。虽然这几个分支在算法实现方面具有一些细微的差别，但 它们都是借助生物进化的思想和原理来解决问题的。九十年代以前，各个 分支所主张的算法成份和应用领域各有侧重，例如遗传算法是基于二进制 串的，并且是结合交叉和变异的操作；而进化策略的主要特点是采用实数 编码和变异操作，实现离散的或是连续的参数优化问题。 5 太原理工大学硕士研究生学位论文 但是，最近几年各分支之问明显的界限正逐渐被消除：算法设计中各 自策略的相互借用，具体应用的算法设计中各种算法成分相互嵌套等。遗 传算法的研究不再仅仅被限制在定长二进制中，进化策略从事者也已经考 虑采用复制算子，进化程序设计也不仅仅是用在有限状态机器的进化，而 遗传编程这一全新的潜在领域也发展了起来，各种文献中出现的都是新术 语和想法。例如“混乱的遗传算法”。 2 遗传算法 5 0 年代末6 0 年代初，一些生物学家开始利用计算机对遗传系统进行 模拟。在此期间，h o l l a n d 正在从事自适应系统的研究。受生物学家模拟 结果的启发，? h o l l a n d 和他的学生首次应用模拟遗传算子来研究适应性中 的人工问题。6 0 年代中期，h o l l a n d 开发了一种编程技术遗传算法， 其基本思想是利用类似于自然选择的方式来设计计算机程序。在软件设计 中，适应性是基于监督程序的不同选择，通过不断剔除效果不佳的程序， 让那些求解问题好的程序越来越占据优势，从而使系统最终能适应任意的 环境。除了认识到选择的必要性之外，h o l l a n d 还十分肯定地赞同群体搜 索的方法。在随后的l o 年中，h o l l a n d 致力于创建一种能表示任意计算机 程序结构的遗传码，以拓宽遗传算法的应用领域。在1 9 7 5 年，h o l l a n d 出 版了一本具有开创性的专著自然和人工系统中的自适应 1 。 1 9 6 7 年，b a g l e y 发表了关于遗传算法( g e n e t i c a l g o r i t h m ，简称g a ) 应 用的第一篇论文并且首次提到了“遗传算法”这个名称 8 。当时。人们对 下棋程序有浓厚的兴趣，b a g l e y 设计了一个可控制的试验棋盘，模拟六个 棋子韵下棋游戏。b a g l e y 构造的遗传算法是用来搜索下棋游戏评价函数中 的参数集，它与我们现在应用的遗传算法很相似，其中利用了复制、交叉 和变异算子。另外，b a g l e y 还敏锐地意识到在遗传算法的丌始和结束阶段 需要有适当的选择，为此，他引入了适应值比例机制。 1 9 7 0 年，c a v i c c h i o 应用遗传算法解决了人工搜索中的两个问题：子程 序选择问题和模式识别问题。在c a v i c c h i o 的遗传算法中，他采用了一个 6 太原理工大学硕士研究生学位论文 预选择策略，即个好的子代替换它的某一个父代，以便保持群体的多样 性。当群体规模较小时，群体多样性的保持尤其显得重要。后来d ej o n g 采用类似的方法成功地运用于函数优化研究之中。 1 9 7 1 年，h o l l s t i e n 完成了关于遗传算法在纯数学优化应用方面的第一 篇学术论文，主要研究了五种不同的选择方法和八种交配策略。 1 9 7 5 年，也就是在h o l l a n d 出版了那本很有影n 向的专著的同一年，d e j o n g 完成了他的博士学位论文一类遗传自适应系统行为的分析【辫。 d ej o n g 把h o l l a n d 的模式定理和他自己细致的计算成果成功地结合在一 起，他的研究成果至今仍是遗传算法发展史上的里程碑。7 0 年代后期， d ej o n g 对遗传算法进行了大量的数值实验，得出了一个结论。对于规模 在5 0 到1 0 0 的群体，经过1 0 到2 0 代的演化，遗传算法都以很高的概率 找到最优或近似最优解。这个结论对于一个变化非常大的问题空间也成 立。d ej o n g 指出，二迸制串中每一位上的变异概率只要在o 0 0 1 的数量级， 就足以能防止搜索陷入局部最优。 到8 0 年代早期，遗传算法已在更广泛的领域中得到应用。1 9 8 3 年， g o l d b e r g 将遗传算法应用于管道系统的优化和机器学 - 5 问题 1 0 】，该系统 模拟了从西南向东北输运天然气的管道系统。g o l d b e r g 的系统不仅用与实 际系统相当的成本满足了供气要求，而且也发展了一套分层容错规则，它 能够对管道漏洞采取适当的反应。 此外，l9 8 4 年，f i t z p a t r i c k ，g r e f e n s t e t t e 和v a ng u c h t 利用遗传算法处 理r 医学图像变换问题。他们的数值结果表明，对人工图像和实际x 光片 的处理都是成功的。而且，遗传算法还被应用到机器学习中，其中最普遍 的例子就是h o l l a n d 建立的分类系统，利用遗传算子，遗传算法可以部分 地生成新的分类，较差的分类被那些新的分类所代替。 g a 还有用于约束优化和多目标优化。s c h a f f e r 提出的矢量评价g a 是 用g a 解决多目标优化问题的先驱。 总的来说，遗传算法的进展还是很快的。进入8 0 年代，遗传算法迎来 7 太原理工大学硕士研究生学位论文 兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤 其是遗传算法的应用领域也不断扩大。目前遗传算法所涉及的主要领域有 自动控制、规划设计、组合优化、图像处理、信号处理、机器学习、人工 生命等。从1 9 8 5 年开始，国际上开始召开遗传算法学术会议，以后每隔 一年召开一次。1 9 8 9 年，美国亚拉巴马大学的d a v i dg o l d b e r g 出版了搜 索、优化和机器学习中的遗传算法一书 1 0 】，为遗传算法这个领域奠定 了坚实的科学基础。1 9 9 1 年，l a w r e n c ed a v i s 出版了遗传算法手册， 对有效地应用遗传算法具有重要的指导作用。目前，遗传算法已在更广泛 的领域中得到了应用。 ( 1 ) 基本原理 遗传算法是一种基于自然选择和群体遗传机理的搜索算法，它模拟了 自然选择和自然遗传过程中发生的复制、交叉和变异现象。在利用遗传算 法求解问题时，问题的每个可能的解都被编码成一个“染色体”，即个体， 若干个个体构成了群体( 所有可能解) 。在遗传算法开始时，总是随机地产 生一些个体( 即初始解) ，根据预定的目标函数对每个个体进行评价，给出 了一个适应值。基于此适应值，选择个体用来复制下一代。选择操作体现 了“适者生存”原理，“好”的个体被选择用来复制，而“坏”的个体则 被淘汰。然后选择出来的个体经过交叉和变异算子进行再组合，生成新的 一代。这一群新个体由于继承了上一代的一些优良性状，因而在性能上要 优于上一代，这样逐步朝着更优解的方向进化。因此，遗传算法可以看作 是一个可行解组成的群体逐代进化的过程。遗传算法的操作过程详述如 下。 编码 利用遗传算法进行问题求解时，首先确定问题的目标函数和变量，然 后对变量进行编码。这样做主要是因为在遗传算法中，问题的解是用二进 制串来表示的，而且遗传操作算子也是直接对串进行操作的。编码方式可 分为二进制编码和所谓的实数编码，即十进制编码。 遗传算法的创始人h o l l a n d 认为，将一个十进制数利用二进制编码后， 8 太原理工大学硕士研究生学位论文 其占的位数增多，描述的比较细致，相当于加大了搜索范围，从而能以较 犬的概率搜索到全局最优解。同时通过一些简单的变换规则就可以逐步地 改进这些二进制编码表示的结构，使之往好的方向“进化”。因此，在他 的专著中基本上采用这种二进制的传统编码方式。总的说来，采用二进制 编码方式有如下优点：它与计算机的编码机制相一致，适于计算机应用； 对于码串的每一位，只有1 和0 两个码值，在交叉和变异等操作中原理 清晰，操作简单；表示的变量范围大，如长为l 的码串最多可表示2 l 个 不同的变量；适合于表示离散变量，而对于连续变量，只要群体总数取足 够多，就可以达到足够的精度。 但是，利用二进制编码方式也存在着缺点。对于一些大规模的多变量 的优化问题，如果其各变量用二进制表示，同时为了保证问题的解具有一 定的精度，那么得到的数字串将会很长，这就使得遗传操作算子的计算量 较大，计算时间增多，同时占用了较大的计算机内存空间；此外，用二进 制来表示问题的解，在优化过程中就需要对参数进行编码和译码，以进行 二进制和十进制之间的数据转换，这就存在数据之间的转换误差( 引入了 量化误差) ，如果目标函数值在最优点附近变化较快的话就可能会错过最优 点。因此，采用实数编码的方式被提出。 “综上所述，采用实数编码要比二进制编码计算量小，不会存在编码和 译码造成的解的误差。但是，具体使用哪种编码方式，要根据实际的优化 问题来确定。 遗传操作 遗传操作是模拟生物基因的操作，它的任务就是根据个体的适应度对 其施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而 言，遗传操作可使问题的解逐代优化，逼近最优解。 遗传操作包括以下三个基本遗传算子：选择、交叉和变异。选择和交 叉基本上完成了遗传算法的大部分搜索功能，变异增加了遗传算法找到接 近最优解的能力。 9 太原理工大学硕士研究生学位论文 选择 选择是指从群体中选择优良的个体并淘汰劣质个体的操作。它建立在 适应度评估的基础上。适应度越大的个体，被选择的可能性就越大，它的 “子孙”在下一代的个数就越多。选择出来的个体放入配对库中。 目前常用的选择方法有以下几种； 赌轮方法，又称适应度比例法，是目前遗传算法中最基本也是最常用 的选择方法。设群体的大小为，个体的适应度为f ( i ) ，则个体i 被选择 的概率b ( i ) 为 几( f ) ：盟、 ( 2 1 ) 厂u ) 。 产l 从式( 2 1 ) 可以看出，+ 概率b ( f ) 反映了个体f 的适应值在整个群体适应 度总和中所占的比例。蜘前所述，个体酌适应值越大，它被选中的概率就 越高。体现了“适者生存，7 不适者被淘汰”这一自然选择原理。被选中的 个体被放入配对库中，随机地进行配对，以便进行下面的交叉操作。 精英保留法：把群体中适应度最高的个体不进行配对交叉而直接复制 到下一代。这样做的好处是保证了进化过程中某一代的最优解不被交叉和 变异操作所破坏。但这也带来了弊端：。局部最优的遗传基因会急速增加而 使进化停滞于局部最优解，也就是说，这种方法影响了遗传算法的全局搜 索能力。 排序选择法：首先根据各个体的适应度大小进行排序，然后基于所排 序号进行选择。 竞争法：随机地选取两个个体，对其适应值进行比较，大的被选中， 小的被自然淘汰：如果两个个体的适应值相同，则任意选取其中的一个。 被选中的个体放入配对库中。重复此过程，直至配对库中包含n 个个体 为止。这种方法既保证了配对库中的个体在解空间中有较好的分散性，同 时又保证了加入配对库中的个体具有较大的适应值。 1 0 太原理工大学硕士研究生学位论文 窗口方法：首先求出目前群体中适应值最小的个体，令其适应值为q 。 将解群体中的每个个体的适应值都减去q 后作为其适应值，再用赌轮法形 成配对库。采用这种方法时，个体入选配对库的概率虽与其适应值直接不 成比例，但关系比较大，与解群中最大的个体与最小的个体的适应值之差 以及个体的分散程度有关。 线性标准化方法：首先，把目前群体中的个体按适应值的大小降序排 列令最大的适应值为u 。解群中的其它个体的适应值以p ，线性递减。再 用赌轮法产生配对库。v 值越大，对解群中优良个体的选择压力越大。 交叉 交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操 、 作。交叉的目的是为了能够在下一代产生新的个体，就像人类社会的婚姻 过程。通过交叉操作，遗传算法的搜索能力得以飞跃性的提高。交叉是g a 获取新优良个体的最重要手段。 交叉操作是按照一定的概率p 。( 即交叉概率) 在配对库中随机地选取 两个个体进行的。交叉的位置也是随机确定的。交叉率p 。的值一般取的很 大，在0 6 到0 9 之间。交叉算子分为以下几种： 一点交叉( 又称简单交叉) 的具体操作是：在个体串中随机地选定一个 交叉点，两个个体在该点前或后进行部分互换，以产生两个新的个体。 两点交叉：与一点交叉类似，只是随机地产生两个交叉点。 多点交叉：是两点交叉的推广，一般较少使用。 一致交叉( 又称均匀交叉) 是通过设置屏蔽字，来决定新个体的基因如 何继承父代个体中相应的基因。当屏蔽字位为l 时，父代的两个个体相应 位互换生成两个新个体的相应位；如果屏蔽字位为o ，则父代的两个个体 的相应位直接复制给新个体的相应位。 根据不同的问题，可以采用多种不同的交叉方式，如部分匹配交叉、 顺序交叉和周期交叉等。对于复杂的多变量问题，一般说来，采用均匀交 太原理工大学硕士研究生学位论文 叉和两点交叉比一点交叉的效果要好。 变异 变异就是以很小的概率p ，( 变异概率) 随机地改变群体中个体( 染色体) 的某些基因的值。变异操作的基本过程是：对于交叉操作中产生的后代个 体的每一基因值，产生一个【o ，1 之间的伪随机数r a n d ，如果r a n d o 5 ，遗传算法就退化为随 机搜索，而遗传算法的一些重要的数学特性和搜索能力也就不存在了。 终止条件 因为g a 是随机搜索，几乎不可能找到精确的全局最优解，所以需要 设定停止准则。下面是几种常见的终止条件，当满足这些条件之一或者是 某几种的结合时，我们认为算法收敛，停止运行。 】) 依代数收敛：若当前群体代数 指定的收敛代数时，认为收敛。 2 ) 依概率收敛：若当前的收敛率 给定的收敛概率时，认为收敛。当前收 敛率指的是n 代前最好的个体得分与当前代中最好个体得分的比值。 3 ) 依群体收敛：若当前群体平均得分群体中最好的得分 0 ) 4 ， 在整个解空间均匀散布，n 。个个体，计算这些个体的得分 5 ， 选择最好的n 。个个体，分别作为n 。个子群体的初始中心c ? ， n r 卜0 ， o 6 e n di f 7 f o r 每一个子群体的中心c | 3 3 太原理工大学硕壬研究生学位论文 8 f f - t ，+ l 9 在c 的周围，按某个分布函数散布品，个个体 1 0 计算这些个体的得分 11 从这s o f + 1 个个体中选择最好个体作为予种体新的t i - 一t l , c ： 1 2 ，e n d f o r 1 3 f o r 每个子群体， 1 4 i “子群体i 已成熟) 15 i f ( 全局公告板未满) 1 6 在全局公告板中记录该局部最优解 1 7 e l s ei f ( 子群体i 的得分优于全局公告板的一个解) 1 8 该子群体得到的局部最优解替代较差的解 1 9 e n di f 2 0 e n d i f 2 1 e n d i f 2 2 。e n d f o r 2 3 e n dw h i l e 趋同操作的停止准则：某子群体的得分在连续的若干代内没有增长 我们就认为该子群体成熟，趋同操作终止。 m e c 的停止准则：若连续若干个成熟子群体得到的解不优于全局公 告板汜录的所有的解，m e c 停止。 我们所定义的趋同操作是局部搜索，从一个初始解开始，通过步骤7 一1 2 的操作，直至找到一个局部最优解( 子群体成熟) 。异化操作定义为 全局搜索，它包含两个功能：1 ) 个体通过全局竞争，选择较好的解作为 子群体的初始中心，由算法中步骤3 6 实现；2 ) 从趋同操作得到的局部 最优解中选择所需要数目的较好的解作为全局最优解，由步骤1 3 - 2 2 实 3 4 太原理工大学硕士研究生学位论文 现。 ( 4 ) m e c 的特点 i ) m e c 继承了g a 的“群体”和“进化”的思想，区别是进化的运 算不同，因而m e c 具有g a 的基本优点。 i i ) 把群体划分为子群体，在此基础上定义的趋同和异化操作分别进 行勘探和开采，这两种功能是非对立的，是协调的，因而便于分别提高效 率。 i i i ) 结构上固有的并行性。 i v ) m e c 可以记忆不止一代的进化信息，这些信息可以指导趋同和异 化向着有利的方向进行。 3 三个基本机制 近二十多年来，人们进行了许多探索，从不同的角度改进g a ，但是 在提高效率与解决早熟两方面的效果并不理想。对于遗传算法性能很难有 明显改进，而m e c 能够显著提高计算效率和收敛性能主要是山于机制上 的原因【2 3 6 3 7 】。 m e c 的定向机制 遗传操作结果是不可预知的 3 8 。首先介绍两个术语：多表象性和多 基因性。多表象。陛( p l e i o t r o p y ) 指的是单一的一个基因可能同时影响一系列 的表象。多基因性( p o l y g e n y ) 指的是单一的一个表象可能同时由许多基因的 交互作用决定的。由于多表象性和多基因性的共同作用，“一对多、多对 一”的交互影响，遗传操作的结果一般是不可预知的。因而不易控制进化 的方向，使得o a 的性能改进变得困难。 而在m e c 中，进化操作趋同和异化都是定向的操作。趋同操作使各 个子群体向各自的局部最优的方向变化，异化操作使优胜予群体向全局最 优的方向变化。 3 5 太原理工大学硕士研究生学位论文 m e c 的记忆机制 遗传算法没有很好地利用计算机的记忆能力。“生物进化没有记忆，有 关产生个体的信息包含在个体所携带的染色体的集合以及染色体编码的 结构之中”。模拟生物进化的遗传算法也是这样，g a 关于环境的所有信息 郡保存在当前群体中的所有的个体中。若这些信息在进化过程中没有遗传 给后代，则这些信息都没有保留下来。换句话说，g a 没有充分地利用从 环境得到的信息指导进化的方向，造成g a 的计算效率较低。 m e c 与g a 不同，m e c 可以记忆若干代的个体的信息，并可以直接 利用这些信息指导进化的方向。正是利用了m e c 的这种汜忆机制，丌发 出了多种改进的趋同和异化策略，指导进化的方向，并进一步提高m e c 的计算效率： m e c 中勘探与开采的协调机制 许多学者从勘探与开采角度分析搜索算法。在g a 中，遗传算予交叉 和变异起“勘探”作用，选择起“开采”作用。然而，在g a 中这两个功 能并不协调，甚至还有许多学者认为在g a 中这两种作用是对立的，这也 是g a 计算效率不高的主要原因之一。关于这个问题的详细讨论请参考 a e e i b e n & ca s e h l p p e r s 关于勘探与丌采的总结，持有这种对立观点 的 弭究人员有x q i & f p a l m i e r i ，l j e s h e l m a n & j d s c h a f f e r 3 9 ，k a ， d ej o n g & w m s p e a r s ，l j e s h e l m a n & r a c a r u a n a ts t s u t s u ie t a l 。 正是由于为了使勘探与开采协调工作的目的，我们建立了m e c 的框 架 2 。在m e c 中，进化操作“趋同”起开采的作用，“异化”起勘探的作 用。重要的是，这二者是相对独立的，可以进行单独开发，且二者是非对 立的。趋同对系统从环境得到局部信息加以开采，迅速搜索局部的最优。 而异化操作在整个解空间进行搜索，选择较优的个体作为中心创建新的予 群体。这两种操作是协调工作的。 由于上述的m e c 与g a 不同的机制，使得m e c 能够比s g a 的计算 效率一般提高5 0 以上。并能够开发出多种不同的趋同和异化策略，指 3 6 太原理工大学硕士研究生学位论文 导进化的方向，进一步提高m e c 的计算效率。 4m e c 的研究成果 ( ) 收敛性证明 在文献 4 0 4 1 中，进行了m e c 算法的收敛性研究，获得了m e c 算 法在离散状态和连续状态下的收敛性，对收敛效率获得了部分成果。解决 的关键技术在于：1 ) 离散状态空间中运用马尔可夫链、吸引域、局部最优 状态等技术获得了收敛性证明。2 ) 在连续状态空间中运用函数的勒贝格测 度，用有限的区间逼近连续空间，即由离散逼近连续获得了连续状态空阃 的收敛性证明。 ( 2 ) m e c 用于非数值优化问题 采用m e c 已经成功地解决了一些非数值优化问题 4 2 ，如t s p 、 j o b s h o p 、系统动态建模和图的最大团问题等。对于这些问题，m e c 都 能够成功地解决编码、趋同异化策略的构造，并比采用其它进化计算方法 在解的精度、计算效率和收敛性能等方面都优越，说明m e c 具有良好的 对问题的适应性和拓展性。其中在求解图的最大团问题中，开发了 m c p m e c t 算法。采用国际组织“离散数学与理论计算机科学( d i s c r e t e m a t h e m a t i c s t h e o r e t i c a lc o m p u t e rs c i e n c e ，d i m a c s ) ”提供的3 0 多个标 准测试图形进行测试，测试结果表明：m c p m e c l 算法的性能明显优于 其它许多算法，如启发式遗传算法，煺火复制启发算法。 ( 3 ) 采用m e c 求辫多目标优化问题 丌发了求解多目标优化的m e c 算法 3 4 ：p a r e t o m e c 和s p m e c ( s c o r e dp a r e t om e c ) 。这两个算法根据m e c 和p a r e t o 的原理求解多目标 优化问题。采用多目标优化领域常用的函数进行性能测试，与当自u 世界公 认的最好的多目标优化算法s p e a ( s t r e n g t hp a r e t oe v o l u t i o n a r y a g o r i t h m s ) 相比较，对于凸的，非凸的，离散的测试函数，这两个算法与s p e a 性能 大体相当；而对于非均匀的测试函数，这两个算法的性能明显优于s p e a 。 3 7 太原理工大学硕士研究生学位论文 ( 4 ) 并行m e c 的研究 在集群计算机上实现了主从式并行m e c 4 3 4 4 】，分析得到了计算加 速比的公式，并与实验数据吻合。有关并行m e c 的研究将在第六章详细 介绍。 ( 5 ) m e c 的应用研究 m e c 自从提出以来，已经应用到了很多领域，包括在图像分析、经 济预测系统的构建、自动控制方向上的应用以及将m e c 用于非数值优化 问题中，下面就这方面的应用研究给出一个概述。 在图像分析方面，有如下几方面的应用：1 ) 在文献 4 5 中，采用