（计算机应用技术专业论文）改进分层遗传算法在车间智能蓝牙贴片中的应用.pdf

摘要 摘要 智能制造系统是是当今研究的热点之一，相比传统制造系统可以通过利用智能制造 技术、多代理技术( a g e n t ) 以及无线通信蓝牙技术等多种技术来解决全局优化问题、面 向生产任务的动态配置优化、实时响应问题、快速适应环境变化等问题。 车间调度问题来源于不同的领域，如柔性制造系统，生产计划，计算机技术，后勤 及通信等，这些问题的共同特性是没有一个有效的算法能在多项式时间内求出其最优 解。作为处于制造系统的底层位置的车间，是制造业最基本组织单位和制造过程的执行 单元，它的合理有效运行将极大影响整个制造系统的效率。 因此，加紧对智能车间制造系统的研究是重要和迫切，加紧对智能制造系统的研究 能解决在传统制造系统中出现的一些难以解决的问题；能适应市场、环境、社会的发展； 能紧跟时代发展的步伐，能使我们的制造系统在激烈的竞争中立于不败之地。 本课题改进了一种新的分层遗传算法，并且结合蓝牙为车间管理系统设计一种新型 的贴片，以无线通信方式取代传统车间有线通信。 论文首先简介了智能车间调度的基本思想；其次研究分层遗传算法，发掘其较传统 遗传算法的优势；然后提出一种改进分层遗传算法，将该算法用于解决智能车间调度中 的资源分配问题，避免了传统遗传算法常见的早熟收敛问题；最后设计一种适用于车间 管理系统的蓝牙贴片，实现其无线传输基本功能，并在p c 机上进行模拟。 关键词：智能控制；车间调度；分层遗传算法；蓝牙 大连交通人! 掌1 7 7 硕十何论文 a b s t r a c t t h ei n t e l l i g e n tm a n u f a c t u r es y s t e mi so n ew h i c ho fh o ts p o t si ss t u d i e sn o w , c o m p a r e s t h et r a d i t i o n a lm a n u f a c t u r es y s t e mt ob ep o s s i b l et h r o u g hu s i n gt h ei n t e l l i g e n c et e c h n i q u eo f m a n u f a c t u r e ，t h em u l t i p r o x yt e c h n o l o g y ( a g e n t ) a sw e l la st h ew i r e l e s sc o m m u n i c a t i o nb l u e t o o t ht e c h n o l o g ya n ds oo nm a n yk i n d so ft e c h n o l o g i e ss o l v e st h eg l o b a l o p t i m i z a t i o n p r o b l e m ，t oo p t i m i z e ，q u e s t i o n sa n ds o o nr e a l - t i m er e s p o n s eq u e s t i o n ，f a s ta d a p t a t i o n e n v i r o n m e n t a lv a r i a t i o nf a c et h ep r o d u c t i o nt a s kd y n a m i cd i s p o s i t i o n t h ew o r k s h o ps c h e d u l i n gp r o b l e mo r i g i n a t e sf r o mt h ed i f f e r e n td o m a i n ，l i k et h ef l e x i b l e m a n u f a c t u r es y s t e m ，t h ep r o d u c t i v ep l a n ，t h ec o m p u t e rt e c h n o l o g y , t h er e a l s e r v i c ea n dt h e c o r r e s p o n d e n c ea n ds oo n ，t h e s eq u e s t i o n sc o m m o nc h a r a c t e r i s t i cd o e sn o th a v ea l le f f e c t i v e a l g o r i t h mt ob ea b l e t oe x t r a c ti t so p t i m a ls o l u t i o ni nt h em u l t i n o r n i a lt i m e a si si nt h e m a n u f a c t u r es y s t e m sf i r s tf l o o rp o s i t i o nw o r k s h o p ，i sm a n u f a c t u r i n gi n d u s t r ym o s tp r i m a r y t i s s u eu n i ta n dt h ep r o c e s so fm a n u f a c t u r ee x e c u t i o nu n i t ，i t sr e a s o n a b l ee f f e c t i v em o v e m e n t w i l la f f e c tt h ee n t i r em a n u f a c t u r es y s t e m se f f i c i e n c ye n o r m o u s l y s ot h ep r o b l e mw h i c ht h e r e f o r e ，s t e p su pt ot h ei n t e l l i g e n c es h o pf a b r i c a t i o ns y s t e m s r e s e a r c hi si m p o r t a n ta n di su r g e n t ，s t e p su pt ot h ei n t e l l i g e n tm a n u f a c t u r es y s t e m sr e s e a r c ht o b ea b l et os o l v es o m ew h i c hi nt h et r a d i t i o n a lm a n u f a c t u r es y s t e mp r e s e n t sw i t hd i f f i c u l t yt o s o l v e ；c a na d a p tt h em a r k e t ，t h ee n v i r o n m e n t ，s o c i e t y sd e v e l o p m e n t ；c a nf o l l o wc l o s eo nt h e t i m ed e v e l o p m e n tt h es t e p ，c a nc a u s eo u rm a n u f a c t u r es y s t e mt ob ei na ni m p r e g n a b l e p o s i t i o ni nt h ek e e nc o m p e t i t i o n t h i st o p i ci m p r o v e do n ek i n do fn e wl a m i n a t i o ng e n e t i ca l g o r i t h m ，a n du n i f i e st h eb l u e t o o t hn e wt op a s t et h ep i e c ef o rt h es h o pm a n a g e m e n ts y s t e md e s i g no n ek i n d ，b yw i r e l e s s c o m m u n i c a t i o nw a ys u b s t i t u t i o nt r a d i t i o nw o r k s h o pl i n e - w i r ec o m m u n i c a t i o n t h e p a p e r h a sf i r s ti n t r o d u c e dt h ei n t e l l i g e n tw o r k s h o pd i s p a t c h e r sb a s i cp h i l o s o p h y ； n e x tr e s e a r c hl a m i n a t i o ng e n e t i ca l g o r i t h m ，e x c a v a t e si tt oc o m p a r et h et r a d i t i o ng e n e t i c a l g o r i t h mt h es u p e r i o r i t y ；t h e np r o p o s e dt h a to n ek i n do fi m p r o v e m e n t l a m i n a t i o ng e n e t i c a l g o r i t h m ，u s e si nt h i sa l g o r i t h ms o l v i n gi nt h ei n t e l l i g e n tw o r k s h o pd i s p a t c h e r sr e s o u r c e d i s t r i b u t i o nq u e s t i o n ，h a sa v o i d e dt h et r a d i t i o ng e n e t i ca l g o r i t h mc o n l m o np r e c o c i o u s r e s t r a i n i n gq u e s t i o n ；t h eu l t i m a t ed e s i g no n e k i n di ss u i t a b l ei nt h es h o pm a n a g e m e n t s y s t e m sb l u et o o t hp a s t e st h ep i e c e ，r e a l i z e si t sw i r e l e s st r a n s m i s s i o nb a s i cf u n c t i o n ，a n d c a r d e so nt h es i m u l a t i o no np cm a c h i n e k e yw o r d s ：i n t e l l i g e n tc o n t r o l ；w o r k s h o pc o n t r o l ；h 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 ； b l u e t o o t h i i 大连交通大学学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢及参考 文献的地方外，论文中不包含他人或集体已经发表或撰写过的研究成 果，也不包含为获得太董塞通太堂或其他教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意。 本人完全意识到本声明的法律效力，申请学位论文与资料若有不 实之处，由本人承担一切相关责任。 学位论文作者签名：彳泼豆畲钞 日期： o 口q ? 1 年，o 月哆日 大连交通大学学位论文版权使用授权书 本学位论文作者完全了解太整銮通太堂有关保护知识产权及保 留、使用学位论文的规定，即：研究生在校攻读学位期间论文工作的 知识产权单位属太整塞通盍堂一，本人保证毕业离校后，发表或使用 论文工作成果时署名单位仍然为太整塞通太堂。学校有权保留并向 国家有关部门或机构送交论文的复印件及其电子文档，允许论文被查 阅和借阅。 本人授权太蓬塞通太堂可以将学位论文的全部或部分内容编入 中国科学技术信息研究所中国学位论文全文数据库等相关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 、 又。 ( 保密的学位论文在解密后应遵守此规定) 学位论文作者始榭札锄始多j 0 日期：占p p 彦年o 月乒彦日日期：a 。乡年，j 月侈日 学位论文作者毕业后去向： 工作单位：电话： 通讯地址：邮编： 审子信箱： 绪论 绪论 1 课题研究背景 机械制造行业是一个国家国民经济的重要支柱和组成部分，随科学技术和社会生产 水平的提高其生产模式在不同阶段发生了巨大变化，其发展进步具有重要意义。伴随着 信息时代的到来，信息科学技术打破了传统的地域经济模式，并向着智能化、一体化方 向发展：知识技术产品的更新周期越来越短；产品的批量越来越小；顾客对产品性能 和质量的要求越来越高；品种趋于多样、个性化；市场环境多变不可预测等。在这种时 代要求下，快速响应市场、对变化及时做出反应同时满足低成本、高效率成为制造业发 展的主要方向。面临这样的形势学术界和企业界提出了诸如精良生产、敏捷制造，全球 制造、智能制造等多种新技术、方法、理念以提高企业生产的快速适应能力和竞争力。 在现代制造业领域中，制造理念、制造思想不断创新、不断更替，先后出现了柔性 制造系统、计算机集成制造系统、敏捷制造、智能制造系统o m s ) 0 - 2 j 以及其它各种先进 制造理念和模式。智能制造系统是当今一种新的制造理念，也是当今研究的热点之一。 那么，智能制造系统与传统制造系统的区别在于，智能制造系统能解决传统制造系统中 的一些无法解决的问题，传统制造系统存在着诸多的问题与弊端，比如说集中式控制系 统可靠性在很大程度上依赖于主控节点的运行状况及通信电缆的可靠性，一旦主控节点 及通信线路出故障，整个系统将全面瘫痪，还比如采用传统制造系统的一些方式与方法 很难解决车间控制系统的全局优化问题、面向生产任务的动态配置优化、实时响应问题、 快速适应环境变化的问题等等，而在智能制造系统中可以通过利用智能制造技术、多代 理技术( a g e n t ) 、无线通信技术以及等多种技术来解决这些问题。 生产调度是对企业的生产过程进行作业计划，即在满足某些约束( 例如作业的前后 关系，资源能力，成本最小化，产品纳期等) 的条件下对作业的优化排序，按照排序的 次序给作业分配时间和资源，使某个执行目标( 例如完成时间，成本等) 达到最优，以 追求企业的利益最大化。一个调度就是在各种制约条件下，在一定时间内各个作业在车 间现有设备上的一个分派。这是一项复杂的工作，也是一个n p ( n o n p o l y n o m i a l ) 问题， 无法用多项式求出其精确解。尽管调度问题已进行了大量的研究并取得了一定的成果， 但是，对于所有的生产作业问题都要得到最优解是困难的，甚至是不可能的，所以，求 解调度问题的优化调度算法一直以来仍然是调度研究的核心。 大连交通大学。r 学硕十学何论文 2 本文主要工作 近年来，遗传算法以及车间智能调度一直是各方研究重点。论文首先通过对分层算 法的研究、比较、分析，提出一种改进分层基于遗传算法调度方法解决作业车间生产调 度平台中出现的资源制约问题，此算法将对免疫遗传算法的初始解生成，信息素分布和 路径选择策略进行改进，生成一种新的分层遗传算法。同时，设计出一种适用于车间调 度的智能蓝牙贴片，结合改进的分层遗传算法，提高其搜索效率，明显提高生产效率。 这种混合策略的思想对企业的计算机化车间生产调度管理具有极其重要的意义。论 文理论密切联系实际，采用真实数据对新算法进行测试；并对新算法从理论和实际方面 进行评价。 本文的课题来源为辽宁省科学技术基金“大连市电子信息产品制造业发展专项资金 申请报告，该项目在研。 本文的主要工作为： 1 系统地研究车间调度理论及其发展状况，并加以概括总结； 2 深入分析遗传算法的基本原理、流程与实现，并对对收敛性，收敛速度进行估计。 并在此基础之上提出一种改进的分层遗传算法，与其他算法进行比较，证明其优越性； 3 将第2 章改进的分层遗传算法运用车间智能控制体系中。提出的新算法根据搜索 的历史信息，自适应的调整遗传过程中的遗传参数以提高算法的稳定和效率，提高算法 的局部搜索能力和解的质量；免疫反馈和免疫选择能淘汰相似个体，维持种群的多样性， 避免算法陷入早熟，改善算法的性能和稳定性。最后在部分柔性和全柔性情况下与其他 算法进行比较。 4 设计并实现了一个多智能体车间调度平台，完成了系统的建模、概要设计、详细 设计、算法设计及软件开发工作，并用真实数据测试其可靠性。 2 第一章智能车间调度研究 第一章智能车间调度研究 1 1 引言 在现代制造业领域中，先后出现了柔性制造系统、计算机集成制造系统、敏捷制造、 智能制造系统( i n t e l l i g e n tm a n u f a c t u r i n gs y s t e m ，i m s ) f l - 2 1 以及其它各种先进制造理念和 模式。智能制造系统是当今一种新的制造理念，也是当今研究的热点之一。 智能制造系统与传统制造系统的区别在于，智能制造系统能解决传统制造系统中的 一些无法解决的问题，传统制造系统存在着诸多的问题与弊端，比如说集中式控制系统 可靠性在很大程度上依赖于主控节点的运行状况及通信电缆的可靠性，一旦主控节点及 通信线路出故障，整个系统将全面瘫痪，还比如采用传统制造系统的一些方式与方法很 难解决车间控制系统的全局优化问题、面向生产任务的动态配置优化、实时响应问题、 快速适应环境变化的问题等等，而在智能制造系统中可以通过利用智能制造技术、多代 理技术( a g e n t ) 以及无线通信蓝牙技术等多种技术来解决这些问题。 ，。 车间调度问题来源于不同的领域，如柔性制造系统，生产计划，计算机技术，后勤 及通信等，这些问题的共同特性是没有一个有效的算法能在多项式时间内求出其最优 解。古典的作业车间调度问题是最著名的机器调度问题之一。问题可以描述为：j 给定一 个工件的集合和一个机器的集合，每个工件包括多道工序，每道工序需要在一台给定的 机器上非间断地加工某一段时间；每台机器一次最多只能加工一道工序；调度就是把工 序分配给机器上某个时间段。问题的目标是找到最小时间长度的调度。在过去的3 0 年 里，机器调度问题吸引了无数个研究者的浓厚兴趣，大量的研究成果相继问世，其中包 括m u t h 和n o m p s o n 3 l ，c o n w a v 掣4 1 ，b a k e r l 5 1 ，f r e n c h 6 1 ，r i n n o o yk a n l 7 1 ，c o f f m a n i s l ， b l a z e w i c z 掣8 l 的著作，以及m o r t o n 和p e n t i c o 的最新著作【9 1 。 因此，加紧对智能车间制造系统的研究是重要和迫切，加紧对智能制造系统的研究 能解决在传统制造系统中出现的一些难以解决的问题；能适应市场、环境、社会的发展； 能紧跟时代发展的步伐，能使我们的制造系统在激烈的竞争中立于不败之地。 1 2 车间控制体系 1 2 1 几种车间控制系统介绍 ( 1 ) 智能制造( i n t e l l i g e n tm a n u f a c t u r i n g ) 所谓智能制造是在制造生产的各个环节中，以种柔性和集成的方式，应用智能制 造技术和智能制造系统进行制造的生产模式，其本质上是一个分布与并行式的制造问题 3 人连交通大学丁学硕十学位论文 协同求解系统。它综合了制造技术、自动化技术、系统工程与人工智能等学科内容，通 过计算机模拟人类专家的智能活动，进行诸如分析、推理、判断，旨在取代或延伸制造 环境中人的部分脑力劳动，并对人类专家的制造智能进行收集、存储、完善、共享、继 承和发展，以实现制造过程的优化，实现一种能融合过去总是被孤立对待的特性( 市场 适应性、经济性、人的重要性、私营自然和社会环境的能力、开放性和兼容能力) 的生 产系统【1 0 l 。 ( 2 ) 精良生产( l e a np r o d u c t i o n ) 精良生产由日本丰田汽车公司的创造。精良生产模式以整体为观点，以社会需求为 依据，以发挥人的因素为根本来有效配置合理使用资源。其实质是在产品开发、生产过 程中，通过项目组和生产小组把各方面的人集成在一起，简化产品开发、生产、销售过 程及组织结构，最大限度的精简以获取最大利益并获取最大的用户满意度。它将近2 0 年出现的先进技术和思想集成化、系统化和理论化，其主要模式有：全面质量管理、准 时化和自动化、并行工成、成组单元以及人的因素。 ( 3 ) 敏捷制造( a g i l em a n u f a c t u r i n g ) 1 1 1 j 敏捷制造a m 是1 9 8 8 年由美国通用汽车公司( g m ) 与美国海里( l e h i g h ) 大学工 业工程系共同提出的。基本含义是：以柔性生产技术和动态组织结构为特点，以高素质 协同良好的工作人员为核心，实行企业间网络集成，形成快速响应市场的社会化制造体 系。基本思想是：通过把灵活的动态联盟、先进的柔性制造技术和高素质的人员进行全 面集成，使企业能够从容应付多变不可预测的市场需求，获得企业长期的经济效益1 1 引。 这些学术界和企业界针对制造业新形势提出的诸多新加工方法、理念，虽然可能各 有侧重，但从产品角度来说，任何技术、方法、理念或生产模式最终都必须在车间完成 加工，落实到车间生产上，即使理念涉及到的是上层管理或运营模式。因此目前针对车 间系统存在大量研究，涉及控制模式、通讯方式、调度策略等诸多方面，其中生产信息 通讯作为上层控制调度的基础层面支持是实现整个车间系统合理控制的关键技术。 1 2 2 车间控制体系的发展 现今制造系统的复杂性、动态性以及技术、经营环境的变化对生产交货期、成本和 质量以及资源利用、系统柔性和动态适应性都提出了更高的要求。相应对制造车间来说 要求其控制更具可靠性、容错性、分布性、自治性甚至智能性。传统车间集中式或递阶 控制结构很难达到这样的要求，需要对其进行改造。目前已有大量针对车间控制的研究， 其结构基本上都倾向于采用分布式。由于代理技术可以较好的实现这样的控制方式并满 足系统智能自治的要求遂成了研究的热点。它是分布式人工智能的一个分支，其出现改 4 第章智能1 i 问凋度研究 变了人类与计算机的交互方式，改变了人们构想、设计和建造包括制造系统在内复杂系 统的方式。代理具有的自主性、交互性、实时性等使它在处理大规模复杂系统问题时有 独特的优越性【1 3 l 。针对车间生产领域，目前大量文献对代理技术在解决车间控制调度的 智能化、全局优化等方面进行了研究，各有侧重，提出了各种控制模型及代理模型，其 中也涉及到了代理间的通信和协调机制。这些研究模型各具特点，但从制造控制的角度 看却有共同之处，其目标都试图实现决策的智能、自治、分布与协调，让车间系统更具 柔性、自适应性以及对变化的动态响应性。 1 3 蓝牙技术简介 蓝牙技术i 悼1 6 】由爱立信公司提出，旨在解决移动电话边界设备连接问题，以使移动 电话、手提电脑、p d a 、数码相机等移动设备简单有效连接起来。1 9 9 8 年5 月，爱立信 联合诺基亚、东芝、i b m 和英特尔成立了s i g ，1 9 9 9 年1 2 月微软加入s i g ，并与其他 几家公司成为了s i g 的9 个领导成员。截止目前，s i g 成员已超过2 0 0 0 多家，其中包 括a m d 、戴尔、惠普、德州仪器等，甚至也包括汽车与相机生产制造商1 1 丌。 蓝牙的技术特点决定它应用范围很广，如手机、笔记本电脑等办公设备；电视、音 响等家用电器，还有在诸如智能大楼监控系统、防盗报警系统等领域也有应用价值。目 前国外，已有一些实验性产品问世，如朗讯公司、英国c s r 公司的蓝牙芯片，爱立信 嵌入蓝牙芯片的无线耳机手机，i b m 应用蓝牙技术的笔记本电脑，东芝的蓝牙个人电脑 附件等。目前国内，对蓝牙的研究尚处于起步阶段，但正受到越来越多关注，包括联想、 海尔、t c l 、科龙、北京t 软件技术有限公司以及北京邮电大学、中辐院等2 0 多家 公司、院校的科研机构先后加入s i g 。家电业巨头海尔于2 0 0 2 年专门成立了研究中心， 将蓝牙产品的开发放在重要位置，春兰集团的蓝牙技术开发工作已取得重大进展。2 0 0 1 年1 0 月，中国电子信息产业集团建成了第一座“蓝牙大厦。一些科研单位和大专院 校也开展了对蓝牙实际应用的研究。如结合蓝牙的家庭电子门，蓝牙二维条码扫描仪系 统，南京航空航天大学的导航研究中心对蓝牙技术在车辆导航系统中的应用进行了研 究，东化大学信息科学与技术学院和铁道科学研究院的技术研发中心对蓝牙技术在无线 分布式测控系统中的应用进行了研究，上海大学机电工程自动化学院甚至对蓝牙在粮情 测控中的运用进行了探索i l 剐。 可以看到蓝牙作为一种全新的短距离无线通信技术，在一些使用场合具有独特优 势，因而除传统通信领域外，它还被广泛用于诸如医疗、交通、工业等其它领域，本研 究的车间环境也是其一。目前还没有将蓝牙用于车间系统的先例，蓝牙贴片的尝试使其 应用进一步拓宽，并为车间系统提供了一种新的、有效的控制通信方式。 5 人连交通入学r 学硕十。学付论文 1 4 多代理技术现状 目前，智能代理技术是人工智能领域研究的热点，其被定义为：具有感知能力、问 题求解能力和交互能力的拟人化实体。智能代理在处理复杂系统的大规模问题时已表现 出了其独特的优越性，因此国际上近年来对智能代理进行了大量的研究。对于制造领域， 国际上对基于代理( a g e n t ) 1 1 9 】的智能技术的研究主要集中在产品设计系统的研究、机 器人控制系统的研究、供应链系统的研究、动态调度等方面。大多数研究者按功能将各 子系统处理为具有一定智能的“代理 ，代理之间以谈判( n e g o t i a t e ) 、投标( b i d ) 、 表决( v o t e ) 等方式进行“交流”，并最终达成合同( c o n t r a c t ) 。国内外对于代理、 交流的协议、谈判的方式及保证总体目标等方面作了大量的理论研究，也取得了部分成 果。 在机械制造领域，由于现代制造系统是高度分散的制造系统，由许多标准化或非标 准化、自治和半自治的加工设备、材料运输设备、机器人等各种制造资源组成，因此它 是多代理系统的最佳应用对象。人们把代理技术应用于制造企业的集成、供应链的管理、 制造业的调度和控制等方面。目前，国际国内已有若干家制造企业、研究机构和大学正 在进行基于代理的制造系统的研究与开发，研究主要集中在以下几个方面： ( 1 ) 基于供应链和企业集成 改进企业的供应链管理，对整个企业的运行系统进行集成化处理，使之形成一个高 效统一的增值链体系，是企业提高其竞争能力的重要手段。研究表明，采用基于多代理 技术的方法进行企业集成和供应链管理，企业能够增加其对市场需求变化的反应性，还 能使企业能够极大地提高其信息交换的效率和快速获得市场反馈。同时，由于采用多代 理系统进行供应链管理和企业集成，使得企业可以通过多代理系统的学习，合理配置供 应链资源，不断提高和优化整个企业系统运作的性能。 ( 2 ) 基于代理的制造 由于规划、调度和控制对制造系统具有重要的实际意义，学者们对其进行了广泛的 研究与探索，各种启发式搜索策略、遗传算法、人工神经网络、模糊逻辑系统等技术被 众多学者用来解决制造规划、调度、控制问题。多代理系统通过分解将复杂性降低，并 在必要的时候以相对较低的成本获得必要的系统适应性和可伸缩性等，而且代理系统能 够动态的协调其控制决策，自主调整其行为，对产品变化、设备故障等事件做出智能化 的反应。代理的这一重要特征正是人们进行基于代理的制造规划、调度和控制研究的原 动力。 ( 3 ) 基于代理的产品 6 第一奄锕能下问调度研究 在基于多代理技术的产品设计和工艺规划方面，不少学者研究提出了基于多代理协 作的设计问题求解框架，以更好的协同敏捷式产品设计过程中的设计任务之间、求解方 法与工具之间以及系统与人之间的关系，以此来集成和协同发挥各种基于知识的推理、 传统c a d 技术及设计师在整个设计求解过程中的作用，从而增强了系统的求解能力和 对具体应用的适应能力。 本章小结 本章中，主要针对车间调度问题的发展状况，研究现状做了深入的研究，特别是对 智能车间调度问题做了概括的介绍。同时给出了遗传算法的概念，为文章的进一步深入 积累理论基础。 7 人连交通人学。r 学硕 学何论文 第二章分层遗传算法 2 1 引言 遗传算法( g a ) 作为一种高度并行随机全局搜索方法，通过代表整个解集的种群 进化，以内在并行的方式搜索多个非劣解，决策者可以在多个解中选择决策方案樊叔维 等人首次将遗传算法应用于变压器的电磁设计，促使了进化类算法的应用。但是，单层 的遗传算法仅在一个种群内部进行遗传操作，并不适合自然界多种群的竞争方式，容易 出现早熟现象，而且由于它一般具有较大的种群规模，需要对较多的个体进行大量的遗 传和进化操作，使得进化运算过程缓慢，难以达到计算速度上的要求。 分层遗传算法( h g a ) 是对基本遗传算法的改进。在分层遗传算法中，子种群中进 行各自独立的遗传操作，经过一段时间可以获得位于个体串上的一些特定位置的优良模 式。再通过高层遗传算法的操作，可以获得不同种类的优良模式的新个体 2 0 l 。 2 2 遗传算法概述 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优 化概率搜索算法它最早由美国密执安大学的约翰荷兰德( j o h nh o l l a n d ) 教授提出， 起源于60 年代对自然和人工适应系统的研究。7 0 年代d ej o n g 基于遗传算法的思想 在计算机上进行了大量的纯数值函数优化计算实验。在一系列研究工作的基础上，8 0 年代由g o l d b e r g 进行归纳总结，形成了遗传算法的基本框架。近年来，遗传算法作为问 题求解和最优化的有效工具，己引起了越来越多的注意。 遗传算法使用群体智能搜索技术，它通过选择、交叉、变异等一系列遗传操作产生 新一代群体，并逐步使群体进化到包含或接近最优解的状态。g a 具有两个鲜明的特点： 遗传算法从多点并行搜索最优解，它的搜索速度很快，且具有思想简单、易于实现、应 用效果明显等优点而被众多应用领域所接受，并在自适应控制、组合优化、模式识别、 机器学习、人工生命、管理决策等领域得到了广泛的应用；遗传算法具有较强的鲁棒性， 特别是对于一些大型、复杂优化非线性系统，更显示出其独特和优越的性能。遗传算 法作为- - i q 新兴学科，在理论、方法上尚未成熟，有待进一步发展和完善。尽管在遗传 算法的研究和应用过程中会出现许多难题，同时也会产生许多不同的算法设计观点，目 前遗传算法的各种应用实践己经展现出了其优异的性能和巨大的发展潜力，它的发展前 景激励着各类专业技术人员把遗传算法的理论和方法运用到自己的工作实践中。 8 第：章分层遗传算法 2 2 1 编码 在遗传算法中用编码描述问题的可行解，即把一个问题的可行解从其解空l 日j 转换到 遗传算法所能处理的搜索空间。编码是应用遗传算法时要解决的首要问题，也是设计遗 传算法时的一个关键步骤。编码方法除了决定个体的染色体排列形式之外，它还决定了 个体从搜索空间的基因型变换到解空间的表现型时的解码方法编码方法也影响到交叉 算子、变异算子等遗传算子的运行方法。由此可见，编码方法在很大程度上决定了如何 进行群体的遗传进化运算以及遗传进化运算的效率。 遗传算法的编码方式主要分为：实数编码和二进制编码。 实数编码方法所谓实数编码方法，是指个体的每个基因值用某一范围内的一个实 数来表示，个体的编码长度等于其决策变量的个数。实数编码方法改进了二进制编码方 法的缺点，可以直接应用于解变量是实向量的情形。由于这种编码方法使用的是决策变 量的真实值，所以实数编码方法也叫做真值编码方法。 实数编码是连续参数优化问题的直接描述，它的特点有： ( 1 ) 适合于在遗传算法中表示范围较大的数； ( 2 ) 适合于精度要求较高的遗传算法； ( 3 ) 便于较大空间的遗传算法，改善了遗传算法的计算复杂性，提高运算效率。 2 2 2 适应度函数 在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某 个物种对于其生存环境的适应程度。对生存环境适应度较高的物种将有更多的繁殖机 会；而对生存环境适应度较低的物种，其繁殖机会就相对较少，甚至会逐渐灭绝。与此 相类似，遗传算法中也使用适应度这个概念来度量群体中各个个体在优化计算中有可能 达到或接近于或有助于找到最优解的优良程度。度量个体适应度的函数称为适应度函数 ( f i t n e s sf u n c t i o n ) 。 。 遗传算法的一个特点是它仅使用所求问题的目标函数值就可得到下一步的有关搜 索信息。而对目标函数值的使用是通过评价个体的适应度来体现的。 2 2 3 基本操作 ( 1 ) 选择算子 选择算子是遗传算法中三大遗传算子之一，用来对群体中的个体进行优胜劣汰操作： 适应度高的个体被遗传到下一代群体中的概率较大，适应度低的个体则以较大的概率被 淘汰。遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体 遗传到下一代群体中的一种遗传运算。 9 人造交通人。zi ：学硕十学何论文 选择操作建立在对个体的适应度进行评价的基础之上。选择操作的主要目的是为了 避免基因缺失、提高全局收敛性和计算收敛率。 目前最常用的选择算子有【2 1 】： 1 、轮盘赌选择算子：是一种回放式随机采样的方法，其中，各个个体的选择概率 和其适应度值成比例。对于轮盘赌选择策略，假设种群大小为m ，个体f 的适应度是e ， 个体i 被选择的概率只是： p i = f j f i ，( f l i b 1 ，2 ，3 m ) ( 2 1 ) 管l 其中，只是第i 个个体的适应度值，并且满足只0 。 选择操作的具体步骤为： a 计算各染色体的适应度值； b 累计所有染色体适应度值，并且记录累加值。 c 产生一个随机数，使得在( o ，s u m ) 上： d 选择对应中间累加值的第一个染色体进入交换集： e 重复以上c 、d 两步骤，直到获得足够数量的染色体； 2 、最优保存选择算子：最优保存法就是把群体中适应度最高的个体不进行配对交 叉而直接复制到下一代中。采用最优保存法的优点是进化过程中某一代的最优解可不被 交叉和变异操作破坏。但是，这样一来，有可能会使局部最优个体的遗传基因急速增加 而使进化有可能陷入局部解。这种搜索方法全局搜索能力差，更适合于单峰型的搜索空 间搜索。采用了最优保存法可以确保算法的收敛性。 3 、排序选择算子：所谓排序选择，是指在计算每个个体的适应度后，根据适应 度大小顺序对群体中个体进行排序，然后把事先设计好的概率表排序分配给个体，作为 各自的选择概率。然后再跟据这个概率使用轮盘选择，这样个体的绝对适应值不直接影 响后代的数量。它的另一个优点是无论对极小化问题或极大化问题，不需要进行适应值 的标准化和调节，可以使用原始适应值进行排名选择。 4 、基于局部竞争机制的选择：该方法思想是从群体中任意选择一定数目的个体( 称 为联姻规模) ，其中适应度较高的选择进入下一代。一般联姻规模选择为2 这种选择 方式只使用适应值的相对值作为选择的标准，而与适应值的数值大小不成直接比例，从 而避免超级个体的影响，在一定程度上，避免过早收敛现象和停滞现象的发生。 5 、父子竞争选择：由于人为设定的种群规模限制以及遗传操作算子中存在的随机 性错误，使得利用遗传算法进行寻优时，在进化过程中往往出现由交叉算子或变异算子 操作而产生的新一代个体值比父代低劣的情况，这样就有可能造成下一代进化时产生 1 0 第一：章分层遗传算法 遗传漂移现象。这将使新一轮的进化偏离或者不能及时按照最优方向进行，增加了搜索 时间，降低了搜索效率。对变异产生的个体，同样可以引入父子竞争机制，如果变异后 的子代的适应度值大于或等于相应父代的适应度值时，替换父代，否则，保留父代，以 保持种群优于父代，同时还允许有较大的变异概率，而不会迷失进化方向，但计算适应 度值次数有所增加。为此，可引入父子竞争机制。 ( 2 ) 交叉算子 所谓交叉运算，是指对两个相互配对的染色体按某种方式相互交换其部分基因，从 而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传 算法中起着关键作用，是产生新个体的主要方法。 二进制编码的交叉算子一般包含两个基本内容： 1 、按一定的概率随机地从选择后产生的新种群中取出要交叉的一对； 2 、选择一定的交叉方法，将两个个体进行交换，从而产生一对新的个体。叫做 交叉概率，它决定了染色体交换的几率，p 越大，染色体交换的几率越高；否则，就越 低。 对于实数编码而言，交叉算子通常包括离散杂交和算术杂交等方式。这里以算术杂 交为例介绍实数编码的交叉方式。 设置，z ，为种群中任意配对的两个个体，如下式： rxf = afxj + ( 1 一口f ) xf + 1 lx ；+ 1s ( 1 一口f ) xf + 口jx j + 1 ( 2 2 ) 杂交获得两个后代工：，z ：，其中，呸为lo 1 i 之间的随机数，i = o ，1 , 2 ，n 一1 ，此时 口，值不确定，称为非一致交叉算子；若一= 。届，称为一致交叉算子。遗传算法中 的所谓交叉运算，是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而 形成两个新的个体。交叉运算是遗传算法区别于其它进化算法的重要特征，它在遗传算 法中起着关键作用，是产生新个体的主要方法。 变异：作为遗传运算过程中产生新个体的两个方法，从能力方面来说，交叉运算是 产生新个体的主要方法，它主要决定了遗传算法的全局搜索能力，而变异运算只是产生 新个体的辅助方法，但它也是必不可少的一个运算步骤。因为它决定了遗传算法的局部 搜索能力。交叉算子与变异算子的相互配合，共同完成对搜索空间的全局搜索和局部搜 索，从而使得遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。二进制编码 时的变异算子非常简单，只是以一定的概率只( 称为变异概率) 将所选个体的位取反。 即若是1 ，则取o ；若是o ，则取1 。有一串长为n 的二进制串，第四位发生了翻转。 大连交通人一学r 。z 硕十学伊论文 变异前：0 1 1 1 0 0 1 1 0 1 变异后：0 1 1 0 0 0 1 1 0 1 0 实数编码时，变异算子的作用不再像二进制编码时仅仅是简单地恢复群体中多样 性的损失，它已成为一个主要的搜索算子。与二进制相比，实数编码的变异方式要丰富 的多，主要包括均匀性变异、正态性变异、非一致性变异和自适应变异等。这里以非一 致性变异为例作介绍，它是各个变量按变异概率各自独立地变异。 设l 。为第m 个个体第1 1 个变量( m = 1 ，2 ，m ，万= 1 ，2 ，n ) 。k ，l 分别为 种群中第n 个变量搜索边界的上下限值，则变异算子为： k t q ( k 一) + ( 2 3 ) 2 2 4 运行参数 遗传算法中需要选择的运行参数主要有个体编码串长度c h r o m l e n t h 、群体大小 p o p s i z e 、交叉概率p c 、变异概率p m 、终止代数g e n c o u n t 、代沟g e n r a t e 等。这些参数 对遗传算法的运行性能影响较大，需认真选取。 ( 1 ) 编码长度c h r o m l e n t h 使用二进制编码来表示个体时，编码串长度c h r o m l e n t h 的选取与问题所要求的求 解精度有关；使用浮点数编码来表示个体时，编码串长度与决策变量的个数n 相等；使 用符号编码来表示个体时，编码串长度c h r o m l e n t h 由问题的编码方式来确定；另外， 也可使用变长度的编码来表示个体。 ( 2 ) 群体大小p o p s i z e 群体大小p o p s i z e 表示群体中所含个体的数量。当p o p s i z e 取值较小时，可提高遗 传算法的运算速度，当却降低了群体的多样性，有可能会引起遗传算法的早熟现象；而 当p o p s i z e 取值较大时，又会使得遗传算法的运行效率降低。建议的范围是2 0 1 0 0 。 ( 3 ) 交叉概率以 交叉操作是遗传算法中产生新个体的主要方法，所以交叉概率一般应取较大值。但 若取值过大的话，它又会破坏群体中的优良模式，对进化运算反而产生不利影响：若取 值过小的话，产生新个体的速度又较慢。一般建议的取值范围是o 4 加9 9 。另外，也可 使用自适应的思想来确定交叉概率【3 2 l 。 ( 4 ) 变异概率已 若变异概率取值较大的话，虽然能够产生较多的新个体，但也有可能破坏掉很多较 好的模式，使得遗传算法的性能近似于随机搜索算法的性能；若变异概率取值太小的话， 1 2 第+ 幸分层遗传算法 则变异操作产生新个体的能力和抑制早熟现象的能力就会较差。一般建议的取值范围是 0 0 0 0 1 4 ) 1 。另外，也可使用自适应的的思想来确定变异概率【3 3 】。 ( 5 ) 终止代数g e n c o u n t 终止代数g e n c o u n t 是表示遗传算法运行结束条件的一个参数，它表示遗传算法运 行到指定的进化代数之后就停止运行，并将当前群体中的最佳个体作为所求问题的最优 解输出。一般建议的取值范围是1 0 0 1 0 0 0 。 至于遗传算法的终止条件，还可以利用某种判定准则，当判定出群体已经进化成熟 且不再有进化趋势时就可终止算法的运行过程。常用的判定准则有下面两种： 1 、连续几代个体平均适应度的差异小于某一个极小的阈值； 2 、群体中所有个体适应