（机械设计及理论专业论文）基于进化类混合算法的桥门式起重机结构优化.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 起重机金属结构占整机重量的6 0 左右，因此从经济性方面考虑，应用现代 优化方法对起重机金属结构进行优化设计，是起重机设计中一个必不可少并且 很有实用价值的一个环节。 鉴于单一算法在解决工程优化问题中存在的一些问题，本文在分析遗传算 法特点的基础上，分别针对其未成熟收敛和后期迭代速度缓慢的缺点，将模拟 退火算法和进化策略引入到遗传算法之中进行弥补，从而构造了进化类混合算 法。算法中处理的几个关键问题分别是： 1 ) 解决了混合离散变量的编码表示问题。算法中采用实数编码分别对连续 型变量、整数变量和离散变量等不同数据进行处理。 2 ) 改进了遗传算法中各个算子根据各算子在算法中所起的作用，对交叉 算子、变异算子和选择算子分别进行了相应的改进，使得算子的功能更加突出。 3 ) 实现了遗传算法、模拟退火算法和进化策略的合理集成。模拟退火算法 的引入，主要是为了避免遗传算法陷入局部最优解，因此将模拟退火算法与变异 算子结合，应用在算法的宏观搜索阶段。进化策略作为一个独立的算子集成到 遗传算法之中，主要负责后期微观搜索阶段的提速和提高解的精度。 用进化类混合算法对测试函数和桥门式起重机进行实例优化，结果表明该 算法能够最大程度地逃离局部最优解，在搜索精度和速度上都有很大的提高， 是一种稳定可靠的算法。因此该算法的应用能够为工程设计提供一定的辅助和 参考作用，使得设计周期大大缩短，提高设计质量，降低设计费用。 关键词：遗传算法；模拟退火算法；进化策略；混合离散变量；桥门式起重机 西南交通大学硕士研究生学位论文第1 i 页 a b s t r a c t i nr e s p e c tt h a tt h ew e i g h to fm e t a l l i cs t r u c t u r ea c c o u n t sf o r6 0 o ft h a to ft h ew h o l ec r a n e ，t oo p t i m i z et h em e t a l l i cs t r u c t u r eo fc r a n e u s i n gm o d e r no p t i m i z i n gm e t h o d s ，f r o mt h ep o i n to fe c o n o m i c a lv i e w , i s a ni n d i s p e n s a b l es t e pi nt h ep r o c e s so fd e s i g n i n gac r a n ea n di so fm u c h p r a c t i c a lv a l u ea sw e l l o w i n gt ot h ec u r r e n tp r o b l e m so fs i n g l ea l g o r i t h mu t i l i z e di n e n g i n e e r i n go p t i m i z a t i o n ，b a s e du p o nt h ea n a l y s i so fg e n e t i ca l g o r i t h m a n dr e s p e c t i v e l ya i m i n ga ti t sd e f e c t ss u c ha si m m a t u r ec o n v e r g e n c ea n d l o ws p e e di nt h el a s to fi t e r a t i o n ，t h i sa r t i c l ei m p o r t i n gs i m u l a t e d a n n e a l i n ga l g o r i t h ma n de v o l u t i o n a r ys t r a t e g yh a sm a d er e p a r a t i o nf o r t h a tg e n e t i ca l g o r i t h ma n dc o n s e q u e n t l ya ne v o l u t i o n a r yh y b r i da l g o r i t h m h a sb e e nc o n s t r u c t e d t h ev i t a lq u e s t i o n sd i s p o s e db yt h a ta l g o r i t h ma s f o l l o w s ： 1 、r e s o l v e dt h ep r o b l e m so ft h ec o d i n ge x p r e s sa b o u tt h em i x e d d i s c r e t ev a r i a b l e s r e a lc o d i n gi su t i l i z e di nt h ea l g o r i t h mt od e a lw i t h d i f f e r e n td a t u ms u c ha sc o n t i n u o u sv a r i a b l e s 、i n t e g r a lv a r i a b l e sa n d d i s p e r s ev a r i a b l e se t c 2 、i m p r o v e de a c ho p e r a t o ro fg e n e t i ca l g o r i t h m a c c o r d i n gt ot h e f u n c t i o no fe a c ho p e r a t o ri nt h eg e n e t i ca l g o r i t h m ，r e l e v a n ti m p r o v e m e n t h a sb e e n m a d ef o rc r o s s o v e ro p e r a t o r 、m u t a t i o no p e r a t o ra n ds e l e c t o p e r a t o r ，w h i c hg i v ep r o m i n e n c et oo p e r a t o r s 3 、a c h i e v e dt h er e a s o n a b l ei n t e g r a t i o no fg e n e t i ca l g o r i t h m 、 s i m u l a t e da n n e a l i n ga l g o r i t h ma n de v o l u t i o n a r ys t r a t e g y t h ei n t e n t i o n 西南交通大学硕士研究生学位论文第1 i i 页 o fi m p o r t i n gs i m u l a t e da n n e a l i n g a l g o r i t h mi st oa v o i dt h ep l u n g i n gi n t o l o c a lo p t i m i z e ds o l u t i o n o fg e n e t i ca l g o r i t h n l ，t h e r e b yw ec o m b i n e d s i m u l a t e da n n e a l i n ga l g o r i t h mw i t hm u t a t i o no p e r a t o rs oa st ob ea p p l i e d i nt h ep h a s eo fm a c r o s c o p i c a l l ys e a r c h i n go ft h ea l g o r i t h m e v o l u t i o n a r y s t r a t e g yi n t e g r a t e di n t ot h eg e n e t i ca l g o r i t h m a sa ni n d e p e n d e n to p e r a t o r m a i n l yt a k e sc h a r g eo fa c c e l e r a t i n gm i c r o c o s m i cs e a r c h i n ga n di m p r o v i n g t h ep r e c i s i o ni nt h el a s t r e s u l t so ft h ee x a m p l eo p t i m i z eo fm e a s u r i n gf u n c t i o na n d t h e o v e r h e a d g a n t r yc r a n e su s i n ge v o l u t i o n a r yh y b r i da l g o r i t h m sh a sp r o v e d t h a tt h ea l g o r i t h mc a rf u r t h e s ta v o i dl o c a lo p t i m i z e ds o l u t i o n , t h es p e e d a n dp r e c i s i o no fs e a r c h i n gh a sb e e ni m p r o v e dp r o d i g i o u s l ya n dt h a ti t i sas t e a d ya n dr e l i a b l ea l g o r i t h n lt h e r e f o r et h ea p p l i c a t i o no ft h e a l g o r i t h mc a np r o v i d ea s s i s t a n c ea n dr e f e r e n c ef o re n g i n e e r i n gd e s i g n t os o m ed e g r e e ，w h i c hc a ng r e a t l ys h o r t e nt h et i m ec o n s u m p t i o no fd e s i g n ， i m p r o v ed e s i g n i n gq u a l i t ya n dr e d u c ed e s i g n i n gc o s t k e y w o r d s ：g e n e t i c a l g o r i t h m ； s i m u l a t e da n n e a l i n ga l g o r i t h m ； e v o l u t i o n a r ys t r a t e g y ；h y b r i dd i s c r e t ev a r i a b l e s ：o v e r h e a da n dg a n t r y c r a n e s 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权西南交通大学可以将本论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复印手段保存和汇 编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密6 髟使用本授权书。 ( 请在以上方框内打“”) 学位论文作者签名：彳殇乡i l 澎指导老师签名：狒以 日期：9 优压f 2 2 -日期：矿石，2 2 、 西南交通大学学位论文创新性声明 本人郑重声明：所里交的学位论文，是在导师指导下独立进行研究工作所 得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体 己经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。 本学位论文的主要创新点如下： 1 ，基于混合算法的实现，用模拟退火算法来弥补遗传算法早熟收敛的缺陷， 用进化策略来补偿遗传算法后期迭代缓慢的缺点，从而实现遗传算法、模拟退 火算法和进化策略三者的集成。 2 ，通过对均匀交叉算子进行改进和变异算子与模拟退火思想的结合，来扩 大搜索区域，避免陷入局部最优解区域而产生早熟收敛。进化搜索算子和选择 算子的应用使得算法在后期迭代中的收敛速度有所提高，并且提高了解的精度。 3 、实数编码的应用能够避免二进制编码的精度不足和h a m m i n g 悬崖等缺 点，应用其对混合离散变量进行处理，能够解决传统方法中优化解的精度低及 圆整所带来的误差问题。 4 、综合遗传算法、模拟退火算法和进化策略的优点，构造了进化类混合算 法，并用实例验证了该混合算法能较好地解决桥门式起重机结构优化等工程混 合离散变量问题。 | | 。一一j 西南交通大学硕士研究生学位论文第1 页 1 1 课题研究的背景 第1 章绪论 由于钢铁、机械制造生产业和铁路、港口交通运输业的增长需求，促进了起 重机运输机械的发展，对起重机运输机械的性能也提出了更高的要求。现代起 重运输机械担当着繁重的物料搬运任务，是工厂，铁路、港口及其他部门实现 物料搬运机械化的关键“1 。起重运输机械对于提高生产力、保证产品质量、减轻 劳动强度、降低生产成本、提高运输效率、加快物资周转和流通等方面均有着 重要的影响，因而起重机设计计算的方法需不断地充实、完善，使设计的起重 机更符合实际使用的要求，更注重功能性、经济性和可靠性。 传统的起重机设计方法是由古典力学和数学为基础的半理论、半经验设计 法、类比法和直觉法等。随着科学技术的快速发展，形成了一些现代设计方法， 如：极限状态设计、优化设计、有限元法、可靠性设计、计算机辅助设计和疲 劳设计等，使起重机设计进入创新、高质量、高效率的新阶段咖。随着工业生 产的发展，起重机金属结构采用电子计算机辅助设计的优化方法越来越普及。 优化方法是保证结构尺寸合理、减轻自重，提高工作效率的一种有效方法。 随着科学技术的飞速发展，各个学科之间的交叉应用也日益显著。在传统优 化方法的基础上，借助生物学和物理学等产生了一些现代智能优化方法：禁忌 搜索算法、遗传算法、人工神经网络、进化策略和模拟退火算法等。这些智能 算法各有特点，并且在不同的应用领域发挥了巨大的作用，成为现代优化领域 中的研究热门。 本论文针对起重机金属结构变量为混合离散变量的情况，在现代智能优化方 法的基础上，根据单个优化方法的优缺点，进行取长补短，提出了一种基于进 西南交通大学硕士研究生学位论文第2 页 化类混合算法的优化方法，目的在于解决工程实践中遇到的混合离散变量优化 问题。 1 2 国内外的研究现状 1 2 1 起重机研究现状 1 、国内发展现状 我国起重运输机械制造业是随着共和国的建立才奠基发展起来的，经过五十 多年，特别是近十几年的飞跃发展，已具有一定的规模和水平，基本形成了较 为完整的科研、生产体系，成为机械工业中的一个独立的行业。并且能为国内 各部门提供多种多样的起重运输机械产品，能独立或通过国际合作为国家重点 工程提供所需的大型成套设备，并有一定的出口量。 我国起重运输机械主要应用在以下几个国家重点支持的基础工业和作为国 民经济支柱的产业：煤炭工业、电力工业、交通运输业、原材料工业和机械制 造业等嘲。在设计方法上，不再单纯依赖根据理论力学和材料力学形成的半理论、 半经验的传统设计方法，而是将有限元法、断裂力学、边界元法、优化设计法、 可靠性设计和疲劳设计等现代设计方法应用到起重机设计之中。现代设计方法 的应用使得起重机的研发进入了崭新的高质、高效的新阶段。 2 、国外发展现状嘲 世界市场对起重运输机械的需求量正在不断增加。由于工业生产自动化程度 的提高和生产规模的不断扩大，以及产品生产过程中物料装卸搬运费用所占的 比例不断增加，迫使企业在生产中更多地采用大型化、高效率、自动化的起重 运输机械设备。德国是世界上最大的起重运输机械出口国，位居日本和美国之 前，其起重运输机械的总产值位居机械制造业各类产品的首位。日本起重运输 西南交通大学硕士研究生学位论文第3 页 机械的技术已达到世界先进水平，目前日本制造起重机械及其零部件的企业约 有1 2 0 0 家美国也是生产起重运输机械的大国，目前有近1 5 0 0 家企业，9 万从 业人员，年产值约1 2 0 亿美元。 起重机在技术发展方面的主要趋势有以下几点： 向大型化、高效率化、无保养化和节能化发展。 随着科学技术的进步，自动化程度的提高，生产规模的扩大，相应要求部分 起重运输机械向大型化发展，并且对生产效率和能耗提出更高的要求。 向自动化、智能化、集成化和信息化发展。 将机械技术和电子技术相结合，将先进的微电子技术、电力电子技术、光缆 技术、液压技术、模糊控制技术应用到机械的驱动和控制系统，实现自动化和 智能化，以适应多批次少批量的柔性生产模式。 向成套化、系统化，综合化和规模化发展。 将各种起重运输机械的单机组合为成套系统，加强生产设备与物料搬运机械 的有机结合，提高自动化程度，改善人机系统。通过计算机模拟与仿真，寻求 参数与机种的最佳匹配与组合，发挥最佳效用。 向模块化、组合化、系列化和通用化发展。 许多通用起重运输机械是成系列成批量的产品，为了降低制造成本，提高通 用化程度，可采用模块化组合的方式，用较少规格数量的零部件和各种模块组 成多品种和多用途的系列产品，充分满足各类用户的需要。也可使单件小批量 生产起重运输机械的方式改换成具有相当批量和规模的模块化生产，实现高效 率的专业化生产。 向小型化、轻型化、简易化和多样化发展。 西南交通大学硕士研究生学位论文第4 页 有相当批量的起重运输机械是在一般的车间和仓库等处使用，用于代替人力 和提高生产效率，但工作并不十分频繁。为了考虑综合效益，要求这部分起重 运输机械尽量减少外形尺寸，简化结构，降低造价和使用维修费用。 采用新理论、新方法、新技术和新手段来提高设计质量 进一步应用计算机技术，不断提高产品的设计水平和精度。开展对起重运输 机械载荷变化规律、动态特性和疲劳特性的研究，开展对可靠性的试验研究， 全面采用极限状态设计法、概率设计法、优化设计、可靠性设计等，利用c a d 提高设计效率与质量，与计算机辅助制造系统相衔接，实现产品设计与制造一 体化。 采用新结构、新部件、新材料和新工艺提高产品性能 结构方面采用新薄壁型材和异型钢，减少结构的拼接焊缝，采用各种高强度 低合金钢新材料，提高承载能力，改善受力条件，减轻自重和增加外形美观。 在机构方面进一步开发新型传动零部件，简化机构，以焊代铸，采用机电一体 化技术，提高使用性能和可靠性。在电控方面开发性能好、成本低、可靠性高 的调速系统和电控系统。 1 2 2 现代智能优化算法研究现状 1 、遗传算法的研究现状 遗传算法( g e n e t i c a l g o r i t h m ，简称g n ) 由美国m i c h i g a n 大学h o l l a n d 于1 9 7 5 年首先提出，是模拟达尔文的遗传选择和自然淘汰的生物进化论的基础上发展 起来的计算模型。 a d a p t a t i o n i nn a t u r a la n da r t i f i c i a ls y s t e m ( h o l l a n d 。1 9 7 5 ) 一书的问世标志着遗传算法的诞生。g o l d b e r g 博士的专著g e n e t i c a l g o r i t h m si n s 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 ) ( g o l d b e r g , 1 9 8 9 ) 是g a 发展中的又一 个里程碑，标志蓑遗传算法在工程实际中得到了应用州”。进入2 0 世纪9 0 年代， 西南交通大学硕士研究生学位论文第5 页 遗传算法迎来了自己快速发展时期。在这1 0 年之中，遗传算法的研究取得了许 多令人瞩目的成果。在理论研究领域，人们提出了一系列新型的改进技术和方 法，如各种改进的编码方法、遗传算子、多种群协同进化的分层遗传算法、 e s h e l m a n 于1 9 9 1 年提出的c h c 算法、s r i n v i v a s 于1 9 9 4 年提出的自适应遗传算 法、基于小生境的遗传算法、以及混合遗传算法、并行遗传算法和多目标遗传 算法等。在应用研究领域，据不完全统计，遗传算法已经在函数优化、组合优 化、生产调度、自动控制、结构优化、图像处理、模式识别、机器学习、数据 挖掘、遗传编程、人工智能与人工生命、管理决策以及物理技术、生物技术、 化学工程和系统仿真等2 0 多个领域中得到应用。 我国关于遗传算法的研究，是从2 0 世纪9 0 年代开始的。近几年来，随着我 国经济条件和科研环境的不断改善，越来越多的人都开始从事这方面的研究。 遗传算法的发展呈现了快速上升的势头，其不论是在数量方面还是在质量方面 都出现了质的飞跃。其中在专著方面的代表是科学出版社的遗传算法的基本 理论与应用、西安交通大学出版的遗传算法理论、应用与软件实现、机械 出版社的机械优化设计遗传算法和清华大学出版的遗传算法与工程优化 等，这些优秀的文献资料，将为我国遗传算法的迸一步发展奠定坚实的基础。 从遗传算法的这个发展过程来看，2 0 世纪7 0 年代是兴起阶段，2 0 世纪8 0 年代是发展阶段，2 0 世纪9 0 年代是高潮阶段。现今，遗传算法正在逐渐地发展 成为一套完善的理论体系，其实用性广、全局搜索、鲁棒性强和易于实现的优 化技术，必将引起国内外新一轮的研究热潮。 2 、模拟退火算法的研究现状 1 9 8 2 年，k i r p a t d c k 等首先意识到固体退火过程与组合优化问题之间存在的 类似性，m e t r o p o l i s 等对固体在恒定温度下达到热平衡过程的模拟也给他们以启 迪：把m e t r o p o l i s 接受准则引入到优化过程中来。最终他们得到一种对m e t r o p o l i s 算法进行迭代的组合优化算法，这种算法模拟固体退火过程，称之为“模拟退 西南交通大学硕士研究生学位论文第6 页 火算法”( s i m u l a t e da n n e a l i n g , 简称s 砧。k i r p a t r i c k ，g d a t tj r 和v e c e h i 等人首 先出版了关于模拟退火算法的研究成果，其次是h a s m i n s k i j 继续在前人的基础 上进行研究。早期大多数最优化问题都是有限区域进行求解，后来k u s h n e r 、 g e l f a n d 和m i t t e r 在无限区域内进行函数优化，并获得了优异的成果“”；由于传 统的模拟退火算法在收敛速度上有很大的缺陷，因此许多学者都开始对其进行 改进。张霖斌等在文献【l l 】中以广义b o l t z m a n - o i b b s 统计理论为基础，采用 依赖于温度的似c a u c h y 分布产生新的扰动模型，建立一种新的快速模拟退火算 法。王雅琳等在文献【l z 中分别采用变异操作和扩大搜索空间的方法，对一 种单循环模拟退火算法予以改进，并用于工业应用之中。向阳等在文献【1 3 中介绍了一种推广模拟退火算法。i & m a l h s a h i n 等在文献【1 4 中提出了一种 双温度模拟退火算法，并将其应用在双层规划问题上。h o n g y e 等在文献【i s 中提出了一种通过平行坐标来加速搜索的加速模拟退火算法。由于模拟退火算 法在理论上能够收敛到全局最优解，所以对改进算法的研究才更有实际意义， 众多学者正在努力钻研将其一般化，使其具有普遍适用性。 3 、进化策略的研究现状 2 0 世纪6 0 年代初，柏林工业大学的学生i r e c h e n b e r g 和h p 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 ) 。早期的e s 的种群中只包含一个个体，而 且只使用变异操作，所使用的变异算子是基于正态分布的变异操作。s c h w e f e l 于1 9 7 7 年提出了( 弘+ a ) 一e s 和( 肛，a ) 一e s ，并引进了交叉操作，使得e s 在非 线性函数的优化问题应用上有了进一步的发展m 1 。 西南交通大学硕士研究生学位论文第7 页 1 3 论文研究的主要内容 本论文为解决桥门式起重机设计专家的结构优化问题而提出的，在分析已 有传统优化算法在解决工程实际问题中遇到的圆整后不满足要求，以及收敛精 度不高等缺点的基础上，应用现代智能优化算法：遗传算法、模拟退火算法和 进化策略三种算法，通过合理的集成，实现三种算法之间的互补，从而形成一 种进化类混合算法。经测试函数和实际工程验证，该算法能够解决实际工程优 化问题，是一种高效、可靠的优化算法。 论文研究的主要内容： l 、对遗传算法、模拟退火算法和进化策略的基本原理和特点进行分析，根 据各算法的特点提出一些改进方法。 2 、。对混合离散变量中遇到的连续变量、整数变量和离散交量分别进行数据 处理。 3 、针对遗传算法中各算子的特点，分别对其进行相应的改进，使得其算子 的功能更加突出。 4 、以构成混合算法基本原则为基础，以遗传算法为总体框架，将模拟退火 算法和进化策略的优点引入到算法之中，构成进化类混合算法。 5 、用测试函数对进化类混合算法进行测试，证明算法的实用性和可靠性。 分别在桥门式起重机金属结构优化中应用该算法，验证其解决工程混合离散变 量问题的能力。 西南交通大学硕士研究生学位论文第8 页 第2 章智能优化算法 本章主要介绍遗传算法、模拟退火算法和进化策略三种智能优化算法的基本 原理和特点，并对现有的算法改进进行总结，为进化类混合算法的实现做准备。 以上三种算法都是目前优化领域应用比较广泛的，且较成熟和有效的算法。这 些算法都是模拟自然界的某些现象进行大规模优化问题的随机性方法，三种算 法都不要求目标函数的连续性、可微性及凸性，而且算法简单，易于实现。 2 1 遗传算法( g 砷 2 1 1 遗传算法的基本原理 许多难解的工程优化问题都可归结为约束优化或组合优化问题，遗传算法作 为一种新的优化技术己经受到广泛的关注。遗传算法在求解无约束优化、线性 规划、随机规划，目标规划以及区间规划等问题中广泛应用。遗传算法可以处 理任意形式的目标函数和约束，无论是线性的还是非线性的，离散的还是连续 的，甚至混合的搜索空间。在解决组合优化问题中，有背包问题、最小支撑树 问题、路径寻优问题、旅行商问题，以及影片递送问题等应用实例。另外在生 产调度问题、机器人智能控制、图象处理和模式识别、机器学习等领域也得到 了成功应用1 。 遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法。遗传算法是 一种宏观意义下的仿生算法，它模仿的机制是一切生命和智能的产生与进化过 程。它通过模拟达尔文“优胜劣汰、适者生存”的原理鼓励产生好的结构，通 过模仿盂德尔遗传变异理论在迭代过程中保持已有的结构，同时寻找更好的结 构。作为一种随机优化与搜索算法，遗传算法只使用适值函数信息，而不使用 西南交通大学硕士研究生学位论文第9 页 导数或其他辅助知识。和传统搜索算法不同，遗传算法从一组随机产生的初始 解，称为“种群( p o p u l a t i o n ) ”，开始搜索过程。种群中的每个个体是问题的一 个解，称为“染色体( c h r o m o s o m e ) ”。染色体是由代表问题的各个变量，称为 “基因( g e n e ) ”，有规律排列构成的，它构成生物在微观的分子层次上的基因型 ( o e n o t y p e ) ，而基因型在环境中呈现的形状成为该生物的表现型( p h e n o t y p e ) 。 遗传和进化发生在染色体上，在每一代中用适应度值( f i t n e s s ) 来测量染色体的 好坏。生成的下一代染色体称为“子代( o 簋s p d n g ) ”。后代是由前一代染色体通 过交叉( c r o s s o v e r ) 、变异( m u t a t i o n ) 或其他高级运算形成的。在形成的新一代群 体中，根据适值的大小选择较优的后代，淘汰较差的后代，从而保持种群规模 是不变化这样经过若干代之后，算法收敛于最好的染色体，它很可能就是问 题的最优解或次优解。 遗传算法在整个进化过程中的遗传操作是随机性的，但它所呈现出的特性并 不是完全随机搜索，它能有效地利用历史信息来推测下一代期望性能有所提高 的寻优点集。这样一代代地不断进化，最后收敛到一个最适应环境的个体上， 求得问题的最优解。 遗传算法的运行过程为一个典型的迭代过程，其必须完成的工作内容和基本 步骤如下“日： l 、选择编码策略，把参数集合z 和区域转换为位串结构空间西； 2 、定义适应值函数f ( x 1 ； 3 、确定遗传策略，包括选择群体大小p o p s i z e ，选择、交叉、变异方法，以 及确定交叉概率、变异概率己等遗传参数； 4 、随机初始化生成群体m ； 5 、计算群体中个体位串解码后的适应值f ( x 1 ； 6 、按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群 体； 7 、判断群体性能是否满足某一指标，或者已完成预定迭代次数，不满足则 西南交通大学硕士研究生学位论文第1 0 页 返回步骤6 ，或者修改遗传策略再返回步骤6 。 2 1 2 遗传算法与传统优化算法的区别 遗传算法模拟生物进化机制，采用群体搜索和个体问信息交换，思想新颖独 特，方法和技术别开生面。与传统的优化算法相比具有许多不同之处，主要体 现在下述方面： 1 、遗传算法的处理对象不是参数变量本身，而是参变量编码后的染色体串 这使得遗传算法可以解决非常广泛的问题。 2 、遗传算法同时处理群体中的多个个体，也就是同时搜索解空间中的一群 点，如象在解空间撒网一样，可以对不同区域进行采样，并不断交换彼此信息。 3 、遗传算法对搜索空间没有任何特殊要求( 如连续、凸性) ；对目标函数几 乎无限制，不要求连续可微，仅要求可用适应度函数评价个体。这就使得遗传 算法的应用领域更加扩宽了。 4 、遗传算法采用概率转移规则而非确定性规则来指导其搜索过程，看似盲 目，实则采用概率这一个工具引导搜索过程向着更优解的区域移动，比随机搜 索方法有更高的搜索效率。 5 、遗传算法具有自组织、自适应等智能特性。应用遗传算法求解问题时， 只需根据问题确定适应度函数，遗传操作算子就能利用进化过程中获得的信息 自行组织搜索，就可能产生更能适应问题环境的后代。遗传算法的这种自组织、 自适应的智能特性赋予了它自动发现环境特性和规律的能力。 6 、遗传算法具有隐含并行性，遗传算法虽然每次只执行与群体规模成比例 的计算，实际上却处理了大量的模式。另外，它也易于采用并行机作并行高速 运算，对并行系统结构没有什么限制，发展潜力很大。 7 、遗传算法具有多解性。遗传算法采用群体搜索策略，并构成不断进化的 群体系列。最后结果中，不但得到最优解，还能提供一些较优解。 由上述可知，遗传算法具有独特的鲁棒性、自适应性、全局优化性和隐含并 西南交通大学硕士研究生学位语文第1 1 页 行性。 2 1 3 传统遗传算法存在的问题 随着科技的发展和工程问题范围的拓宽，问题的规模和复杂度越来越大，传 统单一算法的优化结果往往不够理想，难以达到要求。遗传算法作为一种智能 化的全局搜索算法，自2 0 世纪8 0 年代问世以来就在数值优化、智能控制、机 构优化设计、参数辩识等诸多领域的应用中展现出其特有的魅力，同时也暴露 出许多不足和缺陷。主要体现在以下几个方面： 1 、“早熟收敛”问题。这一问题是由于传统遗传算法的单一进化模式( “复 制一交叉一变异”) 和按适应性选择的方法，使适应值高的个体在下一代中有较高 的存活，因此种群很快趋近于一个局部区域，而由于“遗传漂移”使得该局部 区域不一定是包含最优解。从理论上讲，遗传算法收敛到全局最优解的关键就 是要一定程度上保持种群内性状的多样性。针对早熟问题不少学者也都作过相 关的研究，如g o l d b e r g ( 1 9 8 9 ) 提出使用共享算子，d ej o n g 于1 9 7 5 年提出了 c r o w d i n g 方法，m a h f o u d 予1 9 9 2 年对共享方法中的遗传漂移进行了讨论，1 9 9 4 年m a h f o u d 又对c r o w d i n g 方法进行了改进形成d c ( d e c i s i v ec r o w d i n g ) 算予， 徐川育在文献【1 8 1 中针对变型标准遗传算法的早熟问题提出了一种有效的混 合方法，李书全等在文献【1 9 】中应用一种自适应交叉和变异算子来防止遗传 算法早熟收敛。 2 、计算量大、精度不高。由于传统的遗传算法采用二进制编码方式，它需 要大量的操作进行编码和解码，所以大大地增加了计算量。而二进制编码的精 度依赖于位串的长度，所以对大规模多变量优化问题，由于位串长度的有限而 使计算精度不高。针对计算量大的问题，主要是通过改进遗传编码方法来减少 大量的编码和解码操作耗费的计算时间；而对精度不高的问题，广泛应用的方 法是使用实数编码方法。 3 、全局搜索能力强而局部搜索能力较差。具体表现为遗传算法可以用极快 西南交通大学硕士研究生学位论文第1 2 页 的速度搜索到最优解附近，但要进一步达到最优解则速度极慢。为克服该缺点， 张有富等在文献1 2 0 1 中提出了一种改进的实码加速遗传算法，该算法通过对 实码加速遗传算法的局部参数进行改进，再对最后一次加速收缩后的区间用标 准遗传算法进行精细搜索来实现加速。 4 、对搜索空间变换的适应能力差。当搜索空间增大时，基本遗传算法需急 剧扩大种群规模以实现全局搜索，从而极大的增加了计算量，不仅影响了算法 效率，而且阻碍了遗传算法在工程实践中的应用。 上述缺陷是传统遗传算法在解决优化问题时普遍存在的，改进遗传算法的这 些缺点，一直是遗传算法应用者所研究的重点。 2 1 4 遗传算法的改进 自从1 9 7 5 年h o l l a n d 系统地提出遗传算法的完整结构和理论以来，众多学 者一直致力于推动遗传算法的发展，对编码方式、控制参数的确定、选择方式 和交叉机理等进行了深入的探究，引入了动态策略和自适应策略以改善遗传算 法的性能，提出了各种变形的遗传算法。近几年比较典型的改进遗传算法有： 刘耀儒等在1 2 1 】中采用基于小生境技术与自适应杂交变异概率方法的改进遗 传算法，以解决简单遗传算法的早熟收敛问题。韩喜君等在文献1 2 2 中通过 对排样问题已知解信息进行统计分析，并根据分析结果改进原遗传算法判断个 体好坏的标准，对父代种群进行了优劣分类，针对不同的分类应用不同的遗传 操作，构造了一种改进遗传算法。言宇等在文献【2 3 】中对传统遗传算法的遗 传算子和终止判据等方面进行了改进，使算法计算效率和全局寻优能力均有提 高。何绍武等在文献1 2 4 1 中改进了标准遗传算法的算法参数，采用了最优保 存策略，并运用退火罚函数法处理约束，从而提高算法的全局寻优能力和稳定 性。金觉新等在文献 2 5 1 中将b p 神经网络引入遗传算法之中，构造了一种混 合遗传算法，该算法不仅避免了遗传算法的未成熟收敛和b p 算法易于陷入局部 最优的缺点，而且还大大加快了算法收敛的速度，能获得满意的结果。高龙士 西南交通大学硕士研究生学位论文第1 3 页 等在文献1 2 6 1 中将混合编码策略引入遗传算法中，解决了二进制编码存在的 一些缺陷。另外还有一些遗传算法和模拟退火算法、三等分割算法阗等其他 算法相结合的混合算法。 总之，遗传算法从诞生起发展到现今，不管是在理论还是在实践应用中都 取得了可喜的成绩，但是遗传算法的发展并没有停止不前，因为它并不是尽善 尽美的。因此各种改进层出不穷，总结起来大致从以下方面进行改进：改变 遗传算法的组成成分或使用技术；采用混合遗传算法；采用动态自适应技 术，在进化过程中调整算法控制参数和编码粒度；采用非标准的遗传操作算 子；采用并行遗传算法。 2 2 模拟退火算法( s a ) 模拟退火算法是近年来特别引人注目的一种适应于解大型组合优化问题的 技术，算法的核心在于模仿热力学中固体的退火过程。固体退火是指将固体材 料加热到某一高温状态，然后让其慢慢冷却到常温的这一热处理过程。从统计 热力学的观点来说，随着温度的降低，物质的能量将逐渐趋近于一个较低状态， 并最终达到某种平衡。基于固体退火的机理，1 9 8 2 年，k i r k p a t r i c k 等将退火思 想引入组合优化领域，提出了一种解大规模组合优化问题，特别是n p 完全组合 优化问题的有效近似算法一模拟退火算法。它源于对固体退火过程的模拟，在算 法中采用m e t r o p o l i s 接受准则，并用一组称为冷却进度表的参数控制算法过程， 使算法在多项式时间里给出一个近似最优解。 2 2 1 模拟退火算法基本思想嘲 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却， 加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋 有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。用 西南交通大学硕士研究生学位论文第1 4 页 固体退火模拟组合优化问题，将内能e 模拟为目标函数值f ，温度z 演化为控 制参数t ，即得到解组合优化问题的模拟退火算法：由初始解s 控制参数初值毛 开始，对当前解重复“产生新解一计算评价函数差值一接受或舍弃”的迭代， 并逐步衰减t 值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗 迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表( c o o l i n g s c h e d u l e ) 控制，包括控制参数的初始温度值及其衰减函数、终止温度和m a r k o v 链的长度。 模拟退火算法运行的基本步骤为； 1 、初始化：初始温度r ( 足够大) ，初始解的状态s ( 是算法迭代的起点) ，每 个r 值的迭代次数l ； 2 、对k - 1 2 ，“j 工做第3 至第6 步： 3 、产生新解s ； 4 、计算增量a c - c c s ) 一c ( s ) ，其中c ( s ) 为评价函数； 5 、若a c t 0 则接受s 作为新的当前解，否则以概率e x p ( a c r ) 接受s 作为 新的当前解。 6 、如果满足终止条件则输出当前解为最优解，结束程序。终止条件通常取 为连续若干个新解都没有被接受时终止算法。 7 、r 逐渐减少，且r 一0 ，然后转第2 步。 2 2 2 模拟退火算法的特点 模拟退火算法的主要优点是：不用求目标函数的偏导数及解大型矩阵方程 组，既能找到全局最优解，又易于加入约束条件。但是由于该算法在每一个温 度下都要在给定解的周围不断搜索若干次，直到满足条件为止，因此它的最大缺 点也就是计算效率偏低，所以怎么权衡优化质量和优化效率的关系并提高其质 量和效率都是对s a 进行改进的主要内容。 西南交通大学硕士研究生学位论文第1 5 页 2 2 3 模拟退火算法的改进 在确保一定优化质量要求的基础上，提高模拟退火的搜索效率( 时间性能) ， 是对s a 算法进行改进的主要内容。可行的方案包括： l 、设计合适的状态产生函数，使其根据搜索进程的需要表现出状态的全空间 分散性或局部区域性； 2 、设计高效的退火历程； 3 、避免状态的迂回搜索； 4 、采用并行搜索结构； 5 、为避免陷入局部极小，改进对温度的控制方式； 6 、选择合适的初始状态； 7 、设计合适的算法终止准则。 此外，对模拟退火算法的改进，也可通过增加某些环节而实现。主要的改进 方式包括： l 、增加升温或重升温过程。在算法进程的适当时机，将温度适当提高，从 而可激活各状态的接受概率，以调整搜索进程中的当前状态，避免算法在局部 极小解处停滞不前。 2 、增加记忆功能。为避免搜索进程中由于执行概率接受环节而遗失当前遇 到的最优解，可通过增加存储环节，将“b e s ts of a r ”的状态记忆下来。 3 、增加补充搜索进程。即在退火进程结束后，以搜索到的最优解为初始状 态，再次执行模拟退火过程或局部趋化性搜索。 4 、对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态， 而非标准s a 的单次比较方式。 5 、结合其他搜索机制的算法，如遗传算法，混沌搜索等。 6 、上述各方法的综合应用。 西南交通大学硕士研究生学位论文第1 6 页 2 。3 进化策略( e s ) 2 3 1 进化策略的原理 进化策略是以实数表达问题的进化算法。进化策略具有两种基本形式 似，s t ) 一e s 和似+ a ) 一e s 。似+ a ) 一e s 采用含有肛个个体的群体作为父代群体， 由它们通过重组和变异产生a 个新个体，由+ a 个个体择优选择芦个个体作为 下一代群体。( 弘，a ) 一醪从a 个新个体中选择p 个个体作为下一代，要求a ，p 。 近年来( ，a ) 一层s 得到广泛的应用，它的每个个体的寿命只有一代，更新进化很 快，特别适合于目标函数由噪声干扰或优化程度明显受迭代次数影响的问题。 概括地说，进化策略的工作步骤是： l 、确定问题的表达方式； 2 、随机生成初始群体，并计算其适应度； 3 、根据进化策略，产生新的个体； 重组：将两个父代个体交换目标变量和控制因子，产生新个体； 突变：对重组的个体添加随机量，产生新个体并计算其适应度； 选择：选择优良个体组成下一代群体； 4 、反复执行3 ，直至达到终止条件，选择最佳