（工程力学专业论文）遗传算法的改进及其在机械优化设计中的应用.pdf

山东建筑大学硕士学位论文 摘要 遗传算法是近年来在计算机科学和优化中受到广泛关注的一种模拟生物进化理论 的仿生学算法。与常规的优化算法相比，遗传算法具有隐含并行性和全局收敛性两大 显著特征，并且具有常规优化方法所没有的优点，如不需要梯度计算等。然而，遗传 算法毕竟是一门较新的学科，无论是在理论上，还是在实现上都有许多不完善的地方。 因此，不断地对遗传算法加以研究和改进，使其更加适用于工程实际，以便更好地、 更充分地发挥遗传算法的性能和特点是非常必要的。 本文对遗传算法及其在机械优化设计应用中的相关内容进行了研究，介绍了遗传算 法的基本结构、主要特点及应用于机械优化设计时具有一般意义的算法设计方案和算子 设计方法。 在实际应用中，基本遗传算法存在着收敛速度慢，稳定性差和早熟等问题。为克服 这些缺陷，本文在对遗传算法的基本要点进行介绍的基础上，对选择、交叉和变异等算 子操作过程进行了改进。以典型的遗传算法测试函数验证改进遗传算法的有效性与可 行性。 本文提出了基于惩罚和修复策略的约束处理方法，解决了单一使用惩罚方法时所 遇到的难以解决的问题，方便了遗传算法在约束优化问题中的应用，提高了遗传算法 在工程优化问题中的适用性。 本文运用f o r t r a n 语言编制了机械优化设计程序，对曲柄摇杆机构进行了优化 设计，并将改进的遗传算法得到的优化结果同基本遗传算法的优化结果进行了对比分 析，算例分析表明该程序用于机械优化设计是可行的和高效的，改进的遗传算法比基 本遗传算法有更好的收敛特性，迭代次数减少，优化设计结果也好于基本遗传算法。 关键词：遗传算法，优化设计，算法改进，约束处理，罚函数 山东建筑大学硕士学位论文 i m p r o v e dg e n e t i ca l g o r i t h ma n d i t sa p p l i c a t i o n i nt h em e c h a n i c a lo p t i m i z a t i o nd e s i g n w e iz h i m i n g ( e n g i n e e r i n gm e c h a n i c s ) d i r e c t e db yl ux i a o y a n g a b s t r a c t g e n e t i ca l g o d t h m ( g a ) i so n eo ft h em a i nd i r e c t i o n si nt o d a y sc o m p u t e rs c i e n c e i t s a p p l i c a t i o ni nm e c h a n i c a lo p t i m i z a t i o nh a s a t t r a c t e dm o r ea n dm o r ea t t e n t i o n s c o m p a r e dw i t h t r a d i t i o n a lo p t i m i z a t i o nm e t h o d s ，g e n e t i ca l g o r i t h mh a st w on o t a b l ec h a r a c t e r s o n ei st h e l a t e n tp a r a l l e l i s ma n dt h eo t h e ri ss e a r c h i n gi nt h ew h o l ea r e a g e n e t i ca l g o r i t h mh a ss o m e a d v a n t a g e sw h i c ht r a d i t i o n a lm e t h o d sd o n th a v e f o re x a m p l e ，谢t l lg e n e t i ca l g o r i t h mw e d o n tn e e dt h ec a l c u l a t i o no fg r a d e s n e v e r t h e l e s s ，g e n e t i ca l g o r i t h mi sar e l a t i v e l yn e w s u b j e c t i th a sn o tb e e np e r f e c te i t h e ri nt h e o r yo rr e a l i z i n gt e c h n i q u e s s og e n e t i ca l g o r i t h m n e e d st ob er e s e a r c h e da n di m p r o v e dc o n t i n u a l l yi no r d e rt om e e tt h en e e d so fe n g i n e e r i n g s o m ee s s e n t i a la s p e c t so fg e n e t i ca l g o r i t h ma n dm e c h a n i c a lo p t i m i z a t i o na r ed i s c u s s e d i nt h i sp a p e r t h eb a s i cs t r u c t u r eo fg aa n di t sm a i nc h a r a c t e r i s t i c sa l ei n t r o d u c e d i nt h i s p a p e r , t h ec h a r a c t e r i s t i c so fm e c h a n i c a lo p t i m i z a t i o na n di t sa c t u a l i t i e sa r ei n t r o d u c e d s o m e b a s i cr u l e sa b o u tg a sa l g o r i t h ms t r u c t u r ed e s i g na n da r i t h m e t i co p e r a t o r s d e s i g n sa r e p r o p o s e d g e n e t i ca l g o r i t h mh a sd r a w b a c k ss u c ha ss l o wc o n v e r g e n c e ，l e s ss t a b i l i t ya n d p r e m a t u r ei na c t u a lu s e s t oo v e r c o m et h e s ep r o b l e m s ，r e p r o d u c t i o n ，c r o s s o v e ra n dm u t a t i o n o p e r a t o r sa sw e l la st h ep r o c e d u r ea l ei m p r o v e db a s e d o ni n t r o d u c t i o no ft h ep r i n c i p l e s t h e a v a i l a b i l i t ya n df e a s i b i l i t yo ft h ei m p r o v e dg e n e t i ca l g o r i t h m s a g ep r o v e db yg e n e t i c a l g o r i t h m st e s t i n gf u n c t i o n r e s t r i c t i o nt r e a t m e n tm e t h o db a s e do np u n i s h m e n ta n dr e n o v a t i o nw a sp u tf o r w a r di n t h i sp a p e r i nt h i sw a yd i f f i c u l tp r o b l e m sa l es o l v e dw h e ns i n g l em e t h o dw i t hp u n i s h m e n tu s e d i tm a k e sg e n e t i ca l g o r i t h m st ou s ei nr e s t r i c t i o no p t i m i z a t i o nm o r ec o n v e n i e n t l ya n dp r o m o t e s a p p l i c a b i l i t y o fg e n e t i ca l g o r i t h m si nt h eu s eo fe n g i n e e r i n go p t i m i z a t i o n as t r u c t u r eo p t i m a lp r o g r a mi sw r i t t e ni nf o r t r a na n da p p l i e dt h ep r o g r a mt om e c h a n i c a l d e s i g n t h er e s u l t so ft h ei m p r o v e dg e n e t i ca l g o r i t h ma r ec o m p a r e dw i t ht h a to ft h eb a s i c i i 山东建筑大学硕士学位论文 g e n e t i ca l g o r i t h r a , i ti ss h o w n t h a ti ti sf e a s i b l ea n de f f e c t i v et oa p p l i e dt h i so p t i m a lp r o g r a mt o t h em e c h a n i c a ld e s i g n , t h ei m p r o v e dg e n e t i ca l g o r i t h mh a sah i g h e rs e a r c h i n ge f f e c t i v e n e s s ， a n di t sp e r f o r m a n c ec o n v e r g e n c eh a sg r e a t l ye n h a n c e d , i t sr e s u l t so fo p t i m u md e s i g na l e s u p e r i o rt ot h o s eo ft h eb a s i cg e n e t i ca l g o r i t h m k e y w o r d s ：g e n e t i ca l g o r i t h m , o p t i m i z a t i o nd e s i g n , i m p r o v e m e n to fa l g o r i t h m ， r e s t r i c t i o nt r e a t m e n t ，p e n a l i z a t i o nf u n c t i o n 原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究取得 的成果除文中已经注明引用的内容外，论文中不舍其他人已经发表或撰写过的研 究成果，也不包含为获得山东建筑大学或其他教育机构的学位证书而使用过的材 料对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人 承担本声明的法律责任 学位论文作者签名：墨敏舌：墨盆日期 兰竺12 笸：7 d 学位论文使用授权声明 本学位论文作者完全了解山东建筑大学有关保留、使用学位论文的规定，即： 山东建筑大学有权保留并向国家有关部门或机构送交学位论文的复印件和磁盘，允 许论文被查阅和借阅。本人授权山东建筑大学可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或其它手段保存、汇编学位论文。 保密论文在解密后遵守此声明。 学位论文作者签名： 导师签名： 魏鑫：鲴日期2 缒! ：熊 仑翌三： 日期 图 山东建筑大学硕士学位论文 第1 章绪论 1 1 选题背景和意义 优化设计是二十世纪六十年代随着电子计算机的广泛使用而迅速发展起来 的一门新的学科。优化设计能为工程及产品设计提供一种重要的科学设计方法， 使得在解决复杂设计问题时，能从众多的设计方案中寻得尽可能完善的设计方案 并大大地提高设计质量和设计效率。目前优化设计方法在航空、造船、国防、机 械、电子、电器、交通、建筑、纺织、冶金、石油、化工及管理等领域都得到了 广泛地应用和发展，并且取得了显著的经济效益和社会效益。 最优化是人们在工程技术、科学研究和经济管理等诸多领域中经常遇到的问 题。如结构设计要在满足强度要求等条件下使所用材料的总重量最轻：资源分配 要使各用户利用有限资源产生的总效益最大：安排运输方案要在满足物资需求和 装载条件下使运输总费用最低：编制生产计划应按照产品的工艺流程和客户需 求，尽量降低人力、设备、原材料等成本，使总利润达到最高等。任何一项工程 或一个产品的设计，都需要根据设计要求，合理选择方案，确定各种参数，以期 望达到最佳的设计目标，如重量轻、材料省、成本低、性能好、承载能力高等。 可以预料，随着科学技术特别是计算机技术的不断发展，数学理论和方法向各门 学科和各个应用领域更广泛、更深入地渗透，在当今的信息时代，最优化理论和 技术必将在社会的诸多方面起着越来越大的作用，有着巨大地发展潜力和广泛地 应用前剽1 】【2 】。 常规的设计方法通常是，根据设计人员的经验或通过类比法以相似的设计作 为初始设计方案和参数，然后通过人工作图及复杂的计算确定初始参数是否可 行。若结果不满足要求，则修改初始参数，重新进行人工作图及计算。通常需要 如此循环多次才能得到符合需要的设计结果，并且设计结果一般都不是“最优” 的。 优化设计是在规定的各种设计限制条件下，将实际设计问题首先转化为最优 化问题的数学模型，然后运用各种最优化理论和方法，在计算机上编程进行自动 寻优计算，从满足各种设计要求及限制条件的全部可行方案中，选择出最优设计 方案。与常规的设计方法相比，优化设计的最大优点是：它能根据最优化理论， 从所有可行的设计方案中找到最完善、最合适的一个方案来。在优化设计过程中， 山东建筑大学硕士学位论文 计算机的使用，大大缩短了设计周期、减少了设计误差，提高了设计质量。 有很多常用的优化算法，如无约束最优化方法中的梯度法( 最速下降法) 、牛 顿法、共轭方向法、变尺度法、坐标轮换法和鲍威尔法等：约束最优化方法中的 约束随机方向搜索法、罚函数方法、复形法等。上述这些方法亦可称为传统的优 化方法【3 1 。 随着工程优化问题的日趋大型化、复杂化，优化问题目标函数的性态也变得 越来越复杂( 如函数的连续性、凹凸性、多峰性、多维性等) ，工程中的许多大系 统优化问题都具有很高的非线性和非连续性。由于传统的优化方法在以下几方面 存在诸多缺陷，在一般情况下很难找到这类复杂优化问题的全域最优解。 ( 1 ) 传统优化算法一般对目标函数都有较强的限制性要求( 如连续、可微、单 峰等) ，实际的优化设计问题常常不能满足，甚至达不到这些要求： ( 2 ) 在优化算法实施之前，要进行大量的准备工作( 如求函数的一阶和二阶导 数、某些矩阵的逆等) ，在目标函数较为复杂的情况下，这一工作是很困难的， 有时甚至是不可能的： ( 3 ) 算法的结果一般与初始值的选取有较大关系，不同的初值可能导致不同 的结果，而初始值在很大程度上依赖于优化者对问题背景的认识及所掌握的知识 结构： ( 4 ) 算法缺乏简单性和通用性。针对一个特定问题，使用者需要有相当的知 识和经验去判定，哪一种优化方法更为适用，这是优化方法难以得到更广泛应用 的原因之一。 当人们不满足于用传统优化方法求解某些工程问题时，在2 0 世纪8 0 年代初 期，开始注意到了另一类有别于传统优化算法的智能型优化算法，如遗传算法、 人工神经元网络优化算法、模拟退火算法、蚁群算法、粒子群算法、混合优化算 法、混沌优化算法、禁忌搜索算法、拉格朗日松弛等等。这类算法的共同点是， 通过揭示和模拟自然现象和过程，综合利用数学、物理学、生物进化、人工智能、 神经科学和统计学等理论形成的算法，也被称之为现代优化算法。由于这些算法 在求解非线性、多约束、多极值的问题中显示出了其优越性，赢得了人们的青睐， 目前己逐渐成为解决一些复杂工程优化问题的强有力的工具。 遗传算法是一种模仿自然选择与进化的基于种群数目的随机搜索算法，是根 山东建筑大学硕士学位论文 据生物进化理论，应用群体的搜索技术，通过选择、交叉及变异等遗传操作，使 群体一代一代进化，逐步接近搜索空间中越来越好的区域，直到取得最优解。由 于遗传算法对非线性不连续多峰函数和无解析表达式的优化问题有很强的通用 性，对目标函数具有全局优化性和稳健性，它的搜索是多途径进行的，所以其运 算并行性好、直观简单、可操作性强【4 h 刀。 通俗地说，优化算法就是收敛于最优解的一系列迭代计算。很多经典的优化 算法是根据目标函数的梯度或高阶导数确定迭代计算公式，每一次迭代计算的结 果沿着最速下降方向不断改变，这种搜索方法虽然简单，但对于复杂优化问题极 易陷入局部最优解。遗传算法是通过对一个潜在解的种群进行多方向搜索，使迭 代结果避免陷入局部最优而最终达到全局最优。种群搜索模拟进化过程，即每代 中相对好的解可以得到繁殖的机会，而差的只能消亡。遗传算法采用概率转移律， 以一定的概率选择部分个体繁殖，而剩余个体则消亡，从而将搜索引向解空间中 最可能获得改进的区域。 遗传算法具有传统优化方法不可比拟的优势，它己逐步发展成为一种迭代、 自适应、启发式、概率性的搜索算法，以其在解决不同的非线性问题中的自适应 性、全局最优性及隐含并行性而具有独特的吸引力，这些优势使得遗传算法在工 程设计中具有很大的应用前景。然而，遗传算法毕竟是- - i - j 较新的科学，无论在 理论上还是在实现方法上都存在着很多不完善的地方。因此，不断地对遗传算法 加以研究和改进使其更适于工程实际应用，更好地、更充分地发挥它的性能和特 点是非常必要的。 1 2 机械优化设计的发展和研究现状 在机械设计领域中，追求最优的设计方案一直是工程设计人员不懈努力、奋 斗不止的理想与目标，并且在长期的实际设计中产生了诸如进化优化、直觉优化、 试验探索优化等一些优化策略与方法，并在“设计一评价一再设计 的过程中， 自觉或不自觉地利用经验、知识、图解分析、黄金分割和分析数学等一些经典的 优化方法进行优化设计，解决了一些简单的单变量的优化设计问题。在此阶段， 没有形成完整的优化设计的理论体系，因此可称它为古典优化设计。 随着近代数学分支一一数学规划论的创立，特别是近5 0 年来，计算机及其 计算机技术的迅速发展，使得对工程设计中较复杂的一些优化问题的计算具备了 山东建筑大学硕士学位论文 重要的计算工具，并在航空和航天、汽车和船舶等民生要害工业部门及其一些重 大工程设计的应用中取得了较好的技术和经济效果，同时也促进了工程优化设计 理论和方法的发展，如开发出优化方法程序库、机构与零部件优化设计程序库、 结构优化设计程序库等一些大型的工程优化设计应用软件，并结合工程优化设计 的特点，在多目标、混合离散变量、随机变量、模糊以及人工智能、神经网络及 遗传算法等优化算法方面都取得显著的成果，逐步形成以计算机和优化技术为基 础的近代优化设计。 从产品设计的全局来看，目前的优化设计多数还仅仅停留在确定设计方案后 的参数优化计算方面，因而有时也称它为参数优化设计，或“狭义一的优化设计。 面向产品设计的过程，应将优化设计拓宽到产品的全系统、全性能和全寿命周期 的优化，这项技术总称它为“广义 优化设计，是适应产品设计、c a d 技术发展 需求和在现代科学技术支持下的优化设计技术的新发展。 随着科学技术的发展，机械产品设计的水平和质量直接关系到该产品在市场 上的竞争力。一个能在国际市场上站得住脚的机械产品，一般在技术性能、经济 效益和结构造型三个方面拥有综合优势，优化设计这种先进的设计方法将为产品 具有这样的品质提供了保证。 应用现代设计理论和方法来改进和提高机械零件与系统的设计质量、降低成 本、缩短开发周期、增强产品的竞争能力己被各国实践证明是非常有效的途径。 机械优化设计是现代设计方法中最活跃的分支之一，各种优化方法的研究和应用 使得机械零件及系统的设计更为合理和实用。在机械设计领域中，它首先用于结 构和机构的优化设计，随着研究的深入，优化设计方法目前己愈来愈多地应用到 机械产品的设计中，其主要应用有： a 机械参数优化设计 ( 1 ) 设计方案参数的优化设计：齿轮传动啮合参数、车床变速箱传动参数等： ( 2 ) 系统参数的优化设计：凸轮从动件系统动力学参数、单柱式龙门铣床总 体参数等： ( 3 ) 工艺参数的优化设计：单工序加工切削参数、轧制工艺参数等： ( 4 ) 机构优化设计：平面连杆机构构件尺寸、车辆转向机构尺寸等。 b 机械结构优化设计 山东建筑大学硕士学位论文 ( 1 ) 尺寸的优化设计：锅炉外部尺寸、支撑框架结构尺寸等： ( 2 ) 形状优化设计：压力机、轧钢机机架过渡曲线、连杆形状等： ( 3 ) 拓扑优化设计：起重机、桥梁结构的桁架设计等。 可见，优化设计方法在机械工程设计领域得到了广泛地应用。实践表明，优 化设计不仅为工程设计提供了一种新的科学设计方法，使得在解决复杂设计问题 时，能从众多的设计方案中找到尽可能完善的或最合适的设计方案，并且能大大 提高设计效率和设计质量，具有较明显的经济效益和社会效益。国外设计经验表 明，采用优化设计方法可使设计的结构节约材料或降低造价1 0 5 0 ，如美国 贝尔( b e l l ) 飞机公司采用优化设计方法解决了4 5 0 个设计变量的大型结构优化设 计问题，一个机翼减轻重量达3 5 。一般说来，设计问题愈复杂，其优化设计结 果取得的技术经济效果就愈明显【8 9 1 。 1 3 遗传算法的发展及应用 1 3 1 遗传算法的产生与发展 。： 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 起源于对生物系统所进行的计算机 模拟研究。早在本世纪4 0 年代，就有学者开始研究如何利用计算机进行生物模 拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研 究工作。六十年代到七十年代初期，主要由美国m i c h i g a n 大学的j o h r lh o l l a n d 与其同事、学生们研究形成了一个较完整的理论和方法【l o 】，从试图解释自然系 统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统模型。 h o l l a n d 将该算法用于自然和人工系统的自适应行为的研究中，并提出了遗传算 法的基本定理一一模式定理( s c h e m at h e o r e m ) 。从而奠定了遗传算法的理论基 础。模式定理揭示出了群体中的优良个体( 较好的模式) 的样本数将以指数级规律 增长，因而从理论上保证了遗传算法是一个可以用来寻求最优可行解的优化过 程。并于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 。以后， h o l l a n d 等人将该算法加以推广，应用到优化及机器学习等问题中，并正式命名 为遗传算法。此后，遗传算法覆盖了三个主要研究领域：基本遗传算法的研究， 用遗传算法进行优化和带有分类系统的机器学习。 遗传算法适用于最优化问题应归功于h o l l a n d 的学生d ej o n g ，1 9 7 5 年，d e j o 魄在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验，树 山东建筑大学硕士学位论文 立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。例如，对于 规模在5 0 1 0 0 的群体经过1 0 2 0 代的进化，遗传算法都能以很高的概率找到最 优或近似最优解。他推荐了在大多数优化问题中都较适用的遗传算法的参数，还 建立了著名的d ej o n g 五函数测试平台，定义了评价遗传算法性能的在线指标和 离线指标，为遗传算法的普及推广起了重要作用。 19 8 9 年美国伊利诺大学的g o l d b e r g 出版了名为“g e n e t i ca l g o r i t h m si ns e a r c h , o p t i m i z a t i o na n dm a c h i n el e a r n i n g 的著作，是遗传算法研究领域中影响力最大 的专著，在这本书中，系统总结了遗传算法的主要研究成果，全面而完整地论述 了遗传算法的基本原理及其应用。对于遗传算法的理论及其多领域的应用展开了 较为全面的分析和例证。可以说这本书奠定了现代遗传算法的科学基础，为众多 研究和发展遗传算法的学者所瞩目。1 9 9 1 年，d a v i s 编辑出版了遗传算法手册 ( h a n d b o o ko f g e n e t i c a l g o r i t h m s ) 一书，书中包括了遗传算法在科学计算、工 程技术和社会经济中的大量应用实例。这本书为推广和普及遗传算法的应用起到 了重要的指导作用。 1 9 9 2 年，m i c h a l e w i c z 出版了另一本很有影响力的著作“g e n e t i c a l g o r i t h m s + d a t as t r u c t u r e = e v o l u t i o np r o g r a m s 一，对遗传算法应用于优化问题起到 了推波助澜的作用。经过2 0 余年的发展，该领域的著作和研究成果不断涌现， 遗传算法的理论研究和应用成果取得不断进展，算法本身逐渐趋于成熟，特别是 近年来世界范围形成的进化计算热潮，计算智能己成为人工智能研究的一个重要 方向，使遗传算法受到广泛关注。 8 0 年代中期以来是遗传算法和进化计算的蓬勃发展期，以遗传算法、进化 计算为主题的多个国际会议在世界各地定期召开，为研究和应用的思想、进展和 经验提供了国际交流的机会，并促进了理论与实际工作者之间的相互理解和合 作。自1 9 8 5 年起，两年一次的系列会议i c g a ( i n t e m a t i o n a lc o n f e r e n c eo ng e n e t i c a l g o r i t h m s ) 开始召开，会议集中了遗传算法以及相关领域的各路精英，交流他们 在遗传算法理论及应用中的最新成果，p p s n ( i n t e m a t i o n a lc o n f e r e n c eo np a r m l d p r o b l e ms o l v i n gf r o mn a t u r e ) 是i c g a 姊妹会议，每个偶数年在欧洲召开，第一 次会议于1 9 9 0 在德国召开，其统一主题是自然计算，既源于自然的算法、比较、 理论与实验的理解及其在科学与技术的实际问题中的应用。另一个每两年一次的 山东建筑大学硕士学位论文 系列国际会议a n n & g a ( i n t e l * n a t i o n a lc o n f e r e n c e0 1 1a r t i f i c i a ln e u r a ln e t s & g e n e t i ca l g o r i t h m s ) 19 9 3 年在奥地利召开，i c e c ( i e e ei n t e r n a t i o n a lc o n f e r e n c e 0 1 1e v o l u t i o n a r y c o m p u t a t i o n s ) 第一次会议是1 9 9 4 年在美国o r l a n d o 召开的，这个 会议包含了进化策略、进化规划、遗传算法和遗传规划等多个技术领域。关于此 类内容的会议还有e p ( a n n u a lc o n f e r e n c e0 1 1e v o l u t i o n a r yp r o g r a m m i n g ) ， f o g a ( w o r k s h o po i lf o u n d a t i o no fg e n e t i ca l g o r i t h m s ) 、c o g a n n ( i n t e m a t i o n a l w o r k s h o po nc o m b i n a t i o n so fg e n e t i ca l g o r i t h m sa n dn e u r a ln e t w o r k s ) 等等。在我 国有关遗传算法、进化计算的研究从2 0 世纪9 0 年代以来一直处于不断上升时期， 特别是近年来，遗传算法、进化计算的应用在许多领域取得了令人瞩目的成果 1 1 - 1 3 】。该类研究获得不同渠道的经费资助比例也在逐年上升。 1 3 2 遗传算法的应用 遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的 具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。目前遗传 算法的主要应用领域有 ( 1 ) 函数优化【1 7 】。函数优化是遗传算法的经典应用领域，也是对遗传算法 进行性能评价的常用算例。很多人构造出了各种各样的复杂形式的测试函数，有 连续函数也有离散函数，有凸函数也有凹函数，有低维函数也有高维函数，有确 定函数也有随机函数，有单峰值函数也有多峰值函数等。用这些几何特性各具特 色的函数来评价遗传算法的性能，更能反映算法的本质效果。而对于一些非线性、 多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以 方便地得到较好的结果。 ( 2 ) 组合优化【1 8 】【1 9 1 。随着问题规模的增大，组合优化问题的搜索空间也急剧 扩大，有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对 这类复杂问题，人们巳意识到应把主要精力放在寻求其满意解上，而遗传算法是 寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的n p 完 全问题非常有效。例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、 图形划分问题等方面得到成功的应用。 ( 3 ) 生产调度问题【2 0 】【2 。生产调度问题在很多情况下所建立起来的数学模型 难以精确求解，即使经过一些简化之后可以进行求解，也会因简化得太多而使得 山东建筑大学硕士学位论文 求解结果与实际相差甚远。而目前在现实生产中也主要是靠一些经验来进行调 度。现在遗传算法已成为解决复杂调度问题的有效工具，在单件生产车间调度、 流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。 ( 4 ) 自动控制圈】。在自动控制领域中有很多与优化相关的问题需要求解， 遗传算法已在其中得到了初步的应用，并显示出了良好的效果。例如用遗传算法 进行航空控制系统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的 模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规 则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等，都显 示出了遗传算法在这些领域中应用的可能性。 ( 5 ) 机器人学f 2 4 2 甜。机器人是一类复杂的难以精确建模的人工系统，而遗传 算法的起源就来自于对人工自适应系统的研究，所以机器人学理所当然地成为遗 传算法的一个重要应用领域。例如，遗传算法已经在移动机器人路径规划、关节 机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调 等方面得到研究和应用。 ( 6 ) 图像处理【2 6 】【2 7 1 。图像处理是计算机视觉中的一个重要研究领域。在图像 处理过程中，如扫描、持征提取、图像分割等不可避免地会存在一些误差这些 误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的 重要要求。遗传算法在这些图像处理中的优化计算方面找到了用武之地目前己 在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。 ( 7 ) 人工生命【2 引。人工生命是用计算机、机械等人工媒体模拟或构造出的具 有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两 大主要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是 研究人工生命现象的重要基础理论。虽然人工生命的研究尚处于启蒙阶段，但遗 传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步 的应用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相 成，遗传算法为人工生命的研究提供了一个有效的工具，人工生命的研究也必将 促进遗传算法的进一步发展。 ( 8 ) 遗传编程【2 9 】。k o z a 发展了遗传编程的概念，他使用了以l i s p 语言所表示 的编码方法，基于对一种树型结构所进行的遗传操作来自动生成计算机程序。虽 山东建筑大学硕士学位论文 然遗传编程的理论尚未成熟，应用也有一些限制，但它己成功地应用于人工智能、 机器学习等领域。 ( 9 ) 机器学习【3 0 】 3 1 】。学习能力是高级自适应系统所应具备的能力之一。基于 遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。例如， 遗传算法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数从而更好 地改进了模糊系统的性能：基于遗传算法的机器学习可用来调整人工神经网络的 连接权，也可用于人工神经网络的网络结构优化设计：分类器系统也在学习式多 机器人路径规划系统中得到了成功的应用。 近年来在机械工程领域中，遗传算法的应用也呈现出发展的势态，如在可靠 性分析方面，为了使机械系统获得最高可靠性，采用遗传算法对系统可靠度进行 分配：在统计数据基础上，把失效分布模型及其参数作为参变量进行编码，应用 遗传算法建立更符合实际的失效概率分布模型。在柔性制造系统( f m s ) 调度方 面，用遗传算法运算实现待加工零件在系统中的最短加工时间：针对需多工序加 工的零件为每道工序合理分配设备，在各台设备负荷相等的前提下实现机床设备 的最优分配。在数控加工误差预报与控制方面，采用遗传算法建立最优误差模型， 再根据误差预报的误差修改数控加工程序，实现加工误差的自适应控制。在反求 工程方面，采用遗传算法获得符合原设计的设计和工艺参数，利用遗传优化设计 将所得的原设计的数学模型改进原产品设计。 ， 虽然遗传算法在机械工程应用中还有些问题有待于解决，但是随着研究的进 一步深入和完善，遗传算法在机械工程领域的应用将越来越广。 1 4 遗传算法的研究热点 遗传算法的优点就在于其适用性强，但是标准遗传算法所能够解决的问题非 常有限，所以如何将算法作适当的调整与改进使之能够适用于工程实际问题始终 是人们的研究热点，由于具体问题的差异，需要对遗传算法作不同方面的改进才 能够得到较为理想的结果，总结现有文献，遗传算法的改进主要是对编码方式、 控制参数的确定、选择方式和交叉变异机理等进行了深入的探究，引入了动态策 略和自适应策略以改善遗传算法的性能，从而产生了各种变形的遗传算法 ( v a r i a n t so fc a n o n i c a lg e n e t i ca l g o r i t h m s ，简称v c g a ) 。其基本途径概括起来有 以下几个方面： 山东建筑大学硕士学位论文 ( 1 ) 改变遗传算法的组成成分和使用技术，如选用优化控制参数、适合问题 特性的编码技术等【3 2 】【3 3 1 ( 2 ) 其他优化方法如模拟退火法、禁忌搜索法以及一些传统优化方法等与遗 传算法结合使用，形成混合算法，以提高算法的收敛速度和收敛精度，避免算法 出现震荡或者陷入局部最优 3 4 - 3 6 。 ( 3 ) 应用动态自适应技术在进化过程中调整算法控制参数如交叉率、变异率 等，也可以调整编码的粒度，提高算法的有效性【3 刀。 ( 4 ) 改进遗传算子，使之更加适应相应的优化问题的解决3 8 1 。 ( 5 ) 采用并行的遗传算法【3 9 - 4 1 。 将上述方法应用于改进算法之中，产生了如多种群独立进化的分层遗传算法： 能够随适应度自动改变交叉率和变异率的自适应遗传算法：将每一代个体划分为 若干类基于生物学小生境技术的遗传算法：融合梯度法、爬山法、模拟退火等方 法的混合遗传算法等等，这些改进算法的产生和发展必将能够使遗传算法更好的 应用于工程实际问题的解决。 1 5 本文的主要工作 本论文通过对遗传算法和机械优化设计等方面的内容的分析与综合，编制了 基于基本遗传算法的机械优化程序。针对基本遗传算法存在的收敛速度慢及算法 稳定性差等缺陷，对遗传算法进行了改进，并编制了相应的优化程序。本论文 具体完成了以下几方面的工作： 1 介绍了近年以来得到广泛重视的一种拟生物进化算法一遗传算法，分析 了遗传算法的基本结构和主要特点，介绍了遗传算法用于优化设计时的算法设计 和算子设计的内容。 2 根据遗传算法的机理对遗传算法的选择、交叉、变异算子进行了改进， 可以有效的解决遗传算法存在的收敛速度慢和稳定性差的缺点。 3 对遗传算法应用于优化设计时的数学建模、约束条件处理、作了详细的 介绍和分析。针对约束条件的特点，提出了不可行解的修复策略。 4 将改进后的遗传算法应用到机械优化领域，针对具体的工程实例进行优 化。通过上述工作，拓宽g a 这一优秀算法的应用领域，力争为求解机械优化问 山东建筑大学硕士学位论文 题提供又一强有力的工具。 山东建筑大学硕士学位论文 第2 章遗传算法及其原理 2 1 遗传算法的特点 与传统优化算法相比，遗传算法有以下特点： ( 1 ) 遗传算法以决策变量的编码作为运算对象。与传统的优化算法不同，遗 传算法不是直接以决策变量的实际值本身，而是以决策变量某种形式的编码作为 运算对象进行优化计算。这种对决策变量的编码处理方式，可以使我们在优化计 算过程中借鉴生物学中染色体、基因等概念，模仿自然界中生物遗传和进化等机 理，方便地应用遗传操作算子。特别对那些无数值概念或者很难有数值概念而只 有代码概念的优化问题，这种编码处理方式更显示出其独待的优越性。 ( 2 ) 遗传算法直接以目标函数值作为搜索信息。传统的优化算法不仅需要利 用目标函数值，往往还需要其导数等其它一些辅助信息才能确定搜索方向。遗传 算法仅用由目标函数值变换而来的适应度函数值就可以确定进一步的搜索方向 和搜索范围。对那些复杂的、导数不存在的函数优化问题及组合优化问题等，因 为避开了函数求导这个环节，应用遗传算法就显得比较方便了。再者，直接利用 目标函数值或个体适应度，可使我们把搜索范围集中到适应度较高的区域搜索， 从而提高了搜索效率。 ( 3 ) 遗传算法同时使用多个搜索点的搜索信息。传统的优化算法往往是从解 空间中的一个初始点开始最优解的迭代搜索过程。单个搜索点所提供的搜索信息 毕竟不多，所以搜索效率不高，有时甚至使搜索过程陷入局部最优解而停滞不前。 遗传算法则从一个由多个个体组成的初始群体开始最优解的搜索过程。对这个群 体进行选择、交叉、变异等运算，产生一个新一代的群体，这个过程中包含了很 多群体信息。这些信息可以避免搜索一些不必搜索的点，这就是遗传算法特有的 隐含并行性。 ( 4 ) 遗传算法使用概率搜索技术。很多传统的优化算法往往使用的是确定性 搜索方法，即一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系， 这种确定性也有可能使搜索永远达不到最优点，而限制了算法的应用范围。遗传 算法属于一种自适应概率搜索技术，它的选择、交叉、变异等运算都是以一种概 率的方式来进行的，从而增加了其搜索过程的灵活性。虽然这种概率特性也会使 群体中产生一些适应度不高的个体，但随着进化过程的进行，新的群体中总会更 山东建筑大学硕士学位论文 多地产生出许多优良的个体。 2 2 标准遗传算法具体优化操作 通过定义不同的复制、交叉和变异操作，可以形成不同的遗传算法。最基本 的遗传算法是h o l l a n d 发展的标准遗传算法【4 2 4 3 1 ，它是通过设计变量的二进制编 码和解码来实现。遗传算法运算流程图如图2 1 所示，其具体操作涉及到以下几 个细节： 1 ) 2 ) 3 ) 4 ) 位串解码得到参数 开始 确定实际问题参数集 实数编码 初始化种群p ( t ) a 二进制编码 图2 - 1 遗传算法运算流程图 山东建筑大学硕士学位论文 选定设计变量后，根据优化设计的要求定义各设计变量的搜索范围 x m i n 工m 。】，然后由设定的最小搜索精度办m i n 来确定各设计变量对应的二进制 字串的长度，( 其中证表示取整) ，= i n t 1 0 9 2 ( x 一一石m i n ) h m i n + 1 ) + 1 】 ( 2 1 ) 再由字串长度，确定该字串所对应设计变量的实际求解精度h h = ( 工m “一x m i n ) ( 2 一1 ) ( 2 2 ) 假设对任一设计变量x x m x m a x 】采用长度为i i 的二进制编码，则搜索区 间 x m i n ，石m a x 被离散为2 。个等分点，该设计变量就从这些等分点中取值。由 于各设计变量都与某一既定长度的二进制字串一一对应，所以该设计变量所对应 的二进制字串必然是集合 o o o o ，0 0 0 1 ，1 1 1 0 ，1 l 1 1 中的一个元素。 把所有设计变量的二进制字串依次首尾相接，就构成了一个二进制字串表示的搜 索空间中的可能解。可见，这种二进制编码机制与基因构成生物染色体的方式十 分相似。各设计变量的字串长度越长，变量区间被离散地越细，计算精度也就越 高。 b 群体初始化 在应用遗传算法进行优化设计之前，要对一定群体规模的个体进行初始化， 这些经过初始化的个体将作为遗传进化祖先( 下一代的父代) 的初