（机械设计及理论专业论文）演化设计方法及其应用研究.pdf

大连理工大学硕士论文 摘要 摘要 本论文主要研究演化设计方法及其在机构方案设计上的应用。 多年以来，实现产品设计的智能化、自动化，提高产品设计的创新程度，是人 们所追求的目标。然而，传统的设计方法存在着过于依赖经验、设计周期长以及缺 乏创新等缺点，因此很难满足现代产品的设计要求。2 0 世纪9 0 年代中期，演化设 计方法的提出，为实现上述目标开辟了一条有效的途径。 演化设计方法是从仿生学的基础上发展起来的，它将问题的解表示成演化个体 的形式，通过模拟自然界优胜劣汰的进化过程，来寻求问题的最佳设计方案。演化 设计方法以演化算法或演化思想为理论基础，具有较强的自组织、自适应能力，同 时具有并行性和全局性等特点。目前，演化设计方法已经应用于结构优化设计、方 案设计、人工生命以及智能机器人设计等领域，并取得了令人瞩目的进展。 近年来兴起的关于演化设计方法的研究主要集中在国外，尚没有形成系统的理 论和方法，有待进一步发展。本文在查阅和分析国内外文献资料的基础上，主要研 究了演化设计的基本原理及实现方法，并将其应用于机构方案的设计中。 本文主要研究工作如下： ( 1 ) 综述和分析了近年来的演化设计方法。包括综述其研究进展，归纳和分析 了演化设计方法的内涵、类型及其基本实现方法。讨论了用于行为控制的神经网络 的演化模型的设计。 。 ( 2 ) 在分析了l i p s o n 等的演化设计方法的基础上，研究其具体实现方法，最后 给出机构演化设计实例。 ( 3 ) 以压电驱动式微夹钳的设计为例，在对微夹钳传动机构进行分析，推导出 简化传动分析计算公式，并应用有限元分析和实物测量进行验证的基础上，应用演 化算法对其进行结构参数优化设计。 将演化设计方法应用于机械产品的设计中，将提高设计过程中的自动化程度， 拓宽设计者的思路，提高产品的创新性，因此具有重要的研究价值。 关键词：演化设计；方案设计：神经网络：微夹钳 中图分类号：t p 3 9 1 ；t p l 8 ；t h l l 2 大连理工大学硕士论文 a b s t r a c t a b s t r a c t t h et h e s i s m a i n l y s t u d i e s e v o l u t i o n a r yd e s i g n m e t h o da n d1 t s a p p l i c a t i o nt ot h ec o n c e p t u a ld e s i g n f o rm e c h a n i s m s f o rs om a n yy e a r s ，w ea i mt o d e s i g n t h e p r o d u c t si n t e l l i g e n t l y a n d a u t o m a t i c a l l y ，a n di m p r o v et h ei n n o v a t i o nl e v e l s h o w e v e r ，b e c a u s em o s to f t r a d i t i o n a ld e s i g nm e t h o d sd e p e n do ne x p e r i e n c e so fd e s i g n e r s ，w h i c ht a k e t o ol o n gd e s i g n i n gc y c l ea n dl a c kc r e a t i v i t y ，t h e yc a n n o tm e e tt h e s ed e m a n d s i n a n yc a s e f o r t u n a t e l y ，t h ee v o l u t i o n a r ya l g o r i t h m sd e v e l o p e di n 19 9 0 s h a v eb e e n p r o v e da n e f f e c t i v ea p p r o a c ht os o l v et h i sp r o b l e m e v o l u t i o n a r yd e s i g nm e t h o di so r i g i n a t e df r o mb i o n i c s ，w h i c hr e p r e s e n t s s o l u t i o n sa si n d i v i d u a l s ，a n ds e e k st h eo p t i m a ls o l u t i o nb ys i m u l a t i n gt h e e v o l v i n gp r o c e s so fs u r v i v a lo f t h ef i t t e s ti nn a t u r e t h ee v o l u t i o nm e t h o di s b a s e do nt h e t h e o r y o fe v o l u t i o na l g o r i t h ma n de v o l u t i o nt h i n k i n gw i t h s e l f - o r g a n i z a t i o n ，s e l f - a d a p t a t i o n a n dc h a r a c t e r i s t i c so f p a r a l l e l i s m a n d g l o b a l c u r r e n t l y , e v o l u t i o n a r yd e s i g nm e t h o d h a sb e e na p p l i e dt ot h ef i e l d s o fs t r u c t u r a lo p t i m i z a t i o nd e s i g n ，c o n c e p t u a ld e s i g n ，a r t i f i c i a ld e s i g na n d i n t e l l i g e n tr o b o td e s i g n ，a n dm a n y r e m a r k a b l e p r o g r e s s e s a r ea c h i e v e d t h er e s e a r c ha b o u tt h ee v o l u t i o n d e s i g n m e t h o d si nr e c e n ty e a r si s m o s t l yi na b r o a d h o w e v e r ，t h es y s t e m a t i ct h e o r ya n dm e t h o da r es t i l l n o t d e r i v e d ，w h i c hn e e d su st os t u d yf u r t h e r o nt h eb a s i s o fc o l l e c t i n ga n d a n a l y z i n g ag r e a tq u a n t i t yo fr e f e r e n c e sa th o m ea n da b r o a d ，t h i st h e s i s s t u d i e dt h eb a s i cp r i n c i p l eo fe v o l u t i o nd e s i g na n di t si m p l e m e n tm e t h o d ，a n d i t sa p p l i c a t i o nt ot h ec o n c e p t u a ld e s i g nf o rm e c h a n i s m s t h em a i nw o r k si nt h et h e s i sa r ea sf o l l o w s ： ( 1 ) t h ee v o l u t i o nd e s i g nm e t h o d sa r eo v e r v i e w e da n da n a l y z e d ，w h i c h i n c l u d et h er e s e a r c hp r o g r e s s ，i n t e n s i o n ，t y p e sa n dr e a l i z a t i o nm e a n s t h e n e u r a ln e t w o r ke v o l u t i o nm o d e la p p l i e dt ob e h a v i o rc o n t r o li s a l s ob e d i s c u s s e d ( 2 ) b a s e d o nt h e l i p s o n s e v o l u t i o n d e s i g nm e t h o d ，t h es p e c i f i c r e a l i z a t i o nm e a n sa r e s t u d i e d ，a tl a s t ，t h ee x a m p l e a b o u tm e c h a n i s m e v o l u t i o nd e s i g ni sg i v e n ( 3 ) t a k i n gt h ed e s i g no fp i e z o e l e c t r i cm i c r o - g r i p p e rf o r a ne x a m p l e ， b a s e do na n a l y z i n gi t st r a n s m i s s i o nm e c h a n i s m ，d e d u c i n gt h es i m p l i f i e d l i 大连理王丈学磺圭论文 a b s t r a c t f o r m u l a sf o rt r a n s m i s s i o na n a l y s i sa n dv a l i d a t i n gb yf i n i t ee l e m e n ta n a l y s i s a n de x p e r i m e n t a lm e a s u r e m e n t ，t h es t r u c t u r a lp a r a m e t e r sa r eo p t i m i z e db y e v o l u t i o na l g o r i t h m a d o p t i n g e v o l u t i o nm e t h o dt od e s i g nm e c h a n i c a lp r o d u c t s w i l lb e b e n e f i c i a lt oi m p r o v ea u t o m a t i c i t y i n n o v a t i o na n db r o a d e nd e s i g n e r sm i n d 。 t h e r e f o r e d o i n gr e s e a r c h f o rt h i sm e t h o di so f g r e a tv a l u e k e y w o r d s ：e v o l u t i o nd e s i g n ；c o n c e p t u a ld e s i g n ；n e u r a ln e t w o r k s ； m i c r o - g r i p p e r c l a s sn u m b e r ：t p 3 9 1 ；t p l8 ；t h l1 2 l l i 大连理工夫举醺士论文第一肇缝论 1 1 弓l 言 第一章绪论 工业工程中，特别是机械设计领域中，存在许多复杂机械系统的优化设计问 题，很难用传统的设计方法来解决。7 0 年代，演化算法的提出，为人们求解这类 难题提供了一条有效的途径。目前，演化算法在工业设计中的应用融经越来越广 泛，鬯与其它智能计算技术的结合。形成了一种有效的设计方法，我们称箕为演 化设计方法，它幽现于2 0 世纪9 0 年代中期。 演化设计方法是阻演化算法为基础，模蓣自然界生物静演化过程，求解设计 问题的一种现代伉亿方法。它将生物演纯的原壤与疆饶仡技术和计算梳技术结合 起来，宦l 造了一手 全新静优化设计方法。它其裔舀缀织槛、裔迳应健等餐g 擎路征， 又同时还其鸯良好酌并行性、全局优纯性耱i 墓健挂等特点。困魏，演纯设计方法 其有非常广泛应粥蓠荣晕爨莛要的磷究俊筐，戈其适于处理复杂的工程设诗阅题。 演纯设诗方法豹内涵摆当广泛。从广义上寒蓍，演化设计方法包括鹱有基予 演化思想，按照巍然法贝4 进霉亍计箕的设诗方法。它既可以单独应用予结构优化设 计或方案设讨等阅题的求解，也可以与其它智能计算技术( 如：神经网络、虚拟 现实等) 楣绫合，进行带有智能行为控制的人工生命演化设计。 演化设计方法是建立在生物进化学和计算机科学基础上，它同相关学科技术 的关嚣如图1 - 1 所示，它是以演化算法为理论勘出，由生物进化与计算机科学技 图1 一l 演化设计方法与相关学科的关系 术的结合而成的种多学科交叉的综合技术。 l 大连理工大学硕士论文 第一章绪论 计算机软硬件性能的不断提高，促进了演化设计方法的迅速发展。目前的应 用主要集中在结构优化设计，方案设计，创新设计以及人工生命与智能机器人等 设计领域，并且已经取得了令人瞩目的进展。 1 2 演化设计的研究进展 9 0 年代中期以来，随着计算机运算速度的不断提高，演化设计方法的优越 性逐渐显露出来。下面主要从方案演化设计和人工生命的演化设计两个方面介绍 演化设计方法的研究进展。 1 2 1 机械方案演化设计 演化设计作为一种优化方法，具有较好的自适应性，全局优化性的诸多优点， 已成为解决工程设计问题的一种有效的方法。方案设计问题是工程设计中的关键 问题，演化设计在方案设计中的应用与研究已经取得了一定的进展。 1 9 9 5 年，日本学者y a m a k a w a ，h i r o s h i 1 1 等人提出了“机械设计过程中的遗 传与演化”这一新概念，并应用遗传算法来模拟这一过程。他们将设计过程构思 成为一个分布式多层结构模型，每一层均通过遗传算法进行优化，使其适应度函 数在约束下达到最大值，每一级的适应度函数及约束条件将根据相邻级别的优化 结果来调整，即所谓的演化。 1 9 9 8 年，郝博等提出了一种基于遗传算法的机械方案设计计算机辅助设计系 统模型。以二级圆柱齿轮减速器为例，将方案设计过程看作一个状态空间的问题 求解，采用面向对象的知识表示方法建立多层次网络知识库系统，然后用遗传算 法来控制搜索过程，得到齿轮减速器一组优化的设计方案圆。尽管上述所提到的 研究工作还仅限于理论上的研究或者是简单的应用，演化算法只是作为辅助性的 优化工具，但是，演化设计的优点已经明显的体现出来。 1 9 9 9 年y o s h i m u r a ，m a s a t a k a 3 1 等人模仿生物的进化过程，仅从必要的初始 条件出发，不带有任何人为的预见，对一组候选方案反复进行演化与选择，直到 得出了一个满意的解为止。 2 0 0 1 年，钱志勤、滕弘飞等将演化算法应用于布局方案演化设计，针对带性 能约束布局问题提出了人机交互的演化协同设计方法，解决了航天器舱布局方案 设计问题h ”。 2 大连理工夫学硬士论文第一章绪论 1 2 2 农人工生命的演化设计 近年辩乏，随着人工犍能技术的必越，人们开始试图借助演化的思想，模拟生 物靛演化避程，完全黯魂纯她设计典静特定彳亍为的智s l 机器( 又称人工生命体， a r t i f i c i a ll i f e f o r m ) 。 人工生命( a r t i f i c i a ll i f e ) 的概念是由美国的c l a n t o n 教授于1 9 8 7 年首先 提出来的【6 】，近年来受到了越来越多的关注。智能机器人的设计是其中一个重鼷 夔分支，浚凭算法与入王毒枣经羁络等赣戆技本绩合嚣蕊戆滨纯设计方法在这一镁 域中显示了更大的潜力。 19 9 8 年，墨西哥学者j j u a r e z - g u e r r e m 等人 7 1 将演化策略用于行走机器 ( w a l k i n gm a c h i n e ) 的结梭设计，尝试设计“真实”的行走机器人。他们设计了 两是的行走辊器蘸鍪，行走部分透过魏橇疆释梳鞠实现。蓄宠建立孛蔻擒的交力学 模型，然后利用演化策略寻求一个步调同步的行走机构解并对模泌中的参数谶行 优化。 1 9 9 6 年，英国静w e i - p ol e e ，j o h nh a l l a m 等a t s j 德滨纯i 蘩戈l 耱遗簧算法混 合使用来实现机器入撩锘8 系统的智演化设计，使机器人根据不间的虚拟环境完 成各种不同的动作，并以实现绕过障碍物的动作为例进行了说明。他们将整个遗 传系统划分为大脑( 控臻4 器) 和身体蹰部分，其中大脑部分由个树状结构的逻 辑控摹程序梅藏，翔采交互遣控毒l 穰瘦弱鸯体部分；蠢身薅凝分鬻由一甍安羧枣 组成，决定了机器人燕体的关键结构参数。系统的遗传规划部分用来处理控制程 序树状逻辑的演化；丽遗传算法部分则用于确定结构参数。 1 9 9 8 年，d a i n , r a 对枫器久静行为控毒l 部分涟行了演化设计。应用g p 馒 机器人邋过进讫来达要s 沿墙行走( w a l l f o l l o w i n g ) 鹣行为。由予机器入经历了隧 个环境而得至q 进化的，所以它的鲁棒性较好，程不同环境中能够很好地执行 w a l l f o l l o w i n gi 约f 9 1 。 1 9 9 4 年，k a r ls i m s 骜霹三维环襞下豹虚整凝爨煞形态零嚣行为豹演讫方法遴 行了研究f 。他提出了竟争的演化机制，即在同一个三维虚拟环境下，个体的适 应度值取决于当前群体中其它个体的行为能力，个体之间通过相互竞争来实现优 矬劣汰，获胜者将褥到较意的适应憾，并褥以继续生存和傈塑。s i m s 提出袋蠲 有囱萄( d i r e c t e dg r a p h ) 作鸯个体基弱壅来表示掇器静形态。自 孛经元构成鹣 虚拟的大脑( b r a i n ) 控制着机器的行为，它接收传感器( s e n s o r ) 的输入并输 出控制信号给执行器( e f f e c t o r ) ，输出值以力或力矩的形式控制机器实现动作， 大连理工大学硕士论文 第一章绪论 如图卜2 所示。 1 9 9 9 年r i c h a r d a w a t s o n , s e v a ng f i c i c i 和j o r d a nb p o u a c k 1 1 l 提出了e m b o d i e d e v o l u t i o n 实体演化方法，其主要特点是将演化算法应用于真实机器人的群体中， 代替以前采用的计算机虚拟环境下的动态仿真。通过这种演化设计，使机器人个 体之间能够在现实中相互交流，达到共同进化。 c o n t r o ls y s t e m p h y s i c a ls i m u l a t i o n l ：i g u r e ：c y c l eo l _ e f f e c t sb e t w e e nb m i l l b o d ya n dw o r d ， 图1 2 控制循环的实现 在1 9 9 9 年欧洲人工生命年会( e c a l 9 9 ) 上，波兰的m a c i e jk o m o s i n s l d 和 s 2 y m o n ih a l c w 嫡在他们的文章中提出了一种称为人工生命的自然仿真模型蚴。 f i g ag l l 坤l an 黜恤k 嗍t u r a 图1 - 3f r a m s t i c k 型机器人结构示意图 4 丈连理王太学磺论文 第1 肇缝论 歇设计数毒辽爨生物翅上嬲1 - 3 顼示，具蠢括架结携，据为规器与乡 绷；蠛交互戆 一种手段，杆上带有传隳器和执行器，e 妇大脑( 神经元网络) 控制，它们的作用 类似于生物体的神经和肌肉组织。将一级这样的机器，放潼在三维的虚拟环境内， 其演佬避程取决予对环境豹髓力，在这 十仿真环境下，溪试梳器静橇动瞧和 方肉识剐豹行为熊力，以此性能好坏来 瀚个终螅适应程度。 2 0 0 0 年美国马萨诸塞布兰代斯大学h o dl i m o n 和j o r d a nbp o l l a c k 的一项研 究结果引起科学界的关注3 l 。他们研制出了无需人工干预就熊自行进化和复制的 梳器入。实验中每个瓣器a 都由系潮最鏊本的帮敝船：稀、执行器耪人工棒 经元) 组合页贼。采用计算规模拟机器人麴规动曼力，以l 避藕溅分演化算法产生的 方案是否合邋，经过若干代的演化，最后得到性自龇的机器人结构，并采用快 速自动成型技术制造出机器入实体，如图1 4 所示，是通过逾仲演化设计方法得 至l 个波功静设舌 实物。与m a c i e jk o m o s i n s k i 等久的醑究相纭，l i p s o n 葙p o l l a c k 韵演化设计方法也设计了耪空阈魏真模型来模拟真实环境，然后在此环境下评 测设计的机动性能，作为适成度值。不间之处在于，l i p 9 0 n 和p o l l a c k 将设计与 加工统起来，实现了机器聃设i r 、仿墨骚喃造的自动亿，藏有突破陡的意义。 图1 4l i p s o n & p o l l a c k 的演化设计实物 由上述对演化设计方法研究进展的综述可断瞀出，演仡设计方法其脊醣下特 点： ( 1 ) 演化设计方法主要包搔结构演化设计、方案演化设计和人工生命的演 化设计三个方面。 5 夫连理王夫擘醺士论文 第l 章绪论 ( 2 ) 随着演化技术研究的不断深入，设计的对象已经由单一的局部优化问 题发展到方案设计问题以及自动化设计。 ( 3 ) 警女静疆演纯竣诗已经残为麓究戆熬煮。宅逶 雾包括巍髂( 橇藏结搦) 和大脑( 智能控制部分) 两部分，对于这两部分的演化主要有两种恩路：一是将 两部分分别进行演化构造，依据各自表示方式的特点采用不同演化算法；另一种 就是将鼹部分统一编码，舞e 黥人工 枣缀网络控毒融器的嚣为，将继构与控卷4 两部 分丽时翔入至l 演亿操 乍中，稷据动态镑真牲髓来对设计静适应凌瀵行i 牙毪夸。觚实 际应用来看，研究人员越来越倾向于将两部分作为一个整体来进行演化设计，因 为这也符合生物演化的实际情况。 ( 碡) 对演玩设诗鹣绫巢适应程凌豹浮绥，鬟爱逶过锈卖采蜜凌。在整拿演 化设计滋程中，性能评价显然是一个歪关重要的问题。然而，真囊环境下的机器 人的动态行为仿真非常复杂，因此，现阶段，研究人员通常采用计算机来模拟自 然环境。另外还存在一巾思路，就是将每代演化的结果通过快遴成型技术直接 构造：墨蜜体，然后奁实验中测试薪令傣静性l 。瞧怒这耱方法存程设计蠲翔长， 成本高等缺点。 ( 5 ) 目前来看，用于演化设计的模型都比较简单，构成机器的元件通常都 是最基零的元素，热：耪、节点露弹经元等。这撵，镬黜方索荔予构造，劳 减少了仿真的复杂程溲，同对氇_ 保迸了设计结采的多样性，但怒躐离实用尚有鞭 离。 ( 6 ) 控制部分多采用神经网络找术，其拓扑结构参数以及连接权值也可以参 与演 撼舞。这撵褥餐设诗结采美蠢较爵赘叁适应筑力，提高了设计豹整暮纯零 平。 1 3 本论文的主要羔俸及组织络梅 1 3 1 本论文的主要工作 ( 1 ) 蓄走讨论了演化设计方法瓣蠹涵、类型淤及礴究内容， 设计酌研究进展概况； ( 2 ) 介绍演化算法的基本原理及特点及其实现的方法： ( 3 ) 研究用于行为控制的神经湖络的演化模型的设计方法， 翔季搴经鞠络演毯模鍪麓浚计： 6 势综述了演饯 霪点讨论了递 大连理工犬学硕士论文 第1 章绪论 ( 4 ) 重点分析了l i p s o n 等的演纯设计方法，研究其其体实现方法。并蒋其 痊建于撰掏数方寰设诗孛，绘出是 奉爨恻。 ( 5 ) 应用演化算法谶行微夹钳的传动机构优化设计。在总结并分析了国内 外现有的结梅形式及其设计方法的基础上，推导出微夹锈传动眈及转角的计算公 式，建立提应隐优化数学模型，最后疲尾演纯算法对其逛行求鳃。 1 3 ，2 论文躲组织结构 论文豹组织结梅始图1 5 掰示。 爨1 - 5 论文组绞结构图 大连琏王大学醺士论文 第二章演纯等法斡设计 2 1 演化算法概述 第二章演化算法的设计 演化设计多数是基于演纯算法求进行的，因_ i 眈在研究演亿设计之前，先奔缮 演化算法，以及如何设计演化算法，即所谓的演化算法的设计。 蠡然要中懿生物愁薮生存瑟境矮骞饶建懿叠适应接，各耱兹耱在一秘竞争戆 环境中生存，优胜劣汰，使得物种不断改进。嫩物这种自然进化的能力是惊人的。 近3 0 年来，人们从不同的角度出发对生物系统及其行为特征进行了模拟，产生 了鳖蘑褒代辩技发蓑蠢鏊大影稿鹣耨兴学科。铡羹，辩久类模耧器维方式静模 拟产生了模糊集合理论；对动物脑神经的模拟产生了人工神经网络理论；对自然 界砖，生物的免疫机理的模撅产生了兔疫算法：箍对皂然舆中生物演化机制的模拟 就产生了演纯计算理论。 演化算法魁模拟“物竞天择”与“自然遗传”的生物演化过稷所产生的随机 纯诗算模型。它其旁鑫鳃缀悭、囊学习蛙、歉遥应蛙、舞饶纯性等蟹特铥，又 同时具有内在的并行性、原理的简单性、全局优化性和应用的广泛性。人们公认 1 9 7 5 年h o l l a n d 的有关遗传算法的专著【1 4 j 的发表，标志着演化算法主要分支之一 遗传算法鹣诞生。嚣蘸来看，浚轻：算法怒少数忍穆戆够毒效懿凌复杂蠡罨戆载 复杂工程问题( 如n f 问题) 方法之一【i ”。 2 。1 i 滨德冀法茨努类 广义上的演化算法可分为“仿，主”和“拟物”两类：仿生类演化算法包括遗 蛰黪法( g e n e t i ca l g o r i t h m s ，蓑稔g a ) 、滚纯疆翅( e v o l u t i o n a r yp r o g r a m m i n g ， 简称e p ) 、演化策略( e v o l u t i o ns t r a t e g y ，简称e s ) 和遗传编程( g e n e t i c p r o g r a m m i n g ，简称g p ) ；拟人、拟物类演化算法是指切模拟人藏物理系统的 演化过翟产垒的往纯援索算法，英中最杰密的代表是綦予b o l t z m a n n 演讫策港懿 模拟退火算法。还有些学者将演化髀法的框架扩展到包括模拟生物进化、物理系 统演化移社会系统的演变等所有算法模型。这些算法各自有不同盼融重点，务鲁 大连理工走学硬士论文第二章演纯算法瓣设计 有不闻的生物进纯背景，各裔强诞了垒物滋亿过程串鹣不嗣特淫，毽它翻都产 生穆番棒憔较强弱计雾规冀法，逶攒瑟鞍广。返年来这几璐不阚熬方法积极地 进行了撞互交浚，搜怨它 | 、 之闻约差别正逐濒续小，所以总体地含义上统称它们 为演化算法( e v o l u t i o n a r y a l g o r i t h m s ，简称e a ) 1 6 1 。 总之，广义上的演化算法是攒用计算机系统模拟大自然的演化过程来解决现 实世界中的问题的一切算法，也就是所谓的按自然法则计算的思想。 2 1 2 演化算法豹基本攥絮 演化算法为求解复杂系统优化问题提供了种通用的框架，其基本磷发点是 基于对生物演化过程的模拟。下面给出演化算法的基本框架。 e a 算法： 演纯代数诗数器物始仡：卜； 隧捉产生初始群体鼓疼； 评价群体以0 的适或凄： 个体重组操作：p ( 0 一r e c o m b i n a t i o n p ( 明； 个体变异操作：p ( 0 - - - m u t a t i o n p ( f ) 】； 评价群体p ”( 0 的适应度； 个体选择、复青操作：p ( t + 1 ) - - r e p r o d u c t i o n p ( 砖u p ( 翻； 终止条件判断。若不满怒终正条件，簧l ：f 挣l ，转至第步，继续避行 演化操作过程：若满足终止条件，列：输出当前最往个体，算法结寒。 2 1 3 演化计算的基本特点 滨能髯法秘足令主要分支 速蕊算法、淡地嫂划、演化策路魏遗黄绽理) 虽 然羞黢予囊然界中生物进饯的不同背景，是出不月的研究人员独立地开发出来 的，但它嚣 之蚓有很多相似之处，可统一于上述基本框架之内。上述几种演化算 法共同具有的基本特点如下： ( 1 ) 算法的操作对象都是有多个个体所组成地一个集合，即群体； ( 2 ) 每个个体都有一个对系统环境的适应度，这个适应波是箨法对每个个 体优劣程度的种度量； ( 3 ) 算法都要进行遥择或复希搡佟，黻僵畿够将当蓠群体中懿青较衰适应 璇酌个藩淹多逮保蟹到下一代群体中； 9 大连理工大学硕士论文 第二章演化算法的设计 ( 4 ) 算法都通过个体重组、变异等进化操作，以及对个体所加入的一些微 小变动，来增进群体的多样性； ( 5 ) 算法所模拟的生物演化过程都是一个反复迭代的过程。在群体的这个 迭代演化过程中，个体的适应度和群体中所有个体的平均适应度都不断地得到改 进，最终可得到一个或几个具有较高适应度的个体，它们就对应于问题的最优解 或近似最优解； ( 6 ) 算法所模拟的演化过程均受随机因素的影响，所以它们不易陷入局部 最优点，并都能以较大的概率找到全局最优点： ( 7 ) 算法都具有一种天然的并行结构，均适合于在并行机或局域网环境中 进行大规模复杂问题的求解。 2 2 演化算法的设计 2 2 1 基本设计步骤 在设计演化算法时，通常按以下的基本步骤进行： ( 1 ) 体的表示方法：演化算法求解问题既可以编码转换的形式表示个体 ( 例如：g a ) ，也可以直接采用解空间的向量来表示个体( 例如：e s ，e p ) 。 ( 2 ) 定适应度评价函数：适应度值是对解的质量的一种度量，它通常依赖 于解的行为与环境( 即种群) 的关系。一般以目标函数的形式来表示。解的适应 值是演化过程中进行选择的唯一依据。 ( 3 ) 择策略的确定：优胜劣汰的选择机制使得适应值大的解有较高的存活 概率，这是演化算法与一般搜索算法的主要区别之一。不同的选择策略对算法的 性能也有较大的影响。 ( 4 ) 制参数的选取：控制参数主要包括种群的规模、算法执行的最大代数、 执行不同遗传操作的概率以及其它一些辅助性的控制参数。 ( 5 ) 传算子的设计：演化算法中的遗传算子，主要包括复制( 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 ) 以及其它高级操作。 ( 6 ) 定算法的终止准则：由于演化算法没有利用目标函数的梯度信息，所 以在演化过程中，无法确定个体在解空间的位置。从而无法用传统的方法来判定 算法的收敛与否以终止算法。常用的办法是预先规定一个最大的演化代数或算法 o 犬连理工大学硕士论文第二章滴化算法的设计 在连续多少代以后解的邋应值没有什么明短的改进时，即终止。 下瑟我嚣l 将主要络会遗传舞法谡秘演讫冀法瓣设计。 2 + 2 2 遗传弊法( g e n e t i ca l g o r i t h m s ) 裔1 9 5 7 年超，f f a s 0 ”l 和h o l l a n d t l 4 1 等簇闻稳鑫了模按遴纯过程髂遗传算法。 人们公认h o l l a n d 的著 乍标志着遗传算法煦诞生。现在模拟进化过程的优化算法 总称为演化算法，包括：遗传算法、遗传程序设计、演化策略等。其中遗传算法 跫磷究最深入、盛糟最广泛的一类。基本静遗传箨法螽六个灏分缀籍：编璐祝 制、适应度函数、遗传辫子、遗传参数、约束条件的处理、收敛准则。 2 2 2 1编码辊涮 编码机制是遗传算法的基础。g a 不是对研究对象直接进行讨论，而是通过 菜l 孛编褥辊制，交特定符号( 字母) 按定j 粳f 笋撵成酶警来表示研变对象。正稻疆 究生物遗传是从染色体鬻手，染色体则是由基因排成的串一样。遗传算法的编码 方式有= 进制编码、十进制编码和符号编码等。按照十进制的类型，十进制编码 又可戮分为鑫然数壤码、整数编强、实数编码 浮点数编鹦) 、鬟数编玛衣攒数 编码等五种编码策略。我们通常用二进制编码、十进制编码。下面以优化问题为 例，加以讨论。 垅亿潮题鲍艘形式灸： ， 求：m i n f ( x )，x = ( x l ，x 2 ，- - ，x ，x 。) 盘，五唾 ，i ；l ，2 ，一，n( 2 1 ) 其中：挤；和魂为优化翔题中变量x ；豹土下羰；+ 押必自爨x 的维数。羞楚骞 约束优化问题，则使用罚函数方法将其转换为仅有上、下限约束的参数优化设计 问题。 二进誊编码跫应用最早、最广泛教一秘编玛方式，它根据公式 p ，2 - = q + 气f _ ( 6 ，一q )f 。1 0 ，1 ) ( 2 2 ) 将变爨x 。映射成长度为p 的二进制位串，然后按顺序将每个x 。所对应的位 串连接莛来，帮榆成耱群酪鏊本单傻阶体) 。个体酶长度为抒p ，p 豹大，l 、投蕹 大连理工大学硕士论文帮二章演化算法的设计 实际簧求确定，它决定了搜索空间的大小。 十遂割编码策醢楚撂使瘸逡卷l 基壤彩裁豹染稳锩来袭示鞠题熬令熬豹 编码形式。即染色体的表现形式是一个十进制数串。所谓十进制旗因，就是基因 的表现型( 基因黧) 为一个十迸制数。 窭然数编码就是聚耀鱼然数( 1 ，2 ，国对染色髂基因避行缝璐，它喾翅予经 典的t s p 问题( 货郎担问题) ；整数编码的基因为十进制整数，蹙数编码可用于 求解熬数规划问颓：实效编确，又称为浮点数编码或数值编码，它的蓄困墅为十 避制实数。在实数编羁镶略中，每个个体甥与蝎题豹鼹囱量楣囿长度的实数向量 进行编码，个体中每个分量最开始疆在规定的区域内选取，并且遗传算子的设计 要满避这个约束：复数编码就是基黼墅为十逶翎复数的编码策略；指数编稻褥变 量分戏数字段与一位指数位进行编码，其中数字段由变量辑有的有效数字组成， 它特别适合于大范围搜索。 二迸蒂l 编码与十述蒂l 编褥有掘下不丽： 1 ) 二进傣l 编粥容易产生积操作，并且几乎适合予任何阅题。 2 ) 十进制编码相比，二谶制编码具有更高的精度和效率。 3 ) + 遴蒋编码可戳大大缩短伞体静编鹚长浚。节绔沣箨祝内存静鑫鬻量，胰 褥提撼了计算的速度，特另u 对于多维问题，其效果将廷为显著。它为克服多维优 化中的“维数灾”问鼷提供了一条新途径。 4 ) 卡遴镪编璐哥敬增大释释静靛模，扩展接索空溺，麸蠢麓滚较少瓣迭代次 数、遐大的概率找到全局最优解。 5 ) 十进制个体中的各基因相对独立，便于对个体进行杂交和变异的操作。 6 ) 十逶涮逶掰瞧好，蟹螽工程 建诗天昃鲍懋维习。溪，矮子程_ ；擎静编写，瑟虽 便于与传统数值算法混合编程。 由于十进制编码的诸多优点，现在人们趋向子用十进制编码解决实际的工程 润题。 2 2 2 2适应度函数 在遗传算法中，适应度函数悬用来区分群体中个体( 问题的解) 的好坏，一 般适应度函数值越大的个体越好，反之，适应度函数值越小的个体越麓。奁g a 设诗中，缝霉矮到嚣耱逶密度涵数，即缳始逶应度鼹数和标准逶应发函数。 原始适应度函数是指采用问蹶的目标函数作为邋应度函数，它经常用于极大 1 2 大连理工丈学硕士论文第二牵演纯算法静设计 值求解问题。然而在许多问题中，求解目标更多熊表示为某个函数的极小值求解 这辩需甏把极小僮简逶转纯为标准的形式，g 仡为极大纯情形显适应凄值菲受。 它蠢潋下三种转健形式： 1 ) ，( 菇) 2 ) ，( 搿) c 礓。一“) 0 “( 搿) + q 。 o u ( x ) 0 冀它 s m 秘 书凯鬟则 ( 2 3 ) ( 2 。4 ) ( 2 5 ) 其中：f ( x ) 是适应度函数；u ( x ) 是问题的目标函数；c m 。可以是一个合适的 输入值，也可是迄今为止迸化过程中“( j ) 的最大值或当前群体中甜( 搿) 的最大 值。( _ 。可以是合适的输入值，或是当前一代或前蔗代中的u ( x ) 的最小德。 在应用 e 铡选择辩，遗传算法翠期群体串窭现熬超缀令体( 该个体适应度甄 数篷运运超过群体平均逶应痍函数毽) 会由于在群体中产生过多黪复利，霹导致 早熟收敛；褥且在遗传算法的压魏群体平均适应度爵数镁与最优实验馕太过接遮 时会导致停滞现象。 处理遗传算法早熟和停滞问题的个措施就是对适应度函数进行比例变换。 目前常用的适应度函数的比例变换方法主要有三种：线槛比例变换( 3 固、幂比例 交换( 3 7 ) 和指数t e 例变换( 3 8 ) 。 f ( x ) = a f ( x ) 4 - p f ( x ) = 【，( z ) 】8 f ( x ) = e x p - b f ( x ) 】 ( 2 ，彤 ( 2 7 ) ( 2 8 ) 其中：厂( ) 蹩进行t e 铡变换后的适应度函数；f ( x ) 是朱经变换的适应痰涵数； 搿，声怒系数。 上述三耱毙铡交换中，搬数 s 铡鼹霹以让 # 鬻好靛串保持多款复露4 规会，鹅 砖又隈割了其复毒l 数尽以免其很快控毒l 整个群体，同时提高了棚近串间豹竞争 1 3 大连理工大学硕士论文 第二章演化算法的设计 性。系数卢决定了选择的强制性，其值越小，选择强制就越趋向于那些具有最高 适应值的串，因此本文采用指数比例变换。 2 2 2 3遗传算子 遗传算子最重要有三种：选择算子、交叉算子、变异算子。 ( 1 ) 选择算子( s e l e c t i o no p e r a t o r ) 选择算子也称复制算子。它的作用在于根据个体的优劣程度决定它在下一代 是被淘汰还是被复制。一般地说，通过选择，将使适应度函数值大即优良的个体 有较大的生存机会，而适应度函数值小即低劣的个体继续存在的机会也较小。有 很多方式可以实现有效的选择。目前常用的选择算子有： a 轮盘选择算子 ，” 即适应度函数值为，的个体以，z 的概率继续存在，其中分母为父代 ，仁1 中所有个体适应度之和。 b 排序选择算子 即根据适应度函数值的大小顺序对群体中的个体排序，然后把事先计算好的 概率表按序分配给个体，作为各自的选择概率。 c 排挤选择算子 即新生成的子代将替代或排挤相似的旧父代个体，以提高群体的多样性。 d 最佳个体保存方法 即群体中适应度最高的个体不经遗传算子的操作，直接复制到下一代中。这 种方法很重要，保持最佳个体，可保证遗传算法迅速收敛到局部最优点。但该方 法的全局搜索能力差，它更适合单峰性质的搜索空间，而不适合多峰性质的空间 搜索。所以可将此方法与其他的选择方法相结合。 ( 2 ) 交叉算子( c r o s s o v e ro p e r a t o r ) 交叉算子在遗传算法中起关键作用，是产生新个体的主要方法。交叉算子有 1 4 犬连理工大学硕士论文第二章消化算法的设计 多种形式，燕要有单点交叉、双点交叉、多点交叉、一致交叉和算术交叉算予等。 a 单点交叉篓子 最简单的是单点交叉算予，它魁在个体串中随机设定一个交叉点，然后交换 该点前或后的两个个体的部分结构，从而产生两个新个体。 b 双点交叉冀子 双点交叉与单点交叉很相似，它在个体串中设定两个交叉点，然后对这两点 中间的部分结构避行交换。 c 多点交叉冀子 多点交叉是前述两种交叉的推广，它可在个体串中随机地设定多个交叉点， 然后进行交换。 d 一致交叉冀子 一致交叉是通过屏蔽字来决定新个体的基因继承两个父本个体中的哪个个 体酶纂因。如图2 - 1 所示；当屏蔽字中的往为0 酲重，薪个体a 继承瓣个体蠢中对 应鲍簇困，当屏蔽字毯必l 时，毅个钵a7 继承 珏令体嚣中对应的基因。反之， 可生成新个体b 。 旧个体ax x y y y y l 疆令体by y y y x x 屏蔽字0 1010l 叛令薅a x y y y y x 新个体b y x y y x y 圈2 1一致交叉舅子 ” e 算术交叉舞子 算术交叉算子常用于浮点编码的遗传算法中。对于两个父本个体a 和b ，算 术交叉产生的两个子代a 和b 如( 3 9 ) 和( 3 1 0 ) 所示： a = c a + ( 1 一砖8( 2 9 ) b = c b + ( 1 c ) a( 2 1 0 ) 旗中；c 是0 ，1 1 ，j 二的随机数。当c 楚一个常数时，称为均匀交叉算子：当c 是一个与遮铸代数毒关豹交爨嚣，拣羹 # 缘镑交叉豁子。 ( 3 ) 变异算予( m u t a t i o n o p e r a t o r ) 变异算予是将个体串中的某些熬因位上的基因值加以改变，即用其他的 l s 大连理工大学硕士论文 篇二章演化算法的殴计 基瓣篷替换，麸褥形残个毅瓣令诲。交舅舞子其蠢叛下涎个佟麓：一是使速技 算法具有局部搜索的能力：二是帮助遗传算法维持群体的多样性，以防此出现束 成熟收敛现象。常蕉的炎异算予有：藻本交辩算予、逆转箨子、致交笄算予、 非致变髯算予等。 a 基本变异算子 基本变异算子是指对个体审以变异概率随机指定的募位或某几位基因廉 上的基因值作变异运算。 b 遂转算子 逆转辣子是指在个体串中随机挑选两个逆转点，然后将两个逆转点间的基因 德既逆转概率遂淘捧枣，英舀鹣主要楚为了熊饺邃转算法鬻有稳予生产较好豹模 式，如( 3 11 ) 所示。 a ：y y iy y x x x y ix x y “a ：y yly x x x y y x x y ( 2 1 1 ) c 致变异算子 一致变异算予可使搜索患楚整个搜索空闼内鱼凌移动，从两增加群体的多样 性，