（计算数学专业论文）改进遗传算法在设备布局问题中应用.pdf

硕十论文 基于遗传算法的设备布局 摘要 在全球制造业竞争日益激烈的背景下，很多数学工作者和工程设计人员把他 们的目光投向了设备布局模型的研究和软件的开发。车间布局是否合理，对车 间设备操作，设备间物流管理，场地面积的使用效率以及安全生产起着都有着很 大的影响。设备布局问题属于n p 完全问题，传统的凭借经验等布局方法已经不 能适应现代企业的布局要求，因此本文研究设备布局模型以及针对设备布局模型 寻优的遗传算法有着很重要的现实意义。 本文主要研究了改进遗传算法在制造系统的设备布局问题中的应用。文中首 先对设备布局问题进行了详细的分析和综述，总结了设备布局问题的发展现状， 阐述了遗传算法的发展历史、应用领域等，其次本文深入的研究了遗传算法的遗 传算子和运行参数，针对传统遗传算法搜索方向性不强、以及在种群进化过程中 一些优良模式会被意外淘汰等不足，对遗传算子和算法运行参数进行优化，提出 了改进的遗传算法。本文针对单行和多行设备布局问题，分别建立起优化的线性 布局数学模型，文章最后验证了改进遗传算法在设备布局问题中的有效性。 关键词：数学模型，设备布局，遗传算法，适应度函数，交叉算子，变异算子， 选择算子。 a b s t r a c t u n d e rt h eb a c k g r o u n do fi n c r e a s i n g l yc o m p e t i t i v eo fg l o b a lm a n u f a c t u r i n g ，al o t o fm a t h e m a t i c sa n de n g i n e e r i n gs t a f ff o c u st h e i rs i g h t s o nt h el a y o u tm o d e lo f e q u i p m e n t a n ds o f t w a r ed e v e l o p m e n t i ft h ew o r k s h o pl a y o u ti sr e a s o n a b l e ，h a v eg r e a t i m p a c t o nt h eo p e r a t i o no fw o r k s h o pe q u i p m e n t ，e q u i p m e n t r o o m sl o g i s t i c s m a n a g e m e n t ，e f f i c i e n tu s eo fs p a c ea n dp r o d u c t i o ns a f e t y t h ep r o b l e mo fe q u i p m e n t l a y o u ti sn p c o m p l e t ep r o b l e m ，t h et r a d i t i o n a lm e t h o d s o fe x p e r i e n c ec a n ta d a p tt h e r e q u i r e m e n to ft h el a y o u to fam o d e me n t e r p r i s e ，s ot h i sp a p e rr e s e a r c h e s o nt h e l a y o u to ft h em o d e le q u i p m e n t ，a sw e l l a se q u i p m e n tl a y o u tm o d e lf o rt h eg e n e t i c a l g o r i t h mo p t i m i z a t i o n ，w h i c h h a sav e r yi m p o r t a n tp r a c t i c a ls i g n i f i c a n c e t h i sp a p e rs t u d i e dt h ea p p l i c a t i o no ft h ei m p r o v e dg e n e t i ca l g o r i t h mi n t h e m a n u f a c t u r i n gs y s t e m f i r s t ，t h ep a p e rh a sad e t a i l e da n a l y s i s a n ds y n t h e s i so nt h e l a y o t i to fe q u i p m e n t ，a sw e l la st h es t a t u sq u o ，t h eh i s t o r ya n dt h ea p p l i c a t i o n a r e a s f o l l o w e db yt h i sp a p e r ，ad e p t h s t u d yo fv a r i o u sg e n e t i ca l g o r i t h ma n dg e n e t i c o p e r a t o r sp a r a m e t e r si sd o n e ，a st 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 mh a ss o m es h o r t n e s s s u c ha sb l i n d n e s sa n ds oo n ，t h ei m p r o v e dg e n e t i ca l g o r i t h mi sr e f e r r e d t h e n ，f o c u s o no n e w a va n dm u l t i 1 i n ee q u i p m e n t ，t h el a y o u to fo p t i m i z e dm a t h e m a t i c a lm o d e l i s e s t a b l i s h e d a tl a s t ，a ne x a m p l ei sg i v e nt oi m p r o v et h el a y o u to ft h ee f f e c t i v e n e s so f t h ee q u i p m e n t k e y w o r d s ：m a t h e m a t i cm o d e l ，f a c i l i t yl a y 。u t ，g e n e t i ca l g o r i t h m ，f i t n e s sf u n c t i o n ， c r o s s o v e ro p e r a t o r s ，m u t a t i o no p e r a t o r ，s e l e c t i o no p e r a t o r s s e l e c t i o no fi n t e r n a lf a m i l y ， s e l e c t i o nb e t w e e nf a m i l y 1 1 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本学 位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或公布 过的研究成果，也不包含我为获得任何教育机构的学位或学历而使用过的 材料。与我一同工作的同事对本学位论文做出的贡献均己在论文中作了明 确的说明。 研究生签名： 荜墨惫刃9 年6 月2 夕日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或上 网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并授权 其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密论文， 按保密的有关规定和程序处理。 研究生签名：竖兰鍪 珂年月矽日 硕卜论文改进遗传算法在设备布局中的应用 1 引言 在全球制造业竞争日益激烈的今天，一个优良的生产系统对于增强企业竞争力来 说是至关重要的，其中车间设备布局是制造系统设计的一个重要内容，设备是企业进 行生产的基本单元，合理的设备布局对均衡设备能力，保持物流平衡，降低生产成本 起着非常重要的作用n 1 。研究表明：大约2 0 5 0 的加工费用用于物料运输，而合理 的设备布局至少能节约1 0 3 0 的物料运输费用乜1 。 车间设备布局就是将加工设备、物料输送设备、工作单元和通道走廊等物体合理 的放置在一个有限的生产车间内的过程。车间设备布局合理与否将直接影响到车间的 物流、生产效益、生产成本和生产的安全性等。 在我国，制造系统工厂设计一直沿用过去前苏联的设计办法，对小到设备，大到 整个车间以及厂房的布置都以定性布置为主，主要靠直觉经验法、移植法和群众路线 法。不少行业还存在大量的手工布局现象，采用建立实体模型或者绘制多种布局方案 图的方法，利用设计者本身的设计经验以及少量的定量计算来确定布局方案。传统的 布局设计方法有一个明显的缺点，即缺乏科学定量的问题描述和相应的解决办法。随 着科学技术的迅猛发展、人们经济活动竞争的加剧，经常需要新建或者改建工厂车间， 而如果这些新建或扩建的车间布局设计都完全按照传统定性方法来进行粗放型布置， 不仅周期长、成本高，而且缺乏科学的分析，人为因素干扰大，已适应不了我国经济 的发展要求。因此，亟待我们加强布局设计新方法的研究，并扩大其应用的广度与深 度。 最近，布局问题受到国内外众多学者的关注，通过对布局问题的悉心研究，提出 了多种设备布局描述模型和求解算法。但是由于设备布局问题自身的复杂性，这些设 备布局模型和求解算法解决设备布局问题的范围和和种类很有限，对问题的描述和表 达也有较大的偏差，而且求解过程不够直观，不能充分利用布局设计人员的感性知识。 基于以上原因，本课题的研究在理论和实际应用方面都具有十分重要的意义。 车间设备布局属于n p 完全问题，前人已经验证n p 完全问题在有限的时间内得不到 精确解，随着布局物体数量的增加，解空间呈指数倍的扩大，出现组合爆炸现象，用 基于穷举思想的算法将无法解决。从而很多学者转向使用蚁群算法，遗传算法，启发 式算法等对车间设备布局模型进行寻优，且取得良好的效果。 1 1 车间设备布局问题考虑的要素 车间设备布局是一个布局优化问题，只有对设备进行合理的布局，才能使得生产 过程中生产工艺路线合理，物料流程短，运输工作量少，保证生产的安全性和高效性， 1 引言硕十论文 最终降低企业的生产成本，提高企业的效益。在为设备布局过程中既要考虑定量的因 素，同时也要定性的考虑车间设备布局问题。综合起来主要需要研究以下几个方面的 要素：4 1 满足综合的原则。设计时应该将所有影响布局的因素综合考虑，获得优化方案； 满足物料流向合理，物料流程短的要求。最大限度的减少物流环节，倒运，搬 运次数，尽量满足直达化的要求； 满足生产安全要求； 满足生产过程库存尽可能少的要求； 满足物流系统经济性要求； 尽量满足柔性要求。主要是能够应对设备布局经常需要改变的要求； 尽可能满足美观的要求等； 在以上列举的车间设备布局需要考虑的问题中，有影响最终布局效果的定性要 求，也有干扰布局的定量的要求，很难全部通过建立数学模型。首先定量的研究数学 模型，在解决定量问题即设备布局的总体框架后，可以对设备进行微调，使得生产过 程更加的安全、舒适。 1 2 设备布局研究现状 根据布局空间和待布局物体的形状，我们通常把实际的布局问题抽象归纳分为以 下四类： 二维规则物体布局问题 待布局物体和布局空间都是矩形或圆形，如装盘问题、刀切问题。 二维不规则图形布局问题 待布局物体和布局空间中至少有一个是二维不规则图形。如服装裁剪中的划印布 置问题，造船业板材切割中拼装问题，机械行业冲压下料问题。 三维规则物体靠局问题 包括长方体、圆柱体及球体的布局问题，常见的是待布局物体和布局空问都是长 方体的情况，典型的如集装箱摆放布局。 三维不规则实体布局问题 待布局物体和布局空间是三维不规则实体。如坦克舱布置设计，航天器舱内的仪 器设备布局问题【引。 一般情况下，布局专家都是将待布局设备和布局空问简化成矩形，利用启发式算 法进行求解。本文也将使用同样的思想，将待布局的设备和布局空间简化成矩形，建 立设备布局的数学模型，然后通过算法寻求合理的设备布局方案f 6 1 。 虽然许多学者对设各布局进行广泛而深刻的研究，但是由于设备布局问题本身的 2 硕士论文 改进遗传算法在设备布局中的应用 复杂性，布局问题并没有太大的进展。 车间设备布局的复杂性主要表现在以下两个方面： 建模的复杂性 设备布局模型的建立主要是在简化待布局设备和布局场所的基础之上的，和实际 的设备形状和布局空间的形状还有一定差距，还有设备布局过程中的一些要素无法用 模型来分析，再加上布局专家的一些感性因素的影响等。这些都给模型的建立造成了 很大的干扰。 寻优的复杂性 由于设备布局属于n p 完全问题，所以，无论是传统的还是现代的优化算法，在有 限的时间内均不能得到最优解，这样通过优化算法得到的结果和实际情况就产生了一 定的误差。 1 3 常见的设备布局方式 设备布局除了一行布局方式外还有多行布局、u 形布局、蛇形布局等布局方式， 本文主要研究一行布局和多行布局。见图1 1 【7 】 ：团圜团圈里里里望 l 。鬻援竣绣凰网网圈 。 2 + 甏缝双纾 困 圈 团团圈 因困雹 j 团团匿 番。珲粉话怒 菇， 圈圈圈 5 - 缓带编 图1 1 设备布局的方案 ” 团圈团豳； 闼阁匿匿， 团围圆圈j 3 蠢t t 窭- 符； 6 筏萋布赫 g ，彳 基于设备之间关系分类，制造系统布局主要有三类： 1 ) 生产线布局：如流水生产线。生产设备通常是按照产品的工艺顺序依次排列， 适合于大批量，少品种的生产情况。 2 ) 功能布局：生产设备按照功能特性分成几组，相同功能的机床设备被分为一组 安置在一起，适合于小批量，多品种的生产情况。传统的制造系统布局通常采用功能 布局型式。 l 引言硕士论文 3 ) 单元布局：将机床设备划分成若干个生产子单元分布在整个车间，每个单元只 加工一个或几个零件族。重复配置单元于工厂车间的不同区域，有助于从不同位置对 其进行访问，从而减少和改善物流量，在生产波动频繁的环境中是一种很有效的方法。 生产线式设备布局可抽象为基本线性数学模型，然后运用算法求解；对于功能式、 单元式的设备布局则可分为两步：第一步是单位构建，将车间按功能式或单元式分组 规则分为子单元，首先对这些子单元在车间平面进行单元布局；第二步就是对单元内 的设备进行布局，单元内设备布局也可以抽象为基本线性模型求解博j 。由此，制造系 统设备布局问题都可以转化为线性布局或者单元布局与线性布局的组合模型。论文着 重研究如何建立线性布局数学模型并应用遗传算法进行求解1 7 j 。 1 4 遗传算法的发展历史 图1 2 数学建模求解布局设计 遗传算法的真正产生源于2 0 世纪6 0 年代未到7 0 年代初，美 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 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 ”， 这些有关遗传算法的基础理论，为遗传算法的发展和完善奠定了基础阳1 。 遗传算法被提出之后立即受到了各国学者的广泛关注，有关遗传算法的研究成果 不断涌现。1 9 6 8 年h o l l a n d 提出了著名的模式( s c h e m a ) 定理；1 9 7 5 年d ej o n g 首先 尝试将遗传算法用于函数优化，提出了5 个测试函数用以测试遗传算法的优化性能； 1 9 8 1 年b e t h k e 应用w a l s h 函数分析模式；1 9 8 3 年w e t z e l 用遗传算法解决了n p 难 问题旅行商问题( t s p ) ：1 9 8 5 年s c h a f f e r 利用多种群遗传算法研究解决了多目标优化 问题；1 9 8 7 年g o l d b e r g 等人提出了借助共享函数的小生境遗传算法。1 9 8 9 年， g o l d b e r g 出版专著“g e n e t i ca l g o r i t h mi ns e a r c h ，o p t i m i z a t i o n 。a n dm a c h i n el e a r n i n g ”， 对遗传算法的研究起到了非常大的影响。1 9 9 2 年，m i c h a l e w i c z 出版另一部具有极 大影响力的著作“g e n e t i ca l g o r i t h m + d a t as t r u c t u r e = e v o l u t i o n a r yp r o g r a m m i n g ”。从 2 0 世纪8 0 年代中期起，遗传算法和进化计算到达一个研究高潮，以遗传算法和进化 计算为主题的国际学术会议在世界各地定期召开。1 9 8 5 年，第一届国际遗传算法会 4 硕士论文改进遗传算法在设备布局中的戍用 议( i n t e r n a t i o n a lc o n f e r e n c eo ng e n e t i ca l g o r i t h m s ，i c g a ) 在美国卡耐基梅隆大学召开， 以后每两年召开一届。此外，进化规划年会( a n n u a lc o n f e r e n c e o n e v o l u t i o n a r y p r o g r a m m i n g ，a c e p ) - ：1 9 9 2 年在美国的加州召开第一届会议，以后每隔 两年召开一届；进化计算会l 5 ( ( i e e ec o n f e r e n c eo ne v o l u t i o n a r yc o m p u t a t i o n ) 也于1 9 9 4 年开始定期召开。相关的国际学术会议还有很多。 1 5 遗传算法的特点以及应用领域 遗传算法有如f 特点： 鲁棒性 遗传算法独特的工作原理和机制，使得能在复杂的地形和环境下进行全局优化 搜索。 自组织、自适应性【1 0 】 应用遗传算法求解问题时，在编码方案、适应度函数、遗传算子确定后算法 将利用进化过程中获得的信息自行组织搜索。遗传算法对适应度函数没有限制 性的约束和假设。即不要求适应度函数连续或者可导，甚至不要求适应值函数 为显式的函数。因此适应度函数也可以是映射矩阵或神经网络等隐函数。 并行性 遗传算法的并行性主要表现在两个方面： 1 ) 内含并行性：即遗传算法的遗传操作是从许多个体开始的，一个种群中多个 个体同时进行进化，这使得算法具有并行特征。理论证明，遗传算法每处理 数量为n 的个体，实际处理了, j 个模式。 2 ) 内在并行性：遗传算法本身能够实现并行计算。最简单的并行方式是许多台 计算机各自进行独立种群的进化计算，计算过程中甚至不进行任何形式的通 信，直到每个种群进化收敛得到结果后再进行通信比较，选出最终最有个体 【1 1 1 o 概率转换 遗传算法的寻优规则是由概率确定的，而非确定性的。算法的进化方向和进 化目标由目标函数确定，但是算法的搜索过程则是由概率确定的。但是并不 是等同于完全进行随机搜索。算法在问题空间不是无目的的群举或者完全随 机搜索，而是进行高效率的启发式寻求最优解【1 2 】。 遗传算法良好的全局搜索性能使得其应用非常广泛，且在这些领域取得了很好的 效果。主要应用在以下领域n 3 l ： 函数优化 机器人学 l 引言硕十论文 控制 设计 组合，优化 图象处理、 信号处理、 人工生命等领域 1 6 本文的组织结构 全文分为五章，安排如下： 第一章主要介绍了车间设备布局所需要考虑的因素、设备布局的研究现状、 遗传算法的发展历史以及遗传算法的特点和应用领域。 第二章研究了遗传算法的工作机制、遗传算子和其他遗传参数，针对传统遗 传算法的不足，对遗传算子进行优化，提出改进的遗传算法。 第三章研究了设备布局模型，通过实例，验证了改进遗传算法在设备布局问 题中的有效性。 6 硕十论文基于遗传算法的设备布局 2 遗传算法分析和改进 本章主要介绍遗传算法的遗传算子和其他运行参数，分析传统遗传算法的不足， 针对这些不足，对遗传算子进行优化。 遗传算法中主要由种群初始化、适应值计算、遗传操作、结束条件检验等步骤组 成。其中遗传操作是算法的核心组成部分，是算法实现优化功能的最主要工具。在标 准遗传算法中，这些遗传操作主要由选择算子、交叉算子和变异算子组成。 为了保证算法以概率1 收敛，众多专家学者对遗传算法的编码方法，适应度函数， 遗传算子等进行了改进，且取得很好的效果n 4 l 。 2 1 编码方案 编码是实现遗传算法首要解决的问题。遗传算法通过这种对个体编码的操作，不 断搜索出适应度较高的个体，并在群体中逐渐增加其数量，最终寻求出问题的最优解 或近似最优解。在遗传算法中如何描述问题的可行解，即把问题的可行解从其解空间 转换到遗传算法所能处理的搜索空间的转换方法就称为编码选择机制腼1 。 编码是应用遗传算法求解设备布局要解决的首要问题，也是设计遗传算法时的一 个关键步骤。编码方法除了决定了个体的染色体排列形式之外，还决定了个体从搜索 空间的基因型变换到解空间的表现型时的解码方法。编码方法还影响到交叉算子、变 异算子等遗传操作的运算方法，好的编码方法使得交叉、变异等遗传操作可以简单地 实现和执行，而一个差的编码方法却有可能会使得交叉运算、变异运算等遗传操作难 以实现，还可能会产生很多无对应可行解的编码个体，这在遗传算法中被称为无效解。 虽然无效解有时并不完全是有害的，但大部分情况下却是影响遗传算法运行效率的主 要因素。由此，编码方案很大程度上决定了如何进行群体的遗传运算以及遗传进化运 算的效率。针对不同的具体应用问题设计一种完美的编码方案一直是遗传算法的应用 难点，也是遗传算法的一个重要研究方向耵n 引。目前，还没有一套严密、完整而且具 体的编码指导理论及评价准则。 在编码理论研究方面，密歇根大学的d e j o n g 口7 1 提出了两条操作性相对较强的实 用编码原则： 编码原则一：有意义积木块编码原则，应使用能易于产生与所求问题相关的具有 低阶、短定义长度模式的编码方案。 编码原则二：最小字符集编码原则，应使用能使问题得到自然表示或描述的具有 最小编码字符集的编码方案。 第一条编码原则中，模式是指具有某些基因相似性的个体的集合，而具有短定义 长度、低阶且适应度较高的模式是适合构造优良个体的积木块或基因块，这里可以把 2 遗传算法分析和改进硕士论文 该编码原则理解成应使用易于生成适应度较高的个体的编码方案。第二条编码原则说 明了我们为何偏爱于使用二进制编码方法的原因，因为它满足这条编码原则的思想要 求。理论分析表明，二进制编码方案与其他编码字符集相比能包含最大的模式数，从 而使得遗传算法在确定规模的群体中能够处理最多的模式。具体到单行设备布局情 况，事实上我们要求解的是一个设备排序序列，很顺其自然的，我们可以把设备的排 序直接当作染色体编码，这主要是基于以上提到的有意义编码原则。目前常用的编码 方案有如下几种： 1 ) 二进制编码：由字符集 0 ，1 ) 来表示种群中个体的信息，二进制编码有自身的 优点，同时也存在缺点，例如，当多变量的复杂寻优问题s g a 编码串较长，导致计算量 大、精度低、计算时间长，并且由于遗传算子的单一性，算法对不同问题的适应性较差、 寻优过程易陷入局部最优而出现早熟收敛口引。 2 ) 浮点数编码方式：对问题空间的个体直接操作，可以有效的缩短由基因型到 表现型，以及由基因型到表现型的转换时间。 3 ) 交叉编码模式：例如第一行有设备排序为鸩，m ，恤，第二行为鸠，弘，交叉 编码模式可以表示为 心2 ，m 。1 ，m ，1 ，坞2 ，m ，1 ) 。 2 2 选择算子 选择操作实际上就是对染色体进行复制，它是生物能够保持性状而达到物种稳定 的最主要原因。选择算子主要是根据个体的优劣程度决定是被淘汰还是被复制到下一 代种群中。通常情况下，个体被复制到下一代种群中继续参加进化的可能性和个体对 环境的适应情况是密切相关的，个体在种群中适应度函数值越大，则被复制到下一代 的希望越大，否则，可能被淘汰。因此，选择操作实际是一种筛选，而功能是定向进 化，经过多次选择积累，种群中的个体会迅速向目标函数值高的区域集中，形成质量 很高的种群。 经过众多学者多年悉心的研究，选择算子形式有很多种，不同的选择算子的性质 和使用范围也不尽相同。最常用的选择算子主要有以下几种n 出 1 ) 轮盘选择算子：在标准遗传算法中的选择算子是一种最简单，最常用的，使用 范围最广的比例选择算子，也叫做轮盘选择法。在这种选择算子下，个体被复制到下 一代的概率为 掣( 2 1 )”、一一， f ( 置) = l 其中： 厂( z ) 是个体z 在t 代的适应度函数值 r 硕士论文基于遗传算法的设备布局 f 。( 五) 是t 代种群中所有个体的适应度函数值之和 j = l 可以看出，在比例选择操作下，适应度函数值越大，则被选中的概率也就越大。 反之亦然。因此具有不同适应值的不同个体被选择的概率也各不相同，而这种概率的 差异也叫做选择压。选择压越大，高适应值的个体被选中的概率就更大，搜索就越接 近于确定性搜索；而选择压越小，适应值小的个体被选中的概率也将增加，搜索则接 近于随机搜索。在不同的情况下，选择压需要做出适当调整，选择压的不当可能会使 算法过早收敛而进入局部最优或者趋于随机搜索而降低算法效率。 2 ) 杰出者选择算子：这种选择算子实际上是一种复合操作，即在规模为的 种群选择时，首先用其它任意一种选择算子选择出一1 个个体，然后附加一步操作， 将父代种群中适应值最高的个体以概率l 强制性地复制进入子代中，以此保留历代种 群所发现过的最优个体。 3 ) 排序选择算子：这种算子是将种群中个体适应度函数值进行排序并且给出一个 和位置对应的序号1 ，2 ，则子代种群】，= s ( x ) = ( x ，e ，瓦) 的个体的概率分布取 尸 r = x ， = g 一( _ ，一1 ) p ，= 1 ，2 ，n ( 2 2 ) 其中g = 望半，p o ，丙志】为线性排序选择的参数； 该概率分布也可以取为： 尸 r = x ， = q ( 1 一g ) o 一 ( 2 3 ) 其中q ( 0 ，1 ) 为非线性选择的参数。 还有诸如锦标赛选择，波兹曼( b o l t z m a n n ) 选择、e p 选择等选择算子。如果在遗 传算法中仅仅有选择算子这个唯一的算子，那么后代不会超出初始种群的范围，毫无 多样性可言。为了伎种群具有多样性，能够迅速的朝着最优解方向进化，还需要有交 叉算子和变异算子。 2 3 交叉算子 染色体位串的交叉方式设计，一般与所求问题的特征有关系。通常需要考虑如下 因素： 1 ) 必须保持优良基因能够在下一代中有一定的遗传和继承的机会； 2 ) 必须保证通过交叉操作存在一定的生成优良基因的机会； 交叉算子也有很多不同的形式 1 ) 单点交叉：即随机选择种群中的两个个体，在被选中的两个个体中随机选择一 个交叉点，互换这两个个体的交叉点的基因。具体操作如图2 1 。单点交叉能够保证 9 2 遗传算法分析和改进 硕士论文 较好的模式不被破坏，但是，却不能高效的保持种群个体的多样性。 0 p 网 l po p l _ i )l p 凼 l p0 一 一0 p0 p 网 0 p l p o - 。 l pl 一 凼 1 ，0 00 p 图2 1 单点交叉 2 ) 多点交叉，即单点交叉的推广，在种群中随机选择两个个体，随机选择多个交 叉点，互换被选中个体的交叉点上的基因，多点交叉虽然能够保持种群多样性，但是， 同时良好的染色体模式也容易遭到破坏。 2 4 变异算子 遗传算法在选择算子和交叉算子的作用下已经能够起到种群进化的作用，但在这 个过程中，算法不能保证不会丢失一些重要的遗传信息，或者找到未曾出现在种群中 的优良基因。因此仅仅依靠这两种遗传操作所获得的解可能是局部最优解，算法缺乏 搜索整个解空间的能力。变异算子的引入正是为了解决这一问题。 1 ) 单点变异，即在种群中某个个体的某个基因位上独立的进行基因改变，从而产 生新个体的过程。 对于二进制编码而言，单点变异就是指某个个体的某个基因位有1 变异为0 ，或者 由0 变异为1 若变异概率为巴，则对于个体中的某个基因位的码值变化概率为： 乞( 匆= a 1 ) = 1 一只 ( 2 4 ) 只( 包= 1 一f i t 。) = 只 ( 2 5 ) 对于实数编码而言，变异操作的目的就在于随机地改变该个体中基因的数值。然 而这种基因数值变化的步长设置通常比较困难，较小的步长比较稳健，但搜索效率会 相对较低；大步长变异速度较快，但跳跃性太大容易造成种群不稳定。因此，最优步 长通常视具体情况而定，有时甚至可以在算法中动态改变以适应变化的种群特征。一 个简单的实数编码变异算子为： x = x 0 5 l a ( 2 6 ) 其中：= 喜等，口( 9 以概率去取值1 ，以1 一去取值。，通常嬲= 2 。；为变量的取 值范围。 2 ) 多点变异算子，即单点变异算子的推广，具体变异原理在这里不再赘述。 变异算子尽管在遗传算法中的作用不是第一位的，但却是不可或缺的。变异算子 能够以一定的概率找到遗失的或者未曾出现在种群中的优良基因或重要的遗传信息。 硕十论文基于遗传算法的设备布局 由于变异算子的引进，使算法有能力在整个解空间进行鲁棒搜索而不会陷入局部最 优。 选择、交叉和变异是标准遗传算法中最主要的三种遗传算子。实际上，在遗传算 法研究和发展的3 0 年左右的时间里，遗传算法得到了长足的发展。尤其是近几年的 研究，许多以“遗传算法”为名的研究所提出或者改进的遗传算法和最初h o l l a n d 提 出的标准遗传算法经大不一样了。这主要表现在更多样的遗传算子、更合适的适应值 度量以及更复杂的混合策略等。 在各种其它非经典遗传算子中，保优算子是最常用的一种，也是作用最明显的一 种。在其提出后的一段时间内，对它的研究逐渐将它与选择算子结合在一起而成为选 择操作的一部分。人们在对遗传算法的研究中发现，在种群进化的过程中，由于加入 的交叉和变异算子有能力改变原有的个体基因组合方式，因而能够发现许多新的基 因。但同时，两种繁殖操作也可能带来一个负面影响，即可能概率地破坏掉原本存在 于种群中的优秀基因。在生物的进化中，这种倒退的变化也时有发生。物种某种特性 或功能的退化以及人类的返祖现象等都是基因退化的表现。所以在遗传算法中同样存 在着种群发生退化的可能，这将影响到算法的寻优效率甚至最终优化结果。于是人们 提出一种用于解决这个问题的新算子，即保优算子。保优算子的执行非常简单，在新 种群产生并且计算了种群中每个个体的适应值之后，将适应值最高的个体保存起来， 标记为当代最优个体。当下一代种群产生后，再找出下一代种群的最优个体，然后与 父代最优个体进行比较，若子代最优个体比父代最优个体更为优秀，即适应值更高的， 则将该子代最优个体取代父代最优个体，反之则不做任何替换。经过这种保优操作， 经过若干代进化的种群中能够始终保持进化过程中所找到的历代最优个体，于是能够 有效防止种群整体退化现象。 2 5 遗传算法的进化参数 遗传算法在搜索空间中进行高效的启发式搜索，算法的性能由深度搜索 ( e x p l o i t a t i o n ) 并f l 广度搜索( e x p l o r a t i o n ) i 拘平衡性决定。而这种平衡性又取决于种群规 模、最大进化代数、编码长度、交叉概率、变异概率等参数，因此，这些进化参数的 设置对于整个遗传算法的搜索性能起到了至关重要的作用。 1 ) 种群规模n 种群的规模不仅影响到遗传算法的寻优效果，同时对于算法的执行效率也有着很 重要的影响。种群规模过小，种群缺乏多样性，覆盖面小，容易陷入局部最优解，出 现早熟的现象。种群过大，虽然搜索的范围扩大，不容易陷入局部最优解，但是，严 重限制算法的搜索速度。因此，寻找一个适当的种群数目是研究遗传算法的一个很有 意义的工作。通常情况下，种群大小为几十到几百。 1 1 2 遗传算法分析和改进 硕士论文 2 ) 算法进化的最大代数 遗传算法和传统的优化算法不同，传统的优化算法有明确的算法停止条件。遗传 算法在程序执行之前经常需要明确算法进化的最大代数，而确定最大进化代数g 也是 一件比较麻烦的事情，若g 取值过小，则种群没有足够的时间进化，难以产生出令人 满意的最优解，若g 过大，则会影响算法的执行速度。一般情况下，我们建议最大进 化代数为1 0 0 至l j l 0 0 0 之间。 当然最大进化代数并不是算法终止的唯一的依据。例如，相邻若干代之间种群平 均适应值的变化也常被用于判断算法是否收敛，也可以作为决定算法是否可以退出的 依据。如规定，若相邻两代间种群平均适应值变化量h 占，则退出算法。其中s 是预 先设置的任意正实数。值得指出的是，最大进化代数过小，会导致算法未收敛就退出， 因而得不到全局最优解；而如果设置过大，则浪费系统资源和时间。 3 ) 交叉概率所 在进化策略中，由于只有变异操作而无交叉操作，因而交叉概率可以视为0 。但 是在遗传算法中，交叉算子被认为是最重要的遗传操作之一，因此交叉概率一般取值 较大。然而交叉操作给种群的进化过程带来的不仅仅是积极的促进作用，有时也会因 为过大的交叉概率而破坏掉种群中已经形成的优良基因模式，导致算法随机性增大。 而小概率交叉则降低了算法发现新基因的速度，使得遗传算法搜索进入迟钝状态，而 使算法的收敛速度下降。一般交叉概率取值可在0 7 0 9 之间u 引。 4 ) 变异概率p 。 变异操作在遗传算法中属于辅助性的操作，主要作用就是为了保持种群的多样 性。变异的实质是使搜索个体在搜索空问中随机的跳跃以发现可能存在于领域中的优 良解。若变异概率过大，则使搜索个体在搜索空间内大范围跳跃，算法的启发式和导 向性作用就不明显，随机性增强，遗传算法就开始接近于完全的随机搜索。但若变异 概率过低，则搜索个体仅在很小的领域范围内跳动，发现新基因的可能性下降，优化 效率就很难提高。一般变异概率可取值0 0 0 1 0 1 u 9 l 。 由于遗传算法的进化过程不断推进，种群的平均适应值、多样性等许多性质都在 不断地发生改变，从本质上说，遗传算法是动态和适应性的过程，因此一个固定的参 数很难适用于算法的整个进化过程。这种固定参数的形式与一般的进化思想也是不相 符合的。因此很自然地希望各种进化参数能在算法的进化过程中根据种群的当前特征 进行实时的调整，这种实时的调整就是一种自适应的表现。例如交叉概率，由于算法 进化初期，个体解的覆盖面有限，需要加大力度寻找新的更优个体，因此进化初期的 交叉概率可以适当增大。而到了进化后期，个体已经基本集中在了最优解空间的附近 领域，这时交叉概率应当适当减小以保留已被发现的优良基因。又如变异算子，当种 群内个体基因形式丰富，算法还未收敛时，变异概率可以适当小些，而当算法接近或 1 2 硕七论文基于遗传算法的设备布局 已经收敛，种群平均适应值不变或者只发生微弱改变时，为刺激搜索，可以适当加大 变异概率，从而实现遗传算法从“整体搜索”到“局部搜索”的过程。此外，对于个 体编码串的不同基因位的变异概率也可以不同。例如当算法已接近收敛，进入局部搜 索的微调阶段时，可以采用高基因位小概率变异、低基因位大概率变异的方式进行个 体微调整。事实上，到目前为止还没有一种公认的成熟的参数设置原则和方法，目前 的遗传算法在使用时，其参数设置往往都是借鉴已有经验和对问题的先验知识。 2 6 遗传算法流程图 经过上述对遗传算法各个算子的研究，我们下面给出遗传算法的一般执行步骤和 一般流程图。 s t e p l ：确定目标函数，变量定义域和编码精度，形成编码方案。 s t e p 2 ：随机产生规模为n 的初始种群 墨，x2 k ) 。 s t e p 3 ：对被选入匹配池中的个体进行交叉操作，形成新种群 i ，y ：y n ) s t e p 4 ：以小概率在新种群 誓，y ：坛) 中选择个体进行变异，产生新种群 z l ，z ：z ) s t e p s ：计算新种群 z l ，z ：z n ) 中各个个体的适应度函数值 s t e p 6 ：按照某一选择操作，选择n 个个体形成新种群 五。，x2 。x ) s t e p 7 ：检查算法结束条件，若满足结束条件，则退出程序，当前适应度函数值 最高的就是我们要求的最优解，否则，转蛩j s t e p 3 一般流程图如图2 2 2 遗传算法分析和改进硕十论文 图2 2 遗传算法流程图 2 7 影响遗传算法搜索效率的因素 前面已经讨论，车间设备布局属于n p 完全问题，具有非线性性。目前许多学者致 力于遗传算法解决设备布局问题的研究，并且取得了一定的成果。但是由于存在以下 几个影响遗传算法全局搜索的因素，使得在这一领域还有很大的研究空间。 通过分析，影响遗传算法全局搜索主要因素有如下几个： 1 ) 在一个种群中，每个个体都有趋向某个峰值( 局部最优解) 的潜力，有些个体 趋向某个峰值的可能性较大，我们称之为优良个体，但是某些优良个体在某个时期仅 从适应度函数无法判断其是优良个体，我们称之为隐性优良个体。而遗传算法是根据 个体的适应度来判断个体是否优良的，这样就会导致某些隐性优良个体在进化过程中 被一些超常个体意外淘汰，导致种群过早的收敛，陷入局部最优。 2 ) 由于编码方式和交叉算子设计不当，交叉过程产生优良个体减少，低劣的个体 1 4 硕士论文幕于遗传算法的设备布局 增加。例如我们将5 台设备布置在3 x 3 网格中，个体1 ，2 为局部最优解，见图2 3 【2 0 】【2 1 1 ， 原个体口，b 的阴影部分为交叉点， 禺嚣最扰解 凝个俸a 交叉詹个俸c 禺部最优解 腰个捧b 交叉后个俺d 图2 3 交叉操作 可以看出，将交叉操作施加到原个体口，b 上，产生了个体c ，d ，适应度降低，是 原个体的优良模式被破坏。 3 ) 遗传算法在搜索过程中方向性不强，对于遗传算法的搜索效率有一定的影响。 2 8 改进的遗传算法 针对以上几个个影响遗传算法全局寻优的因素，我们提出改进遗传算法。 1 1 编码 本文中将采用净间距编码方案。 2 ) 交叉算子 为了不破坏优良个体模式，采用自适应交叉操作。我们对于适应度高的个体，以 较小的概率进行交叉，对适应度小的个体，以较大的概率进行交叉操作。自适应交叉 概率为： p c 2 。( p c ! - p c 2 ) ( f - f a v g ) v 。c 1 q a x 一厶曙厶曙 。2 c i3 ) 种g 团挪圈s 岛 2 遗传算法分析和改进 硕十论文 其中： p ，p 为固定值，取p = o 9 ，p = o 5 ， 0 10 2c l 2 厂为当代种群的最大适应度， 。m a x 厂为当代种群的平均适应度， 。a v j z 厂为当前个体的适应度。 由此可以看出，当个体适应度大于种群平均适应度时，则该个体以较小的交叉概 率发生交叉，且适应度越高，交叉的可能性越小，适应度低于平均适应度时，则以较 高的可能性进行交叉，这样就可以有效的避免优良的模式被破坏。 根据交叉概率确定交叉个体，对确定执行交叉的个体进行配对，由于我们采用浮 点数编码方案，可以先随机的生成一个万【o ，1 】，薯( f ) ，x l ( t ) 为第t 代种群的两个个体， 经过交叉 鼍( h 1 ) = 3 x i ( t ) + ( 1 一d ) x j ( t ) ( 2 8 ) x j ( t + 1 ) = 万x i ( f ) + ( 1 一万) 0 ( ，) ( 2 9 ) 3 ) 变异算子 在执行完交叉算子，还需要变异算子对种群个体进行微调，以增加种群的多样性， 和交叉算子一样，如果在整个进化过程中，以一个固定的变异概率确定种群变异情况， 不可避免的会导致优良个体被无意淘汰。我们采用自适应遗传变异，根据个体适应度 的大小确定种群中个体的变异情况。适应度越大，则变异概率越小，适应度越小，则 变异概率越大。自适应变异概率： p c 2 其中： 一。，p ：为固定值，通常取t ，= o 1 ，p ，：= o - 0 1 名a x ，厶v g ，的含义和交叉算子一样。 1 6 枷伽 人i b ( x ) 二( 、x 喃) , m 千m 柿a x 沮 伍b ( 休x ) ( 2 1 1 ) o ，x 为无效染色体 * “v 其中，a f x l 为适应度函数 b ( x 1 为目标函数 c m 。，是一个适当的数值，本文中取目前最大的适应度函数值 根据我们已经得出的多行设备布局模型可以计算出染色体x 的目标函数值，然后 再根据上一章给出的适应度函数，可以计算出染色体彳的适应性。 根据各条染色体的适应度，由上一章我们提出的交叉，变异操作方案对各条染色 体进行进化操作，但是为了不让优良个体不被意外淘汰，我们采用上一章节已经分析 过的家族内部竞争手段进行选择操作。 综合以上各个部分所述，改进的遗传算求解流程如图2 4 2 遗传算法分析和改进 第 步 图2 4 改进遗传算法的寻优流程图 硕十论文基于遗传算法的设稀布局 3 车间设备布局模型的建立和应用实例 在建立模型过程中，我们将待布置得设备和布局空间简化为矩形，西南角为坐标 原点，沿着墙壁方向分别为x 轴方向和y 轴方向，且设备的大小是相同的，设备空间 大小和设备尺寸均为己知，设备全部是纵向布黄的，任何两个设备之间的运输费用由 两个设备唯一决定，和其他因素无关，物料流动只能平行于相关参考线2 3 1 。 3 1 单行布局方式 一行布局方式就是将待布局设备的中心布置在一条x 轴方向的水平线上如图3 1 。 我们可以得到如下数学模型： a ( x ) = d , j l