（检测技术与自动化装置专业论文）基于多层次遗传编码技术机械产品整体方案的三维设计.pdf

沈阿1 理工大学硕士学位论文 摘要 在日趋激烈的市场竞争条件下，企业要想生存发展就必须提高其产品的竞争 力，迅速响应市场需求，进行最佳经营决策。因此，产品设计方案在整个产品开 发过程中占有十分重要的地位，其质量是决定产品最终质量、市场竞争力以及企 业获利最为关键的因素。在国家8 6 3 计划数字化设计与制造专题的资助下，本文 系统地研究了关于机械产品设计方案生成的方法与关键技术。主要内容包括： i 介绍遗传算法的基本理论，并结合应用对象自身的多层次结构特点，提出了多 层次遗传编码技术； 2 借助v i s u a lc + + 6 0 编程语言和s q l s e r v e r 2 0 0 0 数据库软件建立了基于多层 次遗传编码技术的简单多层次结构数字模型演示验证系统，通过验证系统的实 际运行，证实了多层次遗传编码技术应用在具有多层次结构机械产品整体方案 设计中的有效性及准确性； 3 将多层次遗传编码技术与具有多层次结构的机械产品整体方案设计相结合，完 成了面向多层次结构机械产品整体方案设计的遗传算法在数控机床整体方案 设计中的实际应用系统的开发，建立了数控机床整体方案设计系统； 4 在c a ) ( a 实体造型软件的基础上进行了二次开发，使智能设计系统拥有了三维 可视化的图形和文字输出，进一步的完善了数控机床整体方案设计系统的设 计。 关键词：遗传算法；多层次编码；c a x a 二次开发 沈刚理工大学硕七学位论文 a b s t r a c t w i t ht h ei n c r e a s i n g l yi n t e n s em a r k e tc o m p e t i t i o n ，i ti sn e c e s s a r yf o ra ne n t e r p r i s e s s u r v i v a la n dd e v e l o p m e n tt oi m p r o v et h ec o m p e t i t i v e n e s so fi t sp r o d u c t sa n dt or a p i d l y r e s p o n dt ot h er e q u i r e m e n to ft h em a r k e ta n dt om a k et h eb e s ta n dm o s tp r o f i t a b l e m a n a g e m e n ta n dd e c i s i o n s o ，s c h e m eg e n e r a t i o n i nd e s i g no fm e c h a n i c a lp r o d u c t s p l a y sa l li m p o r t a n tr o l ei nt h eo v e r a l lp r o d u c td e s i g n t h eq u a l i t yo fs c h e m e s i sac r u c i a l f a c t o rd e t e r m i n i n gt h ef i n a lq u a l i t yo fp r o d u c t sa n dt h ep r o f i to fp l a n t s w i t ht h es u p p o r t f r o mc h i n e s en a t i o n a l8 6 3h i g h t e c hr e s e a r c hi nt h es u b j e c to fd i g i t i z a t i o nd e s i g n s a n d m a k e s ，t h em e t h o d o l o g ya n dk e yt e c h n i q u e s o fs c h e m e g e n e r a t i o n a r e s y s t e m a t i c a l l ys t u d i e di n t h i sd i s s e r t a t i o n t h em a i nc o n t e n t so ft h ed i s s e r t a t i o na r ea s f o l l o w i n g ： 1 t h eg e n e t i ca l g o r i t h m st h e o r ya n dt h eh i e r a r c h i c a lm e c h a n i c a lp r o d u c ts t r u c t u r e c h a r a c t e r i s t i co ft h e a p p l i c a t i o no b j e c t a l ei n t r o d u c e d t h e n p r o p o s e dt h e h i e r a r c h i c a lg e n e t i cc o d et e c h n o l o g y 2 i nv i r t u eo ft h ev i s u a lc + + 6 0a n dt h es q l - s e r v e r 2 0 0 0d a t a b a s es o f t w a r et os e tu p t h es i m p l em u l t i 1 a y e r e ds t r u c t u r en u m e r i c a lm o d e ld e m o n s t r a t i o nc o n f i r m a t i o n s y s t e mb a s e do nh 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 s i tc o n f i r m e d t h eh i e r a r c h i c a lg e n e t i c c o d et e c h n o l o g yw h i c ha p p l i e di nt h eh i e r a r c h i c a ls t r u c t u r em e c h a n i c a lp r o d u c t h o l i s t i cc o n c e p t u a ld e s i g nt ob ev a l i d i t ya n dt h ea c c u r a c yt h r o u g hm o v i n gt h e c o n f i r m a t i o ns y s t e ma c t u a l l y 3 t h eh i e r a r c h i c a lg e n e t i cc o d et e c h n o l o g ya n dt h eh i e r a r c h i c a ls t m c t u r em e c h a n i c a l p r o d u c t h o l i s t i cc o n c e p t u a ld e s i g nh a sb e e nc o m b i n e dt o g e t h e r i th a sc o m p l e t e dt h e p r a c t i c a la p p l i c a t i o ns y s t e md e v e l o p m e n tw h i c hf a c e s t h eh i e r a r c h i c a ls t r u c t u r e m e c h a n i c a lp r o d u c th o l i s t i cc o n c e p t u a ld e s i g ng e n e t i ca l g o r i t h m si nt h en u m e r i c a l c o n t r o ll a t h eh o l i s t i cc o n c e p t u a ld e s i g n 4 o nt h ec a x a e n t i t ym o d e l i n gs o f t w a r ei th a sc a r r i e do nt h es e c o n dd e v e l o p m e n t i t e n a b l et h ed e s i g ns y s t e mt oh a v et h et h r e ed i m e n s i o n a lv i s i b i l i t yt ot h ef i g u r ea n d c h a r a c t e ro u t p u t a n dh a sc o n s u m m a t e dt h en u m e r i c a lc o n t r o ll a t h eh o l i s t i c c o n c e p t u a ld e s i g np r a c t i c a la p p l i c a t i o ns y s t e md e s i g nu l t e r i o r l y k e y w o r d s ：g e n e t i ca l g o r i t h m s ；h i e r a r c h i c a lg e n e t i cc o d e ；c a x as e c o n dd e v e l o p m e n t 沈阳理工大学 硕士学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由作者本 人独立完成的。有关观点、方法、数据和文献的引用已在文中指出， 并与参考文献相对应。除文中已注明引用的内容外，本论文不包含任 何其他个人或集体已经公开发表的作品成果。对本文的研究做出重要 贡献的个人和集体，均己在文中以明确方式标明。本人完全意识到本 声明的法律结果由本人承担。 作者( 签字) ：赵降喜 e t期 ：加颤矿 学位论文版权使用授权书 本学位论文作者完全了解沈阳理工大学有关保留、使用学位论文 的规定，即：沈阳理工大学有权保留并向国家有关部门或机构送交学 位论文的复印件和磁盘，允许论文被查阅和借阅。本人授权沈阳理工 大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或其它复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：走厍喜 日 期：2 嘭i 彩 指导教师签名：讯5 薹 e t 冁：7 、 目 第1 章绪论 第1 章绪论 现代设计方法是在现代计算机广泛应用的基础上发展起来的一项新技术。是 根据最优化原理和方法，综合各方面的因素，以人机配合的形式在计算机上进行 自动寻优，以选出在现有工程条件下的最佳设计方案的一种现代化方法。本文以 具有多层次结构特征机械产品整体方案设计作为主要的研究对象，通过对人工智 能算法遗传算法的研究，提出了基于知识进化的多层次遗传编码技术，并把 这一改进的遗传算法应用于机械产品整体方案创新设计中，开发了三维多层次结 构机械产品整体方案设计系统。 1 1 课题研究的背景及意义 现代设计技术是根据产品功能要求和市场竞争( 时间、质量、价格) 的需要， 应用现代技术科学知识，经过设计人员创造性思维、规划和决策，制定可以用于 制造的方案，并使方案付诸实施的技术n ，。计算机及其应用技术的发展，使机械产 品方案的设计方式、设计质量、设计效率等均发生了巨大变化，它为设计者提供 了更有效地分析、优化、仿真和绘图等手段，成倍的提高了产品的设计质量和设 计效率。 随着科学技术的飞速发展，产品的功能要求日益增多，复杂性也大大增加， 而产品的设计，尤其是方案设计手段的发展则相对滞后，成为产品设计过程中最 薄弱的环节，机械产品方案设计中的综合设计可以使产品功能实现形式产生根本 性变化，是产品创新过程中最富有创造性，最具有创新潜力的阶段，对产品功能 实现的质量和性能价格比有决定性的作用；但由于机械产品方案设计目前还没有 形成完整的、系统的、规范化的且易于计算机语言实现的理论体系和设计模式， 以至于计算机至今没能在产品的创新设计中很好地发挥作用。目前对于机械方案 的创新设计方法，大多停留在宏观论述上，缺乏创新原理和具体的可操作性，更 没有独立完整的理论体系；因此探讨机械产品方案的创新机理、模式和方法就成 为产品方案设计创新研究的核心内容之一。 本课题研究了产品整体方案设计问题的多层次结构特征，以及多层次结构知 1 沈阳理工大学硕士学位论文 识之间的相互关系，探索一种基于多层次遗传编码表示的产品整体方案设计，建。 立一个多层次结构产品整体方案设计全过程的智能设计工具系统。通过本课题的 研究开发能够提高企业的产品设计能力，从而缩短产品开发周期，降低成本，提 高质量，生产出满足用户需要的产品，使企业在市场竞争中立于不败之地。 i 2 现代设计技术的发展趋势 在当前激烈的市场竞争中，除了确保产品的功能、质量外，还要有创新意识。 在以知识经济为特征的2 l 世纪背景下，全国各行各业都面临新的选择，新的机遇 与挑战，都在构思着新的设想。瞻望未来，现代设计技术的发展与应用，将对推 动国民经济的发展起到重要的作用。 现代设计方法实质上是科学方法论在设计中的应用。其发展趋势大致可分为 以下几个方面： ( 1 ) 数字化产品在其生命周期内的数字化建模是现代设计方法的关键技术 之一，它包括全局产品的信息定义，要用计算机来支持产品生命周期的全过程， 就必须用计算机能理解的方式给出产品生命周期全过程的数字化定义；产品的 数字化工具，即广义的计算机辅助工具，它能将产品信息自动数字化；产品数 据管理，即用计算机对产品开发与生产全过程中的大量数字化信息进行全面的管 理与控制。 ( 2 ) 并行化它是在计算机软硬件支持的信息共享基础上，采用团队工作模 式，可在异地进行设计开发的一种现代设计方法与手段。它有助于实施强强联合， 优势互补，极大地提高企业的产品设计开发能力。 ( 3 ) 智能化是指现代设计方法及技术中越来越明显的智能化倾向：它能 使设计开发入员不必了解设计开发低层的全部细节，而由计算机智能地设计并最 终制造出合乎要求的产品；设计系统具有自动获取新知识，并丰富自己的能力。 ( 4 ) 集成化是指现代设计系统不再是单一的c a d 、c a m 或c a p p 系统，而 是支持产品生命周期全过程的现代设计集成系统。 随着网络技术的蓬勃发展，从用户对产品的功能需求一设计一加工一装配一 成品这一并行工程的实现已成为可能。但是，达到这些目标的重要前提条件之一， 就是实现产品方案设计效果的三维可视化。为此，三维图形软件、智能化设计软 一2 塑! 童堑堡 一 件愈来愈多地应用于产品的方案设计中。国外在这方面的研究己初见成效，我国 设计学者也已意识到c a d 技术与国际交流合作的重要性，及其应当采取的措旖。 1 3 现代机械产品方案设计方法概述 把现代设计方法应用到机械设计中来，称之为现代机械设计方法。其具有以 下主要特点：系统性。现代设计方法是逻辑的、系统的设计方法，强调用系统 工程方法处理技术问题。智能性。重视综合集成，通过计算机以高效率综合集 成高新科技成果，寻求最优方案和参数。创新性。强调激励创造冲动，突出创 新意识，从而开发创新产品。优化性。通过优化理论与方法，运用计算机技术 进行整体优化。先进性。采用先进的设计手段，大大提高设计的质量和效率。 动态性。在静态分析的基础上，考虑载荷谱、负载高等随机变量，进行动态多 变量最优化设计。c a d 化。广泛的应用计算机，使设计、计算、绘图、制造、 改进一体化。日新月异且功能强大的软件使设计工作面貌不断更新，能够包容的 影响设计的因素日益增多，大大提高了设计的精度、稳定性和效率，修改设计极 为方便n 。 目前国内外设计学者进行机械产品方案设计时所采用的具体方式各不相同， 每种方法均有与其相应的主导思想。根据各种设计方法所具有的特征，可以将现 代机械产品方案的设计方法概括为如下几种分类w ： ( - - ) 功能分解法 该方法把产品方案设计过程分为功能分解、功能表示、功能综合三个阶段。 从产品的总功能分析开始，进行由上而下的功能分解，寻求最小功能的可行解， 由最小功能求解得出最小的可行机构解，然后再由下而上进行机构组合，做出粗 略运动简图，经过综合评价，选择最佳方案。 ( - - ) 基于实例的设计方法 该方法利用过去的实例和经验，根据设计的要求和产品的特征，建立产品的 实例模型，并采用面向对象技术描述实例，建立产品实例库，基于设计要求和模 型实例进行推理，从已有的实例模型库中选择相似的实例模型，进而通过设计和 制造知识，对产品相似实例进行评价和修改，获得产品设计的优化解。 ( 三) 设计目录法 3 。 沈阳理工大学硕士学位论文 该方法首先收集功能作用原理，经整理、抽象、分类后，建立具有一定结构 的设计目录。通过对问题的分类和识别，由功能到作用原理的匹配、解的选择和 评价等得到适当的方案解。这种设计方法注重了功能和结构类型之间的有机联系， 有助于方案设计阶段的创新。 ( 四) 键合图法 该方法的研究始于8 0 年代后期，进入9 0 年代有了一定的发展。目前在这方 面的研究可分为两类：以r e d f i e l d 为代表的简单系统的研究；以r o s e n b e r g 和s h a r p 为代表的一般系统研究。前者针对某些简单系统所希望的性能指标，应用键合图 方法确定在物理上能实现的解及解的变形，即多个设计方案。后一种方法根据设 计要求首先建立设计系统的功能模型，然后由该模型产生原理解及解的变形，再 由每个解建立其性能的键合图及数学模型并进行评价，或由功能模型建立键合图，。 由键合图产生多个解的变形，即多个设计方案，最后经评价选定解或设计方案”。 ( 五) 图形建模法 用层次清楚的图形描述出产品的功能结构及其相关的抽象信息，实现了系统 结构、功能关系的图形化建模，以及功能层之间的链接。将设计划分成辅助方法 和信息交换两个方面，利用信息分析方法可以采用图形符号、具有内容丰富的语 义模型结构、可以描述集成条件、可以划分约束类型、可以实现关系间的任意结 合等特点，将设计方法与信息技术进行集成，实现了设计过程中不同抽象层间信 息关系的图形化建模。 ( 六) 价值工程法 在价值工程方法中，认为可靠地实现必要功能是价值工程在产品设计和产品 改进中的技术目标，不能实现必要的功能产品方案，不能成立。在功能分析中完 成功能定义、功能整理和和功能评价。功能定义的要求是用准确、抽象和便于定 量的词汇给每一个功能下一个定义，按照功能的上下位关系及并列关系，将产品 及其零部件的全部功能系统化，建立产品功能的逻辑关系体系，构成树状结构的 功能系统图。 ( 七) 矩阵设计法 在方案设计过程中采用“要求一功能”逻辑树( “与或”树) 描述要求、功能 之问的相互关系，得到满足要求的功能设计解集，形成不同的设计方案。再根据 蔓! 童堡堡 “要求一功能”逻辑树建立“要求一功能”关联矩阵，以描述满足要求所需功能 之间的复杂关系，表示出要求与功能间一一对应的关系，。 k o m e m l 将矩阵作为机械系统方案设计的基础，把机械系统的设计空间分解为 功能子空间，每个子空间只表示方案设计的一个模块，在抽象阶段的高层，每个 设计模块用运动转换矩阵和一个可进行操作的约束矢量表示；在抽象阶段的低层， 每个设计模块被表示为参数矩阵和一个运动方程。 ( 八) 基于虚拟现实的设计 虚拟现实目前被广泛应用于各个领域，目前国内外许多学者都对虚拟现实技 术进行了研究，也取得了丰硕的成果。在产品早期的方案设计领域，虚拟现实技 术同样也受到了众多学者的关注，他们将虚拟现实技术引入了造型设计、结构设 计等过程，并开发出了一些基于虚拟现实的概念设计系统，如3 - d r a w ，j d c a d ， c o v i r d s ( 概念虚拟设计系统) 等。 ( 九) 并行设计法 并行设计是现代设计的发展趋势，它是一种方法学，而不是一种管理技术。 并行设计的目标是在设计过程的早期阶段同时包容设计者和用户，实现用户和产 品所有商业功能之间的交互，即在概念设计领域研究产品的功能、原理、布局、 形状等之间的并行设计。 ( 十) 智能化设计方法 智能化设计主要是利用三维图形软件和虚拟现实技术进行设计，而智能c a d ( i n t e l l i g e n tc o m p u t e r - a i d e dd e s i g n ，i c a d ) 是一种新型的高层次计算机辅助设计 方法与技术。它将人工智能的理论和技术与c a d 相结合，使计算机具有支持人类 专家的设计思维、推理决策以及模拟人的思维方法与智能行为的能力，从而把设 计自动化推向更高的层次”1 。 1 4 课题研究的内容和实现目标 本文通过对机械产品的结构研究，针对其特点再结合知识进化的理论，在基 本遗传算法的基础上提出了多层次结构遗传编码技术的遗传算法。利用该算法把 机械产品作为设计对象，借助于计算机程序设计语言v i s u a lc + + 6 0 、数据库管理 系统软件s q l s e r v e r 2 0 0 0 和绘图工具软件c a x a ，开发了机械产品智能方案设计 一5 一 沈阳理工大学硕士学位论文 系统。 本课题拟争取能够构建适合的典型机械类产品方案设计系统。该系统是一个 人机交互式的机械方案设计平台，设计过程近似于人类的设计过程。易于设计者 掌握和应用。 通过对机械产品方案设计理论和方法的研究学习，目的在于寻求能够适应市 场需求、提高设计效率、解决企业中传统设计方法不足的一种有效途径，探讨在r 企业内适合其机械产品的早期设计阶段能够建立一个计算机辅助方案设计系统， 给设计者提供一种产品早期方案的创新设计方法和设计思维方式。 一6 - 第2 章遗传算法原理 2 1 引言 第2 章遗传算法原理 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 的概念最早是由b a g l e yj d 在1 9 6 7 年提出的；而开始遗传算法理论和方法的系统性研究是在1 9 7 5 年，由m i c h i g a n 大学的j h h o l l a n d 所实行的。该算法是建立在自然选择和群体遗传学机理基础上 的随机、迭代和进化，它是具有广泛适用性的搜索方法。 2 2 遗传算法的来源 遗传算法是基于d a r w i n 的进化论和m e n d e l 的遗传学说发展起来的。d a r w i n 进化论最重要的是适者生存原理，它认为每一物种在发展中越来越适应环境，物 种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。 m e n d e l 遗传学说最重要的是基因遗传原理，它认为遗传以密码方式存在细胞中， 并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质，因 此，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更 适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下 来”“。 遗传算法是一个奇妙的优化过程，它借助于生物进化的选择淘汰，突然变异， 基因遗传等规律产生适应环境变化的优良物种。它作为一种实用、高效、鲁棒性 强的优化技术，发展极为迅速，在各种不同领域中得到广泛应用，引起了许多学 者的关注。在最近兴起的人工生命、遗传编程、进化策略、进化计算等领域中， 研究人员将遗传算法与计算机科学相结合，试图模拟自然界的自适应、自组织和 再生能力，设计出具有“生命的”人工系统。 2 2 1 遗传算法的特点 遗传算法与一般的搜索和优化算法有很多不同之处，它具有如下特点“ - 7 婆塑望三奎堂堡圭堂鱼堡窒 ( 1 ) 智能性。遗传算法的智能性包括自组织、自适应和自学习等。应用遗传算法计 算求解问题时，在确定了编码方案、适应度函数及遗传算子以后，算法将利用计 算过程中获得的信息自行组织搜索。由于基于自然的选择策略为：适者生存、不 适应者淘汰，故而适应度函数值大的个体具有较高生存概率。通常适应度函数值 大的个体具有与环境更适应的基因结构，再通过杂交和基因突变等遗传操作就可 能产生与环境更适应的后代。遗传算法的这种自组织、自适应特征同时也赋予了 它具有能根据环境的变化自动发现环境的特征和规律的能力。自然选择消除了算 法设计过程中的一个最大障碍：即需要事先描述问题的全部特点，并说明针对问 题的不同特点算法应采取的措旎，于是利用遗传算法可以解决那些结构尚无人能 理解的复杂问题。 ( 2 ) 并行性。遗传算法按并行方式搜索一个种群数目的点，而不是单点。遗传算法 的并行性表现在两个方面：一方面，遗传算法是内在并行的，即遗传算法本身非 常适合大规模并行。最简单的并行方式是让若干台计算机各自进行独立种群的演 化计算，运行过程中可以进行或不进行通信，等到运算结束时进行比较，选取最 佳个体。这种并行方式对并行系统结构没有什么限制和要求，可以说，遗传算法 适合在目前所有的并行式或分布式系统上进行并行处理，而且对效率没有太大的 影响。另一方面，遗传算法具有内含并行性。由于遗传算法采用种群的方式组织 搜索，因而可同时搜索解空间的多个区域，并相互交流信息。使用这种搜索方式， 虽然每次只执行与种群规模n 成比例的计算，但实质上已进行了大约o ( n 3 ) 次有 效搜索，这就使得遗传算法能以较少的计算获得较大的收益。 ( 3 ) 遗传算法使用了概率搜索技术，不像传统方法是确定性的搜索，而是一种自 适应概率搜索技术，从而提高了搜索的适应性。传统的优化算法往往使用的是确 定性的搜索方法，一个搜索点到另一个搜索点的转移有确定的转移方法和转移关 系，这种确定性往往也有可能使得搜索永远达不到最优点，因而也限制了算法的 应用范围。而遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等运 算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。虽然这种 概率特性也会使群体中产生一些适应度不高的个体，但随着进化过程的进行，新 的群体中总会更多地产生出许多优良的个体，实践和理论都己证明了在一定条件 下遗传算法总是以概率1 收敛于问题的最优解。当然，交叉概率和变异概率等参 8 j 翌! 童望堡塞垄堕望 数也会影响算法的搜索效果和搜索效率，所以如何选择遗传算法的参数在其应用 中是一个比较重要的问题。而另一个方面，与其它一些算法相比，遗传算法的鲁 棒性也会使得参数对其搜索效果的影响会尽可能的低。 ( 4 ) 鲁棒性。由于遗传算法利用个体的适应度来推动群体的演化，而不管求解问 题本身的结构特征，所以在求解不同的问题时只需要设计相应的适应度评价函数， 而无需修改算法的其它部分，因而具有很好的鲁棒性。 ( 5 ) 非定向性。自然选择和生物繁殖这种非定向机制是遗传算法的关键。它没有 确定的迭代方式，也不依靠梯度下降法似的爬山策略，而是用调整群体内部结构 的方法来增强其对环境的适应度，使问题得到解决。 ( 6 ) 整体优化。传统的优化方法，一般采用的是梯度下降的爬山策略，从而使得 多峰函数的情形容易陷入局部最优。而遗传算法能同时在解空间的多个区域内进 行搜索，并且能以较大的概率跳出局部最优，以找出整体最优。 2 2 2 遗传算法的主要应用领域 遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的 具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。遗传算法 的主要应用领域有以下几个方面： ( 1 ) 函数优化。函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评 价的常用方法。很多人构造了各种各样的复杂形式的测试函数，人们用这些几何 特性各异的函数来评价遗传算法的性能。对于一些非线性、多模型、多目标的函 数优化问题，用其它优化方法较难求解，而遗传算法却可以方便地得到较好的结 果。 ( 2 ) 组合优化。随着问题规模的扩大，组合优化问题的搜索空间急剧扩大，有时在 目前的计算机上用枚举法很难甚至不可能得到其精确最优解。对于这类复杂问题， 人们已意识到应把精力放在寻求其满意解上，而遗传算法正是寻求这种满意解的 最佳工具之一。实践证明，遗传算法对于组合优化中的n p 完全问题非常有效。 ( 3 ) 生产调度问题。生产调度问题在许多情况下所建立起来的数学模型难以精确求 解，即使经过一些简化之后可以求解，也会因简化太多而使得求解结果与实际相 差甚远。遗传算法是解决复杂调度问题的有效工具，在单件生产车间调度、流水 鲨堕里三查兰堡主堂垡堡皇 线生产车间调度、生产规划、任务分配等方面遗传算法都得到有效的应用。 一t ( 4 ) 自动控制。在自动控制领域中有许多与优化相关的问题，遗传算法在解决这些 问题时显示了良好的效果。如利用遗传算法进行航空控制系统的优化、基于遗传 算法的模糊控制器优化设计、利用遗传算法进行人工神经网络的结构优化设计和 权值学习等。 ( 5 ) 机器人智能控制。机器入是一类复杂的难以精确建模的人工系统，遗传算法在 机器人智能控制如移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运 动学求解、细胞机器人的结构优化和行动协调等方面得到了广泛的研究与应用。 ( 6 ) 图像处理和模式识别。遗传算法可用于图象处理中的优化计算方面，如图像恢 复、图像边缘特征提取、几何形状识别等。 ( 7 ) 人工生命。自组织能力和自适应能力是人工生命的两大主要特征，基于遗传算 法的进化模型是研究人工生命现象的重要理论基础。可以预见，遗传算法在人工 生命及复杂自适应系统的模拟与设计、复杂系统突现性理论研究中，将得到更深 入的发展。 ( 8 ) 遗传程序设计。遗传程序设计的主要思想是使用某种编码方法，对某种结构进 行遗传操作以自动生成计算机程序。虽然遗传程序设计的理论尚未成熟，但它已 有一些成功的应用。 ( 9 ) 机器学习。学习能力是高级自适应系统所应具备的能力之一，基于遗传算法的 机器学习，特别是分类器系统，在许多领域得到了应用。例如，基于遗传算法的 机器学习可用于调整人工神经网络的连接权，也可用于神经网络结构的优化设计。 2 3 遗传算法的基本原理 2 3 1 遗传算法的基本思想 遗传算法是一种迭代算法，它从某一随机产生的或是特定的初始解集出发， 按照一定的操作规则，如选择、复制、交叉、变异等，不断地迭代计算以得到新 一代解集，并根据个体的适应度，按照适者生存和优胜劣汰的原则，引导搜索过 程向“最适应环境”的个体( 最优解) 逼近，逐代演化出越来越好的近似解，最终 收敛到问题的最优解或满意解“”。 1 0 第2 章遗传算法原理 2 3 2 遗传算法的基本概念 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在 这个算法中要用到各种进化和遗传学的概念“。这些概念如下： ( 1 ) 串：它是个体的形式，在算法中为二进制串并且对应于遗传学中的染色体。 ( 2 ) 种群：带有特性的个体的集合称为种群，串是群体中的元素。 ( 3 ) 种群大小：在群体中个体的数量称为群体的大小。 ( 4 ) 基因：基因是串中的元素，基因用于表示个体的特征。例如有一个串s = 1 0 1 1 ， 则其中的1 ，0 ，1 ，1 这四个元素分别称为基因。它们的值称为等位基因。 ( 5 ) 适应度：表示某一个体对于环境的适应程度。对生存环境适应程度比较高的物 种将获得更多的繁衍机会，而对生存环境适应程度比较低的物种将获得的繁衍机 会就会相对较少，甚至逐渐灭绝。适应度准则体现了适者生存，不适应者淘汰的 自然法则。 ( 6 ) 遗传因子：d n a 或r n a 长链结构中占有一定位置的基本遗传单位，也称基因。 ( 7 ) 遗传子型：遗传因子组合的模型叫遗传子型。它是性状染色体的内部表现，又 称基因型。一个细胞核中所有染色体所携带的遗传信息的全体称为个基因组。 ( 8 ) 基因座：遗传基因在染色体中所占据的的位置。 ( 9 ) 等位基因：同一基因座可能有的全部基因称为等位基因。 0 0 ) 进化：生物以种群的形式，在其延续生存的过程中，逐渐适应其生存环境， 使其品质不断得到改良，这种生命现象称为进化。 ( 1 1 ) 选择：指决定以一定的概率从种群中选择若干个体的操作。它是一种基于适 应度的优胜劣汰的过程。 ( 1 2 ) 复制：细胞在分裂时，遗传因子d n a 通过复制而转移到新产品的细胞中，新 的细胞就继承了旧的细胞的基因。 ( 1 3 ) 交叉：有性生殖生物在繁衍下一代时两个同源染色体之间通过交叉而重组， 亦即在两个染色体的某一相同位置处d n a 被切断，其前后两串分别交叉组合而形 成两个新的染色体。又称基因重组或“杂交”。 ( 1 4 ) 变异：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使d n a 发生某种变种，产生出新的染色体，它们表现出新的性状。 沈阳理工大学硕士学位论文 ( 1 5 ) 编码：d n a 中遗传信息在一个长链上按一定的模式排列，即进行了遗传编码。 它也可以视做从表现型到基因型的映射。 ( 1 6 ) 解码：从基因型到表现型的映射。 2 4 基本遗传算法 h o l l a n d 的遗传算法被称为基本遗传算法( s i m p l eg e n e t i ca l g o r i t h m s g a ) 。 s g a 采用二进制编码，使用选择、交叉、变异三种遗传算子和基于适应度比例的 选择策略。 2 4 1s g a 的基本步骤 s g a 的基本步骤可用下面的算法进行描述m m 唑 第一步：随机产生n 个个体构成初始群体。 第二步：根据适应度函数计算当前群体中各个体的适应度。 第三步：判断算法终止条件是否满足，若满足则转第八步。 第四步：根据各个体的适应度函数执行选择操作。 第五步：按交叉概率p 。执行交叉操作。 第六步：按变异概率p 。执行变异操作。 第七步：若已得到由n 个新个体构成的新一代群体，则转第二步，否则转第 四步。 第八步：输出搜索结果，终止。 2 4 2 编码表示 在使用遗传算法对一个问题进行求解之前，必须先对问题的解空间进行编码， 以实现解空间到遗传算法搜索空间的映射，也即表现型到基因型的映射。这种映 射可以是点一点、点一多或多一多等m 。 h o l l a n d 提出的遗传算法是采用二进制编码来表现个体的遗传基因型的，它使 用的编码符号集由二进制符号0 和l 组成的，因此实际的遗传基因型是一个二进 制符号串，其优点在于编码、解码操作简单，交叉、变异等遗传操作便于实现， 第2 章遗传算法原理 而且便于利用模式定理进行理论分析等；其缺点在于，不便于反映所求问题的特 定知识，对于一些连续函数的优化问题等，也由于遗传算法的随机特性而使得其 局部搜索能力较差，对于一些多维、高精度要求的连续函数优化，二进制编码存 在着连续函数离散化时的映射误差，个体编码串较短时，可能达不到精度要求； 而个体编码串的长度较长时，虽然能提高精度，但却会使算法的搜索空间急剧扩 大。显然，如果个体编码串特别长时，会造成遗传算法的性能降低。后来许多学 者对遗传算法的编码方法进行了多种改进，例如，为提高遗传算法局部搜索能力， 提出了格雷码( g r e yc o d e ) 编码；为改善遗传算法的计算复杂性、提高运算效率， 提出了浮点数编码、符号编码方法等。为便于利用求解问题的专门知识，便于相 关近似算法之间的混合使用，提出了符号编码法；此外还有多参数级联编码和交 叉编码方法，近年来，随着生物计算理论研究的兴起，有人提出d n a 编码法，并 在模糊控制器优化的应用中取得很好的效果。 2 4 3 适应度函数设计 从数学角度看，遗传算法实质上是一种概率性搜索算法，但它也具有一定的智 能特征。遗传算法是在适应函数的指导下进行搜索，而不是穷举式的全面搜索。 适应度函数评估是选择操作的依据，各个个体适应度的大小决定了它们是继续繁 衍还是消亡，相当于是自然界中各生物对环境的适应能力的大小。通常，适应度 大的个体具有更适应环境的基因结构，再通过基因重组和基因突变等遗传操作， 就可能产生更适应环境的后代。改变种群内部结构的操作皆通过适应度加以控制。 适应度函数的选取直接影响到遗传算法的收敛性及收敛速度，对于提高遗传算法 的智能程度显得尤为重要m i 。 适应度函数求取的是极大值，而且是非负值。可以直接利用问题的目标函数来 定义适应度函数，也可以用目标函数变换的形式来定义。其设计主要考虑以下条 件： 单值、连续、非负、最大化；合理、一致性；计算量小：通用性强。 常用适应度函数有： ( 1 ) 对于求解极大值问题时，f i t ( x ) = s ( x ) ，其中f i t ( x ) 为适应度函数，f ( x ) 为 目标函数：对于求解极小值问题，目标函数采取如下方式转换为适应度函数： 1 3 鎏堕望三茎堂堡主堂垡堡奎 ( x ) = - f ( x ) ( 2 ) 对于求解极大值问题，目标函数采取如下方式转抉为适应度函数： 腓) = p 箩八力老如 其中；。为f ( x ) 的最小值估计。对于求解极小值问题，目标函数采取如下方式 转换为适应度函数： 州= 了。l蓼八凳“ 其中为f ( x ) 的最大值估计。 ( 3 ) 对于求解极大值问题。目标函数采取如下方式转换为适应度函数： ( 小南晓峥外) o 对于求解极小值问题，目标函数采取如下方式转换为适应度函数： ( x ) 2 硼1 例巾) 。 2 4 4 遗传操作 遗传操作是模拟生物基因遗传的操作。在遗传算法中，通过编码组成初始群体 后，遗传操作的任务就是对群体的个体按照它们对环境适应的程度( 适应度评估) 施加一定的操作，从而实现优胜劣汰的进化过程n ”。从优化搜索的角度而言，遗传 操作可使问题的解，一代又一代地优化，并逼近最优解。遗传算法的遗传操作包 括以下三个基本遗传算子：1 ) 选择；2 ) 交叉；3 ) 变异。 选择算子 从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。选择算子有时又称为 再生算子。选择的目的是把优化的个体( 或解) 直接遗传到下一代或通过配对交叉 产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础 上的，目前常用的选择算子有以下几种。 适应度比例方法 适应度比例方法也称轮盘赌选择法，各个个体被选中的概率与其适应度大小成 1 4 蔓! 雯堡生蔓堡堕里 正比，适应度越高的被选择的概率越大。 最佳个体保存方法 该方法的思想是把群体中适应度最高的个体不进行配对交叉而直接复制到下 一代中。此种选择操作又称复制。d ej o n g 对此方法作了如下定义： 设到时刻t ( 第t 代) 时，群体中a ( t ) 为最佳个体。又设a ( 什1 ) 为新一代群体，若 a ( t + 1 ) 中不存在a + ( t ) ，则把a ( t ) 作为a ( t + 1 ) 中的第n + 1 个个体( 其中，n 为群体大小) 。 采用此选择方法的优点是，进化过程中某一代的最优解可不被交叉和变异操 作所破坏。但是，这也隐含了一种危机，即局部最优个体的遗传基因会急速增加 而使进化有可能限于局部解。也就是说，该方法的全局搜索能力差，它更适合单 峰性质的搜索空间搜索，而不适合多峰性质的空间搜索。所以此方法般都与其 他选择方法结合使用。 排序选择方法 所谓排序选择方法是指在计算每个个体的适应度后，根据适应度大小顺序对群 体中个体排序，然后把事先设计好的概率表按序分配给个体，作为各自的选择概 率。这种方法的不足之处在于选择概率和序号的关系需事先确定。此外，它和适 应度比例方法一样都是一种基于概率的选择，所以仍有统计误差。 排挤方法 在自然界中，当一个种群中的个体大量繁殖生存时，为争夺有限的生存资源， 群体中个体之间的竞争压力必然加剧，因此，个体的寿命和出生率也因此而降低。 基于这种机制，d ej o n g 提出了排挤选择方法。采用该方法时，新生成的子代将替 代或排挤相似的旧的父代个体。该方法可提高群体的多样性。 交叉算子 在自然界生物进化过程中起核心作用的是生物遗传基因的重组( 加上变异) 。 同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父 代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜 索能力得以飞跃提高。 下面是几种基本的交叉算子。 ( 1 ) 一点交叉 一点交叉又称为简单交叉。具体操作是：在个体串中随机设定一个交叉点， 沈阳理工大学硕士学位论文 实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个体。 下面给出了一点交叉的例子。 个体a0 0 1 1 1 1 1 0 _ 0 0 1 1 1 0 0 1 新个体a i 配对个体 个体b1 0 1 0 1 0 0 1 寸l o l 0 1 1 1 0 新个体b 其中，交叉点设置在第4 和第5 个基因座之间。交叉时，该交叉点后的两个个 体的码串互相交换。这样，个体a 的第一到第四个基因与个体b 第五到第七个基因 组成一个新的个体a 。同样，可得到新个体b 。交叉点是随机设定的，当染色体 长为1 1 时，可能有n 1 个交叉点设置，所以，一点交叉可能实现n 1 个不同的交叉结 果。 ( 2 ) 二点交叉 二点交叉的操作与一点交叉类似，只是设置2 个交叉点( 依然是随机设定) 。一 个二点交叉的例子表示如下： 个体a0 0 1 1 1 1 1 1 0 o o l _ i o o l l o 新个体a 配对个体 个体b _ l o l l o o l o l - - 4 1 0 l l l l l 0 1 新个体b 由此可见，两个交叉点分别设定在第二基因座和第三基因座以及第五基因座 和第六基因座之间。a ，b 两个体在这两个交叉点之间的码串相互交换，分别生成 新个体a ，和b 。对于二点交叉而言，若染色体长为n ，则可能有( n - 2 ) ( n 3 ) 种交叉点 的设置。 ( 3 ) 多点交叉 多点交叉是前述两种交叉的推广，有时又被称为广义交叉。若用参数c p 来表 示交叉点数，则当c p ：1 时，广义交叉就等效于一点交叉。当c p 为偶数时，根据交 叉互换规律，染色体可以当作基因环来处理。当c p 为奇数时，它可以等效为偶数 点交叉。此时，可假定在码串的头部( 即基因座0 ) 有一个交叉点。一般来讲，多点 交叉较少采用，因为