（管理科学与工程专业论文）进化计算中的模式理论、涌现及应用研究.pdf

摘要 进化计算是借鉴生物进化的思想，在现代遗传学的启发下，发展起来的一种 启发式随机搜索优化方法。进化计算作为一个新的交叉学科，在拥有广阔应用前 景的同时，其理论基础有待进一步加强，对进化计算的工作机理及其内在规律的 认识不仅可以使我们更好地分析算法的性质，如对进化群体动力性质的分析和算 法收敛性的分析，而且可以帮助设计新的进化算法、改进已有的算法。本文的主 要研究内容包括： 1 通过分析进化策略、进化规划、遗传算法和遗传规划的特点，给出了进化 计算的统一框架。从不同的数学分支的角度介绍了进化计算的数学表示。 2 通过分析遗传算法、进化策略、进化规划和遗传规划四种主流进化算法的 进化算子，得到进化计算中进化算子的统一表示。定义了适度模式这一新概念， 并将建筑块的思想推广到整个进化计算领域；针对不同选择机制下进化计算的特 点，通过对遗传算法中模式理论的深入研究，将近似的公式推广到准确的模式理 论公式，将细粒度的模式理论推广到粗粒度的模式理论。同时，研究了模式的形 式不变性，进一步研究了变长度进化计算中的模式理论，从而将模式理论推广到 整个进化计算领域中。最后，在此基础上结合实际应用问题，研究了进化计算中 的建筑块假设问题，取得了较好的结果，表明了建筑块在进化计算中的普遍存在 性。 3 在给出了进化计算中涌现和混沌定义的基础上，结合进化计算中的具体情 况，研究了进化计算中的涌现现象，并从理论和试验两个方面揭示了进化计算中 的涌现现象。将进化算予的作用，抽象成从一个离散拓扑空间到另一个离散拓扑 空f 副的映射，将进化算法等价为离散拓扑空间上的转移自映射的一个复合函数， 以符号动力系统为工具，证明了满足一定条件的有限群体的遗传算法( 周期性现 象的存在) ，构成d e v a n e y 意义下的混沌，给出了基于二进制编码的有限群体遗 传算法在b o w e n 意义下的拓扑熵的范围，并阐述了进化计算中涌现与混沌的关 系。 4 从理论的角度分析了子群遗传算法的特点，给出了子群遗传算法的收敛性 证明，指出了平衡群体早熟和保证具有强进化能力的模式在群体内具有足够的存 活时间是子群遗传算法成功与否的关键。然后应用子群遗传算法解决了典型多模 态函数的优化问题，对子群遗传算法的参数调控进行了研究，研究表明子群遗传 算法的参数控制对算法的表现具有至关重要的作用。 关键词：进化计算，模式理论，涌现，混沌，子群遗传算法 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 ni s ar a n d o mh e u r i s t i cs t o c h a s t i cs e a r c h a l g o r i t h m w h i c hs i m u l a t e s b i o l o g i c a l e v o l u t i o na n dm o d e m g e n e t i c s ， a san o v e l i n t e r d i s c i p l i n a r yf i e l d ，e v o l u t i o n a r yc o m p u t a t i o n h a sa ne x p a n s i v ef o r e g r o u n d a tt h e s a m et i m e ，e v o l u t i o n a r yc o m p u t a t i o nn e e dt oi m p r o v ei t st h e o r yf o u n d a t i o n s t h e u n d e r s t a n d i n g o f e v o l u t i o n a r yc o m p u t a t i o n sm e c h a n i s m sa n dp r i n c i p l e sw i l ln o to n l y h e l pp e o p l ea n a l y z e t h e d y n a m i c b e h a v i o ro fa l l e v o l u t i o n a r yp o p u l a t i o n a n d c o n v e r g e n c eo fa l la l g o r i t h mb u ta l s o a s s i s tp e o p l et od e s i g nan e wa l g o r i t h mo r i m p r o v e t h eo l do n e s t h em a i nc o n t e n t sa r ea sf o l l o w i n g ： 1 w ed e p i c t s e p a r a t e l yt h ef r a n l e w o r k so fe v o l u t i o ns t r a t e g v e v o l u t i o n a r y p r o g r a m m i n g ，g e n e t i ca l g o r i t h m s a n d g e n e t i cp r o g r a n _ 1 m i n gf i r s t l y a n d t h e na f r a m e w o r ko fe v o l u t i o n a r yc o m p u t a t i o ni sg i v e n s o m em a t h e m a t i c a ld e s c r i p t i o n so f e v o l u t i o n a r yc o m p u t a t i o n a r ei n t r o d u c e db y u s i n g d i i r e r e n tm a t h e m a t i c a lm e t h o d s 2 au n i f i e dr e p r e s e n t a t i o no fe v o l u t i o n a r yc o m p u t a t i o ni sf o r m u l a t e do nt h e b a s i so fa n a l y z i n gt h e e v o l u t i o n a r yo p e r a t o r so fe v o l u t i o ns t r a t e g y ，e v o l u t i o n a r y p r o g r a m m i n g ，g e n e t i ca l g o r i t h m sa n dg e n e t i cp r o g r a m m i n g o n eb yo n e a p p r o p r i a t e s c h e m ai sd e f i n e da san e w c o n c e p t a n db u i l d i n gb l o c k sc o n c e p t i o ni se x t e n d e dt oa l l f i e l d si ne v o l u t i o n a r yc o m p u t a t i o n f o rd i f f e r e n ts e l e c t i o nm e c h a n i s mo fe v o l u t i o n a r y c o m p u t a t i o n ，w es t u d ys c h e m a t ae v o l u t i o na n do b t a i ne x a c ts c h e m a t at h e o r e mb a s e d o na p p r o x i m a t es c h e m a t at h e o r e m t h e nc o a r s e - g r a i ns c h e m a t a 也e o r e mi sd e r i v e d f r o maf i n e g a i no n e 0 nt h eo t h e rh a n d ，w es t u d yt h es c h e m a t af o r l ni n v a r i a n c e ，a n d g e ta r e s u l to fs c h e m a t at h e o r e mo f v a r i a b l e - l e n g t he v o l u t i o n a r yc o m p u t a t i o n s o ，t h e s c h e m a t at h e o r e mi se x t e n d e dt oa l le v o l u f i o n a r yc o m p u t a t i o nf i e l d s f i n a l l y , w e a n a l y z et h eb u i l d i n gb l o c k sh y p o t h e s i so ne x p e r i m e n tp r o b l e m s ，a n do b t a i nag o o d o u t c o m e t h e s e p r o v e t h a tt h e b u i l d i n g b l o c k sa r e u b i q u i t o u s i n e v o l u t i o n a r y c o m p u t a t i o n 3t h ed e f i n i t i o n so fe m e r g e n c ea n dc h a o sa r ei n t r o d u c e dt o e v o l u t i o n a r y c o m p u t a t i o n a n dt h e n ，o n t h eb a s i so f e v o l u t i o n a r yc o m p u t a t i o n se x p e r i m e n tr e s u l t s ， w ea n a l y z et h ee m e r g e n c ei ne v o l u t i o n a r yc o m p u t a t i o nf r o me x p e r i m e n ta n dt h e o r y t h ee v o l u t i o n a r yo p e r a t o r sa r ed e f i n e da sam a p p i n gf r o mo n ed i s c r e t et o p o l o g i c a l s p a c ei n t oa n o t h e ro n e a n de v o l u t i o n a r yc o m p u t a t i o ni se q u i v a l e n tt o ac o m p o s i t e f u n c t i o no fs h i f tm a p w ja p p l yd y n a m i c a ls y s t e m sa sat o o lt od oi t t h ep a p e r d e m o n s t r a t e st h a tt h eg e n e t i ca l g o r i t h mw i lf i n i t ep o p u l a t i o ni sc h a o t i ci nd e v a n e y h e n c e ，t h es c o p eo ft o p o l o g i c a le n t r o p yi nb o w e n i sp r e s e n t e d a n dw e e x p l a i nt h e r e l a t i o no fe m e r g e n c ea n dc h a o si ne v o l u t i o n a r yc o m p u t a t i o n 4 w eg i v ea na n a l y s i so fc o h o r tg e n e t i ca l g o r i t h mi nt h e o r y , a n dap r o o fo f a l g o r i t h mc o n v e r g e n c ei sp r e s e n t e d a n dw ep o i n to u t ，t h i si sak e yf a c t o ro f c o h o r t g e n e t i ca l g o r i t h m f o r f i n d i n g ab a l a n c eb e t w e e n e s c a p i n g f r o m p r e m a t u r e c o n v e r g e n c ea n dm a k i n gt h ep o w e rs c h e m a t ao fh i 【g h e v o l u t i o n a r ya b i l i t yh a v i n g e n o u g ht i m ei nt h ep o p u l a t i o n t h e n ，w ea p p l yc o h o r tg e n e t i ca l g o r i t h m t oo p t i m i z e m u l t i m o d a lp r o b l e m s w i t hd i f f e r e n tp a r a m e t e r s ，e x p e r i m e n t a la r ei m p l e m e n t e d ，a n d t h er e s u l t ss h o w p r o p e rp a r a m e t e r sc o n t r o li nc o h o r tg e n e t i ca l g o r i t h mi si m p o r t a n t t o i t sp e r f o r m a n c e 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 ，s c h e m a t at h e o r e m ，e m e r g e n c e ，c h a o s ，c o h o r t g e n e t i ca l g o r i t h m s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得叁鲞盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 靴敝储擗：鹈 签字日期：争卯弓年1 1 月多日 学位论文版权使用授权书 本学位论文作者完全了解盔盗盘堂有关保留、使用学位论文的规定。 特授权盔鲞盘茔可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 剔稚名撇 签字隰加严f ，月多日 天津大学博士论文 第一章绪论 二十世纪六十年代以来，进化计算( e v o l u t i o n a r yc o m p u t a t i o n ，e c ) 作为 一个新兴的交叉学科，从无到有，由弱到强，现在已经成为人工智能领域中的一 个重要分支。在工程技术、社会经济以及科学计算领域中存在着大量的复杂性 计算问题，由于这些问题表现出的高度非线性、不可导甚至不连续，复杂度非常 高，传统的优化算法在这些问题面前显得无能为力，进化计算的出现为解决这类 问题开辟了一条崭新的途径。在过去的四十几年中，以遗传算法( g e n e t i e a 】g o r i t h m s ，g a ) 、进化策略( e v o l u t i o ns t r a t e g y ，e s ) 、进化规划( 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 ) 、遗传规划( g e n e t i cp r o g r a m m in g ，g p ) 为代表的启发式随 机搜索算法，在达尔文( d a r w i n ) 生物进化思想和后达尔文主义( n e o d a r w i n i a n ) 进化思想的启迪下，在遗传学特别是现代分子生物学的启发下f 2 , j ，进化计算在 理论和应用两个方面都取得了长足的发展。 进化计算的快速发展是与其广阔的应用前景紧密相关的。随着社会的不断向 前发展，现实生活中需要解决的问题越来越多，其复杂程度越来越高，对算法的 求解要求也就随之提高了。为了提高算法的性能，必须不断加强对进化计算工作 机理的认识，从根本上解决这问题。本论文的基本内容就是针对进化计算的理 论问题进行研究，并指导算法设计。 1 1 进化计算的发展历程 进化计算的起源可以追溯到二十世纪五十年代中期，f r i e d b e r g 首先将进化 思想与计算机相结合】，用于寻找一个可以计算给定函数的输入输出问题的程 序，这工作可以认为是遗传规划的起点。据目前可查文献记载，b r e m e r m a n n 是首先将进化思想用于计算机解决数值优化问题的学者口】。 他们的开拓性工作是二十世纪六十年代中期遗传算法、进化策略和进化规划 发展的起点，二十世纪八十年代末期的遗传规划也间接的受到了影响。虽然遗传 算法、进化策略和进化规划这三种进化计算中的主流算法是在同时期发展起来 的，并具有相同的生物学背景，面对数值优化问题也极其相似，但在他们近三十 年的早期发展中，彼此间是独立发展的。直到1 9 9 0 年1 0 月份，进化计算领域在 多特蒙德召开的一次会议才将不同研究分支的学者聚集在一起，使不同的分支相 互认知、融合，从而形成进化计算。由于遗传规划求解问题的具体思想与遗传算 法非常相似，在加上其出现的时期比较晚，大多将之并入遗传算法中考虑，本文 第一章绪论 考虑到遗传规划在实际应用中所表现出的特点及其理论上的特性，将蓬勃发展的 遗传规划作为进化计算中的一个独立分支加以考虑。下面，分别介绍一下进化计 算四个主要分支的发展历程。 l i 。i 遗传算法的发展历程 h o l l a n d 被公认为遗传算法的创立者【6 j 。二十世纪六十年代初期，h o l l a n d 在研究生物学、人类社会及控制领域中动态系统的适应性问题时，采用简单的模 拟机制在计算机上模拟复杂的适应性现象。在实验中发现，要想得到稳定的适应 性系统( r o b u s ta d a p t i v es y s t e m s ) ，一个具有进化能力的系统是关键。在这一 时期，遗传算法中的进化操作已经出现了，遗传算法作为一个专有名词首次出现 在1 9 6 7 年b a g l e y 的博士沦文中1 7 j ，算法主要是为了优化游戏程序中的参数设定， 遗传算法的基本机制已经出现。同时期，h o l l a n d 许多学生的工作在遗传算法的 形成过程中起了非常重大的作用，除了b a g l e y 外，还有c a v i e c h i o 和h o l i s t i e n 等人，这些m i c h i g a n 大学的学生最后大多成为该领域的著名学者。 遗传算法和其他任何。门新兴学科一样，在饱受怀疑和反对的目光中走过了 它的最初阶段，到了二十世纪七十年代中期，关于遗传算法的研究才缓慢展开。 1 9 7 5 年，h o l l a n d 出版了遗传算法领域中的第一本专著 a d a p t a t i o ni nn a t u r a l a n da r t i f i c i a s y s t e m s ，这是遗传算法领域中一个里程碑式的著作，该书对 遗传算法中的基本理论及方法进行了系统的阐述，提出了著名的模式理论 ( s c h e m a t at h e o r e m ) 及隐并行性( i m p l i c i tp a r a l 1e l i s m ) ，用以解释遗传算 法的运行机理，在明确了进化算子的前提下，将算法应用于系统适应性研究、自 动控制和机器学习等多个领域陋j 。 1 9 7 6 年在m i c h i g a n 召开了第一次关于遗传算法的讨论会，虽然这是一次仅 有2 0 多人参加的会议，但今天看来其意义却是不可低估的，它使遗传算法的 研究走出了封闭的状态。 遗传算法在最初并不是作为数值优化工具出现的，但其在优化问题上的成 功，却成了遗传算法快速发展的主要原因，c a v i c c h i o 9 1 和d ej o n g u o 在这一方 面做出了突出的贡献。前者使用整数编码的遗传算法进行模式识别的研究；后者 在其博士论文中首次将遗传算法用于函数优化问题，并进一步研究了遗传算法的 理论问题和参数优化问题，利用五个基本函数建立了测试平台，并给出了关于进 化算子的经验分析，d ej o n g 的这一研究结果在今天的遗传算法领域仍具有普遍 的指导意义。 除了m i c h i g a n 大学之外，p i t t s b u r g h 大学是另一个研究遗传算法的中心。 在众多学者的不断努力下，遗传算法不断向前发展。1 9 8 5 年，在p i t t s b u r g h 召 2 天津大学博士论文 开了第一届遗传算法国际会议( i n t e r n a t i o n a lc o n f e r e n c e o ng e n e t i c a l g o r i t h m s ，i c g a ) ，此会议两年举行一次，到1 9 9 7 年为止，该会议一共举办了 七届，1 9 9 9 年i c g a 与遗传规划的会议合并，改为每年举行一次的国际会议 ( g e n e t i ca n de v o l u t i o n a r yc o m p u t a t i o nc o n f e r e n c e ，g e c c o ) ，g e c c o 是 个涵盖进化计算各个领域的综合性国际会议，g e c c o2 0 0 3 将在芝加哥举办。 1 9 8 9 年，遗传算法领域中的另一本专著 g e n e t i ca l g o r i t h m si ns 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 问世了，这是遗传算法领域中另一个里 程碑式的著作，作者g o l d b e r g 在全面研究遗传算法的基础上，对当时的工作进 行了全面细致的总结和分析。该书的最大特点在于理论与应用的结合，不但适用 于广大的研究人员，而且是一本很好的教材 1 ”。 1 9 9 1 年i s g a ( i n t e r n a t i o n a ls o c i e t yf o rg e n e t i ca l g o r i t h m s ) 举办了 一个新的国际会议( f o u n d a t i o n so fg e n e t i ea l g o r i t h m s ，f o g a ) ，该国际会议 在遗传算法领域具有更大的学术影响力，此会议也是两年举行一次，最近的一次 会议，f o g a 2 0 0 3 已经举行，该会议至今共举办了七届，这是一个引领着遗传算 法研究方向的国际会议。f o g a 每两年出版一本会议论文集，该论文集收录的文 章主要以遗传算法理论性研究为主。 1 9 9 4 年6 月，i e e e 神经网络委员会( i e e en e u r a ln e t w o r kc o u n c i l ) 召开 了第一届进化计算国际会议( i e e ei n t e r n a t i o n a l c o n f e r e n c ee v o l u t i o n a r y c o m p u t a t i o n ，i c e c ) ，该会议每年举办一次。1 9 9 9 年该会议与进化规划的会议 合并为一个新的国际会议c e c ( c o n g r e s s o ne 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 h ee v o l u t i o n a r yp r o g r a m m i n g s o c i e t y ) 等几家团体合办，该会议的范围广泛，几乎包括进化计算的所有领域， c e c 2 0 0 3 将在澳大利亚举行。与遗传算法相关的重要会议还有s m c ( i e e e i n t e r n a t i o n a lc o n f e r e n c eo ns y s t e m s m a n c y b e r n e t i c s ) 等等。 1 1 2 进化规划的发展历程 进化规划的思想是l j f o g e l 在1 9 6 0 年首先提出来的。lj f o g e l 在 有限状态机( f i n i t e s t a t em a c h i n e s ) 的研究中发现，早期的神经网络方法和 启发式算法无法满足系统不断提高性能的要求，他希望通过系统的自适应s t n 来 达到这一要求，正是这一基本思想导致了进化规划的产生。所谓状态机就是将周 围的环境情况，用有限字符集中的符号组成的符号序列来表示，根据目前已知的 符号序列得到新的字符序列，通过适应值函数的比较以便获得更准确的预测结 果。1 9 6 6 年l j f o g e l 、o w e n s 和w a l s h 合著了 a r t i f i c i a li n t e l l i g e n c e t h r o u g hs i m u l a t e de v o l u t i o n 一书，该书系统的阐述了进化规划的基本思想， 第一章绪论 在进化规划的过程发展中具有重要的历史意义“。早期的进化规划在问题预测和 自动控制领域获得了一定的成功，这种成功也没有改变进化规划不被接受的命 运。除了l j f o g e l 外，l u t t e r 、h u n t s i n g e r 和d e a r h o l t 等人也为进化规 划的早期发展做出了重要的贡献。l u t t e r 和h u n t s i n g e r 将自动状态机的成果应 用于工程领域，取得了较好的效果；d e a r h o t 则使用进化规划的思想进行实际 问题的解决【l 】。 在二十世纪八十年代中后期，随着应用范围的扩大，进化规划进入了一个新 的发展阶段。在这一发展阶段，d ，b f o g e l 发挥了重要的作用。从二十世纪八 十年代中后期到九十年代，d b f o g e l 使用进化规划解决t s p 问题，改善了求 解性能：他将进化规划应用于连续参数优化问题领域，扩大了进化规划的适用范 围，增强了进化规划的影响力。在此期间，进化规划不断扩展其应用领域，取得 了相当丰富的成果。进化规划作为神经网络中的学习算法，提高了神经网络的性 能；进化规划中的自适应机制，不但提高了其自身的性能，而且被广泛应用于进 化计算的各个方向【1 3 - ”】。 1 9 9 2 年，d b f o g e l 和a t m a r 在美国举办了进化规划的第届会议 ( e v o l u t i o n a r yp r o g r a m m i n gc o n f e r e n c e ) ，该会议每年举办一届，1 9 9 9 年与 i c g c 合并为一个新的国际会议c g c 。l j f o g e l 和d b f o g e l 应用进化规 划算法成功的解决了许多实际问题，例如应用进化规划和神经网络相结合进行胸 部癌症的检测【l 。 1 1 3 进化策略的发展历程 r e c h e n b e r g 、s c h w e f e l 和b i e n e r t 是进化策略公认的发明者【”。1 9 6 4 年， 当时他们还在柏林技术大学上学，在设计一种能够评测在风洞中可弯曲的三维物 体最小变形的设备的过程中发明了该算法。与其他研究工作一样，开始阶段，他 们希望通过传统的数值算法来解决这一问题，结果是失败的，传统的数值算法无 法跳出局部最优解，算法很快早熟。r e e h e n b e r g 首先想到了将进化思想应用到 算法的设计中，它将进化论中的生物选择、重组、变异应用到参数优化中“”，可 以认为进化策略的思想已经形成，虽然这只是进化策略的一个初始形态，但它涵 盖了进化策略的基本思想。r e c h e n b e r g 的基本思想如下：首先随机产生一个离 散的初始个体，然后将一个满足二项分布的变异作用在初始个体上，这样得到一 个新的个体，从这两个个体中选择适应值较大的个体作为下一代的父个体，这就 完成一次循环。这种算法应该称为( 1 + 1 ) 进化策略。 s c h w e f e l 首先将r e c h e n b e r g 的算法付诸于实施【1 ”，s c h w e f e l 的实验非常成 功，算法战胜了局部最优值的陷阱，获得了全局最优解，这成功对与进化规划 天津大学博士论文 而言同样具有里程碑式的意义。b i e n e r t 的贡献在于将进化规划思想应用到实际 具有工业意义的具体问题上【1 9 】，该问题是传统算法所不能解决的问题，b i e n e r t 的硕士论文成功的解决了这一问题，这一工作连接了进化规划的理论与实践，意 义重大。 随后r e e h e n b e r g l 迸一步改进了进化规划，在解决月维凸函数的优化中， 给出了算法的收敛性分析，并在此基础上给出了著名的“1 5 成功原则”，即通 过外在的改变二项分布的方差的经验值。r e c h e n b e r g 又给出了多群体下的进化 策略算法，即( + 1 ) 进化策略，群体内个体间的重组操作也被使用。r e e h e n b e r g 的这项工作对于进化策略的进一步发展起到了决定性的作用，群体概念和重组算 子的引入从理论上完善了进化策略，为其在实际应用中取得成功奠定了理论基 础。但是这一算法由于变异算予缺乏自适应机制而显得先天不足，并未得到广泛 的推广和应用。 s c b w e f e l p 】 在似+ 1 ) 进化策略的基础上迈出了重要的一步，将之推广到 ( + 五) 进化策略和( ， ) 进化策略，这两种形式的进化策略成为后来广泛使用的 两种形式。进化规划中使用的自适应机制在进化策略中也被使用。进化策略的研 究中心在德国，主要以s c h w e f e l 在多特蒙德领导的研究团队和r e c h e n b e r g 在柏 林领导的研究团队为主。 随着并行思想的深入，进化策略在二十世纪九十年代引入了并行概念并取得 了一定的成功。同期正是进化计算各个分支相互融合的时期，进化策略研究团体 发挥了重要的作用。 在进化策略的理论研究方面，h a n s g e o r gb e y e r 做出了重要的贡献。 b e y e r 2 2 , 2 3 1 首先建立了进化策略的数学模型，并以微分几何为工具研究了非球面 适应值空间的性质，研究了( ，旯) 等多种进化策略的收敛性质和算法的动力学性 质，为进化策略的下一步发展打下了基础。 1 9 9 0 年1 0 月，第一届p p s n ( p a r a l l e lp r o b l e ms o l v i n gf r o mn a t u r e ) 会 议在德国举行，该会议每两年举办一次，至今已举办了七届，是欧洲关于进化计 算方面重要的国际会议之一。p p s n 2 0 0 4 将于2 0 0 4 年9 月在英国的伯明翰举办。 1 1 4 遗传规划的发展历程 遗传规划是进化计算中最年轻的分支，1 9 8 9 年，j r k o z a 发表了著名的 论文h i e r a r c h i c a lg e n e t i ca l g o r i t h m so p e r a t i n g 0 1 1 p o p u l a t i o n s o f c o m p u t e rp r o g r a m s ，标志着遗传规划的诞生；1 9 9 2 年、1 9 9 4 年j r k o z a 先 后出版了两部遗传规划的专著，这是遗传规划走向成熟的标志 2 4 ，2 5 1 。 工r k o z a 是h o l l a n d 的学生，他对遗传算法的深入研究是发明遗传规划 第一章绪论 的一个先决条件。在遗传算法中采用的是定长的编码方式，这一方式限制了遗传 算法的应用范围，对于层次化的问题，采用定长的编码方式则显然不合适，遗传 算法很难解决层次化的问题，这种要求呼唤着具有变长编码方式的遗传算法的出 现；计算机程序是一种典型的具有层次化结构的对象，传统的遗传算法编码方式 难以处理这一对象，遗传规划采用长度和大小均可变化的树型结构进行编码，这 种编码方式具有灵活性，而且易于实现，所以遗传规划的编码方式可以很好的解 决这一矛盾。遗传规划的搜索过程就是在计算机程序构成的搜索空间内，通过进 化算子的作用，寻找具有高适应值的计算机程序的过程。 l i s p 语言是遗传规划采用的基本计算机语言。l i s p 语言是1 9 5 8 年由j o h n m c c a r t h $ r 等人发明的一种计算机语言，该语言具有结构简单，易于操作的特点。 该语言的数据结构只有两种，节点( a t o m ) 和目录( 1 i s t ) 。所谓节点就是符号 和数字组成的集合中的任意一个元素，例如在集合 4 ，日，c ，4 ，5 ，6 中，任意一个元 素构成l i s p 语言中的一个节点；所谓目录就是由小扩号构成的嵌套结构，例如 f 4b ( cc ) 66 ) 。遗传规划采用的是解析树表示，l i s p 语言非常适合这种捌 型结构的表示，现在l i s p 语言在遗传规划中仍普遍使用。在l i s p 语言被广泛应 用的同时，遗传规划也适用c 和c ”语言用来解决问题。 j r k o z a 认为应用遗传规划解决实际问题的五个主要准备阶段如下【2 5 | ： ( 1 ) 首先要给定一个终止符号集合； ( 2 ) 基本函数集合； ( 3 ) 适应值函数的度量； ( 4 ) 参数设定； ( 5 ) 运行结果的选定方式和运行终止条件的设定。 j r k o z a 发明了遗传规划，并应用它解决了许多具体问题。在应用快速 发展的同时，遗传规划的理论研究也在快速展开，在这一方面，r i c c a r d o p o l i 等人的工作取得了显著的成果f 2 6 0 孔。针对遗传规划本身的特点，在借鉴遗传算法 中的模式理论的基础上，进一步给出了基于不同交叉和变异情况下的准确模式公 式。建筑块假设在遗传规划中也同样受到了一些质疑1 2 “。 i i 5 进化计算各个分支的融合发展 遗传算法、进化策略和进化规划是在不同的地区，由不同领域内的研究人员 各自独立提出来的，早期面对的问题也各不相同，彼此之间缺乏必要的学术交流。 进化策略和进化规划领域的研究人员首先建立了联系，通过学术会议两个领域的 研究人员将这种联系保持了下来，随后遗传算法和遗传规划加入了进化计算这个 大家庭。虽然不同的分支各有特点，但他们具有相同的仿生基础一生物迸化思想。 天津大学博士论文 1 9 9 0 年b e z d e k 在多特蒙德的会议上首次使用了进化算法( e v o l u t i o n a r v a l g o r i t h m s ) 一词，现在进化算法和进化计算( e v o l u t i o n a r yc o m p u t a t i o n ) 早 通用的。 随着进化计算各个分支的相互融合，不同分支的国际会议或是相互合并，或 是将其它分支的研究方向纳入自己的会议范围内，进一步加强了彼此间的联系。 比如进化规划中的自适应机制已经被遗传算法和遗传规划所借鉴，随着时间的推 移这种相互融合的趋势必将进一步加强。 1 9 9 3 年，m i t 出版社开始出版发行 e v o l u t i o n a r yc o m p u t a t i o n ，这季 刊成为进化计算领域中重要的学术杂志，该期刊面向进化计算领域中理论和实际 应用问题，现任主编是m a r cs c h o e n a u e r 。1 9 9 7 年，i e e e 出版了另一本重要的 进化计算刊物i e e et r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n 。这些国际 刊物的问世，促进了学术界的相互交流，使进化计算的各个分支真正融合为一体。 1 2 进化计算的主要特点 进化计算是一种基于自然选择机制下的全局性随机搜索算法。它从随机产生 的初始群体开始，经过进化算子的不断作用，在迭代过程中逐步改进当前群体中 个体的适应值，直到算法得到问题的最优解或满意解为止，在总结进化计算各个 分支特点的基础上，给出进化计算的主要特点。 1 2 1 遗传算法与遗传规划的主要特点 遗传算法具有以下主要特点： ( 1 ) 遗传算法对优化对象限制很少。由于遗传算法在选定编码方式后，处 理的是参数的编码集而不是函数本身，所以对优化函数的性质没有具体的要求。 这与传统优化方法对优化函数在连续性、可导方面的要求不同。 ( 2 ) 遗传算法的搜索初始点是初始群体，而不是单一的初始点，这种方式 有利于搜索过程以较大的概率跳出局部极值点，提高了算法搜索到问题全局最优 解的能力【2 。 ( 3 ) 遗传算法具有显著的隐并行性【。从模式的角度考虑遗传算法的求解 过程，算法在处理群体中个体的同时，也在对此个体所在的模式进行处理，具有 并行处理的性质。 ( 4 ) 遗传算法构造简单、易于实现，对具体的运行环境没有过多的限制， 可以在不同的软硬件平台上实现。 ( 5 ) 遗传算法具有典型的动力学特征。遗传算子在算法运行过程中会产生 7 墅兰一堕堡 涌现现象，遗传算法在求解一些问题时会表现出混沌及分形特征。 遗传规划除了具有遗传算法所具有的上述五个特点外还具有如下特点： ( 6 ) 遗传规划采用动态编码方式，可以解决层次化问题，扩大了进化计算 的研究范围。 ( 7 ) 遗传规划的输出结果是动态可变的。 1 2 2 进化规划的主要特点 进化规划具有以下主要特点： ( 1 ) 进化规划是一种采用自适应机制的进化算法。在进化规划中步长向量 受进化过程的控制自发的进行调解。 ( 2 ) 进化规划的搜索初始点也是初始群体，而不是单一的初始点，算法采 用自顶向下和自底向上的方式进行搜索。 ( 3 ) 进化规划中不采用重组和交叉算子。进化规划将群体内的每一个个体 看作是一个物种，物种间的杂交是不存在的，因此算法不使用重组和交叉算子， 这是进化计算中的一个特例f 1 3 0 ! 。 ( 4 ) 进化规划构造简单、易于实现，可以与其它启发式算法结合使用，也 可以作为其他算法的一个学习工具，例如在神经网络中的应用。 ( 5 ) 进化规划具有典型的动力学特征。算法在运行过程中，随着时间的推 移，进化群体表现出动力学特征。 1 2 3 进化策略的主要特点 进化策略具有以下主要特点： ( 1 ) 进化策略是首先采用自适应机制的进化算法 1 , 3 1 1 。 ( 2 ) 进化策略的搜索初始点最初使用的是单一的初始点，这种方式的进化 策略已基本不再使用；现在普遍使用的进化策略算法也是采用初始群体作为搜索 的初始点。 ( 3 ) 进化策略构造简单、易于实现，可以采用嵌套方式来应用这一算法。 ( 4 ) 进化策略具有典型的动力学特征。特别是在o n e m a x o + 1 ) 问题上， 已经有了肯定的结论。 1 2 4 进化计算的特点总结 综合l 卫1 1 2 3 节的内容，下面给出进化计算的主要特点 天津大学博士论文 ( 1 ) 进化计算具有宽广的适用范围。由于进化计算采用灵活的编码方式( 二 进制编码、实数编码和字符集编码等) ，算法处理的是编码集合，因此对优化对 象没有过多限制。 ( 2 ) 进化计算的搜索初始点是初始群体，而不是单一的初始点，这种方式 有利于搜索过程以较大的概率跳出局部极值点，提高了算法搜索到问题全局最优 解的能力。这是进化计算区别于一般启发式算法的主要特点之一。 ( 3 ) 进化计算构造简单、易于实现，可以相互之间结合使用，也可以与其 它启发式算法结合使用。 ( 4 ) 进化计算具有内在的并行计算特征。 ( 5 ) 进化计算具有典型的动力学特征。 ( 6 ) 进化计算是一种启发式随机搜索算法。 1 3 进化计算的理论研究 进化计算的理论研究主要集中在算法的收敛性研究和运行机理研究两个方 面。在这两个方面，进化计算的各个分支各有特点。 1 3 1 遗传算法和遗传规划的理论研究 因为遗传算法的理论研究基本涵盖了遗传规划的理论研究，所以在本节将- 者统一考虑。遗传算法在收敛性上的研究主要分为随机模型方法和解析方法。 应用随机模型方法对遗传算法的收敛性进行研究，是因为遗传算法的进化过 程可以表示为有限状态下的马尔可夫链( m a r k o vc h a i n ) 。这种表示的前提是遗 传算法下一代群体中个体的存在概率，仅与上一代群体的存在概率相关，与其它 无关。遗传算法所要解决的问题，一般可以表示为有限空间上的求解过程，