（计算机软件与理论专业论文）遗传算法在计算机辅助沙发设计中的研究与应用.pdf

山东师范大学硕十学位论文 遗传算法在计算机辅助沙发设计中的研究与应用 摘要 随着科学技术进入一个多学科相互交叉、相互渗透、相互影响的时代，源于 模拟某一自然现象或过程并且具有自组织、自学习、自适应等特征的神经网络、 细胞自动机和进化计算等研究方向近年来得到了前所未有的蓬勃发展 遗传算法是基于进化理论的原理发展起来的一种广为应用的高效率的随机 搜索优化方法，在各种计算智能的研究中，这种算法得到了广泛的关注，它是在 达尔文进化论、门德尔一摩根遗传学说的启示下，通过模拟自然界中的“物竞天 择，优胜劣汰”的优生法则及物种遗传规律发展起来的一类算法 遗传算法在一些设计优化问题中已显示出巨大潜力和深远影响，但距离实现 一个能与人的行为相匹配的系统还很远。尤其是在一些创新设计应用，如建筑、 音乐、艺术、设计，由于评价标准主要依赖于人的主观想法，很难对个体的适应 度函数进行描述系统如何能在执行最优化的过程中，为个体提供进化机会的同 时，也最大限度的避免产生退化的可能；而且可以实现一种智能化的评价方法等 问题，成为计算机辅助概念设计的研究热点。 一一人工神经网络和遗传算法是两种以生物学为基础的现代优化算法，因其优越 性而被广泛应用于诸多领域。 在客观剖析相关领域存在的实际问题的基础上，本文具体所做工作如下： 1 对遗传算法进行分析。介绍了遗传算法的基本原理、基本遗传算法的改 进及设计方法并对遗传算法的收敛性进行了分析，给出了一个统一的收敛标准 然后，介绍了基于树结构的遗传算法。最后，分析了遗传算法在设计问题中的应 用价值。 2 对径向基神经网络的原理、结构、方法，分类进行了研究。指出r b f 弧i 以其结构简单、非线性逼近能力强、收敛速度快、全局收敛以及良好的推广能力， 引起各领域工作者的极大关注，被广泛应用于信息处理、模式识别、函数逼近、 智能控制和数据挖掘等许多领域。 3 一种遗传算法和人工神经网络技术结合的研究。 通过分析生物在环境生态系统中的成长模式，论文强调生物进化是一个在生 态环境里结合先天遗传进化和后天竞争学习进化的复杂过程；在传统遗传算法的 基础上，我们采用神经网络和遗传算法结合的方法。选用遗传算法找到粗略的最 优值区，作为神经网络的初始值，再用r b f 神经网络进行训练，采用r b f 神经网络 逼近g a 的适应度函数，解决了适应度函数的表示问题，达到了很好的效果。新算 法增强了智能搜索的能力，加快了种群的收敛速度 4 遗传算法和人工神经网络技术结合起来应用于计算机辅助概念设计中的 山东师范大学硕士学位论文 应用测试。 论文以沙发设计为例，基于组合原理和实例推理的创新设计机制，将上述遗 传算法和人工神经网络技术结合起来应用于计算机辅助概念设计中，具体实现了 许多构思巧妙、造型新颖的沙发样例。与此同时，实验测试数据也比较说明了本 算法的高效运行性能。 本文对遗传算法与人工神经网络技术结合及其在计算机辅助概念设计中的 应用方面进行了探讨，希望能够对相关领域的进一步研究工作起到一定的推动作 用。 关键词：遗传算法，r b f i 州，计算机辅助设计，概念设计，创新设计 中图分类号：t p 3 9 1 7 2 山东师范大学硕士学位论文 r e s e a r c ho nt h eg e n e t i ca l g o r i t h mi nc o m p u t e ra i d e ds o f a d e s i g na n d i t sa p p f i c a t i o n a b s t r a c t m r e s e a r c h e so na r t i f i c i a ln e u r a ln e t w o r k s ，c e l l u l a ra u t o m a t aa n de v o l u t i o n a r y c o m p u t a t i o nc h a r a c t e r i z e db ys e l f - o r g a n i z i n ga n ds e l f - l e a r n i n ga n da d a p t a t i o n , r o o t i n g f r o ms i m u l a t i n gs o m en a t u r a lp h e n o m e n o no rt h ep r o c e s sh a v eb e e nd e v e l o p e d g r e a t l ya st h e s c i e n c ea n dt e c h n o l o g ye n t e r i n gt h et i m ew h e nm u l t i - d i s c i p l i n e s i n t e r e r o s s ，s e e p sm u t u a l l ya n da f f e c t sm u t u a l l y g e n e t i ca l g o r i t h m ( g a ) i s 晰d e l yu s e da n de f f i c i e n tr a n d o ms e a r c ho p t i m i z a t i o n m e t h o d s ，w h i c hp r e m i s e do nt h ep r i n c i p l eo f t h ee v o l u t i o nt h e o r y i nv a r i o u ss t u d i e s a h o u tc o m p u t a t i o n a li n t e l l i g e n c e 。t h i sm g o f i t h mi sc o n c e r n e d 、析d e l y t h i sa l g o r i t h m w h i c hi si n s p i r i t e db yt h ed a r w i n se v o l u t i o nt h e o r ya n dt h em e n d e l sg e n e t i c s ， s i m u l a t e sp r o c e s s e si nn a t u r a ls y s t e mt h a tf o l l o wt h el a w so ft h eg e n e t i cs p e c i e sa n d t h ep r i n c i p l eo f t h en a t l l r a ls e l e c t i o na n ds u r v i v a lo f t h ef i t t e s t t h ee v o l u t i o n a r yc o m p u t a t i o nt e c h n i q u eh a db e e ns h o w ng r e a tp o t e n t i a la n d f a r - r e a c h i n gi m p a c t0 nd e s i g no p t i m i z a t i o n , b u ti ti sf a rf r o mr e a l i z i n gas y s t e mo f m a t c h i n g t h eh u m a np e r f o r m a n c e i np a r t i c u l a r , i ns o m ei n n o v a t i o nd e s i g n a p p l i c a t i o n sf i e l d s ，s u c ha sc o n s t r u c t i o n , a r t ，m u s i c ，d e s i g n , i ti sd i f f i c u l tt oe v a l u a t e t h ef i t n e s sb e c a u s et h em e a s u r ed e p e n d sm a i n l yo nt h eh u m a nm i n d h o wt h es y s t e m c a np r o v i d et h ee v o l u t i o no p p o r t u n i t yf o rt h ei n d i v i d u a la lt h es a i i 砖t i m em a y 曲u l l l a v o i dd e g e n e r a t i n gi nt h ee x e c u t i o no p t i m i z a t i o np r o c e s sa n dm a yr e a l i z et h e i n t e l l i g e n t f i m e s sf i m c t i o nh a v eb e c o m et h eh o t s p o t i nt h er e s e a r c ho n c o m p u t e r - a i d e dc o l l c e p t u a ld e s i g n a r t i f i c i a ln e u r a ln e t w o r k s ( a n n ) a n dg e n e t i ca l g o f i t h m ( g a ) b a s e do nb i o l o g yh a v e b e e nu s e dw i d e l yb e c a u s eo f t h e ks u p e r i o r i t y t os o l v et h er e l a t e dq u e s t i o n s , t h e r eh a sb e e ns p e c i f i cc o n t r i b u t i o ni nt h i sa r t i c l ea s f o l l o w s ： 1 t h i sp a p e ri sd e v o t e dt og a f i l s li ta n a l y z e st h eb a s i ct h e o r e n l qo fo a , t h e i m p r o v e m e n to fo a , d e s i g nm e t h o do fg aa n da n a l y z e sa s t r i n g e n c yo fo a , a n d p r e s e n t sa u n i f o r ms t a n d a r df o ra s l l - i n g e n c y t h e nak i n do f g ab a s e d0 1 1t r e es t r u c t u r e i sr e v i e w e d f i n a l l y , i td i s c u s s e st h ep r o g r e s so f g ai nc a d f o l l o w e db yt h ea n a l y s i s o f t h em a i np r o b l e m si nt h i sr e s e a r c h i n gf i e l d 2 a n a l y z et h eb a s i ct h e o r e m s , c h a r a c t e r i s t i c sa n dt h ec l a s s i f i c a t i o no fr b f n n f i r s t , i n t r o d u c et h ec o n c e p to f r b f n 3 q r b f n nw h i c hh a sd r a w nm u c ha t t e n t i o nd u e i i i 山东师范大学硕士学位论文 t oi t ss i m p l es u u c t u r e g o o dg e n e r a l i z a t i o na b i l i t ya n df a s tc o n v e r g e n c e a n di th a s b e e ns u c c e s s f u l l yu s e di nm a n yf i e l d s ，s u c ha ss y s t e mi d c n t i f i c a t i o n , i n f o r m a t i o n p r o c e s s i n g ，p a t t e r nr e c o g n i t i o n , i n t e l l e c t u a lc o n t r o la n dd a t am i n i n g 3 r e s e a r c ho nt h ea n na n dg aw h i c ha r et i e di nw e d l o c k b ya n a l y z i n gt h eb i o l o g i c a ld e v e l o p m e n tm o d e li nt h ee c o s y s t e m , t h ep a p e rh a s e m p h a s i z e db i o l o g i c a l e v o l u t i o nc o m b i n e d c o n g e n i t a l h e r e d i t a r y f e a t u r ea n d c o m l x 吨i t i v el e a r n i n g a n db a s e do nt h et r a d i t i o n a lg e n e t i ca l g o r i t h m 。w eu s et h e m e t h o do f a n na n dg aw h i c ha r cf l e di nw e d l o c k s e l e c tg a f i n d i n gr o u g ho p t i m u m v a l u ea r e aa si n i t i a lv a l u eo fa n n ，a n di ti st r a i n e db ya n n t h ef i t n e s sf u n c t i o no f g ai sa p p r o x i m a t e db ya r t i f i c i a ln e u r a ln e t w o r k p r o b l e me x p r e s s i n go ff i t n e s s f u n c t i o ni ss o l v e d t h en e wc o e v o l u t i o n a r ya l g o r i t h mn o to n l ys t r e n g t h e n e dc a p a c i t y o f i n t e l l i g e n ts e a r c hb u ta l s oa c c e l e r a t e dt h ec o n v e r g e n c yo f t h ep o p u l a t i o n 4 t h ea p p l i c a t i o n - t e s to ft h en e wc o e v o l u t i o n a r ya l g o r i t h mi nt h ec 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 ( c a c d ) t h ep a p e rh a s s t u d i e dt h ea p p l i c a t i o no ft h en 州 c o e v o l u t i o n a r ya l g o r i t h mi nt h ec 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 ) b a s e do n c o m b i n a t i o np r i n c i p l ea n dc a s e - b a s e dr e a s o n i n gm e c h a n i s m a n dt h es y s t e mh a s s h o w e dm a n yc o n s t r u c t i o ne x a m p l e so fi n g e n i o u si d e aa n di n n o v a t i v es h a p e f i n a l l y , t h e e x p e r i m e n t r e s u l t ss h o w e dt h en e wa l g o r i t h mh a s h i g h e r - p e r f o r m a n c e c h a r a c t e r i s t i ct h a nt r a d i t i o n a lg e n e t i ca l g o r i t h m as t u d yi sc o n d u c t e d0 1 1 c o e v o l u t i o n a r yt e c h n i q u ea n d i t s a p p l i c a t i o ni n 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 ) i nt h i sp a p e r i ti sh o p e dt h a ti tc o u l d p r o m o t e dt h ed e v e l o p m e n to f t h er e l a t er e s e a r c hf i e l d s k e y w o r d s ：g e n e t i ca l g o r i t h m , r b f n n ，c a d ，c o n c e p t u a ld e s i g n , c r e a t i v ed e s i g n c l a s s i f i c a t i o n ：1 甲3 9 1 7 2 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得( 注：如没有其他需要特别声 明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：糨 字：浏芴 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权堂撞可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存，汇编学位论文( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：泉崔 导师签字： 刹芴 签字日期：2 0 0 7 年午月习日 签字日期：2 0 07 年4 月却日 山东师范丈学颈士学位论文 1 1 研究背景 第1 章绪论 1 1 1 产品创新设计的新要求 产品的设计“3 在产品开发过程中起着重要作用。据统计，产品全生命周期的 成本在产品设计阶段有9 0 已经被决定。但是，设计人员在设计产品时，由于知 识面、设计经验和设计知识等方面的限制，产生一个合理的方案十分困难。另外， 设计是一个群体协作的工作工程，现代产品的复杂性使得单个设计人员不可能胜 任复杂的设计任务，因此新一代计算机辅助设计的研究必须为设计人员提供分布 式环境下的设计工具和支撑框架，以支持企业生产出高质量、高可靠性、低成本、 有创意和有市场竞争力的产品。 产品设计的目的是要创新产品，满足市场需要，重视创新设计也就是为产品 走向市场奠定良好的基础。设计的综合部分具有以下特性：( 1 ) 创造性；( 2 ) 多解 性；( 3 ) 近似性；( 4 ) 不完全性：( 5 ) 经验性；( 6 ) 综合性。实践表明，产品创新主 要来自产品功能、原理、形状、布局和结构等方面的创新。现代产品更新换代的 速度显著加快，要求大幅度缩短设计阶段的时间，正因如此，自8 0 年代中期以来， 计算机辅助创新设计脚脚逐渐受到人们的普遍重视。 计算机辅助设计技术发展至今已经有几十年的历史，且日趋成熟，并已被广 泛的应用到机械、汽车、航空、建筑等各个领域，成为现代工程设计不可或缺的 辅助工具。c a d 技术促进传统产业和学科的更新和改造，实现设计自动化，增强 企业及其产品在市场上的竞争能力这种趋势促使企业在着手进行新产品开发时 把面向产品的创新性、外观造型，人机工程等的设计提到了一个新的高度，从而 也迫切要求对工业设计的研究能有进一步的突破，以提高企业形象、产品设计水 平和市场竞争力。 在产品创新过程中，设计师的思维、经验以及领域知识起着相当重要的作用， 许多学者尝试从人工智能角度出发，进行产品创新设计的研究，利用计算机的快 速运算能力和人工智能技术，辅助设计者迸行创新设计，成为当前涉及领域的研 究热点之一。以知识为基础的产品创新竞争是2 1 世纪初全球制造业竞争的核心 i 1 2 沙发家具设计的历程、现状和发展趋向 随着人们对物质和精神需求的提高，家具产品生产，消费逐渐追求个性化， 并要求产品具有较高的品位，文化内涵和良好的功能。产品的功能已不再是消费 山东帅范大学硕士学位论文 者决定购买的最主要因素。产品的创新性、外观造型、宜人性、环保性等因素越 来越受重视。产品更新周期越来越短，这使得产品必须随着用户需求的变化而不 断更新 近年来，个性产品在市场上备受欢迎，消费者对产品的外观要求越来越高， 这使得产品必须跟着用户的需求变化不断更新。加上沙发产品其设计的特点；内 部零件的尺寸及外形很大程度上依赖于产品的外型，设计主要取决于产品的造 型 目前，我国的沙发设计h ”主要有三种模式：模仿设计、改进设计、创新设 计。模仿设计主要表现在仿制国内外市场上流行的沙发款式，以尽快适应市场的 需要；改进设计是在模仿他人设计的款式的基础上，融入一部分自己的设计思想， 对沙发的局部加以改进或改型，形成自己的设计产品；而创新设计则是依照工业 设计的原理，走开发创新的道路。如何实现沙发产品的c a d 快速创新设计嘲，成 为沙发行业竞争的焦点。 从生产设备的自动化程度看，目前我国有许多家具生产厂家已经引进了以加 工中心为主体的自动化生产线。这为在我国实现家具生产的计算机集成制造系统 ( c o m p u t e ri n t e g r a t i o nm a n u f a c t u r es y s t e m ，即c i m s ) 打下了基础，而长期困 扰我国家具业发展的问题是家具设计，作为计算机集成制造系统的重要组成部分 计算机辅助设计( c o m p t e r - a i d e dd e s i g n ，即c a d ) 是解决这一问题的有效途径。 利用相关的室内设计和动画软件，进行家具的动画设计，以展示单一家具的结构， 家具在具体虚拟环境中的整体效果展示；这将为设计者和消费者在设计阶段就可 以看到成品的最终效果。这样既加速了家具的设计又提高了产品设计的成功率， 同时还可以形成产品在设计阶段就被消费者接受的一种崭新的家具营销方式。为 了我国家具工业未来的发展，开发设计出符合我国国情的家具计算机辅助设计将 有重要的意义。 家具c a d 技术经过了几十年的发展，在家具设计方面得到了广泛的应用。c a d 技术已经由过去的代替手工绘图的辅助作用，进入到有效的全面辅助设计阶段， 贯穿于设计和生产的全过程。但是仍存在不足，如款式设计软件没有自身的专业 优势，其功能很容易被通用的图形设计软件所实现。随着计算机技术、c a d 技术 的发展，家具c a d 技术朝着标准化、集成化、智能化、网络化、并行工程、虚拟 技术的方向发展 1 1 3 计算机辅助概念设计 1 概念设计 概念设计是设计过程的早期阶段，其目标是获得产品的基本形式或形状。广 义上的概念设计包含了从产品的需求分析到进行详细设计之前的设计过程。它包 2 山东师范大学硕士学位论文 括功能设计、原理设计、形状设计，布局设计和初步的结构设计概念设计的各 个环节紧密相连，在设计过程中互相依赖，互为驱动 一般意义上的概念设计是指在产品的功能和原理基本确定的情况下，产品外 观造型的设计过程 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 技术以及认知与思维 科学嘲1 ”n 妇。 目前已有的许多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 4 遗传算法应用于计算机辅助设计技术的现状 摹t 近年来，国外已经有一些将遗传算法1 1 3 1 应用于创新设计的研究。澳大利亚悉 尼大学设计计算与认知研究中心的g e r o “”教授和他的同事一起，进行了用遗传算 法生成建筑平面图的研究，新颖的建筑平面图可以满足多个模糊的限制和目标管 理。他们还展示了进化如何通过对著名的建筑风格学习，生成新的建筑物，g e r o 已经在英国剑桥成功的组织了7 届设计中的人工智能国际会议，在澳大利亚悉尼 举办了4 届创新设计计算模型国际会议，对创新设计的计算模型，以及遗传算法 对创新设计的支持。作了卓有成效的研究。 意大利米兰工艺学院的s o d d u 教授利用计算机模拟技术生成艺术品，如台灯， 雕刻等，他在意大利米兰成功的组织了5 届生成艺术国际会议，对进化计算在建 筑设计、工业设计、艺术设计和音乐创作的理论研究及应用方面做了深入的探讨。 n a k a n i s h i 利用遗传编程技术开发了服装款式辅助设计系统“”，它将款式的 一系列相关尺寸编码为染色体，系统根据用户的选择进化款式，l e e 和c h o 等人提 出交互式遗传算法( i g a ) n 帕，即通过与用户的交互获得适应度函数，从而解决 款式适应度的评价问题。 山东师范大学硕士学位论文 香港理工大学的f r a z e r 教授领导的研究小组将遗传算法应用于玻璃杯设计、 建筑设计以及t a n g i b l ei n t e r f a c e 的研究当中。 英国l o u g h b r o u g h 大学的i j g r a h a m 将遗传算法应用于计算机辅助设计中， 论述了遗传算法在计算机辅助设计系统中应用的新进展。 浙江大学潘云鹤“”1 校长及他的学生们在创新原理、创新过程的描述模型和 计算模型方面做了很多探索性的工作，通过综合和类比生成设计等智能c a d 技术， 创造性地解决了图案构图、色彩和描绘等知识表达及实现的问题。他们近期的创 新设计研究成果敦煌石窟虚拟漫游与壁画复原，能让你领略到可视化创新设 计的神奇魅力在远离敦煌数千公里的杭州，你轻点鼠标，就可以“走”进著 名的第4 5 窟内，身临其境的观看窟内七身彩塑和壁画。 1 2 问题的提出 一，算法的收敛性能尚待改善 遗传算法在一些设计优化问题中已有相当数量的应用，但距离实现一个能与 人的行为相匹配的系统还很远。尤其是在一些创新设计应用( 如建筑、艺术、音 乐、设计) 中，由于传统的遗传算法最明显的缺点是它的收敛性问题，包括存在 收敛速度慢且存在未成熟收敛等缺陷，因而其在为个体提供进化机会的同时，也 不可避免地产生了退化的可能。 二、评价方法需由人工完成 由于设计目标的复杂性使得定义一个能描述刻画设计优劣适应废函数极为 困难，因此，目前的概念设计的方法主要是运用人机交互技术：在执行最优化的 过程中，让设计师对个体做出评价，反复进行人机交互，最终得到设计师心目中 的理想的设计方案。但也存在一个显著的问题：在个体数目非常多的情况下，势 必会加大设计师的工作量、降低系统的运行速度。 三、创新设计的复用问题 设计过程是极端复杂的，包含着人们对思维的全部划分：抽象( 逻辑) 思维、 形象思维、创造性思维，此外还有经验起着非常重要的作用，尤其是在设计的早 期阶段，当把沙发( 组件) 作为设计知识的模式置于设计的进化环境中，则相当 于在可能的空间中从较优点出发进行搜索，提高了设计效率；同时，对其遗传操 作( 选择、交叉、变异) 则可实现不同沙发( 组件) 问的类比设计，体现出形象 思维和创造性思维的特征。然而，如何有效地集成大量承载着优秀设计经验的沙 发( 组件) 并进行系统地有效管理以支持概念设计环境下的复用问题亟待解决。 4 1 3 本文的内容及主要工作 根据前面的论述，遗传算法在计算机辅助设计方面的应用还有十分广泛的研 山东师范大学硕士学位论文 究前景本文将概念设计的创新研究与计算机技术紧密结合起来，通过使用计算 模型和计算机工具，利用计算机的高信息存储量以及可视化手段，开发一个支持 沙发产品创新设计的环境。本文将遗传算法引入计算机辅助设计当中，使沙发产 品的创新设计更加智能化，使其生成的图像更有创意我们正在将机器学习、遗 传算法及人工神经网络等技术相结合，开发具有自主知识产权、支持产品创新设 计的环境。 本文将做以下几方面的主要工作： 第二章对遗传算法进行分析。i 介绍了遗传算法的基本原理、基本遗传算法的 改进及设计方法并对遗传算法的收敛性进行了分析，给出了一个统一的收敛标 准。最后，分析了遗传算法在设计问题中的应用价值 第三章对径向基神经网络的原理、结构、方法、分类进行了研究。指出r b f i 州 以其结构简单、非线性逼近能力强、收敛速度快、全局收敛以及良好的推广能力， 引起各领域工作者的极大关注，被广泛应用于信息处理、模式识别、函数逼近、 智能控制和数据挖掘等许多领域。 第四章研究遗传算法在计算机辅助创新设计中的应用。本文把遗传算法引入 到计算机辅助设计中来，在此基础上，将遗传算法和人工神经网络技术结合起来， 选用遗传算法找到粗略的最优值区，作为神经网络的初始值，再用r b f 神经网络 进行训练，采用r b f 神经网络逼近g a 的适应度函数，解决了适应度函数的表示问 题，建立一个基于遗传算法的智能沙发款式c a d 系统模型。 同时，本文作了遗传算法和人工神经网络技术结合起来应用于计算机辅助概 念设计中的应用测试。 论文以沙发设计为例，基于组合原理和实例推理的创新设计机制，将上述遗 传算法和人工神经网络技术结合起来应用于计算机辅助概念设计中，具体实现了 许多构思巧妙、造型新颖的沙发样例与此同时，实验测试数据也比较说明了本 算法的高效运行性能。 5 山东师范大学硕士学位论文 2 1 遗传算法概要 第2 章遗传算法分析 2 1 1 遗传算法的生物学和遗传学基础 生命的基本特征包括生长、繁殖，新陈代谢和遗传与变异。生命是进化的产 物，现代的生物是从长期的进化中发展起来的。达尔文( 1 8 5 8 年) 用自然选择学 说( n a t u r es e l e c t i o n ) 来解释物种的起源和生物的进化，该学说是一种被人们 广泛接受的生物进化学说。自然选择学说( n a t u r es e l e c t i o n ) ，包括了三个方 面： ( 1 ) 遗传( h e r e d i t y ) 这是物种稳定存在的原因。亲代将生物信息交给子 代，子代按照所得的信息发育，分化，因此子代总是和亲代具有相同或相似的形 状。 ( 2 ) 变异( v a r i a t i o n ) 亲代和子代之问以及子代的不同个体之间总有些差 异，这种现象我们称为变异。变异是随机发生的，变异的选择和积累是生命多样 性的根源。 ( 3 ) 生存斗争和适者生存。自然选择来自繁殖过剩和生存斗争。由于弱肉强 食的生存斗争不断地进行，其结果是适者生存，具有适应性变异的个体被保留下 来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，物种 变异被定向的朝着一个方向积累，于是性状逐渐和原始的祖先种不同，演变为新 的物种。这种自然选择过程是一个长期的、缓慢的、连续的过程。 生物进化的奇异本领是值得仿效的。正因如此，1 9 6 2 年，美国m i c h i g a n ( 密 执安) 大学的心理学教授和电工及计算机科学教授j o h nh h o l l a n d 和他的同事、 学生研究出一种叫遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 的搜索算法，其目 的是解释自然的自适应过程及设计一个体现自然界机理的软件系统。g a 的数学框 架是6 0 年代末形成的并且在1 9 7 5 年h o l l a n d 的专著中予以介绍。随后g a 开始吸引 大量的研究者和探索者使得这一理论得到不断的扩充和完善。 2 1 2 遗传算法的指导思想 遗传算法“”是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模 型。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存+ 检测”的 迭代过程的搜索算法。它采用简单的编码技术来表示各种复杂的结构，并通过对 一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜 6 山东师范大学硕士学位论文 索的方向。 2 1 3 遗传算法的基本操作 遗传算法的操作对象是代表问题可能潜在解集的一个种群( p o p u l a t i o n ) 。 所谓种群是指染色体带有特征的个体的集合，该集合内个体数称为群体的大小， 有时个体的集合也成为个体群。一个种群则由经过基因( g e n e ) 编码( c o d i n g ) 的一定数目的个体( i n d i v i d u a l ) 组成。每个个体实际上是染色体( c h r o m o s o m e ) 带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部 表现( 即基因型) 是某种基因组合，它决定了个体的形状的外部表现。因此在一 开始我们需要实现从表现型到基因型的映射即编码工作。仿造基因型的编码很复 杂，我们往往进行简化，如二进制编码初代种群产生之后，按照适者生存的原 则和优胜劣汰的原理，逐代( g e n e r a t i o n ) 演化产生出越来越好的近似解。在每一 代，根据问题域中个体的适应度( f i t n e s s ) 大小挑选( s e l e c t i o n ) 个体，并借 助于自然遗传学的遗传算子( g e n e t i co p e r a t o r s ) 进行组合交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 产生出代表新的解集的种群。这个过程将导致种群像自然进 化一样的后生代种群比前生代种群更加适应于环境，末代种群的最优个体经过解 码( d e c o d i n g ) ，可以作为问题近似最优解 遗传算法采纳了自然进化模型，如选择、交叉、变异、迁移等。如图2 - 1 表 示了遗传算法的过程。计算开始时，定数目的n 个个体( 父个体1 、父个体2 、 父个体3 、父个体4 ) 即种群随机的初始化，并计算每个个体的适应度函数( 适 应度函数是指为了体现染色体的适应能力，引入的对问题中的每一个染色体都能 进行度量的函数。通过适应度函数来决定染色体的优、劣程度，它体现了自然进 化中的优胜劣汰原则。对优化问题，适应度函数就是目标函数) ，第一代也即初 始代就产生了。如果不满足优化准则，开始产生新一代的计算。为了产生新一代， 按照适应度函数选择个体，父代要求基因重组( 交叉) 而产生子代所有子代按 照一定概率变异然后子代的适应度函数将被重新计算，子代被插入到种群中父 代取而代之，构成新的一代( 子个体1 、子个体2 、子个体3 、子个体4 ) 这一 过程循环执行，直到满足优化准则为止。 7 山东师范大学硬士学位论文 图2 - i 避传算法的过程 简单遗传算法的遗传操作主要有三种：选择( s e l e c t i o n ) 、交叉( c r o s s o v e r ) 、 变异( m u t a t i o n ) 改进的遗传算法大量扩充了遗传操作，以达到更高的效率 ( 1 ) 选择操作也叫复制操作，根据个体的适应度函数值所度量的优、劣程 度决定它在下一代是被淘汰还是被遗传。一般地说，选择将使得适应度较大( 优 良) 个体有较大的存在机会，而适应度较小( 低劣) 的个体继续存在的机会也较 小。简单遗传算法采用赌轮选择机制，令f i 表示群体的适应度值之总和，f i 表示种群中第i 个染色体的适应度值，它产生后代的能力正好为其适应度值所占 份额f i f i ( 2 ) 交叉操作的简单方式是将被选择出的两个个体p l 和p 2 作为父母个体，将 两者的部分码值进行交换。假设有如下八位长的二个体： 厂_ t t 广1 r t 厂 j l l 0 0 1 0 i l l l l o p l 厂1 广厂广t t | 1 f 1 1 0 1 1 j l l o j o i l p 2 l l l l l l j u 产生一个在1 到7 之间的随机数c ，假如现在产生的是3 ，将p 1 和p 2 的低三位交 换：p l 的高五位与p 2 的低三位组成数串1 0 0 0 1 0 0 1 ，这就是p l 和p 2 的一个后代q 1 个体；p 2 的高五位与p l 的低三位组成数串1 1 0 1 1 1 1 0 ，这就是p l 和p 2 的一个后代q 2 3 山东师范大学硕士学位论文 个体。其交换过程如下图2 - 2 所示： 匝圈璃碉 图2 - 2 交叉示意图 ( 3 ) 变异操作的简单方式是改变数码串的某个位置上的数码。我们先以最简 单的二进制编码表示方式来说明，二进制编码表示的每一个位置的数码只有o 和1 这两个可能，比如有如下二进制编码表示： 其码长为8 ，随机产生二个l 至8 之间的数k ，假如现在k = 5 ，对从右往左的第5 位进行变异操作，将原来的0 变为1 ，得到如下数码串( 红色的数字1 是被变异操 作后出现的) ： 二进制编码表示时的简单变异操作时将0 与1 互换；o 变异为1 ，1 变异为0 。 ( 4 ) 控制参数 并不是所有被选择了的染色体都要进行交叉操作和变异操作，而是以一定的 概率进行，一般在程序设计中交叉发生的概率要比变异发生的概率选取得大若干 个数量级，交叉概率取0 6 至0 9 5 之间的值；变异概率取0 0 0 1 至0 0 1 之间的值 2 1 4 遗传算法的流程 遗传算法的工作流程见图2 3 所示。遗传算法类似于自然进化，通过作用与 染色体上的基因寻找好的染色体来求解问题。与自然界相似，遗传算法对求解问 题本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于 适应度值来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗传算法中， 通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始群体；通 过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的 个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群。对这个新 种群进行下一轮进化。这就是遗传算法的基本原理 下面就是遗传算法思想： ( 1 ) 初始化群体； 9 山东帅范大学硕士学位论文 ( 2 ) 计算群体上每个个体的适应度值： ( 3 ) 按由个体适应度值所决定的某个规则选择将进入下一代的个体： ( 4 ) 按概率p c 进行交叉操作： ( 5 ) 按概率p c 进行变异操作； ( 6 ) 没有满足某种停止条件，则转第( 2 ) 步，否则进入( 7 ) ( 7 ) 输出种群中适应度值最优的染色体作为问题的满意解或最优解。 程序的停止条件最简单得有如下二种：完成了预先给定的进化代数则停止； 种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有 改进时停止。 图2 - 3 遗传算法的流程 2 2 编码方式 在遗传算法的运行过程中，它不对所求解问题的实际决策变量直接进行操 作，而是对表示可行解的个体编码施加选择、交叉、变异等遗传操作，通过这种 遗传操作来达到优化的目的，这是遗传算法的特点之一。 编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键 步骤。d e j o n g 曾提出了两条操作性较强的使用编码原则删。 编码原则一应使用能易于产生与所求问题相关的且具有低阶、短定义长度 模式的编码方式。 编码原则二应使用能使问题得到自然表示或描述的具有最小编码字符集的 编码方案。 山东师范大学硕士学位论文 总的来说，这些编码可以分为三大类：二进制编