（计算机应用技术专业论文）基于小生境技术协同进化的创新概念设计.pdf

中文摘要 在建筑设计领域，需要大量具有特色的创新性建筑设计来适应快速发变化的 市场需求，提升国家或地区的竞争能力。随着市场经济的日益发达，建筑创新仅 仅依靠人来进行设计，很难满足快速发展的市场需求。到目前为止，虽然计算机 模型发展迅速，但是这些模型多数以人工草图为基本设计原型，设计者必须通过 勾画草图来实现他们的设计思想，进而进入详细设计等后续环节。目前急需要一 种具备刨新特点的计算机辅助设计工具。 受自然和人类社会规律的启发，利用获得智慧的灵感进行科学研究和生产活 动，乃至用于日常生活，是人类不断推陈出新、生生不息的动力之源。以遗传算 法“1 、进化策略比、进化规划n 3 为代表的进化算法则是这种思想的体现和结晶。 自它们被提出以来，即因其卓越的鲁棒性能而备受关注，并越来越多地在各个领 域获得重要应用。受生物界中食物链关系、共生关系启发而提出的协同进化 ( c o - e v o l u t i o n ) 是近年来发展起来的很有前途的方法h 】。 论文提出了一种基于小生境技术的协同进化模型。这种模型将协同进化算法 与小生境技术相结合，具有动态的适应度调节，对于进化的最优解集中放置，一 方面提交决策机构，保证了找到最佳解决方案的可能性，可以保持解的多样性， 克服了单种群独立进化数据不共享的缺点，比其他的进化算法有不过早收敛的优 越性。另一方面将不满意的最优解的一部分返还子种群重新进化，保证了进化的 速度。 论文将产品的创新概念设计捌引入建筑设计领域，结合基于小生境技术的协 同进化算法，用v c h 6 0 和a c i s 设计了一套建筑创新概念设计工具。利用该工 具，能够进行一些建筑方面的概念设计，开阔建筑设计人员的设计思路，实现一 些意想不到的设计效果，开拓了建筑领域中的创新概念设计之路，与其它的c a d 软件结合，它将构成一套强大的创新概念设计系统。 关键词：协同进化小生境适应度概念设计 a b s t r a c t i nt h ef i e l do fa r c h i t e c t u r ed e s i g n , i tn e e d ss o m ec h a r a c t e r i s t i ci n n o v a t i o n a r c h i t c e t u m ld e s i g n st oa d a p tt h ef a s tc h a n g e so ft h em a r k e t sd e m a n d s t h i sc a l l p r o m o t es o m ec o m p a n y sc o m p e t i t i o na b i l i t y w i t ht h ed a yb yd a yd e v e l o p m e n to f t h em a r k e te c o n o m y , o n l yw i t ht h ed e s i g n so ft h ep e r s o n ，i tw i l lb ev e r yd i f f i c u l tt o s a t i s f yt h ef a s td e v e l o p m e n to ft h em a r k e t u pt on o w , a l t h o u g ht h ec o m p u t e rm o d e l d e v e l o p m e n ti sr a p i d ，t h e s em o d e l sm o s tt a k et h ea r t i f i c i a ls c h e m a t i cd i a g r a ma st h e b a s i cd e s i g np r o t o t y p e sa n dt h ed e s i g n e rm u s tr e a l i z et h e i rd e s i g nt h o u g h t sw i t l lt h e s c h e m a t i cd i a g r a m sa n dt h e ne n t e rt h ed e t a i l e dd e s i g na n ds o0 nt h ef o l l o w i n gl i n k c o m p u t e ra s s i s t e dd e s i g nt o o lw i t l li n n o v a t i v ec h a r a c t e r i s t i ci sn e e d e du r g e n t l ya t p r e s e n tt i m e t h ei n s p i r a t i o no f n a t n r ea n dh u m a ns o c i e t y sr u l e sa n dt h eu s i n go f t h ew i s d o m t 0e a l t yo nt h es c i e n t i f i cr e s e a r c ha n dt h ep r o d u c t i o nl i f ei st h es o u r c ep o w e rw h i c h t h eh u m a n i t yu n c e a s i n g l yw e e d st h r o u g ht h eo l dt ob r i n gf o r t ht h en e wa n dg r o w s c o n t i n u a l l y t h ee v o l u t i o na l g o r i t h m ( e a ) w h i c hi sc o n s i s t e do fg e n e t i ca l g o r i t h m s ( g a ) t 1 1 、e v o l u t i o ns t r a t e g i e s ( e s ) i 2 a n de v o l u t i o n a r yp r o g r a m m i n g ( e p ) t 3 i st h e c r y s t a l l i z a t i o no ft h i sk i n do ft h o u g h t s i n c ei th a sb e e np r o p o s e d , i ti sp a i da t t e n t i o n t on a m e l yb e c a u s eo fi t sr e m a r k a b l er o b u s t n e s sa n dm o r ea n dm o r ei m p o r t a n t a p p l i c a t i o ni so b t a i n e di nm a n yf i e l d s t h ec o e v o l u t i o n 4 1w h i c hi se n l i g h t e n e db y t h er e l a t i o n si nt h eb i o s p h e r ef o o dc h a i ni st h ev e r yi m p o r t a n tm e t h o di nt h er e c e n t y e a r s t h i sp a p e rp r o p o s e dac o e v o l u t i o nm o d a lb a s e do nt h en i c h et e c h n o l o g y t h i s m o d a lc o u n e c t st h em u l t i - p o p u l a t i o nc o ，e v o l u t i o na n dt h en i c h et e c h n o l o g y i th a st h e d y n a m i cf i t n e s ss h a r i n ga n dm u l t i p l es o l u t i o n s f o rs o m eb e s ts o l u t i o n s ，i tw a s c e n t r a l i s ml a i da s i d e o nt h eo n eh a n db ys u b m i t t i n gt h ep o l i c y - m a k i n go r g a n ，i tw a s p o s s i b l et of i n dt h eb e s ts o l u t i o n s i to v e r c o m e st h es h o r t c o m i n g sw h i c ht h es i n g l e p o p u l a t i o ne v o l u t i o nh a si n d e p e n d e n t l y 证t l ln o ts h a r i n gd a t e s i tc a l ln o tc o n v e r g e e a r l yc o m p a r e dt oo t h e re v o l u t i o na l g o r i t h m s o nt h eo t h e rh a n db yr e t u r n i n gp a r t so f t h eb e s ts o l u t i o n st ot h es u b - p o p u l a t i o nt or e - e v o l u t i o n ，i th a sg u a r a n t e e dt h e e v o l u t i o n ss p e e d i nt h i sp a p e r ，s o m ep r o d u c t s i n n o v a t i o nc o n c e p td e s i g ni s i su s e di nt h ef i e l do f i a r c h i t e c t u r a ld e s i g n c o n n e c t i n gw i t ht h ec o e v o l u t i o na l g o r i s m sb a s e do nt h en i c h e t e c h n o l o g ya n d w i t hv c 十卜6 0a n da c i s t h i sp a p e rd e s i g n e da n dr e a l i z e das e to f t h e c o n s t r u c t i o ni n n o v a t i o nc o n c e p td e s i g nt 0 0 1 w i t ht h i st 0 0 1 t h ec o n s t r u c t e r sc a nc a r r y o ns o l n ek i n d so fa b s t r a c td e s i g n s t h i sc a no p e na r c h i t e c t u r a ld e s i g n e r s m e n t a l i t y a n dr e a l i z es o m eu n e x p e c t e dd e s i g ne f f e c t s i to p e n e dt h er o a do fd e s i g n so f g e n e r a t i v ec o n c e p t i o ni na r c h i t e c n t r e c o n n e c t i n gw i t hc a ds o f t w a r e ，i tw i l l c o n s t i t u t eo n es e to f f o r m i d a b l ei n n o v a t i o n sc o n c e p t sd e s i g ns y s t e m k e yw o r d s ：c o - e v o l u t i o n , n i c h e ，f i t n e s s , c o n c e p t i o nd e s i g n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞盘茎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：历私m 翻p签字日期：时年，2 月2 7 曰 学位论文版权使用授权书 本学位论文作者完全了解鑫生盘茎有关保留、使用学位论文的规定。 特授权鑫鲞蠢茎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文储签名：坪加卿 签字日期：砧年忙月幻日 导师签名： ) 而乙 签字日期：? 9 吒年，猬2 7 日 第一章引言 1 1 研究背景 第一章引言 大自然是人类获得灵感的源泉。将生物界所提供的答案应用于工程问题的求 解被实践证明是一个成功的方法。生命科学中的遗传学原理决定了有生命世界的 多样性和统一性，筑成了物种的纷繁复杂，无限多样。进化的历史告诉我们，生 物的进化是一个漫长而复杂的过程，在这个过程中，生物从低级、简单的状态向 高级、复杂的状态演变，遵守的是“优胜劣汰，适者生存”的自然法则。现在， 人们已经认识到进化不仅仅在生命科学的范畴中存在，进化作为一种优化的过 程，还可以在计算机上模拟，并应用到工程领域中叫。 创新概念设计是设计学中重要的研究课题，有关该方面的研究已经有了许多 文献刚。在创新设计研究方面，香港理工大学设计学院一直是该方面领导者， 其院长j o h nf r a z e r 教授是英国剑桥大学的教授，国际著名的设计专家，多年来 致力于进化计算在设计中应用的研究，曾经成功的将遗传算法应用于建筑设计， 产生令人耳目一新的建筑，并因此获国际设计与技术金奖，被誉为遗传算法在建 筑设计中应用的奠基者。他在香港理工大学建立并领导的设计技术研究中心，由 在英国剑桥大学获博士学位的唐明晰博士担任设计中心副主任，已经发表7 0 多 篇人工智能在设计中应用的论文，并已经与英国、美国、意大利、日本等国家的 高校和设计研究机构建立了密切的合作关系。浙江大学等高校在创新设计方面也 有很好的工作。 计算机辅助创新( c o m p u t e ra i d e di n n o v a t i o n ) 是新产品开发中的一项关键 基础技术，它是以近年来在欧美国家迅速发展的发明创造方法学( t r i z ) 研究为基 础，结合本体论，现代设计方法学、计算机技术、多领域科学知识，综合而成的 创新技术。 1 2 研究目的 最近2 0 年，创新进化设计得到广泛的研究，它已经成为最重要的计算和创 新设计技术之一。许多研究人员投身于这一领域，研究工作涉及到自生长系统、 遗传程序设计、创新进化系统等等。其中，p j b e n t l e y 的论文系统地揭示了利 第一章引言 用遗传算法进行创新和优化概念设计的思想，他提出了一种利用遗传算法作为核 心的遗传算法设计系统，并且演示了对1 5 个实体对象在传统和非传统两种方式 下设计的成功进化，例如桌子、五棱柱等等”1 。 进化计算可能是将来最有前途的工具，但是，由于进化算法和技术的复杂性， 它的应用现在却常常被局限到单体进化嘲。进行多目标优化和研究更有强有力算 法的任务已经提到日程，这就是多种群协同进化算法。 在建筑设计领域，虽然计算机辅助设计模型发展迅速，但是这些模型多数以 人工草图为基本设计原型，设计者必须通过勾画草图来实现他们的设计思想，进 而进入详细设计等后续环节，设计基本上依靠设计家的“灵感”。如何为设计家 提供更多的选择余地，以及如何为他们提供人脑想象不到的设计方案，是一个突 出的问题m 。 1 3 论文主要工作 本文主要研究了进化计算的一个重要方面一多群体协同进化，建立了一种基 于动态小生境技术的多种群协同进化模型，发展了建筑物创新概念设计的思想， 并将两者综合运用，开发了一套用于建筑创新设计的工具。应用表明，这种工具 能极大地提高设计作品的创新水平，激发设计人员的创作灵感。对于一个实际的 复杂的建筑设计，往往会得到出其不意的效果。 全文各章节所研究的内容安排如下： 第一章：引言。讨论了论文的研究背景，问题提出、意义及主要工作。 第二章：协同进化模型。分析了进化计算的相关理论及小生境理论，解析了 小生境的判定方法，构建了一种基于小生境技术的协同进化模型。描述了该模型 的进化过程。 第三章：创新概念设计研究。这一章讨论了创新概念设计的重要问题，将产 品方面的概念设计应用于建筑设计领域。分析了几种创新方法。 第四章：基于小生境技术的协同进化在创新概念设计的应用。详细阐述了模 型的表现型、基因型、适应度的构建方法，并给出了进化的交叉算子、变异算子 和选择算子的形式，介绍了a c i s 的相关知识，描述了楼体进化模型，最终展示 了利用a c i s6 , 0 和v c + + 6 0 设计的建筑创新概念设计工具生成的实力过程。 第五章对本文的研究工作进行了总结和展望。 第二章基于小生境技术的协同进化算法 第二章基于小生境技术的协同进化算法 生物学上，协同进化( c o e v o l u t i o n ) 是指生物与环境、生物与生物之间在 进化过程中产生的依存关系，或在生态上密切相关的物种相关联地进化，或仅指 一个物种( 或一个种群) 的遗传结构由于回应另一物种( 或种群) 遗传结构的变 化而发生的相应改变。 小生境( n i c h e ) ；小生境是指特定环境下的一种组织结构。在自然界中，往 往特征，形状相似的物种相聚在一起，并在同类中交配繁衍后代。 自然选择是对适应度进行的，适应度是依赖于表现型的，表现型则是被基因 型决定的，而遗传的操作( 变异、交叉) 是在基因型上操作的。因此整个进化的 过程就是这样一层一层涌现出来的。 大自然是我们解决各种问题时获得灵感的源泉，仿生学的成功为此提供了证 明，可以根据自然法则来产生新的更好解。进化计算就是基于这种想法而发展 起来的一种通用的问题求解方法。 2 1 进化计算 2 1 1 进化计算的概念与发展 “进化计算( e v o l u t i o n a r yc o m p u t a t i o n ，简称e c ) ”这一术语是在二十世 纪九十年代初被提出的。它是模拟生物进化过程中“优胜劣汰”的自然选择机制 和遗传信息的传递规律的算法的总称，其目的是将模拟生物进化的不同分支的学 者在思想上集中起来，促进它们的共同发展0 1 ，研究模拟生物的进化规律来解决 实际工程中的复杂优化问题。在九十年代初期以前，不同分支间并没有交流，直 至1 9 9 0 年，才在进化计算的一些国际会议上产生了相互之间的交流与切磋。现 在，进化计算已经成为一门较独立的新的计算技术学科，以遗传算法为核心的进 化计算会将二十一世纪的计算智能推向一个个崭新的应用领域。 2 1 2 进化计算的分支 目前，进化计算主要有遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 、遗传 编程( g e n e t i cp r o g r a m m i n g 简称g p ) 、进化策略( e v o l u t i o ns t r a t e g i e s ，简 第二章基于小生境技术的协同进化算法 称e s ) 和进化编程( e v o l u t i o n a r yp r o g r a m m i n g ，简称e p ) 等分支组成，其它的 诸如d n a 计算和分子计算( m o l e c u l a rc o m p u t i n g ) ，也开始应用在实际问题中， 但还没有形成一个体系，比较零散。 进化计算的四个分支的共同点是群体进化、优胜劣汰、有向随机和梯度信息 无依赖性等。不同点是进化算子的不同，选择方式的不同以及适合解决问题的类 型不同等，下面结合它们的基本原理进行详细论述。 ( 一) 遗传算法( g a ) 遗传算法是进化计算的第一个算法。早在二十世纪六十年代初，美国 m i c h i g a n 大学的j h h o l l a n d 教授就意识到了生物进化过程中蕴含着的朴素 的优化思想。他借鉴了达尔文的生物进化论和孟德尔的遗传定律的基本思想，并 将其进行提取、简化与抽象，提出了第一个进化计算算法一遗传算法。1 9 7 5 年 出版了他的专著( a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s “，标志 着遗传算法的正式诞生。在这本专著中，他称之为“g e n e t i cp l a n s ”，详细阐 述了遗传算法的基本思想和结构框架。”g e n e t i ca l g o r i t h m s ”一词是首先出现在 j d b a g l e y 的博士论文中，他研究了遗传算法在博弈论( 六子棋) 中的参数搜索， 这是遗传算法最早的应用“。“遗传”与“算法”的结合体现了生物科学与计算 机科学的相互渗透，相互融合。 图2 1 原理性地描述了自然进化与遗传算法之间的对应关系。 竺书 筹电 图2 - 1 自然进化与遗传算法的关系 1 、遗传算法的基本理论 由于遗传算法是一种启发式的有向随机搜索算法，在进化过程中是否收敛到 全局最优解成为其应用于实际问题是否成功的关键。然而，h o l l a n d 的模式定理 并没有从理论上回答遗传算法的全局优化性，它只是研究了群体中部分特征模式 的样本数目随进化代数的变化规律。近年来，关于遗传算法的全局收敛性证明， 4 第二苹基于小生境技术的协同进化算法 许多学者进行了理论上的研究，取得了一定的成果“”。除了收敛性的证明，遗 传算法的控制参数选取也是一个极其重要的理论问题，因为控制参数直接影响着 遗传算法的优化效率。但控制参数的选择与使用的遗传算子和具体应用问题密切 相关。j j g r e f e n s t e t t e 利用离线性能( o f f - 1 i n ep e r f o r m a n c e ) 和在线性能 ( o n l i n ep e r f o r m a n c e ) 评价控制参数的优化效率，研究了用遗传算法来优化 控制参数“”。自适应的杂交率和变异率“”、特殊问题( 如组合优化问题) 的遗传 算子的研究“”也是遗传算法基本理论的重要研究内容。 2 、遗传算法的特点 遗传算法具有内在并行性( i n h e r e n tp a r a l l e l i s m ) 和内含并行性( i m p l i c i t p a r a l l e l i s m ) 。前者是指遗传算法的适应度评价是并行的，可以在并行机上进 行，同时，可以采用多群体进化，群体之间可以进行通信。后者是指遗传算法虽 然每代仅处理个个体( 为群体规模) ，但却有效处理了o ( n 3 ) 个模式。关 于遗传算法的并行处理研究多集中于前者。 3 、遗传算法的广泛应用 遗传算法的应用是一个发展最为迅速的研究方向。目前已经在模式识别o ”、 图象处理、人工智能进化计算的过去、现在与未来瞄”、经济管理、机械工 程啪一、电气工程嘲、通讯嘲、分子生物学3 等举不胜举的领域中获得了较成功 的应用。但如何将各专业的知识融入到遗传算法的算子中，目前仍在继续研究。 4 、基本遗传算法( s g a ) s g a 是一种统一的最基本的遗传算法，它只使用选择( s e l e c t i o n ) ，交叉 ( c r o s s e r ) ，变异( m u t a t i o n ) 这三种基本的遗传算子，其遗传进化操作过程简单， 容易理解，是其他一些遗传算法的雏形和基础，它不仅为各种遗传算法提供了一 个基本框架，同时也具有一定的应用价值。 ( 1 ) s g a 构成要素 a 、染色体编码方法。基本遗传算法使用固定长度的二进制符号串来表示群 体的个体，其等位基因( a l l e l e ) 是由二值符号集 0 ，1 ) 所组成的初始 群体中各个个体的对应位，基因值可用均匀分布的随机数来生成。 b 、个体适应度评价。s g a 使用与个体适应度成正比的概率来决定当前群体中 每个个体遗传到下一代群体中的机会多少，为正确计算这个概率，要求 所有个体的适应度必为正数或为0 。 c 、遗传算子。s g a 使用下述三种遗传算子：选择运算使用比例算子，交叉运 算使用单点交叉算子，变异运算使用基本位变异算子或均匀变异算予。 d 、运行参数。s g a 需提前设定：群体大小m ，即群体中含有的个体数目，一 般2 0 1 0 0 ；遗传运算的终止进化代数t ，一般取1 0 0 5 0 0 ；交叉概率只， 第二章基于小生境技术的协同进化算法 一般取0 4 0 9 9 ；变异概率p 】l l ，一般取0 0 0 1 0 1 。 ( 2 ) s g a 的实现 a 、个体适应度评价：在遗传算法中，以个体适应度的大小来确定该个体被 遗传到下一代群体中的概率。个体适应度越大，该个体被遗传到下一代 的概率越大，反之亦然。s g a 使用比例选择算子来决定群体中各个个体遗 传到下一代中的数量。要求所有个体的适应度必为正数或0 ，不能为负。 b 、比例选择算子：比例选择实际上是一种随机选择机制，也口q 赌盘选择， 因为这种方式与赌博中的赌盘操作非常相似。它具体的执行过程是：首 先算出群体所有个体适应度之和，其次计算出每个个体的相对适应度的 大小，比值即为各个个体被遗传到下一代群体中的概率，最后用模拟赌 盘操作来确定各个个体被选中的次数。 c 、单点交叉算子；它是最常用和最基本的交叉操作算子，操作步骤如下： 对群体的两两个体随机进行交叉配对，对每一对相互配对的个体，随机 设置某一基因座之后的位置为交叉点，对每一对相互配对的个体，依设 定的交叉概率在其交叉点处相互交换各个个体的部分染色体，即产生两 个新的个体。 d 、基本位变异算子：它的执行过程是对个体的每一个基因座依变异概率指 定其为变异点，对每一个指定的变异点，对其基因位做取反运算或用其 他等位基因值来代替，以产生一个新的个体。 ( 3 ) s g a 的执行步骤 a ，确定决策变量及各种约束条件，即确定个体的表现型x 和问题的解空间。 b ，建立优化模型，即描述目标函数的类型及其数学描述形式或量化方法。 c 、确定表示可行解的染色体编码方法即确定个体的基因型x 及其搜索空间。 d 、确定解码方法，即确定由个体基因型x 到个体表现型x 的对应关系或转换 方法。 e 、确定个体适应度的量化评价方法，即确定由目标函数值厂( 力到个体适应 度的转换规则。 f 、设计遗传算子，即确定选择运算、交叉运算、变异运算等遗传算子的具 体操作方法。 g 、确定遗传算法的有关运行参数。 ( 二) 进化策略( e s ) 进化策略e s 哪是二十世纪六十年代由德国的h p s c h w e f e l 和i r e c h e n b e r g 在研究流体动力学中的弯管形态优化过程中共同开发出的一种适合于实数变量 的、模拟生物进化的优化算法。其优化能力主要依靠变异算予的作用，后来受遗 6 第二章基于小生境技术的协同进化算法 传算法的启迪，也引入了杂交算子，不过，杂交是进化策略的辅助算子 早期进化策略的种群中只包含一个个体，而且只使用变异操作。在每一代变 异后的个体与其父体进行比较再选择两者之优。这一选择策略目前称为( 1 + 1 ) 策略。它使用的变异算子是基于正态分布的变异操作，这种进化策略称为( 1 + 1 ) 进化策略或二元( t w o - m e m b e r e d ) 进化策略。( 1 + 1 ) 进化策略存在很多弊端， 如有时收敛不到全局最优解，效率较低等。它的改进即是增加种群内个体的数量。 从而进化为( p + 1 ) 进化策略。此时种群有u 个个体，随机地选取一个个体进行 变异，然后取代群体中最差的个体。( p + 1 ) 进化策略与( 1 + 1 ) 进化策略的相 似之处是每次只产生一个后代，为了进一步提高效率，后来又发展为( p + ) 进化策略和( 1 j ， ) 进化策略，并且引进了重组( r e c o m b i n a t i o n ) 操作，即 由二个个体按类似于杂交的方式生成一个个体。( u + ) 进化策略根据种群内 的1 1 个个体产生x 个个体( 用变异和重组) ，然后将p + x 个个体进行比较再在 其中选取 个最优者。( p ， ) 进化策略则是在新产生的 个个体中选取| 1 个 最优者，这两种进化策略中的选择方法分别被称为九选择和p 选择。 进化策略和遗传算法的不同之处在于：遗传算法要将原问题的解空间映射到 位串空间之中，然后再实行遗传操作。它强调个体基因结构的变化对其适应度的 影响；而进化策略则是直接在解空间上进行操作，它强调进化过程中从父体到后 代行为的自适应性和多样性。从搜索空间的角度来说，进化策略强调进化过程中 搜索方向和步长的自适应调节。 进化策略主要用于求解数值优化问题。近年来，遗传算法也采用十迸制编码 技术来求解数值优化问题。e s 与g a 的互相渗透使得它们没有很明显的界限了。 ( 三) 遗传编程( g p ) 在遗传算法的发展中，将线性编码改进为非线性编码，是近年来提出的一种 新的思路。1 9 9 2 年s t a n f o r d 大学的j r k o z a 溉嘲首先提出了一种在编码方式上 与常规遗传算法有着本质不同的仿生进化算法，它采用了层式编码结构，由于在 遗传算法的基础上，改进了编码方法，他称之为“遗传编程” ( g e n e t i c p r o g r a m i n g ，简称g p ) ，同遗传算法一样，它们都属于新兴的进化计 算学科；但相对于遗传算法，遗传编程更适合应用于层式结构的优化。遗传编程 g p 是由遗传算法发展、延伸而来的，传统的遗传算法是用定长的线性字符串表达 问题，而工程中许多复杂问题往往不能用简单的字符串表达所有的性质，因此有 必要对传统的遗传算法进行改进。遗传编程就是在此背景下产生的，它与遗传算 法最大的不同是以层次结构( “树”型) 表达问题，而且其结构与大小都是动态 自适应调整；因此，遗传编程更适于表达复杂的结构问题。遗传编程的任务就是 从由许多树型可行解组成的搜索空间中寻找出一个具有最佳适应度的“树”。遗 7 第二章基于小生境技术的协同进化算法 传编程提供了一套寻找具有最好适应度的“树”的方法。目前，遗传编程的研究 已经渗透到工程技术科学，生命科学及社会科学的各个领域中。 ( 四) 进化编程( e p ) 进化编程e p 是在二十世纪六十年代提出的。美国的l j f o g e l 等为求解预 测问题提出了一种有限状态机进化模型，在这个进化模型中，机器的状态基于均 匀随机分布的规律来进行变异侧。九十年代，d b f o g e l 借助于进化策略方法对 进化规则进行了发展，又将其思想拓展到实数空间，使其能够用来求解实数空间 中的优化问题，并在其变异中引入正态分布技术，后来用到数值优化及神经网络 的训练等问题之中m 。它与进化策略有许多相似之处。个体的表示同进化策略， 不同之处在于它不用杂交算子，变异与选择方式也与进化策略不同。 进化计算学科的出现，促进了它的不同分支之间的交流，可以取长补短。上 述四个主要分支是由不同的学者独立提出的，在1 9 9 2 年之前，基本上是独立发 展，没有交流。各个分支都有自己的优缺点，研究它们的优越性，并融合成新的 进化算法，可以促进进化计算更广泛的应用。目前，进化计算已经在人工智能、 知识发现、模式识别、图象处理、决策分析、产品工艺设计、生产调度、股市分 析等仍然不断增加的领域中发挥出了显著的作用。 2 1 3 进化计算的设计 生物学术语与其在进化计算中的应用对照如表2 - 1 所示。 表2 1 生物学术语与其在进化计算中的应用对照 生物学遗传算法 染色体字符串 基因字符位 基因型字符串结构 表现型字符串含义 杂交字符串片段的互换 变异字符位的改变 参照生物进化规则，在设计进化算法时，通常按以下的基本步骤进行： 1 确定编码方案：进化算法求解问题不是直接作用在问题的解空间上，而是利 用解的某种编码表示。选择何种编码表示有时将对算法的性能、效率等产生 很大的影响。进化算法求解问题时，既可以用编码转换的形式表示个体( 例 如：6 a ) ，也可以直接采用解空间的向量表示个体( 例如：e s ，e p ) 。 8 第二章基于小生境技术的协同进化算法 2 确定适应度评价函数：适应度是对解的质量的一种度量，它通常依赖于解的 行为与环境( 即种群) 的关系。一般以目标函数的形式表示。解的适应度是 进化过程中进行选择的唯一依据。 3 选择策略的确定：优胜劣汰的选择机制使得适应度高的解有较高的存活概率， 这是进化算法与一股搜索算法的主要区别之一。不同的选择策略对算法的性 能也有较大的影响。 4 遗传算子的设计：进化算法中的遗传算子主要包括选择( s e l e c t i o n ) 、复制 ( r e p r o d u c t i o n ) 、交叉( c r o s s o v e r ) 、变异( m u t a t i o n ) 以及其他高级操作。 5 控制参数的选取：控制参数主要包括编码串长度、群体规模、执行不同遗传 操作的概率、算法执行的最大代数以及其他一些辅助性的控制参数。 6 确定算法的终止准则：由于进化算法没有利用目标函数的梯度等信息，所以 在进化过程中，无法确定个体在解空间的位置，从而无法用传统的方法来判 定算法的收敛与否以终止算法。常用的方法是预先规定一个最大的进化代数， 或规定算法在连续多少代以后解的适应度没有明显改进时即终止。 进化算法流程如图2 - 2 所示： l 迭代过程 图2 2 进化算法流程 2 1 4 进化计算的国际国内研究现状 进化计算的研究与应用，无论是研究队伍的规模，发表的论文数量还是网上 的信息资源，发展速度都很快，已经得到了国际学术界的广泛认可。1 9 9 4 年， i e e e 神经网络委员会主持召开了第一届进化计算国际会议，并成立了i e e e 进化 9 第二章基于小生境技术的协同进化算法 计算委员会，此会每3 年与i e e e 神经网络国际会议、i e e e 模糊系统国际会议在 同一地点先后连续举行，共同称为i e e e 计算智能c i 国际会议，并分别出版并列的 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 ，i e e et r a n s a c t i o n so n n e u r a ln e t w o r k s 和i e e et r a n s a c t i o n so nf u z z ys e t 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 a c h i n e l e a r n i n g ：i e e et r a n s a c t i o n so ns y s t e m s ，m a na n dc y b e r n e t i c s ：c o m p l e x s y s t e m s ：a r t i f i c i a li n t e l l i g e n c e 等重要国际期刊上经常见到。由此可见进 化计算的发展之快。除了i e e e 举行的进化计算国际会议以外，其实，早在1 9 8 5 年，就在美国的p i t t s b u r g h n 开- 第一届遗传算法国际会议口7 1 ，在会议期间，国 际遗传算法学会( i n t e r n a t i o n a ls o c i e t yo fg e n e t i ca l g o r i t h m s ) 也宣告成 立。自此，来自不同学科和工程应用领域的各国学者在遗传算法方面有了交流、 探讨的国际论坛。国际遗传算法会议每两年召开一次洲。此外，其他类型的各 种会议，如以遗传编程、进化策略或进化编程为主题的研讨会也很频繁“”。 i n t e r n e t 技术的发展给进化计算的研究者带来了丰富的信息资源，使他们可以 获取更广泛、快捷的交流以及极大地获取有关进化计算的科研资料，同时可以随 时了解有关进化计算研究与应用的最新进展。 美国海军后勤研究中心对进化计算的研究极为重视，于1 9 8 5 年首先在电 子网络上建立了全球性的有关遗传算法的信息交流节点 ( g a - l i s t r e q u e s t o a i c n r l n a v y m i l ) ，不定期编辑出版电子遗传算法文摘( g a d i g e s t ) ，交流有关遗传算法的最新信息( 如有关研究和应用以及会议等方面的 最新信息) 。网络上与进化计算有关的信息实际上是一个有关进化计算的巨大资 料库，为使研究人员更方便地利用这些资源，在交互网络上建立了几个比较大的 节点，称为e n c o r e ( e v o l u t i o n a r yc o m p u t a t i o nr e p o s i t o r yn e t w o r k ) 。通过 这几个节点中的任一个，不仅可以了解到网络上主要的有关进化计算的信息，而 且可以获取自由软件，交流科技报告等，如，可获得1 9 5 7 年到现在的所有有关 遗传算法的科技论文的目录，该目录中包括2 5 0 0 多篇文献。”。 除了期刊、会议、电子信息库外，进化计算的软件也形成商业化产品。根据 系统开发和设计目标的不同，可分为三类：面向应用的系统、面向算法的系统和 工具包系统，在面向应用的系统中，采用了许多创新性的策略，如p c b e a g l e 和 x p e r t r u l e ，g e r n s y s 等系统可用遗传算法生成知识域的新规则。 国外进化计算的研究内容十分广泛，发展也瞬息万变。下面概述一下国外的 研究现状，特别是美国、英国和德国等走在进化计算研究前列的国家的研究成果。 ( 1 ) 美国1 1 1 i n o i s 大学的d e g o l d b e r g 在他领导的i i i i n o i s 遗传算法实验室 第二章基于小生境技术的协同进化算法 ( i i i i n o i sg e n e t i ca l g o r i t h m sl a b o r a t o r y ，l l l i g a l ) 中对遗传算法的基本 理论进行了广泛地研究，取得了一系列的成果“”。早在1 9 8 9 年，他就出版了目 前被认为是遗传算法最经典、最全面的教科书。 ( 2 ) h k a r g u p t a 将s h a n n o n 的信息熵呻1 引入遗传算法，研究了遗传算法群体的多 样性，他借鉴了通信领域中的信息冗余性，研究了在不损失进化群体的多样性的 情况下如何提高冗余性嘲1 。 ( 3 ) 关于遗传算法的控制参数的优化和优化效率的性能评估的研究也引起一些 学者的重视，遗传算法的控制参数是指群体规模、杂交率、变异率以及其他一些 遗传算法的参数。目前，还没有一种通用的方法，可以根据要解决的问题自动地 设置高效的控制参数，只能根据经验和多次运行遗传算法的结果进行人工设置和 修正。j j g r e f e n s t e t t e 利用遗传算法来优化遗传算法的控制参数( m e t a g a ) ， 通过k a d e j o n g 提出的优化效率的性能评价指标“在线性能”与“离线性 能”叫来构造适应度，获得了一些有益的结论。 ( 4 ) h o l l a n d 的标准遗传算法并没有提供如何解决约束优化问题，在应用遗传算 法解决工程中的复杂优化问题时，对于约束的处理是一个至关重要的问题。 m i c h a l e w i c z 对此作了坚持不懈地研究，提出了几种较有效的方法“。对于约束 的处理，应用最多的方法是惩罚函数法。 ( 5 ) 模式识别是机器智能与自动化的支撑技术，进化计算在模式识别中也发挥了 它的优势，主要集中在特征提取上。从n 个初始特征中选出n ( n n ) 个有效特征 是一个典型的n p 问题，进化计算可以在不搜索全部解空间的情况下，获得最佳 的或接近最佳的有效特征集“”。 ( 6 ) 进化计算的优势之一在于全局优化性，而其局部优化性却不足，因此，有的 学者提出将进化计算与其他局部优化方法进行结合，实践证明局部优化性得到了 提高刚。 ( 7 ) 近年来，进化计算的专著也不断推出，极大地丰富和促进了进化计算的研究 耵踟 。 由于进化计算与传统优化技术相比，具有许多优势，而且在人工智能中有着 广阔诱人的应用前景，国内对进化计算自九十年代以来也开展了广泛地研究工 作，特别是将进化计算应用在不同的领域中，取得了令人瞩目的成就。但与国外 相比，国内对进化计算的理论基础研究还不够深入。 国内以武汉大学软件工程国家重点实验室为领先。进化计算( 他们称之为“演 化计算”) 成为他们的并行计算研究室的一个重要的研究方向，目前已经出版了 专著1 ，并有许多硕士、博士研究生围绕进化计算选题。另外，中国科学技术大 学的陈国良教授等出版了遗传算法的著作”。最近三年来，西安交通大学以进化 第二章基于小生境技术的协同进化算法 计算为主题的研究工作也逐渐活跃起来，