（管理科学与工程专业论文）进化技术及其在计算机辅助概念设计中的应用.pdf

独创声明 ￥5 9 8 7 3 5 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得( 注：如没有其他需要特别声明的，本栏可 空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同 志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名：翊进 、 导师签字：3 、协c ；2 7 签字日期：20 0 4 年年月2 日签字日期：20 0 4 年叶月“日 i 鬈臻、导师同童 匆全文公布 摘要 摘要 进化技术是基于“适者生存、不适应者淘汰”思想而发展起来的一种通用的问题求解 技术。它采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的 遗传操作和优胜劣汰的自然选择来指导学习和确定搜索方向。进化技术不仅具有较高的效 率而且具有简单、易于操作和通用的特征，而且这些特征正是进化算法越来越受到人们青 睐的主要原因之一。 进化技术在一些设计优化问题中已有相当数量的应用，但距离实现一个能与人的行为 相匹配的系统还很远。尤其是在一些创新设计应用，如建筑、艺术、音乐、设计，由于评 价标准主要依赖于人的主观想法，很难对个体的适应度做出评价。如何能在执行最优化的 过程中，将适应度函数与偏序理论相结合，从而构造新的评价方法，成为计算机辅助概念 设计的研究热点。 本文首先概要介绍了进化技术的基本思想，以及概念设计与计算机辅助概念设计的含 义，探讨了进化技术在概念设计中应用的现状，并分析了当前该研究领域中存在的主要问 题。 第2 章对进化技术进行了分析。首先，深入分析了进化计算的特点、分类：以遗传算 法为例分析了进化算法的设计方法；介绍了遗传算法的基本定理并对遗传算法的收敛性进 行了分析，给出了一个统一的收敛标准。然后，介绍了基于树结构的遗传算法。最后，给 出了基于偏序关系的进化技术，以及利用它求解概念设计问题的步骤。 第3 章对概念设计的原理、方法进行了研究。首先，介绍了概念设计及计算机辅助概 念设计的含义，指出目前c a c d 的研究内容主要有三方面：概念设计方法学、产品信息模 型及基于该模型的概念设计求解方法的研究、c a c d 系统的研制；然后，介绍了本文所用 到的三种概念创新设计方法：基于组合原理的概念创新设计方法、进化设计方法、基于实 例推理的概念创新设计方法，并介绍了产品信息模型的建立技术；最后，结合传统的计算 机辅助概念设计方法以及组合原理和进化技术，提出了一种概念创新设计的求解方法。 第4 章研究进化技术在计算机辅助概念设计中的应用。本章实现了一个基于进化技术 的计算机辅助概念设计系统。首先，给出了系统的总体结构，指出本系统由三部分组成： 基于进化技术的组件创新模块、三维模型数据库、基于进化技术的创新设计方案生成模块。 然后，分别对系统的三个部分进行了介绍，在基于进化技术的创新设计方案生成模块中， 系统把对设计方案评价的若干个目标构成偏序关系，以此作为对设计方案进行排序的依 据：另外，系统采用计算机评价与人工评价相结合的方式，当进化算法连续若干代，设计 方案仍无明显改进时，交互e a 与自主e a 之间的接口子模块将通知交互e a ，发挥人的作 用，以设计师的评估来替代计算机对个体的评估，从而设计出满意的新的创新设计方案。 最后，用实验数据证明了本系统的工作效率。 本文在进化技术及其在计算机辅助概念设计中的应用方面进行了探讨，希望能够对进 第1 页 摘要 化技术及其在概念设计中的应用起一定的推动作用。 关键词：进化技术，偏序关系，计算机辅助概念设计，组合原理，进化设计，实例推理 中图分类号：t p 3 9 1 7 2 第2 耍 垒! ! 翌! ! e v o l u t i o n a r yt e c h n i q u e a n di t sa p p l i c a t i o ni nc o m p u t e r a i d e d c o n c e p t u a ld e s i g n a b s t r a c t e v o l u t i o n a r yt e c h n i q u ei sa u n i v e r s a lt e c h n i q u ei ns o l v i n gp r o b l e m s ，w h i c hd e v e l o p so nt h e b a s i so f s u r v i v a lo ft h ef i t t e s t c o d i n gt e c h n i q u ei s e m p l o y e di ne v o l u t i o n a r yt e c h n i q u et o e x p r e s sc o m p l e x s t r u c t u r e s i ne v o l u t i o n a r yt e c h n i q u e ，s t u d yi sg u i d e da n ds e a r c h i n gd i r e c t i o n s a r ed e t e r m i n e db yg e n e t i co p e r a t i o n so nc o d i n gs t r i n g s n o to n l yd o e se v o l u t i o n a r yt e c h n i q u e h a v eh i 【g he f f i c i e n c y ，b u ti ti sa l s ou n i v e r s a la n de a s yt ob ei m p l e m e n t e da n dt h e s em e r i t sa r e j u s tp a r to f t h em a i nr e a s o n sw h yi ti sf a v o r a b l e e v o l u t i o n a r yt e c h n i q u eh a ss h o w n a g r e a tp o t e n t i a lt ow o r k o u ts e v e r a lr e a l w o r l dp r o b l e m s i nt h ep o i n to fo p t i m i z a t i o n ，b u ti ti ss t i l l q u i t ef a r f r o mr e a l i z i n gas y s t e mo fm a t c h i n gt h e h u m a np e r f o r m a n c e e s p e c i a l l y ，i nc r e a t i v ea p p l i c a t i o n ss u c ha sa r c h i t e c t u r e ，a r t m u s i c ，a n d d e s i g n ，i ti sd i f f i c u l tt oe v a l u a t et h ef i t n e s sb e c a u s et h em e a s u l ed e p e n d sm a i n l yo n t h eh u m a n m i n d i ti sb e c o m i n gas t u d ) f o c u sh o wt oc o m b i n ef i t n e s sf u n c t i o na n dp a r t i a lo r d e rt h e o r yt o c o n s t r u c tan e wm e t h o df o re v a l u a t i o n i nt h i s p a p e r ，c h a p t e r 1 p r e s e n t s a g e n e r a l i n t r o d u c t i o nt oe v o l u t i o n a r yt e c h n i q u ea n d c o m p u t e r a i d e dc o n c e p t u a ld e s i g n t h e ni t d i s c u s s e st h ep r o g r e s so fe v o l u t i o n a r yt e c h n i q u ei n c a c d ，f o l l o w e db yt h ea n a l y s i so f t h em a i n p r o b l e m si nt h i sr e s e a r c h i n g f i e l d c h a p t e r2i sd e v o t e dt oe v o l u t i o n a r yt e c h n i q u e f i r s t ，i ta n a l y z e st h ec h a r a c t e r i s t i c sa n d t h e c l a s s i f i c a t i o no fe v o l u t i o n a r yt e c h n i q u e ju s e sg e n e t i ca l g o r i t h m ( g a ) i ni l l u s t r a t i o no fh o wt o d e s i g ne v o l u t i o n a r ya l g o r i t h m s ( e a s ) ，i n t r o d u c e sb a s i ct h e o r e m so fg a ，a n a l y z e sa s t r i n g e n c yo f g a a n dp r e s e n t sau n i f o r ms t a n d a r df o ra s t r i n g e n c y t h e nak i n do fg ab a s e do nt r e es t r u c t u r e i sr e v i e w e df i n a l l y i tp r e s e n t sa ne v o l u t i o n a r yt e c h n i q u eb a s e do i lp a r t i a lo r d e r ，f o l l o w e db yt h e p r o c e s s i ns o l v i n g c o n c e p t u a ld e s i g np r o b l e m sw i t h t h i st e c h n i q u e c h a p t e r3i n v e s t i g a t e st h et h e o r i e sa n dt e c h n i q u e so fc o n c e p t u a ld e s i g n f i r s t i ti n t r o d u c e s t h ed e f i n i t i o no fc o n c e p t u a ld e s i g na n dc o m p u t e r - a i d e dc o n c e p t u a ld e s i g n a n ds u m m a r i z e st h e m a i ni s s u e si nt h ep r o g r e s so fr e s e a r c h e so nc a c d ：m e t h o d o l o g yo fc o n c e p t u a ld e s i g n p r o d u c t i n f o r m a t i o n m o d e l i n g r e s o l u t i o nm e c h a n i s m so fc o n c e p t u a ld e s i g n a n dc a c dt e c h n o l o g y t h e ni ti n t r o d u c e s3m e t h o d so fc o n c e p t u a ld e s i g n ，w h i c ha r ee m p l o y e di nt h i sp a p e r ：t h e m e t h o db a s e do nc o m b i n a t i o np r i n c i p l e e v o l u t i o n a r 3 d e s i g nm e t h o da n dc a s e b a s e dr e a s o n i n g m e t h o d a n di n t r o d u c e st h et e c h n i q u eo fp r o d u c ti n f o r m a t i o nm o d e l i n g f i n a l l y i tp r e s e n t sa r e s o l u t i o nm e c h a n i s mo fc o n c e p t u a l d e s i g nb yc o m b i n i n gt r a d i t i o n a l m e t h o d ，c o m b i n a t i o n p r i n c i p l ea n de v o l u t i o n a r yd e s i g n c h a p t e r4p r e s e n t s ac o n c e p t u a l d e s i g ns y s t e mb a s e do ne v o l u t i o n a r yt e c h n i q u e f i r s t i t p r e s e n t st h es t r u c t u r eo f t h es y s t e m ，p o i n t i n go u tt h a tt h es y s t e mc o n s i s t so f3 p a r t s ：t h em o d u l e 第3 负 b a s e do n e v o l u t i o n a r yt e c h n i q u e t o g e n e r a t e c r e a t i v e c o m p o n e n t s ，a d a t a b a s eo ft h r e e d i m e n s i o n a lm o d e l sa n dt h em o d u l eb a s e do ne v o l u t i o n a r y t e c h n i q u et og e n e r a t e c r e a t i v e d e s i g n s t h e n i ti n t r o d u c e st h e3 p a r t sr e s p e c t i v e l y i n t h em o d u l eb a s e do ne v o l u t i o n a r y t e c h n i q u e t og e n e r a t ec r e a t i v ed e s i g n s ，t h em o d u l ee v a l u a t e sd e s i g n sa c c o r d i n gt oa p a r t i a lo r d e r c o n s t i t u t e db ys e v e r a le v a l u a t i n go b j e c t s i na d d i t i o n ，t h em o d u l ei n t e g r a t e sc o m p u t e re v a l u a t i o n a n da r t i f i c i a le v a l u a t i o n i fn oo b v i o u si m p r o v e m e n ti sa c h i e v e di nt h e s ed e s i g n sa f t e rs e v e r a l g e n e r a t i o n s ，am e s s a g e w i l lb es e n tt oi n t e r a c t i v ee a b yt h ei n t e r f a c eb e t w e e ni n t e r a c t i v ee a a n di n d e p e n d e n c ee a t h e na r t i f i c i a le v a l u a t i o nw i l lb em a d ef o rt h e s ed e s i g n st ow o r ko u t s a t i s f a c t o r yc r e a t i v ed e s i g n s f i n a l l y ，t h ee f f i c i e n c yo f t h es y s t e mi sp r o v e db ye x p e r i m e n td a t a a s t u d yi sc o n d u c t e d o ne v o l u t i o n a r yt e c h n i q u ea n di t sa p p l i c a t i o ni nc a c d i nt h i sp a p e r i ti sh o p e dt h a ti tc o u l dp r o m o t et h ed e v e l o p m e n to fe v o l u t i o n a r yt e c h n i q u ea n di t sa p p l i c a t i o ni n c a c d k e y w o r d s ：e v o l u t i o n a r yt e c h n i q u e ，p a r t i a l o r d e lc o m p u t e r a i d e dc o n c e p t u a ld e s i g n ， c o m b i n a t i o np r i n c i p l e ，c a s e b a s e dr e a s o n i n g c l a s s i f i e a t i o n ：t p 3 9 17 2 第4 页 第l 章绪论 1 1 研究背景 第1 章绪论 大自然是人类解决各种问题时获得灵感的源泉。几百年来，将生物界所提供的答案应 用与实际问题求解己被证明是一个成功的方法，并且已形成一个专门的科学分支仿生 学。自然界所提供给人类的答案是经过漫长的自适应过程进化过程而获得的结果。出 了进化过程的最终结果，也可以利用这一进化过程去解决一些较为复杂的问题。人们不必 非常明确地描述出问题的全部特征，只需要根据自然法则来产生更好的解。 进化技术f 是基于这种思想而发展起来的一种通用的问题求解技术。它采用简单的编 码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的 自然选择来指导学习和确定搜索方向。由于它采用种群( 即一组编码表示) 的方式组织搜 索，这使得它可以同时搜索解空间内的多个区域。而且用种群组织搜索的方式使得进化算 法特别适合大规模并行计算。在赋予进化技术自组织、自学习、自适应等特征的同时，优 胜劣汰自然选择和简单的遗传操作使进化计算具有不受其搜索空间限制性条件的约束及 不需要其它辅助信息的特点。这些新的特点使得进化算法不仅获得较高的效率而且具有简 单、易于操作和通用的特征，而且这些特征正是进化算法越来越受到人们青睐的主要原因 之一。 基于进化技术的概念设计是复杂面富创造性的活动，是进化方法和逻辑推理的结合， 一方面体现出设计思维的诸多特征；另一方面为形象思维和创造性思维的计算机实现提供 了一定程度上的可能性，拓展了设计方法学和设计自动化的研究思路。 1 1 1 进化技术 达尔文进化论思想在自动问题解决中的应用始于2 0 世纪5 0 年代，远在计算机飞速发 展阶段之前【1 1 。2 0 世纪6 0 年代，进化论思想的三种不同实现分别在三个地方发展起来。 在美国，f o g e l 提出了进化规戈1 ( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) b ，3 】，而h o l l a n d 称他的方法 为遗传算法( g e n e t i ca l g o r i t t m a ，g a ) h ”。在德国，r e c h e n b e r g 和s c h w e f e l 发明了进化策略 ( e v o l u t i o n a r ys t r a t e g y ，e s ) 扣”。在以后的大约1 5 年中，这些领域分别有了自己的发展；自 从2 0 世纪9 0 年代初，它们成为了一门技术的不同分支，这门技术就是进化计算。同样是 在2 0 世纪9 0 年代初，第四个分支遗传程序设计( g e n e t i cp r o g r a m m i n g ，g p ) 出现了1 8 , 9 1 。 这整个领域称为进化计算，又称为进化算法。进化规划、遗传算法、进化策略和遗传程序 设计是它的四个分支。 进化技术的基本出发点是基于对生物进化过程的模拟，在求解问题时，不是直接作用 在问题的解空间上，而是利用解的某种编码表示，它为求解复杂系统优化问题提供了一种 通用的框架，。下面给出进化技术求解问题的基本框架： 进化代数计数器初始化：t 卜0 ； 随机产生初始群体p ( t 1 ： 评价群体p ( t ) 的适应度 第5 页 第1 章绪论 个体交叉操作：p 7 ( f ) 卜c r o s s o v e r p ( t ) 】 个体变异操作：p ”( r ) 卜m u t a t i o n p ( r ) 】 评价群体p ”( f ) 的适应度； 个体选择、复制操作：e ( t + 1 ) 卜r e p r o d u c t i o n p ( t ) up ”( r ) ； 终止条件判断。若不满足终止条件，则f - - - t + 1 ，转到第步，继续进行进化操作 过程；若满足终止条件，则：输出当前最优个体，算法结束。 1 1 2 计算机辅助概念设计 1 概念设计 概念设计是设计过程的早期阶段，其目标是获得产品的基本形式或形状。 广义上的概念设计包含了从产品的需求分析到进行详细设计之前的设计过程。它包括 功能设计、原理设计、形状设计、布局设计和初步的结构设计。概念设计的各个环节紧密 相连，在设计过程中互相依赖，互为驱动。 一般意义上的概念设计是指在产品的功能和原理基本确定的情况下，产品外观造型的 设计过程。 2 计算机辅助概念设计 计算机辅助概念设计( c o m p u t e r a i d e dc o n c e p t u a ld e s i g n ，c a c d ) 是c a d 领域的一个 重要分支。概念设计是一个相当复杂的过程，因为一个好的设计方案既要有合理的功能结 构、美观的造型、简便的操作，同时还要富有创新性。因此，c a c d 涉及设计方法学、人机 工程学、人工智能技术、c a d 技术以及认知与思维科学。 目前已有的许多c a d 系统，如a u t o c a d 、3 d sm a x 、a u t o d e s ki n v e n t o r 等，它们的着 眼点主要是“设计表达”，存在许多约束限制，从而导致其基本上是一个在设计方案基本 定型之后的概念化( 草图化) 绘图工具，而非辅助设计工具。所以，如何运用c a d 技术研制 出c a c d 系统，支持从需求分析到方案求解的概念设计全过程，就成为c a c d 需要解决的主 要问题之一。 针对上述情况，c a c d 的研究以及c a c d 系统的开发就应运而生了。c a c d 系统的根 本目的就在于能有效支持产品的创新设计。在设计早期应用c a c d 系统至少有以下好处： 能满足概念设计师的各类特殊需求，能有效提高概念设计的质量，能更为简捷地生成设计 对象，能提供一个进行信息交流和对象评价的更好的平台，可以避免因设计失败而造成的 浪费。 1 1 3 相关工作 进化技术在一些设计优化问题中已展示出巨大的潜力，目前，在产生潜在创新个体方 面已经有一些研究与应用：如澳大利亚悉尼大学的j o h ns g e r o 等详细阐述了应用遗传 算法进行布局设计的问题i lu j ；香港理工大学的f r a z e r 教授领导的研究小组将遗传算法应用 于玻璃杯设计l 、建筑设计以及t a n g i b l ei n t e r f a c e 的研究当中；钱志勇等综合了人机交互 的遗传算法并在约束布局优化中得到了应用z j ：b a l a k r i s h n a n 等从杂交、变异和新群体的 产生机制三个角度描述了一种改进的遗传算法，并应用于动态布局问题的求解1 13 j ；韩国的 第6 页 第1 章绪论 h e e - s uk i m 将交互式遗传算法应用于服装设计中【1 4 l ；山东师范大学的刘希玉教授将进化 技术应用于建筑概念设计中【l ”，刘弘教授将进化技术应用于概念创新设计中”1 。 另外，进化技术在设计问题参数优化方面也已经有一些应用，如：b e n t l y 年l ? w a k e f i e l d 1 6 提出了一个用于设计光学棱镜的自动创新设计系统。f u n e s 芹1 p o l l a c k ”用人工进化来产生 可实现特定目标的二维或三维l e g o ( 垒高拼装玩具) 结构。这样得到的结构十分合适，而且 远远好于人工设计的结构。t o u r a 年1 n a g a s a k a l l 8 1 用独特的方法来表示基因型、“胚层”1 1 9 l 、 和表现型，从而实现人造卫星的外形设计。他们采用了一种所谓的适应演变型外形表示法： 实际的外形是由繁殖规则与外界环境的交互决定的。英国l o u g h b r o u g h 大学的i 。j g r a h a m 将 遗传算法应用于计算机辅助设计中 2 0 1 ，论述了遗传算法在计算机辅助设计系统中应用的新 进展。 1 2 问题提出 进化技术在一些设计优化问题中已有相当数量的应用，但距离实现一个能与人的行为 相匹配的系统还很远。尤其是在一些创新设计应用( 如建筑、艺术、音乐、设计) 中，由于 评价标准主要依赖于人的主观想法，很难对个体的适应度做出评价。目前研究中存在的问 题主要有： 1 选择操作需要由人工来完成 由于设计目标的复杂性定义一个能描述刻画设计优劣的适应度函数极为困难，因此， 目前的概念设计的方法主要是运用人机交互技术：在执行最优化的过程中，让设计师对个 体做出评价，反复进行人机交互，最终得到设计师心目中理想的设计方案。但也存在一个 问题：在个体数目非常多的情况下，势必会加大设计师的工作量、降低系统的运行速度。 2 进化算子的设计问题 现有的设计方法f 2 1 】大多采用单点交叉，但单点交叉容易产生过早收敛。搜索缺乏健壮 性。 3 编码技术 b e n t l y 提出的实体分割技术只适合描述外形是平面的实体，很难用于曲面体的描述。 另外，现有的基于二进制编码的概念设计方法为了避免在进化过程中产生无效个体， 大多采用染色体变异 2 1 , 1 4 1 。但在方法实现上，染色体变异比单比特变异更为复杂。如果在 编码时，让组件的数目与二进制编码表示的最大数目相等( 例如：用3 个二进制位表示染 色体，那么就组件的个数为8 ，那么染色体的编码就可取遍0 0 0 1 l l 范围内所有二进制值) ， 就可将单比特变异应用于设计问题中了。 1 3 本文的内容及主要工作 本文针对上述问题，对现有的进化算法进行改进，针对设计问题，在执行最优化的过 程中，将适应度函数与偏序理论相结合，从而构造新的评价方法，对设计方案进行评价、 排序。 本文的研究内容组织如下： 第2 章对进化技术进行了分析。首先深入分析了进化计算的特点、分类；以遗传算法 为例分析了进化算法的设计方法：介绍了遗传算法的基本定理并对遗传算法的收敛性进行 了分析，给出了一个统一的收敛标准。然后，给出了基于偏序关系的进化技术，以及利用 此技术的解决问题的算法结构。最后，分析了进化技术在设计问题中的应用价值。 第7 页 第1 章结论 第3 章对概念设计的原理、方法进行了研究。首先，介绍了概念设计及计算机辅助概 念设计的含义，指出目前c a c i ) 的研究内容主要有三方面：概念设计方法学、产品信息模 型及基于该模型的概念设计求解方法的研究、c a c d 系统的研制。然后，介绍了本文所用 到的三种概念创新设计方法：基于组合原理的概念创新设计方法、进化设计方法、基于实 例推理的概念创新设计方法，并介绍了产品信息模型的建模技术。最后，结合传统的计算 机辅助概念设计方法以及组合原理和进化技术，提出了一种概念创新设计的求解方法。 第4 章研究进化技术在计算机辅助概念设计中的应用。本文把对设计方案评价的若干 个目标构成偏序关系，以此作为对设计方案进行排序的依据；另外，本文采用计算机评价 与人工评价相结合的方式。当进化算法连续若干代，设计方案仍无明显改进时，交互e a 与自主e a 之间的接口子模块将通知交互e a ，发挥人的作用，以设计师的评估来替代计 算机对个体的评估，从而设计出满意的新的创新设计方案。 第8 页 第2 章进化技术分析 2 1 计算与进化 第2 章进化技术分析 制造具有智能的机器一直是人类的梦想，直到1 9 5 6 年人工智能技术的出现，人们为 此做出了巨大的努力。近年来，随着人工智能应用领域的不断扩大，传统的基于符号处理 机制的人工智能方法在解决知识表示、处理模式信息及解决组合矛盾等方面的问题所遇到 的困难变地越来越突出。 基于上述原因，寻求一种适于大规模并行而且具有某些智能特征( 如自组织、自学习、 自适应等) 的算法已成为有关学科的一个研究目标。而近些年来，一些新的研究方向如神 经网络、细胞自动机和进化计算等，由于它们都是模拟某一自然现象或过程而发展起来的， 并且具有适于高度并行与自组织、自学习、自适应等特征，引起了人们的极大兴趣。这些 新方法通过“拟物”和“仿生”以使问题得到解决，它们为解决某些复杂问题提供了新的 契机。 大自然是人类解决各种问题时获得灵感的源泉。几百年来，将生物界所提供的答案应 用与实际问题求解已被证明是一个成功的方法，并且已形成一个专门的科学分支仿生 学。自然界所提供给人类的答案是经过漫长的自适应过程进化过程而获得的结果。出 了进化过程的最终结果，也可以利用这一进化过程去解决一些较为复杂的问题。人们不必 非常明确地描述出问题的全部特征，只需要根据自然法则来产生更好的解。 进化计算正是基于这种思想而发展起来的一种通用的问题求解方法。它采用简单的编 码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的 自然选择来指导学习和确定搜索方向。由于它采用种群( 即一组编码表示) 的方式组织搜 索，这使得它可以同时搜索解空间内的多个区域。而且用种群组织搜索的方式使得进化算 法特别适合大规模并行计算。在赋予进化计算自组织、自学习、自适应等特征的同时，优 胜劣汰自然选择和简单的遗传操作使进化计算具有不受其搜索空间限制性条件的约束及 不需要其它辅助信息的特点。这些新的特点使得进化算法不仅获得较高的效率而且具有简 单、易于操作和通用的特征，面且这些特征正是进化算法越来越受到人们青睐的主要原因 之一。 进化计算在2 0 世纪六七十年代并未受到普遍的重视。其主要原因一是当时这些方法 本身还不够成熟；二是这些方法需要较大的计算量，而当时的计算机还不够普及而且速度 也达不到要求，这样就限制了它们的应用：三是当时基于符号处理的人工智能方法正处于 其顶峰状态，使得人们难以认识到其它方法的有效性及适应性。到了2 0 世纪8 0 年代，人 们越来越清楚地意识到传统人工智能方法的局限性，并且由于计算机速度的提高以及并行 计算机的普及，进化计算表现出很好的应用前景。根据德国d o r t m u n d 大学在1 9 9 3 年末的 一份研究报告报道，进化算法已在1 6 个大领域和2 5 0 多个小领域中得到了应用。 当前，进化计算的研究内容十分广泛，主要集中在进化计算的理论研究、进化计算的 设计与分析、进化优化、进化人工神经网络、并行和分布式进化计算、进化机器学习、硬 件进化及进化软件等领域以及在这些领域中的应用研究。可以预料，随着进化计算理论的 不断深入和应用领域的不断拓宽，进化计算必将取得更大的成功。 第9 页 第2 章进化技术分析 2 1 1 进化计算的特点 进化算法与传统的算法有很多不同之处，最主要的特点体现在下述几个方面。 ( 1 ) 智能性 进化计算的智能性包括自组织、自学习、自适应等特点。应用进化计算求解问题时， 在确定了编码方案、适应度函数及遗传算子以后，遗传算法将利用进化过程中获得的信息 自行组织搜索。由于基于“适者生存、不适应者淘汰”的选择策略，适应度大的个体具有 较高的生存概率。通常适应度大的个体具有与环境更适应的基因结构，再通过交叉和基因 变异等遗传操作就可能产生更适应环境的个体，进化算法的这种白组织、自适应特点同时 也赋予了它根据环境的变化自动发现环境的特性和规律的能力。自然选择消除了算法设计 过程， j 的一个最大障碍：即需要事先描述问题的全部特点，并说明针对问题的不同特点算 法应采用的措施。因此，利用进化算法可以解决那些具有未知结构的复杂问题。 ( 2 ) 本质并行性 进化计算的本质并行性表现在两个方面：一是进化计算内在并行性( i n h e r e n t p 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 ) ，由于进化计算采用种群的方式组织搜索，从而它可以同时搜索解空间内的多 个区域，这种搜索方式能以较少的计算获得较大的收益。 ( 3 ) 其它特点，如过程性、多解性、不确定性、非定向性、内在学习性、统计性、稳健 性、整体优化性。 进化订算与传统搜索算法相比，采用的策略不同，具体差别如下： ( 1 ) 进化算法不是直接在解空间上，而是利用解的某种编码表示； ( 2 ) 进化算法从一个群体期多个点而不是一个点开始搜索，这是它能以较大的概率找 到整体最优解的主要原因之一； f 3 1 进化算法使用解的适应性信息( 即目标函数) ，并且在增加收益和减少开销之间进行 权衡，而传统的搜索算法一般要使用导数等其它辅助信息； ( 4 ) 进化算法使用随机转移规则而不是确定性的转移规则。 目前，进化算法的发展还不够成熟，但它已经表现出其它算法无法比拟的优点。随着 大规模并行计算机和分布式计算机系统性能的不断提高以及对生物进化系统的进一步认 识，人类将有可能模拟更接近于自然的进化系统。 2 1 2 进化计算的分类 达尔文进化论思想在自动问题解决中的应用始于2 0 世纪5 0 年代，远在计算机飞速发 展阶段之前。2 0 世纪6 0 年代，进化论思想的三种不同实现分别在三个地方发展起来。 在美国，f o g e l 提出了进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 2 , 3 j ，而h o l l a n d 称他的方法 为遗传算法( g e n e t i ca l g o r i t h m ，g a ) 4 , 5 1 。在德国，r e c h e n b e r g 和s c h w e f e l 发明了进化策略 ( e v o l u t i o n a r ys t r a t e g y ，e s ) ”。在以后的大约1 5 年中，这些领域分别有了自己的发展；自 从2 0 世纪9 0 年代初，它们成为了一门技术的不同分支，这门技术就是进化计算。同样是 在2 0 世纪9 0 年代初，第四个分支遗传程序设计( g e n e t i cp r o g r a m m i n g ，g p ) i 现了 8 , 9 1 。 这整个领域称为进化计算，又称为进化算法。进化规划、遗传算法、进化策略和遗传程序 设计是它的四个分支。 进化算法为求解复杂系统优化问题提供了一种通用的框架，其基本出发点是基于对生 物进化过程的模拟。下面给出进化技术求解问题的基本框架： 第1 0 页 第2 章进化技术分析 进化代数计数器初始化：t t ，则以进化过 程中所得到的具有最大适应度的个体作为最优解输出，终止计算。 2 2 1 2 s g a 的数学描述 以g o l d b e r g 总结出的最基本的遗传算法基本遗传算法【2 3 1 ( s g a ，s i m p l eg e n e t i c 篇1 5 页 第2 章进化技术分析 a l g o r i t h m ) 为例来说明一般遗传算法的数学描述。s g a 可定义为一个8 元组【2 2 s g a = ( c ，e ，p o ，n ，o ，f ，甲，z 1 ) 式中c 个体编码方法。s g a 使用固定长度的二进制符号串来表示群体中的个体， 其等位基因由二值符号集( o ，1 ) 所组成，编码长度用三表示。 e 个体适应度评价函数。以x 表示一个决策变量，即群体中的一个个体，f ( x ) 表示 个体五的适应度。 只初始群体。 群体规模。s g a 群体规模恒定，一般用表示群体中个体的数目。 中选择算子。s g a 使用比例选择算子。 r 交叉算子。s g a 使用单点交叉算子，交叉概率为见。 甲变异算子。s g a 使用位均匀变异算子，变异概率为，第，代个体j 的变异 概率记为p 。( x ，f ) 。 r 遗传算法终止条件。s g a 使用r 作为终止进化代数。 2 2 2 编码方式 在遗传算法的运行过程中，它不对所求解问题的实际决策变量直接进行操作，而是对 表示可行解的个体编码施加选择、交叉、变异等遗传操作，通过这种遗传操作来达到优化 的目的，这是遗传算法的特点之一。 编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。d e j o n g 曾提出了两条操作性较强的实用编码原则口】。 编码原则一应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码 方式。 编码原则二应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案a 总的来说，这些编码可以分为三大类：二进制编码方式、浮点编码方式、符号编码方 式i 矧。 1 二进制编码方式 二进制编码方式是遗传算法中最常用的一种编码方式，它所使用的编码符号集是由二 进制符号o 和1 所组成的二值符号集 o ，1 ) ，它所构成的个体基因型是一个二进制编码符 号串。 二进制编码符号串的长度与问题所要求的符号精度有关。假设某一参数的取值范围是 u 。m ，u 。】，我们用长度为l 的二进制编码符号串来表示该参数，则它总共能够产生2 。 种不同的编码，若使参数编码时的对应关系如下： 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 一u 。 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 = 1 一u 。，。+ 6 第1 6 页 第2 章进化技术分析 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 = 2 l 1 一u 。 则二进制的编码精度为 6 ：u r e a x - u , i 2 。一1 二进制编码方式有以下一些优点： 编码、解码操作简单易行； 交叉、变异等遗传操作便于实现： 符合最小字符集编码原则； 便于利用模式定理对算法进行理论分析。 2 浮点数编码方式 对于一些多维、高精度要求的连续函数优化问题，使用二进制编码来表示个体时将会 有一些不利之处。 首先是二进制编码存在着连续函数离散化的映射误差。个体编码串的长度较短时，可 能达不到精度要求；而个体编码串的长度较长时，虽然能提高编码精度，但会使遗传算法 的搜索空间急剧扩大。 其次是二进制编码不便于反映所求问题的特定知识，这样也就不便于开发对问题专门 知识的遗传运算算子，人们在一些经典优化算法的研究中所总结出的一些宝贵经验也就无 法在这里加以利用，也不便于处理非平凡约束条件。 为改进二进制编码方法的这些缺点，人们提出了个体的浮点数编码方法。所谓浮点数 编码方法，是指个体的每个基因值用某一范围内的一个浮点数来表示，个体的编码长度等 于其决策变量的个数。 在浮点数编码方法中，必须保证基因值在给定的区间限制范围内，遗传算法中使用的 交叉、变异等遗传操作也必须保证其运算结果所产生的新个体的基因值也在这个区间限制 范围内。 浮点数编码方式有以下几个优点： 适合于在遗传算法中表示范围较大的数； 适合于精度较高的遗传算法； 便于较大空间的遗传搜索： 改善了遗传算法的计算复杂性，提高了运算效率； 便于遗传算法与经典优化方法的混合使用； 便于设计针对设计问题的专门知识的知识型遗传算子； 便于处理复杂的决策变量约束条件。 3 符号编码方式 符号编码方式是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含 义的符号集。这个符号集可以是一个字母表，如 a ，b ，c ，d ， ；也可以是一个数字符号表， 如 1 ，2 ，3 ，4 ，5 ，) ；还可以是一个代码表，如 a 1 ，a 2 ，a 3 ，a 4 ，a 5 ，) 等等。 符号编码的主要优点是： 符合有定义积木块编码原则； 便于在遗传算法中利用所解问题的专业知识； 便