（电力系统及其自动化专业论文）并行遗传算法的分布式实现.pdf

华中科技大学硕士学位论文 a b s t r a c t s t r o n gc o m p u t i n gc a p a b i l i t yi st h ef o u n d a t i o no fs c i e n t i f i cr e s e a r c h a l lt h et i m e ，t h e p a r a l l e lc o m p u t a t i o nm e a n i n gs y n c h r o n i s me x e c u t i o ni s t h ef o c u so fs t u d y ；w i t ht h e p r o g r e s s e s o fs o f t w a r e ，t h ed i s t r i b u t e d c o m p u t a t i o nm e a n i n gs c a t t e r i n g s i n s p a c ew a s d e v e l o p e dr a p i d l y i nr e c e n ty e a r s g e n e t i ca l g o r i t h mi sah n do fo p t i m i z a t i o na l g o r i t h mu s i n ge x t e n s i v e l y ；i t sn a t u r a l p a r a l l e la n dl i t t l e d a t a c o n t r o ld e p e n d e n c e t or e a l i z et h ep a r a l l e lc o m p u t a t i o no f g e n e t i c a l g o r i t h mh a sr e m a r k a b l ea d v a n t a g e st h a no t h e rr e l a t i v e l yo p t i m i z a t i o nm e t h o d s p a r a l l e l g e n e t i ca l g o r i t h m su t i l i z et h et r e a t m e n ta b i l i t i e so fs e v e r a lp r o c e s s o r st o s e a r c hi nm o r e e x t e n s i v es o l v i n gs p a c e ，c a l lb eu s e di nc o m p l i c a t e ds y s t e mo p t i m i z a t i o n ，d e s i g n i n ge t c s o i ti sa l w a y st h ee m p h a s i so f g e n e t i ca l g o r i t h mr e s e a r c h t h i sp a p e ri n t r o d u c e sg e n e t i ca l g o r i t h m ，d e v e l o p m e n t so f p a r a l l e lc o m p u t a t i o n sa n d a p p l i c a t i o n so fg e n e t i ca l g o r i t h m t a k i n gs i m p l eg e n e t i ca l g o r i t h ma se x a m p l e ，t h i sp a p e r d e s c r i b e st h ec o m p u t a t i o np r o c e s sa n dt h ec h a r a c t e r i s t i c so fg e n e t i ca l g o r i t h m a f t e rt h e s u m m a r i z a t i o no f m e t h o d st oi m p r o v eg a sp e r f o r m a n c e ，t h i sp a p e rs h o w ss o m em o d e l so f p a r a l l e lg e n e t i cm g o d t h ms u c h 孙s i m p l ep a r a l l e lm o d e l ，m a s t e r s l a v ep a r a l l e lm o d e l ， c o a r s e - g r i np a r a l l e lm o d e l ，f i n e g r a i np a r a l l e lm o d e la n dt h ea n a l y s i so ft h o s ep a r a l l e l m o d e l s p a r a l l e lg e n e t i ca l g o r i t h mc 锄b er e a l i z e db yp a r a l l e lc o m p u t e ro rd i s t r i b u t e ds y s t e m r e a l i z a t i o no f d i s t r i b u t e ds y s t e mb a s e do np c si sc o m p a r a t i v e l yc o n v e n i e n tf o rt h eu s i n go f p a r a l l e lc o m p u t e ri s n tw i d e c o m m u n i c a t i o n i st h ef o u n d a t i o no fd i s t r i b u t e ds y s t e m ；t h i s p a p e ri n 仃o d u c e ss o m ec o m m u n i c a t i o np r o t o c o l ss u c ha sc o r b a ，d c o m ，j a v a r m ia n d t h e i rd i s t i n c t n e s s d e s c r i b e s 也es t r u c t u r eo fs o f t w a r eb a s e do nc o r b aa n dh o w t ow r i t ea d i s t r i b u t e dp a r a l l e ls y s t e mi nc + + b u i l d e ra n dv i s i b r o k e re n v i r o n m e n t a c c o r d i n gt ot h ec h a r a c t e r i s t i co fd i s t r i b u t e ds y s t e m ，t h i sp a p e rg i v e sa ne n h a n c e d c o a r s e g r a i nm o d e l ，r e a l i z e si tu s i n g t h ea c k l e yf u n c t i o na n dt h e na n a l y s e st h ep a r a m e t e r s e f f e c to np e r f o r m a n c e a tl a s t , t h i sp a p e rm a k e st h et h r e eg o r g e sp l a n t su n i t sc o m m i t m e n t u s i n g t h i sd i s t r i b u t e d p a r a l l e lg e n e t i ca l g o r i t h m d i s t r i b u t e d p a r a l l e lg e n e t i ca l g o r i t h m i sau n i v e r s a l e c o n o m y , 1 1 i g h - p e r f o r m a n c e o p t i m i z a t i o nm e t h o d ；t h e r e f o r e t h e r ea r ee x t e n s i v ea p p l i c a t i o n p r o s p e c t so f i t k e y w o r d ：g e n e t i ca l g o r i t h m ，d i s t r i b u t e dp a r a l l e lc o m p u t e ， c o r b a ， c o a r s e - g r a i n ， u n i t sc o m m i t m e n t i i 华中科技大学硕士学位论文 1绪论 1 1 遗传算法的概述与发展 自然界是一个和谐平衡、多姿多彩的系统，随着科学研究的发展，在很多领域 人们开始深入学习自然界的优点。生物进化过程蕴含着一种搜索和优化的先进思想， 将这种思想用于科学研究和工程技术领域而发展起来的方法，就是遗传算法。 遗传算法g a ( g e n e t i ca l g o r i t h m ) 模拟自然界中生物进化的发展规律，在人工系 统中实现特定目标的优化，是一种建立在自然选择原理和自然遗传机制上的迭代式自 适应概率性搜索方法【1 l ，它模拟生物染色体的结构来组成变量，使用变量群体来模拟 生物群体，用选择和变异算子使变量在某个基因上发生变化，用适应值来衡量变量变 量的好坏，迭代过程中的变量如同进化的生物，逐渐趋向高级。 遗传算法和其他的科学技术一样，都经历了一段逐渐发展壮大的过程。早在上世 纪5 0 年代后期，一些生物学家就着手采用电子计算机模拟生物的遗传系统，尽管这 些工作纯粹是研究生物现象，但是其中也使用了现代遗传算法的一些方法，比如，1 9 6 0 年美国人a s f r a n s e r 为了建立生物的表现型方程，使用了o 一1 字符串来表示方程中 的三个未知数。6 0 年代，芝加哥大学教授j h h o l l a n d 在研究自适应系统时，提出了 系统本身和外部环境相互协调的遗传算法，1 9 6 8 年，j h h o l l a n d 教授又提出了模式理 论，它成为遗传算法的主要理论基础。j d b a g a y 在关于博弈论的一篇论文中，第一 次正式提出了遗传算法g a ( g e n e t i ca l g o r i t h m ) 这个名称。1 9 7 5 年，j h h o l l a n d 教 授的专著自然界和人工系统的适应性( a d a p t a t i o n i n n a t u r a l a n d a r t i f i c i a ls y s t e m ) ) ) 正式出版，全面介绍了遗传算法1 4 】，这一事件被看成遗传算法问世的标志，j h h o l l a n d 也被视作遗传算法的创始人。 8 0 年代期间，许多研究工作者积极从事遗传算法的研究，使遗传算法成为人工智 能领域的又一个研究熟点。1 9 8 7 年，d l a w r e n c e 教授总结了人们长期从事遗传算法 的经验，公开出版了遗传算法和模拟退火( g e n e t i ca l g o r i t h ma n ds i m u l a t e d a n n e a l i n g ) ) ) 一书，以论文集的形式用大量实例介绍遗传算法。1 9 8 9 年，d e g o l d b e r g 博士出版了遗传算法一搜索、优化及机器学习( g e n e t i ca l g o r i t h m s - - i n s e a r c h ， o p t i m i z a t i o na n dm a c h i n el e a r n i n g ) ) ) ，全面系统的介绍遗传算法，使这一技术得到普 华中科技大学硕士学位论文 及提高。 由于研究遗传算法的科学工作者越来越多，1 9 8 5 年，在美国举行了第一届遗传算 法国际学术会议( i m e m 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 ) ，与会者交流运用遗 传算法的经验，以后，每两年都举行一次这种会议。 9 0 年代，遗传算法不断向广度和深度发展。这一时期，关于遗传算法的专著有十 多本，比如1 9 9 1 年，d l a w r e n c e 出版了遗传算法手册( h a n d b o o ko fg e n e t i c a l g o d t h m ) 一书，详尽介绍了遗传算法的工作细节， 1 9 9 6 年，z m i c h a l e w i c z 的专 著遗传算法+ 数据结构= 进化程序( g e n e t i ca l g o r i t h m + d a t as t r u c t u r e = e v o l u t i o n p r o g r a m s ) ) ，深入讨论了遗传算法的各种专门问题。 遗传算法以概率性的搜索来查找变量空间，具有良好的稳定性，收敛性，有着 其他搜索方法所缺乏的独特优点，但是也存在一些需要深入研究和有待解决的课题， 目前，遗传算法的研究内容主要有以下几个方面： 1 适用范围问题：一般而言，对同一个问题，存在两种或两种以上的解决方法， 比如对同一个优化问题，即可以使用遗传算法，又可以使用模拟退火，到底使用那一 种方法更好，现在通常是将两种实现进行比较才能得到结果，而很少能根据问题的性 质进行判断，同样，对于同一种方法，也存在适合应用在那些问题上的问题。遗传算 法虽然已经在很多领域得到了应用，研究工作者也做了很多遗传算法与其他算法计算 性能的比较分析研究，但是现在还没有一种理论能解决遗传算法的使用范围问题，即 那些问题适用于用遗传算法解决，那些用其他的优化算法更好。对算法的适用问题， 1 9 9 5 年，s t a n f o r d 大学w o l p e r t 和m a c r e a d y 教授提出了n of r e el u n c h ( 简称n f l ) 定理f 7 】其结论概括如下： 假定有a ，b 两种任意( 确定或随机) 算法，对于所有问题集，它们的平均性能是 相同的( 性能可采用多种方法度量，如最优解、收敛速度等) ，即 p ( e if ，n ，4 ) = p ( oi ，n ，b ) ij 其中，0 为个体适应度的概率曲线，f 为适应度函数，n 为群体大小。 n f l 定理的证明可参见相关文献，y uc h ih o 和d a v i dl p e p y n e 对于上述结论用 矩阵地方式从另一个角度进行了解释【引，例如，如果遗传算法求解某问题集时的性能 比模拟退火的性能好，那么会有模拟退火求解另一问题集时的性能比遗传算法的性能 2 华中科技大学硕士学位论文 好，平均所有的情况，两种算法的性能是相同的，根据n f l 定理，算法性能的好坏 不仅与一定的问题有关，而且与个体适应度的概率曲线c 有关，不能随便应用到任何 问题的求解中。 n f l 定理说明了优化算法在问题集上的性能不平衡性，它从总体上讨论了优化算 法的适用性，但是正如w o l p e r t 和m a c r e a d y 指出的，n f l 本身还存在一些问题，对 算法自身性能的理解还需要完善，目前该理论还存在需要商榷的地方。对于某个具体 的算法，它也没有说明那些问题适用该算法较好，那些应用该算法性能不好，在这个 方面，还有大量的理论工作要做。 2 遗传算法的数学基础：遗传算法虽然已经得到了广泛的应用，但是遗传算法 的理论基础仍然很薄弱，收敛性分析，性能分析仍然是一个很困难的问题。遗传算法 的数学基础主要基于j h h o l l a n d 教授的模式理论，它是证明遗传算法的收敛性的传统 手段，模式定理中模式适应度难以计算和分析，b e t h k e 运用w a l s h 函数和模式转换发 展了有效的分析工具。但是随着遗传算法应用的广泛，它的应用方式也不断地发展， 引进了一些新的算子。对这些新形式的遗传算法，模式理论已经很难提供理论分析的 基础。近年来m a r k o v 链在遗传算法的收敛性分析中得到了很广泛的应用，g o l d b e r g 和s e g r e s t 首先使用m a r k o v 链分析了遗传算法，e i b e n 等用m a r k o v 链证明了保留最 优个体的遗传算法的遗传算法的概率性全局收敛，r u d o l p h 用齐次有限m o r k o v 链证 明了带有复制、交换、突变操作的基本遗传算法收敛不到全局最优解，不适合于静态 函数优化问题，建议改变复制策略以达到全局收敛。b a c k 和m u h l e n b e i n 研究了达到 全局最优解的遗传算法的时间复杂性问题。虽然m a r k o v 链在遗传算法的数学分析中 应用较广，但是它分析的对象基本上都是简单遗传算法模型，对于复杂的遗传算法， 应用m a r k o v 链依然是很困难的。对于遗传算法的性能分析，现在还没有理论上的方 法，一般是通过试验，对不同参数的计算性能进行比较来确定最后的参数，但是经过 多年的实践也总结出了遗传算法计算过程中的一些特性，如遗传算法的局部搜索能力 差等，为改善遗传算法的性能提供了一定的指导。从总体上来说，缺乏具体的性能分 析限制了遗传算法更大规模的应用。 3 遗传算法性能的提高：遗传算法用于解决优化问题的效果较好，但是随着遗 传算法应用范围越来广泛，解决的问题越来越复杂，计算量也不断增大，如何提高遗 传算法的性能是近来研究的重点方向之一，另外，遗传算法有早熟的缺点，如何改迸 华中科技大学硕士学位论文 遗传算法的收敛性也非常重要。提高遗传算法计算性能的方法较多，如调整计算参数， 设计新的算子，运用混合遗传算法，并行处理等。调整参数指调整遗传计算过程中群 体规模，适应度计算，交叉，变异等的计算参数，如增大群体规模，使用变化的交叉 率变异率等。混合遗传算法一般在遗传算法的某一计算过程中应用其他的优化算法， 如将模拟退火算法应用到遗传算法中调整交叉率。随着计算机技术的发展，近来并行 遗传算法受到了越来越大的关注。并行遗传算法利用遗传算法的并行性，使用多个处 理器进行处理，可以处理更多的群体，在更大的空间进行搜索，与调整参数的方法相 比，它更简单，与混合遗传算法相比，它更通用。大部分的并行遗传算法是用并行机 实现的，并且得到了大量的理论结果与实际应用，随着分布式计算的发展，利用分布 式系统实现并行遗传算法越来越引起了研究者的注意。分布式系统可以采用现在通用 的p c 机，与并行机实现相比，分布式系统具有经济性，但是另一方面，由于分布式 系统的物理分散度较大，利用分布式系统进行并行计算时要加入同步协调机制，系统 中的处理器差别大，因此运行速度比并行机慢，它目前主要应用在一些非实时性的问 题上，如大型的系统设计与优化。 遗传算法一出现就受到了科学工作者的广泛关注，目前，遗传算法发展迅速，己 被广泛应用于系统优化，机器学习，工程控制，模式识别，人工智能，故障诊断，以 及计算机技术等领域【2 ，3 ，9 1 ，取得了良好的效果。随着遗传算法的基本原理，方法及其 应用的深入研究m 1 1 】，其应用范围也越来越广泛，为许多传统的优化方法难以解决的 优化问题提供了崭新的途径【1 0 , 1 2 , 1 3 , 1 4 , 1 5 。 1 2 分布式并行计算的发展 分布式并行计算指利用分布式系统同步协调的进行运算，它在分布式计算的过程 中使用同步信号来协调各个分布任务的执行。分布式计算的特征是空间上的分散，当 这种特性与时间上的并行性相结合时，就是分布式并行处理，实际上，分布式与并行 一直是密不可分的，在并行机中，处理嚣本身也是分散的，在分布式系统中，软件的 执行也离不开同步。 早期的高性能并行计算主要是利用并行机来实现，近2 0 年来，计算机计算性能 的提高，尤其是p c 机性能的提高和普及，使昂贵的大型机、数据中心和无尘微机室 逐渐成为历史，取而代之的是桌面计算机，工作组服务器，以及小型机，由这些计算 4 华中科技大学硕士学位论文 机组成的分布式系统已经在逐步取代并行机的作用。 早期的大型机不仅开发费用高，而且维护不方便，软件设计复杂，主要应用于研 究所和国防部门，人们一直在研究种可以将各种较小，功能较简单的计算机组成一个 系统的方法，比起原来的集中式系统，这种系统具有坚定性强，维护方便，扩充容易， 效率较高等优点。1 9 7 6 年，美国卡内基梅隆大学用5 0 台l s l l l 型微型计算机组成了 一个分布式系统c m ，此后，加州大学伯克利分校研制了x 树系统，威斯康星大学麦 迪逊分校研制了a r a c h n e 系统，此外还有m i c r o n e t 、l o c u s 、c m d s 等等系统。 分布式系统的出现就产生了分布式处理，最开始的主一从机系统中由各个哑终端 处理用户输入输出，计算，查询等处理集中在主机上，随着硬件系统的不断完善，终 端具有的能力越来越强，不仅可以处理输入输出，还可以参与部分计算处理，最后， 由于单个计算机的功能已经能够处理以前由“服务器“承担的功能，这种主一从式的 系统也就失去了物理上的对应意义，而变成了软件服务之间的s e r v e r c l i e n t 系统。 如硬件系统一样，软件系统也是不断发展的。早期的程序设计比较简单，不需要 跨越进程，更不用跨机器平台，采用单一语言就可以实现。随着软件复杂度的提高， 某些复杂工作即使利用面向对象技术也不能由单一进程完成，需要多个进程彼此分 工，相互合作。随着计算机通讯范围从进程到局域网，到互联网，分布式系统的范围 也越来越广泛，软件技术的发展使分布式计算不仅可以利用局域网内的资源，而且可 以利用接入网络的任一台机的计算能力。不仅有常用的t c p i p ，i p x s p x 协议等，还 有o d b c ，r p c ，m o m 等等应用在不同情况，各有特点的通讯技术及协议。这些通 讯技术和规范的发展，给分布式计算的软件开发提供了灵活多样的实现方式。 分布式并行今后的发展不仅与硬件的发展有关，而且与软件技术的发展密切相 关，软件方面，面向对象程序设计方法与通讯技术的发展，使分布式系统越来越可靠， 安全性越来越好，联系范围也越来越广。当前的分布式系统都要求用户对各处理器之 间的传输做出一定的处理，可能是最低级的处理机通信，也可能是在c o r b a 、d c o m 等协议上的通信，对用户的要求较高，同时，分布式系统具有很大的不确定性与伸缩 性，人工处理一个大系统中的交互传输是一个十分困难的问题。目前，分布式计算研 究的重点是分布式软件的自动生成，在软件的自动编译方面已经取得了较大进展。由 于软件设计与同步措施方面的复杂性，目前的分布式处理主要集中在局域网范围内， 侣是如c o r b a ，d c o m 等分布式计算标准都已经具有了互联网传输能力，将来可能 5 华中科技大学硕士学位论文 有更好的软件传输标准，也可能会出现种更高效的设计方法，以适应大范围内多处 理器的同步协调需要而不是采用现在的消息策略，目前，很多计算机厂家已经在这个 领域进行了很多研究，并提出了一些更新的概念如网格计算等，可以相信，利用互联 网将目前无数的处理器联系起来进行计算的分布式系统在不久的将来会变为现实。在 硬件方面，一方面，虽然目前处理器的性能提高已经越来越困难，但是随着新材料与 新工艺技术的发展，单处理器的处理能力肯定将越来越强，另一方面，新的传输器件 如光纤等的应用使计算机间通讯速度得到了大幅度的提高，将来的分布式系统的传输 通道将是一个高速公路，数据速度飞速提高，通信消耗时间在整个分布式计算中所占 地比例将越来越低。 1 3 分布式并行遗传算法计算的研究意义和内容安排 人们认识自然界的能力是与计算能力密切相关的，古代的科学由于没有计算能力 的支撑，所以进展十分缓慢，范围也不广，而电子计算机的发明为现代科学的发展提 供了强大的动力。 尽管电子计算机的计算能力不断地增长，但是科学技术的飞速发展对计算能力的 要求永远没有止境。提高计算性能的基本途径主要有三种，一是提高器件的运行速度， 如提高处理器芯片地处理速度，增大存储器的容量以及开发新型计算机等，二是改进 系统结构，如开发并行处理机和分布式计算，三是应用计算算法，将计算能力集中在 需要重点计算的区域，对一些细节问题进行忽略以提高计算效率，此类方法有很多， 如线形规划、非线形规划、动态规划等，遗传算法也是其中之一。 目前计算机元件主要是应用微电子技术在硅片上生成微电路，由于物理条件的限 制，要进一步提高传统结构计算机的集成度和速度已经比较困难，为此人们开始开发 新的计算机材料，如纳米计算机，光计算机，量子计算机等，尽管这些新型计算机都 取得了一定的进展，但是短时间不太可能得到实际的应用。并行机的出现使计算机的 数据处理和计算能力大大的提高了，目前所有的高性能计算机基本上都是并行机，但 是并行机的硬件结构比较复杂，研制费用高，扩展性差，而且开发充分发挥并行机性 能的并行软件系统也非常困难，所以在并行机方面的进展比较缓慢。 发展最快的是p c 机，随着性能的不断提高，现在的p c 机已经具有以前的小型 机，中型机甚至大型机的性能，并且得到了广泛的运用。由于p c 机的标准化结构， t 6 华中科技大学硕士学位论文 丰富的软件基础。基于现有的p c 机的分布式处理系统近些年来得到了很大的发展。 分布式计算极大的提高了计算能力，如何利用这一计算优势，促进分布式计算在各个 领域地应用。是迫切需要解决的问题。 分布式计算提高计算能力，是充分利用单机之外的计算资源，它不仅需要硬件的 支持，而且需要软件设计技术和计算过程本身的结构支持。对于一个紧密耦合的串行 计算过程，由于存在数据和控制上的紧密相关性，在分布式计算环境中，将这种计算 过程进行分解比较困难，而且还会增加软件设计的复杂度。因此，一个本身支持并行 性的计算过程是提高分布式计算系统计算能力必需的。遗传算法本身就具有并行性， 这种并行性不仅表现在遗传算法的隐并行性上，而且遗传算法种群中各个个体之间 以及各个种群之间都具有并行性，如果在分布式系统中利用遗传算法的这些特性，开 发具有分布式并行计算能力的遗传算法，将大大提高遗传算法的计算能力，解决更大、 更复杂系统的优化和设计问题。 利用并行机实现遗传算法并行的研究较早，得到的研究成果也较多，但是利用分 布式系统实现遗传算法并行的研究还不多，这一方面是因为分布式系统是近年才引起 人们的相当关注，另一方面是因为分布式系统实现的并行目前在性能上不如利用并行 机实现的并行。但是分布式并行也有它的优点：使用广泛，它可以基于普遍使用的p c 机，在没有条件使用并行机的情况下，使用分布式系统实现的并行遗传算法可以用于 对实时性要求不高的场合，如复杂系统的离线分析或设计等等，因此也很有研究的必 要。 本文讨论了分布式并行遗传算法的几种设计结构以及一种改进的粗粒度分布式 并行遗传算法的实现，文章章节安排如下： 第一章绪论介绍了遗传算法和并行计算的情况。 第二章介绍了遗传算法计算的基本过程，遗传算法的特性和改进遗传算法性能的 方法，以及并行遗传算法的几种模式。 第三章说明了分布式并行计算的发展过程，实现分布式并行的几种关键技术，这 些技术的比较，以及基于c o r b a 的分布式并行系统的结构和特性。 第四章一步步的说明了在c h b u i l d e r 和v i s i b r o k e r 发环境下如何实现一个分布 式并行系统，并以a e k l e y 函数为对象，介绍了一种改进的粗粒度分布式并行遗传算 法的实现，并分析了该算法的计算性能。 _ 一 7 华中科技大学硕士学位论文 = = = = = = = 穹= = = = = = = = = 昌= 昌= 昌昌昌暑= = 毒毒葛昌= = = = = 皇篁= 薯= = 葛= ! 第五章介绍了分布式并行遗传算法在水电厂机组负荷分配中的应用。 第六章为全文总结。 华中科技大学硕士学位论文 2 遗传算法 2 1 遗传算法的一般结构 遗传算法是一种基于生物自然选择与遗传机理的随机搜索方法，和传统搜索算法 不同，遗传算法从一组随机产生的初始解，称为种群( p o p u l a t i o n ) ，开始搜索过程， 种群的每个个体是问题的一个解，称为染色体，染色体一串符号组成，比如一个二进 制字符串，这些染色体在后 续迭代中不断进化，称为遗 传在每一代中用适应值来 衡量染色体的好坏，生成下 一代染色体，即后代。后代 是由前一代染色体通过交叉 或者变异运算形成的，新一 代形成后，根据适应值的大 小淘汰部分后代，保持种群 的大小是个常数。适应值高 的染色体被选中进行遗传的 概率较高，这样，经过若干 代之后，算法会收敛于最好 的染色体，它很可能就是问 题的最优解或者次优解。遗 传算法的一般结构可描述如 图】一l 。设p ( t ) 和c ( t ) 分别表示第t 代的双亲和后 代，使用计算机抽象语言来 表达时程序过程如下： b e g i n t = 0 ： 图l 一1 遗传算法的计算过程 9 华中科技大学硕士学位论文 初始化p ( t ) ： 评估p ( t ) w h i l e 不满足终止条件d o 选择p ( t ) 获得c ( t ) 对c ( t ) 进行重组 p ( t + 1 ) = c ( t ) ： t = t + 】： e n d 由于遗传算法的发展，它的实现过程并不是固定不变的，选择，变异等遗传算子 的运算过程可能不一样，操作对象也可能不同，比如g o l d b e r g 提出的遗传算法形式就 是先重组出一个子代，然后从子代和父代中选择生成下一父代【5 6 】。 2 2 遗传算法的特点 遗传算法模仿的是自然界的进化过程，遗传算法在以下几个方面不同于传统的优 化方法，g o l d b e r g 总结为如下几点： 2 2 1 遗传算法运算的是解集的绽码，而不是解集本身 遗传算法交替的在编码空间和解空间中工作，它模仿生物的染色体结构对变量进 行编码，编码后的变量如同生物的基因链一样。计算时在编码空间对染色体进行遗传 运算，而在解空间对解进行评估和选择，选择算子联结了染色体与它所表达的解的性 能。在计算过程中的这种空间转换，将遗传算法的计算对象与具体的问题区分开来， 使遗传算法的计算与所要解决问题的具体细节区分开来，在解的收受过程中不需要了 解问题的内在性质，所以遗传算法具有通用性，可以处理任意形式的目标函数和约束， 无论是线性的还是非性的，离散的还是连续的，甚至混合的搜索空间。 如何将问题中的变量转化为编码表达的染色体是遗传算法的关键问题，h o l l a n d 的编码方法是二进制串，但对于许多遗传算法的应用，这种简单的编码方法很难直接 描述出问题的性质，近1 0 年来，针对特殊问题，提出了各种非o 一1 串的编码方法， 例如约束优化的实数编码，组合优化的整数编码。选择适当的编码方式是遗传算法的 基础，对于任何应用问题，都必须将解的表达方式和适用于该表达方式的遗传算子结 1 0 华中科技大学项士学位论文 合起来分析考虑。 2 2 2 遗传算法的悬一种并行的搜索算法 遗传算法的并行性来自两个方面：一方面，遗传算法模仿的是自然界的进化过程， 计算时模仿了自然界的多样性，进行计算的对象不是单个解而是一个群体。通过保持 一个潜在解的种群进行多方向搜索，在计算时，各个个体的适应值计算之间是相互独 立的，即没有控制上的依赖，也没有数据上的依赖，因此是可以并行处理的，不仅如 此，由于遗传算法可以从一个初始产生的随机种群，通过计算达到最优解，因此，如 果是多个种群进行计算，那么这多个种群之间也是相互独立的，可以并行处理。另一 方面，j h h o l l a n d 教授的模式理论的隐并行机理说明，如果遗传算法的群体规模为n ， 那么它可以处理的模式为o ( n 3 ) 4 3 5 1 ，因此，遗传算法是一种多点齐头并进的并行 算法。 2 2 3 遗传算法只使用报一信息，而不使用其他辅助知识 一般来说，优化算法是收敛于最优解的一系列计算步骤。多数经典的优化方法基 于目标函数的梯度或者高阶导数产生一个确定的计算系列，需要将所解决的问题用数 学函数表达，而且要求数学函数的一阶或者二阶导数存在，这类方法只作用于解空间 的单个解，通过相邻解的比较，这个解沿着收敛方向不断改进，随着迭代的进行，最 后收敛子最优解。遗传算法在搜索过程中，借助选择，交叉，突变等操作，使解在编 码以及解空间内变化，这种变化是随机的，因此不需要了解所解问题的内在性质，只 需要用适应值来控制变化的方向，体现适者生存的自然选择规律，无需添加任何额外 的作用，就能使群体的品质不断得到改进。 2 2 4 遗传算法采用概奉的，面不是麓定的状杏转移规剐 根据自然的进化规律，进化的方向是不确定的。遗传算法中的初始群体一般是随 机产生的，采用的选择，交换，变异算子也是根据概率而进行运算，它控制的是期望 值而不是确定值，对相同的父群体，得到的子群体是不确定的。即使使用相同的计算 参数，每一次计算产生的群体，结果也往往不会完全相同。 遗传算法的搜索策略，即不是盲目式的乱搜索，也不是穷举式的全面搜索，它是 有指导的搜索，指导遗传算法执行搜索的依据是适应度，也就是它的目标函数，在适 l l 华中科技大学硕士学位论文 应度的驱动下，遗传算法逐步逼近目标值。 2 3 改进遗传算法性能的方法 遗传算法的性能主要包括收敛性和计算速度。收敛性主要是指遗传算法能不能收 敛到全局最优解，而计算速度就是指收敛到最优解所需要的时间。改进遗传算法的性 能主要有以下几个方面： 2 3 1 选择合适的编码方式 遗传算法的第步设计就是将解空间的值映射到编码空间，这种映射取决于编码 的方式。常用的编码方式有二进制编码，实数编码等等。 最广泛采用的编码方式是二进制编码，这种编码方式符合了计算机的表达方式， 将解转换成二进制字符串后，交叉和变异操作可以在解的局部范围内进行。实现这种 编码和解码也比较简单。这种编码的缺点是编码长度，当变量个数较多或变量的精度 要求较高时，使用这种编码的染色体会变得很长，运用遗传操作时很不方便，搜索范 围较小，效率较低，而且占用的内存空间很大，不利于计算。 实数编码是另种应用较广的编码方式，相对于二进制编码，使用实数编码不用在 解空间和编码空间之间相互转化，避免了编码与参数间的转换操作所需的计算，以及 由此引起的量化误差，提高解的精度和运算速度，在理论上能以任意精度取得结果， 特别是在搜索空间较大时，实数编码的优势更为明显。但是实数编码遗传算法中交叉 与变异操作改造个体时，是通过改变构成个体的部分或全部实数( 而不是位) 实现的， 造成了个体转移矩阵呈现出特殊的模式，这种特殊模式使实数编码遗传算法相对于二 进制位编码更易于陷于局部最优解1 1 7 j 。 其他的编码方式也比较多f i s a g ，一般是结合所求解问题的实际情况设计，如解配 词问题时使用的a s c 码编码，解决最小生成树问题的边编码等。选择新的编码方式 的时候，必需保证码空间和解空间映射的唯一性，以及编码染色体的可行性、合法性， 而且在运算时一般要根据具体编码方式的不同，对交叉算子，变异算子进行适当地修 改，因此一个新的编码不仅需要考虑编码的计算效率，还要考虑遗传算子的设计，这 也是其他的编码形式推广的一个很大的障碍。 除了设计新的编码方式外，还有一种方法是对编码的编排顺序进行改进，比如对 1 2 华中科技大学硕士学位论文 多变量的优化，一般的二进制编码时是将各个二进制编码串连起来，如果调整一下编 码的位置，将各变量的相应位组合起来，则可以将搜索区域分成粗搜索区域和细搜索 区域，先搜索各变量的第一位，再搜索各变量的第二位，直到最后完成所有搜索【”】。 这种方法也可以提高计算性能。 2 3 2 诅蔓控铆参数 遗传算法中的控制参数主要是指群体规模，交叉率，和变异率，其中对算法性能 影响较大的是群体规模和交叉率。 群体规模就是群体中个体的个数，通常记为p o p s i z e ，如果群体是随机分布的，群 体规模越大，它对应的解空间越大，找到最优解的可能性也较大，反之，群体的规模 小，则群体的多样性变差，搜索空间变小，容易使算法收敛于一个局部最优解，即早 熟。 交叉是最重要的遗传运算，它同时对两个染色体操作，组合两者以产生新的后代， 交叉的最简单方法是单点交叉，即在双亲的染色体上随机的选一个断点，将断点某一 侧的基因位相互交换，从而形成两个新的后代，这种方法对于各种编码方式都适用。 交叉运算的目的是通过现有个体的重新组合得到新的搜索空间，遗传算法的性能在很 大程度上取决于采用的交叉运算的性能。 交叉率( 记为p c ) 定义为由交叉运算产生的后代数与种群中的个体数的比，它将 参加交叉运算的染色体个数的期望值控制为p c p o p s i z e 。使用较高的交叉率，同样的 一个群体可以达到更大的解空间，从而降低停在非最优解的机会，但是这个比率太高， 则会因搜索不必要的解空间而消耗大量的计算时间。 变异运算在染色体上产生随机的变化，一种简单的变异方法是替换一个或多个基 因。在遗传算法中，变异可以提供初始种群中不含有的基因，或找回选择过程中丢失 的基因，为种群提供新的内容。 变异率p m 定义为种群中变异基因数在总基因数中的百分比，变异率控制了新基 因导入种群的比例，如果变异率太低，一些有用的基因就不能进入选择，算法的搜索 性变差，不能从局部最优解跳出，影响了算法的收敛性；如果变异率太高，即随机的 变化太多，那么后代就可能失去从双亲继承的机会，遗传算法失去从过去的搜索中学 习的能力，变成了一个随机搜索的过程，增大了计算量。 1 3 华中科技大学硕士学位论文 从以上分析可以看出，改变控制参数对计算性能影响较大，由于迄今还没有理论 上的计算，所以这3 个参数的调整是遗传算法设计时的一个难点2 3 1 。 另一个方法是在计算过程中动态的改变参数f 1 4 】，因为在遗传算法的初期，需要保 持群体的多样性，以获得更大的搜索空间，防止算法陷于局部最优解，此时可以采用 较大的交叉率p c 和较大的变异率p m ：到遗传算法的后期，当群体已经收敛到最优解 附近时，就需要减少变化量，使搜索集中到最优解的附近，应该使用较小的p c 和p m 值。在计算的初期和后期采用不同的计算参数，可以提高算法的整体性能，但是p c ， p m 参数变化的时间与幅度仍然需要不断实验得出。 2 3 3 新的遗传算子 除了交叉算子，选择算子，变异算子以外，为了提高遗传算法的性能，还可以设 计使用其他的算子f 2 ”。 最常用的非标准算子是最佳值保留算子，标准遗传算法的收敛证明是基于群体规 模的无穷大和迭代次数的无穷大的，但是在实际中不可能有那么大的规模，为了保证 遗传算法能够以概率1 找到全局最优解，在遗传算法中引入了最佳值保留算子，即在 遗传操作结束后，用父代的若干个最优或者次优个体直接代替子代中的个体，这样保 证历代出现的优良个体不会自动丢失，只有产生更好的个体时才会被取代，并为下一 代遗传提供良好的母体。实际运算表明使用最佳值保留算子可以加快算法的收敛速 度，减少计算量。 除了最佳值保留算子之外，应用较多的还有确定算法搜索方向的算子( 如梯度算 子) 和重点搜索某一区域的算子( 如正交搜索算子) 等。梯度算子利用目标函数的梯 度或者在函数值附近作小幅的震动，以确定变量的下一步搜索方向，减少盲i + i 搜索的 范围。正交搜索算子采用正交表安排实验，在当前最优点周围采样试验点，期望从中 找到新的点，其适应值比当前最优点的适应值好，它在当前最优点的邻域内以最经济的 方式同时搜索多个点，因而效率较高。 2 3 4 其他方法 除了以上方法外，还有很多对标准遗传算法的改进措施，如双倍体遗传算法，加 速遗传算法【2 7 l ，小生境遗传算法i 矧等，还可以将遗传算法与其他算法结合起来以提高 算法的性能2 8 _ 2 9 3 1 3 3 】，如将遗传算法和模拟退火算法结合起来埘，将遗传算法和神 1 4 华中科技大学硕士学位论文 经网络算法结合。因为优化算法较多，遗传算法与其他算法相结合产生的新算法也较 多。 除此之外，还可以使用调整惩罚因子和增大随机搜索空间的方法来提高性能，惩 罚因子随着状态变量越限程度的增加而呈指数增长，更有利于协调惩罚函数值和目标 函数值之间的关系，加快收敛速度【2 5 , 2 6 。而采用更好的随机数发生器，则可以让群体 分布更均匀，多样性更好。 2 4 并行遗传算法 虽然遗传算法通常可以在合理的时间内找到满意解，但随着求解问题的复杂性及 难度的增加，提高遗传算法的运行性能就显得尤为突出。前面已经讨论了改进遗传算 法的性能的各种方法，这些方法的引进有定的效果，但是通常局限于某一类问题， 遗传算法是一种通用性很强的优化算法，如果引进的方法只在某些问题中的表现比较 好，而在另一类方法中表现不好，无疑会降低它的这种通用性。 遗传算法具有天然的并行性c 3 卯，如何应用遗传算法的这一特性，提高遗传算法的 性能是一个很有价值的研究课题。近年来，计算机分布式处理技术飞速发展，将分布 在各处的计算机的计算能力组织起来，实现高性能计算，是计算机技术的一个新的里 程碑。利用遗传算法的并行性与分布式计算的强计算能力，近些年来已经取得了不少 的成果3 6 , 3 7 , 3 s , 3 9 1 。 根据并行的程度不同，遗传算法的并行计算模式也不一样，常用的并行模式有以 下几种： 2 4 1f 奄单并行模式 这是最简单的一种遗传算法 并行模式，多台计算机各自独立的 进行遗传计算，运行过程中，各台 计算机不进行通讯，等到运算结束 时再对各处理器的结果进行比较， 选取最佳个体作为解，过程如图 2 1 。这种并行