（计算机应用技术专业论文）遗传蚁群混合算法及其在车间调度问题中的应用.pdf

摘要 随着市场竞争的日趋激烈，每个企业都在寻求更好的生产与运作管理方案， 以提高企业的生产、经营和管理效率，从而提高企业的核心竞争优势。生产与 运作管理的核心是车间调度问题能否高效地获得优化解，研究车间调度问题具 有很大的理论意义和现实价值。 车间调度问题是解决如何按时间的先后分配资源来完成不同的生产任务， 使预定目标最优化的问题。作业车间调度( j o b s h o p 调度) 问题是许多实际车 间调度问题的简化模型，是一个典型的n p h a r d 问题。该问题具有约束性、非 线性、不确定性、大规模性等复杂性，已被证明在多项式时间内得不到最优值。 近年来，对于j o b s h o p 调度问题求解方式主要有启发式算法和元启发式算法， 但各有其不足之处：元启发式方法的运行时间长，可获得较好的解，但其解不 稳定；启发式方法可在较短的时间内得到鲁棒性较强的解，但是极少获得较优 的解。 为了更好地解决作业车间调度问题，将一些解决某类问题较好的算法组合 起来。遗传算法具有快速随机的全局搜索能力，但对于系统中的反馈信息利用 却无能为力，当求解到一定范围时往往做大量无为的冗余迭代，使得求精确解 效率降低。蚁群算法是通过信息素的累积和更新收敛于最优路径上，具有分布 式并行全局搜索能力，但初期信息素匮乏，求解速度慢。本文根据遗传算法和 蚁群算法的特点，尝试将两个算法动态融合来求解j o b s h o p 调度问题。算法动 态融合的思想是：在最佳点( 遗传算法和蚁群算法融合时刻) 之前利用遗传算 法的特性，快速、全面地生成优秀染色体；从其中选出一部分比较优秀的染色 体并将其转换为初始蚁群算法的信息素分布；在最佳点之后利用蚁群算法的正 反馈性、高效性求取车间调度问题的最优解。最后，本文针对j o b - s h o p 问题中 经典问题的f r 类和l a 类的部分问题进行实验仿真计算。结果表明遗传蚁群混 合算法的收敛率更高，具有更好的全局收敛性能，遗传蚁群混合算法在更少的 迭代次数达到全局最优解，具有更高的收敛速度。 关键词：遗传算法； 蚁群算法；遗传蚁群算法；车间作业调度问题 j o b s h o p 调度问题 a b s t r a c t w i t ht h ei n c r e a s i n gk e e nm a r k e tc o m p e t i t i o n ，e a c he n t e r p r i s el o o k sf o rb e t t e r s o l u t i o n st o p r o d u c t i o n a n do p e r a t i o n m a n a g e m e n ta i m i n ga ti m p r o v et h ec o r e c o m p e t i t i v ea d v a n t a g e t h ek e yt o t h em a n a g e m e n to fp r o d u c t i o na n do p e r a t i o n m a n a g e m e n t i st oa c h i e v et h e o p t i m a ls o l u t i o n s t h e r e f o r e ，t h es t u d yo fj o bs h o p s c h e d u l ep r o b l e mi st h eg r e a ts i g n i f i c a n c e j o bs h o pp r o b l e mi st os o l v et h ep r o b l e mt h a tm a k i n gp r e a r r a n g ei so p t i m i z a t i o nb y a s s i g n i n gr e s o u r c e st of i n i s hd i f f e r e n tm a n u f a c t u r et a s k sa c c o r d i n gt ot i m ee a r l yo rl a t e j o bs h o pp r o b l e mi st h ec o n c e n t r a t em o d e lo fm a n ya c t u a lj o bs h 叩s h e d u l ep r o b l e m s ， a n di ti sat y p i c a ln o n d e t e r m i n l s t i cp o l y n o m i a l - t i m eh a r dp r o b l e m t h ep r o b l e mh a s m a n yc o m p l e xc h a r a c t e r i s t i c s , s u c ha sc o n s t r a i n t s , n o n l i n e a r i t y , u n c e r t a i n t ya n dl a r g e s c a l e s oi ti sr e p o r t e dt h a ti t 啪tg e tt h eb e s to u t c o m et h r o u g hp o l y n o m i a l i nr e c e n t y e a r s , m e t a - h e u r i s t i c sa l g o r i t h ma n dh e u r i s t i c sa l g o r i t h ma r et w ok i n d so fa l g o r i t h mf o r j o bs h o pp r o b l e m h o w e v e r , t h e ya r ea l lh a v es h o r t a g e si nd i f f e r e n tf a c e t ：a l t h o u g h m e t a - h e u r i s t i e sa l g o r i t h ms p e n d sl o n gr u n t i m ei ng e t t i n gb e t t e ra n s w e r , t h ea n s w e ri ss t i l l n o ts t a b l e ；h e u r i s t i c sa l g o r i t h m 啪g e ts t r o n gl i f e - f o r c ea n s w e ri nm u c hs h o r t e rt i m e ，b u t t h e r ei sr a r eb c t l c r8 u s w e r ho r d e rt os o l v et h ej o bs h o pp r o b l e mb e t t e r l y , w ec o m b i n es o m ea l g o r i t h m sw h i c h i sg o o da t i ns o l v i n gs o m ep r o b l e m s t h eg e n e t i ca i g o r i t h e mh a st h ea b i l i t yo fg l o b a l s e a r c h i n gq u c i k l ya n dr a n d o m l y , b u ti ti si n a d e q u a t ei nf e e d i n gb a c ks y s t e mi n f o r m a t i o n i t a l w a y sm a k e sal o to fr e d u n d a n c ya c c o u n tw h i l ei tg e t ss o m ed e g r e e , w h i c hm a k e st h e e f f i c i e n c yo fs o l v i n gp r o b l e mf a l l i n g a n tc o l o n yo p t i m i z a t i o na l g o r i t h mg e t st h eb e s t r o u t eb yc u m u l a t i n gi n f o r m a t i o na n du p d a t i n gt h ei n f o r m a t i o n0 1 1t h ep a t h ，i th a st h ed i s - t r i b u t e da n dc o l l a t e r a la b i l i t yi ng l o b a ls e a r c h i n g , b u tt h es p e e do fi tb e c o m e ss l o w l y b e a ：a u s et h ei n f o r m a t i o ni sp i n c ha tf i r s t i nt h i st h e s i s , a i ma ts t r o n gp o i n to fg e n e t i c a l g o r i t h ma n da n tc o l o n yo p t i m i z a t i o na l g o r i t h m , w ep r o p o s e st oc o m b i n eg e n e t i ca l g o r i t h i nw i t ha n tc o l o n yo p t i m i z a t i o na l g o r i t h mt os o l v ej o bs h o pp r o b l e m t h ei d e ao f d y n a m i cc o m b i n i n gg e n e t i ca l g o r i t h mw i t ha n tc o l o n yo p t i m i z a t i o na l g o t i t h m ：a tf i r s t u s i n gg e n e t i ca l g o r i t h mg e t ss o m e e x c e l l e n tp o p u l a t i o n sq u i c k l ya n dr o u n d l yb e f o r et h e b e s tp o i n t ，w h i c hi st h et i m et h a tg e n e t i ca l g o r i t h ma n da n tc o l o n yo p t i m i z a t i o na l g o r i t h m g e tt o g e t h e r c h o o s es o m eg o o dp o p u l a t i o n sa n dt r a n s l a t i n gt h e mt ot h ee a r l i e ri n f o r - m a t i o nd i s t r i b u t i o no fa n tc o l o n yo p t i m i z a t i o na l g o r i t h mf r o mt h ep o p u l a t i o n sw h i c hi s a c h i e v e db yg e n e t i ca l g o r i t h m u s i n gt h ea n tc o l o n yo p t i m i z a t i o na l g o r i t h mt og e tt h e b e s ta n s w e ro fj o bs h o pp r o b l e mb yt h ea l g o r i t h mc h a r a c t e r i s t i c so fp o s i t i v ef e e d b a c k a n dh i g he f f i c i e n c ya f t e rt h eb e s tp o i n t f i n a l l yw em a k ee m u l a t i o n a le x p e r i m e n tf o rs o m e c l a s s i ct y p ef t p r o b l e ma n dt y p el a p r o b l e mo f j o bs h o pp r o b l e m t h eo u t c o m ei d i c a t e s t h a tg a - a c oh a sb e t t e rc o n s t r i n g e n c ya n db e t t e rw h o l ec o n s t r i n g e n c y g a = a c og e t s t h eb e s tp o p u l a t i o na n db e t t e rc o n s t r i n g e n c ys p e e di nl e s si t e r a t i v en u m b e r k e yw o r d s ：g e n e t i c a l g o r i t h m ；a n tc o l o n yo p t i m i z a t i o na l g o r i t h m ；g a - a c o ； j o bs h o ps c h e d u l ep r o b l e m ；j o bs h o pp r o b l e m ； m 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：黏 妊日期：啤牡归s 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权 保留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名搬名：盥慨例砰罗 武汉理工大学硕士学位论文 第1 章绪论 1 1 车间调度在企业生产中的意义 制造业是国民经济的支柱产业，没有发达的制造业，就没有国家的真正繁 荣和强大。制造技术是完成制造活动所需的一切技术手段的总称，是支持高质 量制造业的技术后盾。其中，生产车间调度技术又是最重要的制造技术之一， 在制造企业中有着举足轻重的地位1 5 1 】，尤其在制造业发生了翻天覆地变化的今 天，显得格外重要。一方面，随着电子技术、计算机技术的发展，制造设备的 自动化水平和加工能力得到了极大的提高，制造过程自动化水平也逐渐提高， 使得生产调度问题变得更加复杂，往往超过人的正常决策能力。另一方面，随 着市场竞争的激烈化和国际化，出现了多种先进管理理念及制造模式，它们的 核心思想无一不是为了适应市场小批量、多品种和更具个性化的要求，缩短供 货周期，控制产品成本，提高产品质量，提高设备利用率等旧所以，传统的 依靠人来指挥生产加工过程的模式已经远远不能适应新的制造环境的需要，迫 切需要研究有效的生产调度方法和建立生产调度软件系统，使得生产过程能够 更加合理和高效运行。生产调度的理论和方法属于软科学，运用它既不需要增 加投资和设备，又不需要增加人员，就可以提高生产和工作效率因此，研究 生产调度的理论和方法，对于力求建设“节约型”社会的今天，提高工作效率 和经济效益，有着重要的现实意义【卅。 生产车间调度问题就是解决如何按时间的先后分配有限资源来完成不同的 生产任务，使预定目标最优化的问题。追本溯源，它来源于对制造车间生产计 划与控制的研究，但是又不能将它与生产计划混淆。工程应用体系中，经常从 时间周期角度定义长期规划、中期计划和短期计划，调度则仅限于在生产故障 或出现异常情况下的动态调度和再调度问题。但这种体系仅针对特殊情况，不 具有广泛意义还有一种体系是将调度的概念泛化，将整个车间的生产指挥 范畴的活动均称为调度问题，并将其分解成几个层次进行研究，涉及计划和调 度等一系列活动。然而，为了问题阐述和研究的方便，摒弃上述两种概念体系， 武汉理工大学硕士学位论文 将工艺计划归入计划问题，将调度问题明确为针对加工活动的排序和加工时间 的确定问题。 好的生产调度能提高资源的利用率和操作管理水平，生产出具有竞争力的 产品。车间的调度优化工作，其在提高生产效率，降低生产成本等方面起着重 要的作用。 1 2 车间调度问题概述 1 2 1 车间调度问题定义 1 9 5 4 年，j o h n s o n 研究了两台机床的流水车间调度问题。这标志着调度理论 研究的开始。由于调度问题的理论价值和实用意义，在后来的5 0 年中，有无数 多篇关于调度问题的文献发表，其中包括m u t h 和t h o m p s o n ，c o n w a y ，r i n n o o y ， c o f f m a n ，f r e n c h ，m o r t o n ，b l a e w i c 2 ，c h r e t i e n n ee t a l 等八篇专著。 总的说来，车间调度问题的实质就是在时间上合理配置系统的有限资源，以 满足特定目标的要求。典型的车间调度问题包括一个要完成的作业集，每个作 业由一个操作集组成；各操作的完成需要占用机床或其他资源，并且必须按一 些可行的工艺次序进行加工；每台机床可进行作业的某个操作。在约束条件下， 调度的目标是将作业合理地安排到各机床，并合理安摔作业的加工次序和加工 开始时间，同时优化一些性能指标【柚1 1 2 2 车间调度问题分类 生产车间调度系统的分类方法很多，主要有以下几种： 1 加工系统的复杂度，可分为单机、多台并行机、h o w s h o p 和j o b s h o p 。 2 问题是所有的操作任务都在单台机器上完成，为此存在任务的优化排队 问题；多台并行机的调度问题更复杂，因而优化问题更突出；f l o w - s h o p 型问题 假设所有作业都在同样的设备上加工，并有一致的加工操作和加工顺序； j o b - s h o p 是最一般的调度类型、并不限制作业的操作的加工设备，并允许一个作 业加工具有不同的加工路径。 3 性能指标，分为基于调度费用和调度性能的指标两大类。 4 生产环境的特点，可将调度问题分为确定性调度和随机性调度问题。 2 武汉理工大学硕士学位论文 5 作业的加工特点，可将调度问题分为静态调度和动态调度。 静态调度是指所有待安排加工的作业均处于待加工状态，因而进行一次调度 后、各作业的加工被确定、在以后的加工过程中就不再改变； 动态调度是指作业依次进入待加工状态、各种作业不断进入系统接受加工、 同时完成加工的作业又不断离开，还要考虑作业环境中不断出现的动态扰动、 如作业的加工超时、设备的损坏等。因此动态调度要根据系统中作业、设备等 的状况，不断地进行调度。实际调度的类型往往是j o b s h o p 型，且是动态的。 1 2 3 车间调度问题的特点 车间调度问题有以下几个特点： 1 复杂性 一是生产因素的多样化与复杂性；二是车间调度问题是在等式或不等式约束 下优化某些性能指标，在计算量上往往是n p h a r d 问题。因此，在求解车间调 度问题上，一些常规的优化方法往往无能为力。 2 动态随机性 生产中会出现设备故障、急件插入、人员误操作等不可预见因素，生产调度 需要根据生产情况做出动态调整。 3 多目标性 车间调度往往是多目标的，可分为基于作业交货期的目标、基于作业完成时 间的目标、基于生产成本的目标等【“ 1 2 4 车间调度问题评价标准 车间调度问题的优化目标是评价调度方案优劣的标准，常见的调度指标有： 1 反映调度成本的指标 调度中发生的费用有；启动成本、换线成本、加工费用、工人加班费用、过 期赔偿费用、在线库存费用、调度管理费用等。由于调度净现值指标能综合反 映上述费用，所以得到了广泛应用。 2 反映调度性能的指标 包括：生产周期、平均流动时间、机床利用率、工人利用率等。 3 反映用户要求的指标 3 武汉理工大学硕士学位论文 包括：最大拖期时间、平均拖期时间、拖期零件的数量等。 1 2 5 车间调度问题的研究现状和研究方法 自从车间调度问题在2 0 世纪5 0 年代被开始广泛研究以来，经过几十年的 发展，产生了许多车间调度问题的类型和求解方法。对于车间调度问题， 根据加工系统的复杂性，可分为单机、多台并行机、f l o w s h o 口问题和j o b s h o p 问题；根据性能指标，可分为基于调度费用和调度性能的指标两大类。根据生 产环境的特点，也可以将调度问题分为确定性调度和随机性调度问题。根据作 业的加工特点，也可以将调度问题分为静态调度和动态调度。实际中，车间调 度的类型往往是j o b - s h o p 型，且是动态的。目前研究比较多的是作业车间调度 ( j o b - s h o p ) 问题【2 d 1 和流水车间调度( f l o w s h o p ) 问题“，并随着对各类调度 问题研究的深入及各种交叉学科的发展，出现了许多新的车间调度理论【5 6 1 7 1 和 方法i s 。 1 启发式规则 1 9 5 4 年，j o h n s o n 提出了两台机床上f l o w - s h o p 排序问题的最优算法，从 此人们开始对排序理论的研究。s t e v e n sa n dg e m m i l l ( 1 9 9 7 ) 用启发式方法解决 了两机器f l o w - s h o p 的排序问题。这些启发式规则简单易行，但难以得到全局 优化结果，且对问题的性质与应用场合的依赖性较强。 2 仿真方法 建立在排队论、p e t r i 网、极大代数等方法的基础之上，通过仿真分析在不 同情况下系统的性能来进行计划和调度，其效果依赖于仿真模型的优劣( 蔡自 兴，1 9 9 0 ) 。另外，对j o b - s h o p 问题有较好性能的方法并不能保证对柔性制造 系统调度问题同样有较好的结果( r a h i m i f a r da n dn e w m a n ，1 9 9 7 ) 。 3 经典运筹学中的分枝定界法、割平面法等被用来解决表达为整数规则的 调度问题( b e r r a d ae t a l ，i 9 8 6 ) 。 这些解析方法可以解决规模较小的一些问题，但是在解决多重复杂条件约束 和含有不确定因素的调度优化问题时结果不理想( a a n c ne t a l ，1 9 9 3 ) 。 4 模拟退火方法 模拟退火方法模仿晶体的冷却过程，它渐近收敛于全局最优解，但收敛速度 较慢。m i t t c n t h a l 用模拟退火算法实现了单台机器n 工件的调度问题，模拟退 火算法还被用于f l o ws h o p 排序、机器分组和有资源约束的调度问题( r a b c l o 4 武汉理工大学硕士学位论文 c t a l ，1 9 9 3 ) 。 5 神经网络方法 神经网络方法已被成功地应用于解决组合优化问题，但在大规模、复杂调度 系统中，存在计算速度慢与结构参数难以确定的缺点。f o o 等( 1 9 9 8 ) 应用随 机h o p f i e l d 网络来解决调度问题，构造网络能量函数i v a p n o v 函数进行优 化，当网络迭代收敛时，能量函数达到最小。 6 基于知识的方法 基于知识的调度方法用专家系统自动产生调度来辅助人去调度( f a r h o o d i f a a 9 9 0 ，d o u b l e g e r iz ，1 9 9 3 ，b e n - a r i e h ，1 9 8 6 ) 。它将传统的调度方法与基于 知识的调度评价相结合，对设计用于生产实际的高效益、高柔性的现代集成制 造系统具有启发意义。 7 遗传算法 遗传算法是一种兼顾优化效果和计算效率的方法，适合于在复杂而庞大的搜 索空间中寻找优化解，在搜索过程中自动获取和积累有关搜索空间的知识，并 自适应地控制搜索过程算法简单、鲁棒性强，易于并行分布处理，非常适合 予解决调度问题( o r v o s hd a v i d1 9 9 4 ，c h i ua n df u l 9 9 7 ，f l e u r ya n dg o u r g a n d 1 9 9 8 ) 。1 9 8 5 年d a v i s 首次将遗传算法用于解决调度问题，d a g l i 提出了排序 中局部交换和环状交换等l 。 8 各种算法的混合算法 由于各种调度算法都不同程度地存在着这样或那样的优缺点，所以，近来人 们开始把各种近似算法的组合应用研究作为热点，以弥补各自的缺点，发挥各 自的优势，达到寻优的目的。 1 3 本文内容 本章根据遗传算法和蚁群算法都各自的特点、扬长避短、充分发挥它们各 自的优势，提出遗传蚁群混合算法。并运用遗传蚁群混合算法，对车间调度问 题中的最典型调度问题j o b - s h o p ( 司题进行试验仿真。本论文完成的工作如下： 1 对调度问题进行科学描述。 2 介绍遗传算法的思想起源、基本原理和遗传操作。 3 介绍蚁群算法的思想起源、原理及流程操作。 5 武汉理工大学硕士学位论文 4 提出遗传蚁群混合算法，详细介绍混合算法的操作步骤，并给出算法的 流程图和操作伪代码。 5 分析车间调度问题中典型调度问题j o b - s h o p 调度问题，运用遗传蚁群混 合算法进行实验仿真计算，对结果进行对比分析，并得出结论：在规模不大的 j o b - s h o p 问题上，遗传蚁群混合算法略优于使用单个的蚁群算法或遗传算法， 但效果不是很明显。当规模稍微大一点的时候，遗传蚁群混合算法明显优于蚁 群算法或遗传算法，随着规模地不断增大，性能改进的效果越明显。 6 武汉理工大学硕士学位论文 第2 章遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是h o l l a n d 于1 9 7 5 年受生物进化论的 启发而提出了。遗传算法的提出一定程度上解决了传统的基于符号的处理机制 的人工智能方法在知识表示信息处理和解决组合爆炸等方面所遇到的困难，其 自组织、自适应、自学习和群体进化能力使其适合于大规模复杂优化问题。遗 传算法是基于“适者生存”的一种高度并行、随机和自适应优化算法，它将问 题的求解表示成“染色体”的适者生存过程，通过“染色体”群的一代代不断 进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从 而求得问题的最优解或次优解。 2 1 生物进化及遗传算法基本原理 自从达尔文的进化论得到人们的接受之后，生物学家们就对进化机制产生 了极大的兴趣。化石一记录表明我们所观察到的复杂结构的生命是在相对短的 时间进化而来的，对这一点包括生物学家在内的许多人都感到惊奇。 虽然目前关于推动这个进化的机制还没有完全弄清楚，但它们的某些特征 己为人所知。进化是发生在作为生物体结构编码的染色体上，通过对染色体的 译码部分地生成生物体，但下面几个关于进化理论的一般特性己广为人们所接 受： 1 进化过程发生在染色体上，而不是发生在它们所编码的生物个体上 2 自然选择把染色体以及由它们所译成的结构的表现联系在一起，那些适 应性好的染色体经常比适应性差的染色体有更多的繁殖机会。 3 繁殖过程是进化发生的那一刻，变异可以使生物体子代的染色体不同于 它们父代的染色体，通过结合两个父代染色体中的物质，重组过程，以在子代 中产生有很大差异的染色体。 4 生物进化没有记忆。有关产生个体的信息包含在个体所携带的染色体的 集合以及染色体编码的结构之中，这些个体会很好的适应它们的环境。 大多数生物体是通过自然选择和有性生殖这两种基本过程进行演化的。自然 7 武汉理工大学硕士学位论文 选择的原则是适应者生存，不适应者淘汰。自然选择决定了群体中哪些个体能 够存活并繁殖；有性生殖保证了后代基因中的混合与重组。比起那些仅包含单 个亲本的基因拷贝和依靠偶然变异来改进的后代，这种由基因重组产生的后代 进化要快得多。 遗传算法是基于生物进化理论的原理发展起来的一种广为应用的、高效的 随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息 交换，搜索不依赖于梯度信息。它是在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 d a r t i f i c i a ls y s t e m s ) 。遗传算法最初被研究的出发点 不是为专门解决最优化问题而设计的，它与进化策略、进化规划共同构成了进 化算法的主要框架，都是为当时人工智能的发展服务的迄今为止，遗传算法 是进化算法中最广为人知的算法。近几年来，遗传算法主要在复杂优化问题求 解和工业工程领域应用，并取得了一些令人信服的结果，所以引起了很多人的 关注。而且在发展过程中，进化策略、进化规划和遗传算法之间差异越来越小。 遗传算法是从代表问题可能潜在解集的一个种群开始。其中，种群是由经过 基因编码的一定数目的个体组成，每个个体实际上是带有特征的实体染色体作 为遗传物质的主要载体，即多个基因的集合，其内部表现( 即基因型) 为某种 基因组合，它决定了个体形状的外部表现。因此，在一开始就需要实现从表现 型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进 行简化，如二进制编码，浮点数编码等。初始种群产生之后，按照适者生存和 优胜劣汰的原理，逐代演化，产生越来越好的近似解。在每一代，根据问题域 中个体的适应度大小挑选个体，并借助于自然遗传学的遗传算子进行组合交叉 和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样， 后代种群比前代更加适应环境，末代种群中的最优个体经过解码，可以作为问 题近似最优解。 2 2 遗传算法的基本步骤 遗传算法一般包括参数设计、适应度函数的设计、编码、初始种群的产生、 选择、交叉、变异等操作。 8 武汉理工大学硕士学位论文 1 算法参数的确定。通常包括种群规模、选择概率、交叉概率、变异概率、 进化代数等。 2 确定适应度函数。由于遗传算法通常基于适应度进行遗传操作，因此合 理的适应度函数能够将各个体的优劣程度得以体现，并适应算法的进化过程。 3 确定问题的编码方案。由于遗传算法通常不直接作用于问题的解空间， 而是利用解的某种编码表示来进行进化，因此选择合理的编码机制对算法质量 和效率有很大影响。 4 初始种群的产生。遗传算法是对种群进行的进化操作，这样必须为遗传 操作准备一个由若干初始解组成的初始群体。初始群体的每个个体都是通过随 机方法产生的。 5 遗传算子的设计。通常包括选择、交叉、变异等操作。 6 确定算法的终止条件。终止准则应根据所求解问题的性质，在优化质量 和效率方面作合理均衡或侧重。 具体工作流程图如图2 1 所示 9 武汉理工大学硕士学位论文 图2 - 1 遗传算法的流程图 2 - 3 遗传算法的主要操作 2 3 1 遗传编码 遗传算法的优化过程不是直接作用于问题参数本身，而是在一定编码机制对 应的编码空间上进行的，由问题空间向遗传算法编码空间的映像称作编码，而 由编码空间向问题空间的映像称作解码。编码的选择是影响算法性能与效率的 重要因素，在设计编码策略时，常常考虑以下三个问题： 1 完备性。对问题空间的任何一个点有表达空间的一个点与之对应，即问 题空间的所有可能解都能表示位所设计的基因编码形式 2 非冗余性。问题空间和表达空间一一对应。 二进制编码是遗传算法中最早普遍采用的一种编码方法。在实际应用中为 武汉理工大学硕士学位论文 了更有效地发挥遗传算法的作用，针对特定的问题提出了多种编码方法。下面 介绍几种常用的编码技术。 二进制编码 是将原问题的解映射成0 、1 组成编码串的遗传空间，此操作称为二进制编 码，结果再通过解码过程还原成其解空间的解，然后再进行适应度的计算。 由于很多数值与非数值优化问题都可用二进制编码来应用遗传算法，同时 表达的模式最多，所以二进制编码方法是遗传算法中最常用的一种编码方法， 它具有以下优点： ( 1 ) 编码、解码操作简单易行； ( 2 ) 交叉、变异等遗传操作便于实现； ( 3 ) 符合最小字符集编码原则； ( 4 ) 便于用模式定理进行分析，因为模式定理就是以二进制位基础的。 实数编码 直接采用十进制的实数编码是连续参数优化问题直接的自然描述。在实数 编码情况下，我们将一个实参数矢量对应成一个染色体，一个实数对应一个基 因，一个实值对应成一个等位基因。使用实数编码有以下优点： ( 1 ) 基因以实数编码消除了因编码精度不够，使得搜索空间中具有较优适 应度值的可能解未能够表示出来的隐患。 ( 2 ) 遗传算法用实数编码的基因，具备了利用连续变量函数具有的渐变性 的能力。渐变性表示变量小的变化所引起的对应函数值的变化也是小的。 ( 3 ) 用浮点数编码时应注意： 应保证基因值在给定的区间限制范围内； 在使用交叉、变异等遗传算子时，也必须保证其运算结果所产生的 新个体基因也在同一限制范围内； ( 4 ) 当多个字节来表示一个基因时，交叉运算必须在两个分界字节进行。 g r a y 码编码 g r a y 码编码是二进制编码的一个变种，在求解连续优化问题中，能改进二 进制编码由于遗传算法的随机特性而使其局部搜索能力较差的特性。g r a y 码编 码方法为其连续的两个整数所对应的编码值之间仅仅只有一个编码位是不相同 的，其余编码位都完全相同。 例如，有一个二进制编码为b 岛岛。6 2 h ，其对应的g r a y 码为 1 1 武汉理工大学硕士学位论文 g - g ，g ，1 9 2 9 l ，贝u 满足g j 一饥f i g ，一b l “o 岛，f - ，一1 ，f 一2 ，2 j g r a y 码编码的特点：任意两个整数的差是这两个整数所对应的g r a y 码的海 明距离。 符号编码方法 符号编码方法是指染色体编码中的基因取自一个无数值含义，而只有代码 含义的符号集例如，整数和字母排列编码对于组合优化问题最为有效。由于 组合优化问题最为关键的是寻找满足约束项目的最佳排列或组合，因此字母排 列编码对于这类问题是最有效的方法。 2 3 2 适应度函数 遗传算法将问题空间表示为染色体位串空间，为了执行“适者生存”的原则， 必须对个体位串的适应性进行评价。因此，适应度函数就构成了对个体的生存 能力评价。根据个体的适应度，就可决定它在此环境下的生存能力。一般来说， 好的染色体结构具有比较高的适应度，即可以获得较高的评价，具有较强的生 存能力。 由于适应值群体中个体生存机会选择的唯一确定性指标，所以适应度函数的 形式直接决定着群体的进化行为在函数优化中，适应度函数可由目标函数变 换得到，可以有以下三种处理情况： 1 直接以待求解的目标函数转化为适应度函数，即： 若目标函数为最大化问题纠= g ( 2 - 1 ) 若目标函数为最小化问题日( x ) = g ( x ) ( 2 - 2 ) 2 若目标函数为最小问题，则： f c 。一g ( x ) g b ) c m “ f(x)。j(2-3) i o其它情况 其中系数c ，存在多种选择方法，它可以是一个合适的输入值，也可以用迄 今为止进化过程中g ( x ) 的最大值，但c 一最好与群体无关 若目标函数为最大问题，n - 阽 ) 一c 。 ，o ) 。j 1 0 l g ( 力c 。 ( 2 4 ) 其它情况 武汉理工大学硕士学位论文 其中系数c 。存在多种选择方法，它可以是一个合适的输入值，也可以 采用迄今为止进化过程中g ( x ) 的最小值，但c 。最好与群体无关。 3 若目标函数为最小问题，也可为： ，。) 一丽1 c 苫o , c + g o ) 苫。 ( 2 - 5 ) 若目标函数为最大问题，则： 1 ，o 下盖丽 。o , c - g o ( 2 - 6 ) 上两式c 为目标函数界限的保守估计值。 适应度函数对遗传算法的收敛速度和结果影响很大。如果过分强调当前的较 优解，就可能很快降低种群的多样性，造成不成熟收敛；如果对当前较优解强 调不够，算法就很容易丢失已经找到的较优解信息，从而不能在合理的时间内 收敛到较好的解因此在具体的应用中，适应度函数的设计要结合求解问题本 身的要求而定 2 3 3 遗传算子 遗传算法一般包括选择、交叉和变异三种。它们构成了遗传算法具备强大搜 索能力的核心是模拟自然选择以及遗传过程中发生的繁殖、杂交和突变现象 的主要载体利用遗传算子产生新一代群体，实现群体进化。 1 选择算子 选择算子( 或称复制算子) 是对群体中的个体按优胜劣汰的方式选取，并遗 传到下一代群体的运算操作，它是建立在群体中个体的适应度评估基础上的。 适应度较高的个体被遗传到下一代群体中的概率较大，适应度较低的个体被遗 传到下一代群体中的概率较小。通过选择操作可以避免基因缺失，提高全局收 敛性和计算效率。 目前，主要的选择算子方法有适应度比例选择法、最佳个体保存法、排序选 择法、期望值法等形式。 ( 1 ) 适应度比例选择法 适应度比例选择法是基本的选择方法，也叫赌轮或蒙特卡罗选择。该方法 的基本思想是：各个个体被选中的概率与其适应度大小成正比。 设种群大小为m ，个体i 的适应度为只，则个体f 被选中的概率只为： 武汉理工大学硕士学位论文 a 导( i - 1 , 2 , m ) p i 。靠 1( 2 7 ) 显然，概率只反映了个体i 的适应度在整个群体的个体适应度总和中所占的 比例，个体适应度越大，其被选择的概率就越高，反之亦然。 ( 2 ) 最佳个体保存法 该方法的思想是把种群中适应度最高的个体不进行配对交叉而直接复制到 下一代中，当然这样做的前提是下一代中不存在该个体。 采用该方法的优点是，进化过程中某一代的最优解可不被交叉或变异操作破 坏。但是，这也隐含了一种危机，即局部最优个体的遗传基因会急速增加而使 进化有可能陷于局部解。也就是说，该方法的全局搜索能力差，它适合于单峰 性质优化问题的空间搜索，而不适合于多峰性质的空间搜索。所以此方法一般 与其它选择方法结合使用。 ( 3 ) 排序选择法 排序选择法的基本思想是在计算出每个个体适应度后，根据适应度大小在群 体中对个体排序，然后把事先设计好的概率表按序分配给个体，作为各自的选 择概率。 这种方法的不足之处在于选择概率和序号的关系需事先确定。此外，它和适 应度比例法一样都是一种基于概率的选择，所以仍有统计误差 ( 4 ) 期望值法 当个体数不太多时，适应度比例选择法有时因随机数可能会出现不正确地反 映个体的选择，即存在统计误差，也就是说，适应度高的个体有可能被淘汰， 适应度低的个体也有可能被选择。为了克服这种缺点，期望值法的基本思想是 根据每个个体在下一代群体中的生存期望来进行随机选择运算。 2 交叉算子 交叉算子用于组合出新的个体，在解空间中进行有效搜索，同时降低对有效 模式的破坏概率。 遗传算法的二进制编码通常采用单点交叉和多点交叉。 ( 1 ) 单点交叉 首先随机确定一个交叉位置，然后对换交叉点后的子串。譬如，父串为 ( 1 0 1 1 1 0 0 1 ) 和( 0 0 1 0 1 1 1 0 ) ，若单点交叉位置为4 ，则后代个体为( 1 0 1 1 1 1 1 0 ) 和( 0 0 1 0 1 0 0 1 ) 。 1 4 武汉理工大学硕士学位论文 ( 2 ) 多点交叉 首先随机确定多个交叉位置，然后对换相应的子串。若两点交叉，交叉榧 为2 、5 ，父代个体同上，则后代个体为( 1 0 i l o l l o d 和( 0 0 1 1 1 0 1 1 0 ) 。 遗传算法的十进制编码的交叉操作类似于遗传算法的二进制编码。 遗传算法的实数编码通常采用双个体算术交叉或多个体算术交叉。 ( 1 ) 双个体算术交叉 针对选中的两个个体进行交叉，即- 4 畸+ ( 1 一a ) x 2 ，t - 口吃+ ( 1 4 h ， 中随机数a e ( o , 1 ) ，而，毛为父代个体，t 为后代个体。 ( 2 ) 多个体算术交叉 对多个选中个体进行交叉，即x 。- 口而+ + 口毛，其中薯为父代个体，| 后代个体，罗4 l - 1 r a 。【0 1 】 筒 3 变异算子 当交叉操作产生的后代适应度不再进化且没有达到最优时，就意味着篑 的早熟收敛。这种现象的根源在于有效基因的缺损，变异操作在一定程度_ f 服了这种情况，有利于增加种群的多样性。 二进制或十进制编码中通常采用单位置换或多位置替换式变异，即用夏 种基因替换某一位置或某些位置上原先的基因。 实数编码中通常采用扰动式变异，即对原先个体附加一定机制的扰动身 现变异，即工- 工+ n 4 ，其中工和x 分别为新旧个体，叩为扰动幅度参数，j 随机扰动变量。言可以服从高斯分布、柯西分布、均匀分布 组合优化问题中的遗传算法的变异操作通常采用互换、逆序和插入操作 ( 1 ) 互换操作( s w a p ) ，即随机交换染色体中两不同基因的位置。 ( 2 ) 逆序操作( 小) ，即将染色体中两不同随机位置间的基因串逆序 ( 3 ) 插入操作( 玳s ) ，即随机选择某个点插入到串中的不同随机位置。 譬如，若状态为( 5 4 1 7 9 8 6 2 3 ) ，两随机位置为2 、6 ，则s w a p 的结界 ( 5 8 1 7 9 4 6 2 3 ) ，i n v 的结果为( 5 8 9 7 1 4 6 2 3 ) ，玳s 的结果为( 5