下载文档原格式
资源受限项目调度问题综述摘要针对资源受限项目调度问题，总结国内外项目调度的发展过程及研究成果。
在对问题的类型进行分类的基础上，结合大量文献对常见的算法进行描述并重点介绍了关键技术的研究状况。
进一步地，将资源受限项目调度问题做进一步的拓展，简略介绍多目标、多项目、任务可拆分的项目调度问题。
最后对问题进行总结，并提出自己的看法。
0 引言现代项目越来越趋于大型化、复杂化，要求工期更短、成本更低。
再加上行业细分越来越发达这种新情况给项目管理带来了更高的要求。
如何在更短时间内、在保证质量的前提下，以更低的成本完成项目，成为项目管理人员关心的问题。
在项目运作过程中，资源受限项目调度问题RCPSP(resource-constrained project scheduling problem)是一个重要的优化问题，它是最常见的生产调度问题，是项目管理中最为经典和核心的问题之一1项目调度发展过程项目调度问题自20世纪中期被提出来，传统的计划技术有甘特图（又称横道图，Gant Chart,Gc）、关键活动图、网络计划技术。
几种典型的网络计划技术有：关键路径发（Critical Path Method,CPM）、项目计划评审技术（Program Evaluation and Review Technique,PERT）、优先图方法（PDM）、图解评审技术（Graphical Evaluation and Review,GERT）、风险评审技术（Venture Evaluation and Review Technique,VERT）.最初被广泛应用于项目进度计划的工具是甘特图技术，它用二维坐标的形式，用线条在二维空间中表似乎出整个项目期间计划和实际的活动完成情况，直观表明项目中所含各项活动的执行顺序，以及每项活动的开始/结束时间和持续时间。
该方法形象直观，易于掌握，但是不能体现工作间的相互依赖关系，不能体现工作过早开始或者过完开始所造成的后果。
课程设计报告设计题目：基于进化算法的车辆路径问题求解学院：电子工程学院专业：电子信息工程班级： 020915 学号：学生姓名：电子邮件：时间： 20012年9月成绩：指导教师：刘静西 安 电 子 科 技 大 学 电 子 工 程 学 院 课 程 设 计（报告）任 务 书 学生姓名 指导教师 职称 教授 学生学号 专业 电子信息工程 题目 基于进化算法的车辆路径问题求解 任务与要求 了解进化算法（Evolutionary Algorithms ），介绍其基本思想、主要分支于基本流程。
了解车辆路径问题（Vehicle RoutingProblems ），介绍其基本分类、各类问题的具体模型与异同点。
最后给出一种进化算法求解某类车辆路径问题的基本方法。
开始日期 2012 年 8 月 27 日 完成日期 2012年 9 月 7 日 课程设计所在单位 智能信息处理所研究所 2102年 9月 7 日…………………………装………………………………订………………………………线………………………………………………………………摘要随着社会主义市场经济的发展，作为“第三利润源泉”的物流对经济活动的影响日益明显，物流配送业得到了迅速发展。
物流车辆路径优化调度，是物流配送中的关键环节，对企业提高服务质量、降低物流成本、增加经济效益的影响也较大。
在现实生产和生活中，邮政投递问题、公共汽车调度问题、电力调度问题、管道铺设问题、机器人路径规划、计算机网络拓扑设计问题等都可以抽象为物流配送车辆调度问题。
物流配送车辆路径调度问题作为一个NP难题，可选的配送路径方案计算量将随着客户数量的增加以指数速度急剧增长。
进化算法是基于生物进化机制的搜索算法，适合于求解复杂系统优化问题，特别是组合优化问题有明显的优势。
因此，用进化算法求解该问题就成为人们研究的一个重要方向。
本文在对国内外物流配送车辆调度现状及其实现技术对比的基础上，结合vRP(vehieleRoutingProblem)问题模型，研究了进化算法解决车辆路径问题的方法，并开发了基于进化算法的智能物流配送系统。
第１４卷㊀第２期Ｖｏｌ．１４Ｎｏ．２㊀㊀智㊀能㊀计㊀算㊀机㊀与㊀应㊀用ＩｎｔｅｌｌｉｇｅｎｔＣｏｍｐｕｔｅｒａｎｄＡｐｐｌｉｃａｔｉｏｎｓ㊀㊀２０２４年２月㊀Ｆｅｂ．２０２４㊀㊀㊀㊀㊀㊀文章编号：２０９５－２１６３（２０２４）０２－０１３３－０７中图分类号：ＴＰ３０１文献标志码：Ａ考虑运输时间的柔性作业车间调度问题研究冯旭青，尹瑞雪（贵州大学机械工程学院，贵阳５５００２５）摘㊀要：针对工件实际加工过程中工件转移的重要性，对运输时间的柔性作业车间调度问题进行优化研究，建立了以最小化最大完工时间和总碳排放量为优化目标的调度数学模型，并提出了一种改进的ＮＳＧＡ－Ⅱ算法㊂算法采用基于工序和机器特征的双链式编码方法，设计了针对工件运输时间的插入式解码操作；为探索到更优的前沿解设计了一种局部邻域搜索策略；基于非支配解引入了节能低碳策略进行排放量调整；通过仿真实验对比结果，表明了改进ＮＳＧＡ－Ⅱ算法及其求解考虑运输时间的柔性作业车间调度问题的有效性㊂关键词：柔性作业车间；运输时间；ＮＳＧＡ－Ⅱ算法；局部邻域搜索策略ＲｅｓｅａｒｃｈｏｎｔｈｅｆｌｅｘｉｂｌｅｊｏｂｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｃｏｎｓｉｄｅｒｉｎｇｔｒａｎｓｐｏｒｔａｔｉｏｎｔｉｍｅＦＥＮＧＸｕｑｉｎｇ，ＹＩＮＲｕｉｘｕｅ（ＳｃｈｏｏｌｏｆＭｅｃｈａｎｉｃａｌＥｎｇｉｎｅｅｒｉｎｇ，ＧｕｉｚｈｏｕＵｎｉｖｅｒｓｉｔｙ，Ｇｕｉｙａｎｇ５５００２５，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｇｉｖｅｎｔｈｅｓｉｇｎｉｆｉｃａｎｃｅｏｆｗｏｒｋｐｉｅｃｅｔｒａｎｓｆｅｒｓｉｎａｃｔｕａｌｍａｃｈｉｎｉｎｇｐｒｏｃｅｓｓｅｓ，ｔｈｉｓｓｔｕｄｙｃｏｎｄｕｃｔｓｏｐｔｉｍｉｚａｔｉｏｎｒｅｓｅａｒｃｈｏｎｔｈｅｆｌｅｘｉｂｌｅｊｏｂｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｃｏｎｓｉｄｅｒｉｎｇｔｒａｎｓｐｏｒｔａｔｉｏｎｔｉｍｅ．Ｉｔｅｓｔａｂｌｉｓｈｅｓａｓｃｈｅｄｕｌｉｎｇｍａｔｈｅｍａｔｉｃａｌｍｏｄｅｌｗｉｔｈｔｈｅｏｂｊｅｃｔｉｖｅｓｏｆｍｉｎｉｍｉｚｉｎｇｔｈｅｍａｘｉｍｕｍｃｏｍｐｌｅｔｉｏｎｔｉｍｅａｎｄｔｈｅｔｏｔａｌｃａｒｂｏｎｅｍｉｓｓｉｏｎｓ．Ｆｕｒｔｈｅｒｍｏｒｅ，ａｎｉｍｐｒｏｖｅｄＮＳＧＡ－ＩＩａｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄ．Ｔｈｅａｌｇｏｒｉｔｈｍｕｔｉｌｉｚｅｓａｄｕａｌ－ｃｈａｉｎｃｏｄｉｎｇｍｅｔｈｏｄｂａｓｅｄｏｎｏｐｅｒａｔｉｏｎａｎｄｍａｃｈｉｎｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓ，ａｌｏｎｇｗｉｔｈａｎｉｎｓｅｒｔｉｏｎ－ｂａｓｅｄｄｅｃｏｄｉｎｇｏｐｅｒａｔｉｏｎｆｏｒｗｏｒｋｐｉｅｃｅｔｒａｎｓｐｏｒｔａｔｉｏｎｔｉｍｅ．Ａｄｄｉｔｉｏｎａｌｌｙ，ｔｈｉｓｒｅｓｅａｒｃｈｉｎｔｒｏｄｕｃｅｓａｌｏｃａｌｎｅｉｇｈｂｏｒｈｏｏｄｓｅａｒｃｈｓｔｒａｔｅｇｙｔｏｅｘｐｌｏｒｅｂｅｔｔｅｒＰａｒｅｔｏｆｒｏｎｔｓｏｌｕｔｉｏｎｓａｎｄｉｎｃｏｒｐｏｒａｔｅｓａｎｅｎｅｒｇｙ－ｓａｖｉｎｇａｎｄｌｏｗ－ｃａｒｂｏｎｓｔｒａｔｅｇｙｆｏｒｅｍｉｓｓｉｏｎａｄｊｕｓｔｍｅｎｔｂａｓｅｄｏｎｎｏｎ⁃ｄｏｍｉｎａｔｅｄｓｏｌｕｔｉｏｎｓ．Ｔｈｒｏｕｇｈｃｏｍｐａｒａｔｉｖｅｓｉｍｕｌａｔｉｏｎｅｘｐｅｒｉｍｅｎｔｓ，ｔｈｅｒｅｓｕｌｔｓｄｅｍｏｎｓｔｒａｔｅｔｈｅｅｆｆｅｃｔｉｖｅｎｅｓｓｏｆｔｈｅｅｎｈａｎｃｅｄＮＳＧＡ－ＩＩａｌｇｏｒｉｔｈｍｉｎａｄｄｒｅｓｓｉｎｇｔｈｅｆｌｅｘｉｂｌｅｊｏｂｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｗｉｔｈｔｒａｎｓｐｏｒｔａｔｉｏｎｔｉｍｅｃｏｎｓｉｄｅｒａｔｉｏｎｓ．Ｋｅｙｗｏｒｄｓ：ｆｌｅｘｉｂｌｅｊｏｂｓｈｏｐ；ｔｒａｎｓｐｏｒｔｔｉｍｅ；ＮＳＧＡ－ＩＩａｌｇｏｒｉｔｈｍ；ｌｏｃａｌｎｅｉｇｈｂｏｒｈｏｏｄｓｅａｒｃｈｓｔｒａｔｅｇｙ基金项目：国家自然科学基金（５１７６５０１０）㊂作者简介：冯旭青（１９９７－），女，硕士研究生，主要研究方向：绿色设计与制造㊂通讯作者：尹瑞雪（１９７６－），女，博士，教授，硕士生导师，主要研究方向：绿色设计与制造㊂Ｅｍａｉｌ：ｙｉｎｒｕｉｘｕｅ＠ｓｉｎａ．ｃｏｍ收稿日期：２０２３－０２－１７０㊀引㊀言随着工业的不断发展，制造业处于能源消耗的主体位置㊂据研究表明，中国制造业在全国范围内消耗的电能达５０％以上，随之产生的二氧化碳排放量不少于２６％［１］㊂降低制造能源消耗主要有两种方法，一是研发高性能的节能机床设备，但往往需要高额成本投入；二是车间调度优化，在基于现有的企业资源条件下，在一定程度上可以满足节能减排的需求㊂柔性作业车间调度问题（ＦｌｅｘｉｂｌｅＪｏｂＳｈｏｐＳｃｈｅｄｕｌｅＰｒｏｂｌｅｍ，ＦＪＳＰ）自１９９０年被首次提出以来［２］，由于其工件加工路径柔性与设备选择灵活性的特点，已是相关调度研究领域的重点之一㊂研究人员就ＦＪＳＰ的优化求解展开了大量的研究，Ｄｉｎｇ等［３］从编码和解码操作㊁粒子间通信机制等方面对粒子群优化算法进行改进；王玉芳等［４］设计了一种改进的混合蛙跳算法优化最大完工时间；赵小惠等［５］改进了蚁群算法，用以提高ＦＪＳＰ优化求解的效率；李宝帅等［６］通过引入正余弦算法策略改进鲸鱼优化算法，以实现完工时间的优化；杜凌浩等［７］设计了种群间的协同策略来优化完工时间；Ｌｉ等［８］提出了一种改进多目标蜂群算法，以优化最小化最大完工时间㊁机床总负载以及最大机床负载；吴秀丽等［９］为求解总成本和提前／延期惩罚双目标分布式ＦＪＳＰ模型，提出了改进差分进化算法㊂综上所述，以往研究多以加工时间相关目标为主，缺少对车间生产的碳排放及机床能源消耗相关调度优化目标的关注，且优化时间指标多以单目标优化为主㊂此外，要求工件加工当前工序的加工结束时即可开始下一道工序的加工，在调度模型中加以这一约束，从而忽略了加工过程中工件在机器间转移所消耗的运输时间㊂通常来说，车间中机床按加工精度㊁加工方式等可分为多种，且用途不完全相同㊂工件不同工序也需要在具有不同加工工艺的机床上完成加工，并且工件转移过程消耗的运输时间与加工时间存在耦合关系㊂因此，考虑到工件各工序在机器间的转移过程客观存在，本文在以上研究的基础上，将运输时间的柔性作业车间调度问题（ＦｌｅｘｉｂｌｅＪｏｂＳｈｏｐＳｃｈｅｄｕｌｉｎｇＰｒｏｂｌｅｍｗｉｔｈＴｒａｎｓｐｏｒｔａｔｉｏｎｔｉｍｅ，ＦＪＳＰ－Ｔ）作为研究对象，构建以最小化最大完工时间和总碳排放量为优化目标的调度优化模型，并设计了一种改进的ＮＳＧＡ－Ⅱ算法进行求解㊂通过与常用的多目标优化算法就标准案例和实例进行测试对比分析，验证了ＩＮＳＧＡ－Ⅱ算法的有效性㊂１㊀ＦＪＳＰ－Ｔ问题描述与模型建立１．１㊀问题描述考虑运输时间的柔性作业，车间调度问题可描述为：有ｎ个工件等待分配到ｍ台机器上完成其加工任务㊂每个工件Ｊｉ有一道或多道工序，同一个工件中的工序加工顺序为已知；每道工序可供加工的机器不止一台，组成各工件的可加工机器集㊂每道工序根据调度规则，从其加工机器集合中选择其一；已知工序在机器之间进行转移所消耗的运输时间；以及在其可加工机器集合中各加工机器上的加工时间与碳排放量，根据选择加工机器的不同而改变㊂１．２㊀模型建立为方便建立调度优化模型，参数定义见表１㊂表１㊀ＦＪＳＰ－Ｔ模型参数表Ｔａｂｌｅ１㊀ＰａｒａｍｅｔｅｒｓｏｆＦＪＳＰ－Ｔｍｏｄｅｌ符号参数含义ｎ工件总数ｍ机器总数Ｊ所有工件的集合，Ｊ＝｛Ｊ１，Ｊ２， ，Ｊｎ｝，ｉɪ［１，ｎ］Ｍ所有机器的集合，Ｍ＝｛Ｍ１，Ｍ２， ，Ｍｍ｝，ｊɪ［１，ｍ］ｐｉ工序数Ｃｍａｘ最大完工时间Ｐｋｉｊ工序Ｏｉｊ在机器Ｍｋ上的加工时间Ｏｉｊ工件ｉ的第ｊ道工序Ｃｉ工件ｉ的完工时间ＴｏｋＭｋ的开机时间ＴｃｋＭｋ的关机时间ＴｐｒｅｋＭｋ的待机时间Ｔｏｂｉｊｋ工序Ｏｉｊ在机器Ｍｋ上加工时间Ｔｋｉｊ，ｈ工序Ｏｉ（ｊ－１）的加工机器Ｍｈ运输到工序Ｏｉｊ加工机器Ｍｋ的运输时间ＥｏｋＭｋ在开机状态下单位时间碳排放量ＥｃｋＭｋ在关机状态下单位时间碳排放量ＥｐｒｅｋＭｋ在待机状态下单位时间碳排放量ＥｏｂｋＭｋ在加工状态下单位时间碳排放量Ｐｔｒａｎｓ运输设备功率δ电能碳排放转换因子Ｙｋｉｊ决策变量，若工序Ｏｉｊ在机器Ｍｋ上加工，则Ｙｋｉｊ＝１，否则取０Ｘｏｃｋ决策变量，若机床Ｍｋ上所有工件加工完成，则Ｘｏｃｋ＝１，否则取０Ｘｉｊｋ决策变量，若工序Ｏｉｊ在机床上加工，则Ｘｉｊｋ＝１，否则为０４３１智㊀能㊀计㊀算㊀机㊀与㊀应㊀用㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀第１４卷㊀㊀㊀本文综合考虑最大完工时间和总碳排放量，将建立双目标协同优化的ＦＪＳＰ－Ｔ模型表示如下：目标函数：（１）最小化最大完工时间（单位：ｍｉｎ）最大完工时间是衡量工厂能否准时完成加工任务的重要指标，对其优化在一定程度上能提高车间的生产效率，可用式（１） 式（２）计算：ｆ１＝ｍｉｎＣｍａｘ＝ｍｉｎ（ｍａｘ｛Ｃｉ｝），ｉɪ［１，ｎ］（１）Ｃｉ＝ðｐｉｊ＝１ðｍｋ＝１（Ｐｋｉｊ＋Ｔｋｉｊ，ｈ）㊃Ｙｋｉｊ，ｈɪ［１，ｍ］（２）㊀㊀（２）最小化总碳排放量（单位：ｋｇＣＯ２）车间加工过程中，能耗大多由机床加工生产过程中产生，机床一次开机关机碳排放量（Ｑｏｃ）㊁待机碳排放量（Ｑｐｒｅ）㊁加工碳排放量（Ｑｏｂ）以及运输碳排放量（Ｑｔｒａｎｓ），可用式（３） 式（７）计算得出：ｆ２＝ＱＣＰ＝Ｑｏｃ＋Ｑｐｒｅ＋Ｑｏｂ＋Ｑｔｒａｎｓ（３）Ｑｏｃ＝Ｑｏ＋Ｑｃ＝ðｍｋ＝１Ｅｏｋ㊃Ｔｏｋ＋Ｅｃｋ㊃Ｔｃｋ()㊃Ｘｏｃｋ（４）Ｑｐｒｅ＝ðｍｋ＝１Ｅｐｒｅｋ㊃Ｔｐｒｅｋ（５）Ｑｏｂ＝ðｍｋ＝１Ｅｏｂｋ㊃Ｔｏｂｉｊｋ㊃Ｘｉｊｋ（６）Ｑｔｒａｎｓ＝ðｎｉ＝１ðｐｉｊ＝１Ｐｔｒａｎｓ㊃Ｔｋｉｊ，ｈ㊃δ，ｈɪ［１，ｍ］，ｋɪ［１，ｍ］（７）㊀㊀式（３）中，ＱＣＰ为总碳排放量，式（４） 式（７）中，ＱＯ㊁ＱＣ㊁Ｑｐｒｅ㊁Ｑｏｂ和Ｑｔｒａｎｓ分别为机器Ｍｋ处于开机㊁关机㊁待机㊁加工状态以及运输过程的碳排放总量㊂约束条件：Ｔｋｉｊ，ｈȡ０，ｉɪ［１，ｎ］，ｋɪ［１，ｍ］，ｊ，ｈɪ［１，ｍ］（８）Ｔｋｉ１，ｈ＝０，ｉɪ［１，ｎ］，ｋɪ［１，ｍ］，ｊ，ｈɪ［１，ｍ］（９）Ｃｉȡ０，ｉɪ［１，ｎ］（１０）ＴｓｋｉｊȡＰｋｉ（ｊ－１）＋Ｔｋｉ（ｊ－１），ｈ（１１）㊀㊀式（８）和式（１０）分别约束每道工序在机器之间的运输时间和每道工序完工时间为非负；式（９）约束任何一个工件的第一道工序都不考虑运输时间；式（１１）约束工序的开工时间不小于前一道工序的加工时间与运输时间之和㊂２㊀ＮＳＧＡ－Ⅱ算法改进２．１㊀编码与解码为了解决调度车间的工序排序以及机器指派这两个子问题，本文根据工序以及机器的特征，采用并行双链式实数编码方法如图１所示，上下编码染色体长度相当㊂上层表示工序编码染色体，以工件号及其出现的次数表示工序号；下层是机器编码染色体，其中编码数字代表了同一位置工序所选择的加工机器号㊂同一位置（用ｉｎｄｅｘ表示）的工序与机器基因构成基因信息组，ｉｎｄｅｘ＝１表示工序Ｏ２１在机器Ｍ１上加工，所有位置的工序与机器编码组成一个ＦＪＳＰ－Ｔ的调度可行方案㊂工件编码2312311M1M1M3M2M1M3M3机器编码O21O31O11O22O32O12O131132133图１㊀编码染色体Ｆｉｇ．１㊀Ｃｏｄｉｎｇｃｈｒｏｍｏｓｏｍｅｓ㊀㊀初始化种群采用随机初始化生成方式，即将所有工序随机排序方式获取工序编码方案，避免算法优化初期消耗过多的时间，而着重迭代过程中更加优秀调度解的探索㊂工序编码方案确定后，对应工序基因在其可加工机器集中任选一台加工机器构成机器编码染色体，按该方法生成大小为Ｐｏｐｓｉｚｅ的初始种群㊂解码操作是对编码染色体的翻译过程，在满足调度约束的条件下，为工序指派加工机床以获取调度方案［１０］㊂工件在转移过程中，消耗的运输时间会增加工件总完工时间从而改变调度结果，因此在解码操作中基于运输时间设计改进的插入式解码方法，根据工件与机器的不同状态可分为：（１）工序是首道工序，所选的加工机器是首次进行加工，则不考虑运输时间直接安排加工㊂（２）工序是首道工序但不是其加工机器上的首道加工工序，则判断该工序在所选加工机器上的加工顺序，取出前一道工序结束加工的时间，将其作为此工序的开始加工时间㊂（３）工序是非首道工序，机器非首次加工，考虑该工序与同一个工件的上道工序是否在同一机器上加工，如果是同一机器加工无需进行工件转移，则该工序的开始时间为同一个工件上道工序的完工时间，否则本工序需要考虑运输时间；若当前加工机器上存在可进行工序插入的时间段，将其加入到允许５３１第２期冯旭青，等：考虑运输时间的柔性作业车间调度问题研究位置，更新完工时间㊂２．２㊀交叉和变异操作交叉和变异操作是算法迭代优化求解调度最优解的核心环节，通过基因交叉重组和突变保留个体中优秀基因并保持种群的多样性，还可以增强算法的搜索性能㊂以染色体Ｐ１和Ｐ２为例，描述工序编码染色体和机器编码染色体进行交叉操作后产生子代染色体Ｃ１的过程㊂Ｐ１和Ｐ２的总工序数为８，工件总数为３，机器总数为３；工序染色体采用ＰＯＸ交叉［１１］；机器染色体进行交叉操作方法如下：（１）随机生成一个元素仅为０和１，且长度等于总工序数的数组，如［０，０，１，１，０，０，１，０］，其中０元素所在位置为Ｎ＝［１，２，５，６，８］；（２）依次找到Ｎ中元素对应Ｐ１中工序号的加工机器，将其与父代Ｐ２中对应工序的加工机器进行交换㊂经过机器交叉操作后，工序没有发生变换，对应机器交叉点的机器进行交叉，如图２所示㊂P1 P2 C321321331 3122133113112323 2213132221321331 12221333图２㊀机器交叉示意图Ｆｉｇ．２㊀Ｍａｃｈｉｎｅｃｒｏｓｓｄｉａｇｒａｍ㊀㊀染色体在进行变异操作时采用动态变异概率，用式（１２）计算：Ｐｍ＝Ｐ０＋β（ｇｅｎ／Ｍａｘｇｅｎ）（１２）式中：Ｐｍ为动态变异概率，Ｐ０为初始变异概率，β为变异概率调整系数，ｇｅｎ和Ｍａｘｇｅｎ表示当前和最大迭代次数㊂工序变异执行两个变异点工序互换的方式，进行工序互换得到新染色体可能存在非可行解，需再进行染色体修复；机器变异则是再随机生成两个变异点，将两变异位置的机器分别更换为各自在其加工机器集中的最短加工时间的机器㊂２．３㊀局部邻域搜索策略和节能策略通过对种群中每个染色体进行邻域搜索，帮助算法在寻优过程中跳出局部收敛㊂本文设计了一种局部领域搜索策略，对工序采用两点变异，将两个变异位置工序进行互换后，对其机器编码染色体采用单点变异的方式，先确定变异点为变异位置的工序从其可加工机器集中任意择其一，从而构成了其局部邻域解㊂重复上述操作，直至种群中所有个体完成其邻域解的探索㊂为进一步挖掘车间节能潜力，引入调度节能方法中常用的关机重启策略［１２］，该策略旨在减少各机床待机时段的能量消耗，以实现节能减排的最终目标㊂若机床的待机时间过长，将考虑是否使用关机重启策略，而机床重启次数过多会在一定程度上减少使用时间，从而降低机床的寿命㊂因此，机床是否采用关机重启策略，需要满足条件约束，即机床待机时长大于当前机床关机重启策略的时间；且待机碳排放要高于机床关机重启的能量消耗，以确保在不损坏机床寿命的同时实现节能减排㊂２．４㊀算法实现步骤ＩＮＳＧＡ－Ⅱ算法主要步骤描述如下：（１）设置算法初始化参数，其中包括种群规模㊁迭代次数㊁交叉概率等，并生成初始化种群；（２）通过锦标赛方法选出适合繁殖的染色体，组成父代种群；（３）对父代种群中的个体通过基因突变和相互交叉的方式，探索出新的解，组成子代种群；（４）合并子父种群个体后，解码并进行非支配排序和拥挤度的计算，获得下一代种群个体；（５）如果达到算法终止条件，即最大迭待次数，则输出最优的ｐａｒｅｔｏ前沿解集，否则转至步骤２继续迭代求解㊂３㊀实验分析本文算法在ＭＡＴＬＡＢＲ２０１６ｂ软件上实现，运行环境为：１２ｔｈＧｅｎＩｎｔｅｌ（Ｒ）Ｃｏｒｅ（ＴＭ）ｉ５－１２５００Ｈ２．５０ＧＨｚ处理器，１６．０ＧＢ的内存㊂ＩＮＳＧＡ－Ⅱ算法参数设置为：种群规模Ｐｏｐｓｉｚｅ＝１００，迭代次数Ｍａｘｇｅｎ＝１００，交叉概率Ｐｃ＝０．８，初始变异概率Ｐ０＝０．０５，变异概率调整系数β＝０．４㊂算法采用多目标优化问题求解中得到广泛应用的覆盖率Ｃ［１３－１４］和非支配解数量Ｖｉｎ作为算法评价指标㊂覆盖率Ｃ的计算方法如式（１３）：Ｃ（Ｘ，Ｙ）＝１｜Ｙ｜（｜｛ｙɪＹ｜∃ｘɪＸ：ｘ≻ｙ｝｜）（１３）式中：Ｘ㊁Ｙ分别表示算法Ｘ㊁Ｙ的非支配前沿解，｜Ｙ｜６３１智㊀能㊀计㊀算㊀机㊀与㊀应㊀用㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀第１４卷㊀为算法Ｙ非支配解集的大小，Ｃ（Ｘ，Ｙ）的值越大表示算法Ｘ越好㊂此外，Ｖｉｎ表示算法ｉ的最优非支配解的个数，其值越大越好㊂３．１㊀算法比较分析为验证ＩＮＳＧＡ－Ⅱ算法在ＦＪＳＰ优化求解的有效性，选取Ｋａｃｅｍ等人［１５］提出的不同规模标准案例进行仿真测试，优化目标为最大完工时间㊂将ＩＮＳＧＡ－Ⅱ算法（记为Ａ）与ＩＷＯＡ算法［１６］（记为Ａ１）㊁ＨＡ算法［１７］（记为Ａ２）和强化学习的ＩＮＳＧＡ２算法［１８］（记为Ａ３）均求解不同大小的测试案例，比较各算法的最优解，并计算ＩＮＳＧＡ－Ⅱ对比其余算法的提升效果见表２㊂其中，ｎˑｍ为ｎ个工件在ｍ台机器上加工， 表示文献未给出求解结果，加粗体为测试案例的最优解㊂表２㊀Ｋａｃｅｍ案例求解结果比较Ｔａｂｌｅ２㊀ＣｏｍｐａｒｉｓｏｎｏｆｓｏｌｕｔｉｏｎｓｏｎＫａｃｅｍｃａｓｅ算例ｎˑｍＡ１Ａ２Ａ３Ａ算法对比提升效果／％Ａ１Ａ２Ａ３４ˑ５１１１１１１１１０００８ˑ８１４１５１５１４０６．７６．７１０ˑ７１３１３１３１１１５．３８１５．３８１５．３８１０ˑ１０７７ ７００ １５ˑ１０１４１２１５１２１４．２９２００㊀㊀分析表２可知，ＩＮＳＧＡ－Ⅱ算法在前４个Ｋａｃｅｍ案例上取得了调度最优解；在Ｋａｃｅｍ１０ˑ７案例的最优解表现优于ＩＷＯＡ算法㊁ＩＮＳＧＡ２算法以及ＨＡ算法，提升效果达到１５．３８％；Ｋａｃｅｍ８ˑ８案例相较于ＨＡ和ＩＮＳＧＡ２算法提升了６．７％，与ＩＷＯＡ算法取得同样的最优解㊂此外，ＩＮＳＧＡ－Ⅱ算法在Ｋａｃｅｍ１５ˑ１０案例优化求解中相较于ＨＡ算法达到了２０％㊂由此可知，本文提出的ＩＮＳＧＡ－Ⅱ算法表现出了ＦＪＳＰ的优化求解相较于其他算法的有效性㊂３．２㊀改进策略有效性验证为了进一步验证算法设计的局部搜索策略与关机重启策略的有效性，选用文献［１９］中６个工件在６台机器上加工的柔性制造车间加工实例进行测试㊂该柔性制造车间实例包括：工序在机器上的加工时间㊁加工单位碳排放量卸载时间㊁机器启动㊁卸载；准备阶段的单位碳排放量（单位：ｋｇ（ＣＯ２）／（ｋＷ㊃ｈ））以及启动时间（单位：ｍｉｎ）单位碳排放量㊂参考文献［１４］拓展运输设备功耗为２ｋＷ，运输时间和实例数据详见表３ 表５；电能碳排放转换因子参照文献［２０］设置为０．８０４２；参照文献［１２］，加工任务中所有机床最大允许关机重启次数为３㊂表３㊀实例运输时间Ｔａｂｌｅ３㊀Ｔｈｅｔｒａｎｓｐｏｒｔａｔｉｏｎｔｉｍｅｏｆｄｉｆｆｅｒｅｎｔｉｎｓｔａｎｃｅｓ机器机器Ｍ１Ｍ２Ｍ３Ｍ４Ｍ５Ｍ６Ｍ１０６．７４６．７７８．６６１０．８５９．９２Ｍ２６．７４０６．３２７．６８８．６５７．２０Ｍ３６．７７６．３２０７．８３４．４６６．１６Ｍ４８．６６７．６８７．８３０８．２５６．９１Ｍ５１０．８５８．６５４．４６８．２５０７．７７Ｍ６９．９２７．２０６．１６６．９１７．７７０表４㊀柔性制造车间各工件在机器上的加工数据Ｔａｂｌｅ４㊀Ｍａｃｈｉｎｉｎｇｄａｔａｏｆｗｏｒｋｐｉｅｃｅｓｏｎｍａｃｈｉｎｅｉｎｆｌｅｘｉｂｌｅｍａｎｕｆａｃｔｕｒｉｎｇｗｏｒｋｓｈｏｐ工件加工时间／加工阶段单位碳排放量／卸载时间Ｍ１Ｍ２Ｍ３Ｍ４Ｍ５Ｍ６Ｏ１１９／３／１１３／２／１ １３／２／１ １３／２／１Ｏ１２ ７／３／１５／２．１／１１４／２／２１３／３／２ Ｏ１３ ５／２．４／１ １５／２／１７／１．７／１Ｏ１４１２／２／１ １４／２／２１２／２／１ Ｏ１５６／３．１／１６／３．２／１８／１．５／１７／２／１４／１．２／１８／１．５／１Ｏ１６ １５／１．６／２ １３／３／１１５／１．６／１Ｏ２１１３／１．５／１ ４／１／１１６／２．３／１１１／２．５／１ Ｏ２２ １５／１．２／１６／２．２／１６／２．２／１ １２／１．３／１Ｏ２３５／２．３／１ １３／１．６／１１０／２．６／１１３／２．３／２ Ｏ３１１４／２．４／２１５／２．７／２５／１／２５／２．８／１４／３．２／１ Ｏ３２ ６／２／１７／２．１／１ １６／１．２／１１２／２／３Ｏ３３５／２．５／１８／２．２／１ １１／２．５／１ １４／１／３Ｏ３４ ６／１．５／１１７／２．１／１１４／２．４／１１２／２／１ Ｏ３５１７／２．４／１ １４／２．４／１６／３／１７／２．４／１１３／２．３／２Ｏ４１１９／３／１ ２０／３／２１３／２．５／１１５／２．４／２ Ｏ４２ １０／２．５／１７／１／１１３／２．５／２７／５／１１５／１．４／１Ｏ４３４／２．５／１８／２／１ １５／２／２Ｏ４４１０／３．２／１ ６／１．６／１ ６／１．６／２ Ｏ４５１５／２．６／２８／２．３／１１５／１．７／２１３／２／２ Ｏ５１ ６／２．２／１ ７／２．６／１１２／２／１５／０．９／１Ｏ５２８／４／２ １２／２．６／１１５／２．５／２ ８／０．６／１Ｏ５３１３／２．４／１１２／２．３／２ １６／１．６／２７／０．８／１Ｏ５４ ４／２／１６／２／１６／３／２１２／１．４／１ Ｏ５５１３／２．３／２ ７／２．５／１ ８／１．３／１Ｏ５６１１／２．８／２３／２．５／１１０／２．５／１１２／２．４／１１５／１／２５／０．９／１Ｏ６１ １１／１．２／１ ７／１／１８／０．８／１Ｏ６２ ８／２／１１２／３／１ ４／１／２Ｏ６３１０／２．４／１５／１／１ １３／２．１／１ ６／１／１Ｏ６４１６／２．２／２ ８／１．７／２ １２／１．１／２７３１第２期冯旭青，等：考虑运输时间的柔性作业车间调度问题研究表５㊀机器时间及各阶段单位碳排放量Ｔａｂｌｅ５㊀Ｍａｃｈｉｎｅｔｉｍｅａｎｄｕｎｉｔｃａｒｂｏｎｅｍｉｓｓｉｏｎｓｉｎｅａｃｈｓｔａｇｅ机器时间／ｍｉｎ启动重启单位碳排放量／ｋｇ（ＣＯ２）㊃（ｋＷ㊃ｈ）－１启动准备卸载重启Ｍ１２．２３１．５２０．５０．２２．２２Ｍ２１．４２．５１．７５０．４０．１５２．３Ｍ３３．１４．１１．５５０．３５０．１２Ｍ４１．５２．８１．６８０．４２０．１５２．２５Ｍ５２．３３．２１．７２０．３６０．１２．１８Ｍ６１．６２．６１．４５０．２５０．１１．８㊀㊀本文ＩＮＳＧＡ－Ⅱ算法与不考虑关机重启策略的ＩＮＳＧＡ－Ⅱ＿１算法，以及不包含局部邻域搜索和关机策略的ＮＳＧＡ－Ⅱ算法采用相同的初始化参数㊂此外，复现文献［２１］中提出的候鸟优化算法（ＭｉｇｒａｔｉｎｇＢｉｒｄｓＯｐｔｉｍｉｚａｔｉｏｎ，ＭＢＯ），其算法参数为：邻域解数量与共享解数量为１０，巡回次数为３，鸟群大小为１００，迭代次数为１００㊂将ＩＮＳＧＡ－Ⅱ算法与３种比较算法求解柔性制造车间拓展实例，优化目标为问题模型中的最大完工时间ｆ１与碳排放总量ｆ２，独立求解１０次并记录算法的最优解结果见表６，４种算法的ｐａｒｅｔｏ前沿分布情况如图３所示㊂M B ON S G A -2I N S G A -2-1I N S G A -2580570560550540530520510500490657075808590最大完工时间/m i n碳排放量/k g图３㊀不同算法ｐａｒｅｔｏ前沿分布图Ｆｉｇ．３㊀Ｐａｒｅｔｏｆｒｏｎｔｉｅｒｄｉｓｔｒｉｂｕｔｉｏｎｏｆｄｉｆｆｅｒｅｎｔａｌｇｏｒｉｔｈｍｓ㊀㊀采用Ｃ和Ｖｉｎ两个指标评价算法性能，在此柔性制造车间实例中，Ｃ（ＩＮＳＧＡ－Ⅱ，ＩＮＳＧＡ－Ⅱ＿１）＝Ｃ（ＩＮＳＧＡ－Ⅱ，ＮＳＧＡ－Ⅱ）＝Ｃ（ＩＮＳＧＡ－Ⅱ，ＭＢＯ）＝１，Ｃ（ＩＮＳＧＡ－Ⅱ＿１，ＩＮＳＧＡ－Ⅱ）＝Ｃ（ＭＢＯ，ＩＮＳＧＡ－Ⅱ）＝Ｃ（ＮＳＧＡ－Ⅱ，ＩＮＳＧＡ－Ⅱ）＝０，覆盖率指标结果表明，ＩＮＳＧＡ－Ⅱ算法优化求解出的ｐａｒｅｔｏ解集优于其他３种算法获得的最优解；Ｖｉｎ指标结果表示为ＶＩＮＳＧＡ－Ⅱｎ＝ＶＩＮＳＧＡ－Ⅱ＿１ｎ＝６是４种算法中探索到非支配前沿解数量最多的算法，二者表现出同样的搜索性能；但ＩＮＳＧＡ－Ⅱ算法在Ｃ指标上优于ＩＮＳＧＡ－Ⅱ＿１算法，这也说明本文设计关机重启的节能策略能够有效降低碳排放量；其次ＭＢＯ算法和ＮＳＧＡ－Ⅱ算法的ＶＭＢＯｎ＞ＶＮＳＧＡ－Ⅱｎ，ＭＢＯ算法常用多目标优化问题求解，其在ＦＪＳＰ的双目标优化求解同样具有较优的性能，ＶＮＳＧＡ－Ⅱｎ＝２说明ＮＳＧＡ－Ⅱ算法陷入了局部最优，缺少有效探索问题全局最优解的方法㊂ＩＮＳＧＡ－Ⅱ＿１算法相较于ＮＳＧＡ－Ⅱ算法在最大完工时间和总碳排放量优化目标上多求解出４个最优解，说明前者的分布性更好㊂结合表６中的非支配前沿解集，比较不同算法在两个调度目标上的优化效果，ＩＮＳＧＡ－Ⅱ算法相较于ＩＮＳＧＡ－Ⅱ＿１算法在最大完工时间为６８．３２ｍｉｎ时，碳排放量降低了４．１５％，相较于ＮＳＧＡ－Ⅱ和ＭＢＯ算法ｐａｒｅｔｏ解在两目标上均有所降低，这进一步说明了局部邻域搜索策略和基于ｐａｒｅｔｏ最优解的节能策略的有效性㊂此外，本文ＩＮＳＧＡ－Ⅱ算法的非支配前沿在４种算法的非支配前沿对比图中可以看出，ＩＮＳＧＡ－Ⅱ算法的ｐａｒｅｔｏ前沿位于其余３种算法的左下方，说明ＩＮＳＧＡ－Ⅱ算法可以求得更优的ｐａｒｅｔｏ前沿，这与上述对比算法中的两个测试性能指标分析结果一致㊂以上结果表明，ＩＮＳＧＡ－Ⅱ算法可以有效地解决考虑运输时间的柔性作业车间调度问题㊂表６㊀对比算法的非支配解集Ｔａｂｌｅ６㊀Ｃｏｍｐａｒｉｓｏｎｏｆｔｈｅｎｏｎ－ｄｏｍｉｎａｔｅｄｓｏｌｕｔｉｏｎｓｅｔａｍｏｎｇｄｉｆｆｅｒｅｎｔａｌｇｏｒｉｔｈｍｓ算法序号最大完工时间／ｍｉｎ碳排放总量／ｋｇ（ＣＯ２）ＭＢＯ１７３．７８５５５．４７７２７４．５９５５０．８１１３７９．７８５４４．０７２４８７．３２５３８．７０６５８８．２４５３０．９１８ＩＮＳＧＡ－Ⅱ１６８．３２５１２．８１６２７３．２４５０４．８７１３７３．７８５０２．３３１４７４．３２４９９．２１７５７８．９８４９９．００２６８９．１５０１．６８５ＩＮＳＧＡ－Ⅱ＿１１６８．３２５３５．０３２２７３．２４５３２．２７３７３．７８５２９．８６４７４．３２５２４．３５１５７８．９８５１９．９５７６８９．１５０７．２８３ＮＳＧＡ－Ⅱ１７８．３７５６９．１９９２７５．５１５７０．４２４４㊀结束语本文针对考虑运输时间柔性作业车间调度问题，建立了以最小化最大完工时间和总碳排放量为优化指标的柔性作业车间调度模型㊂８３１智㊀能㊀计㊀算㊀机㊀与㊀应㊀用㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀第１４卷㊀为了有效解决考虑运输时间的ＦＪＳＰ，提出一种改进ＮＳＧＡ－Ⅱ算法，通过采用基于工序与机器特征的双层编码方法，解码操作中设计的考虑了工件在机器之间的运输时间插入式解码方法，局部邻域搜索策略和关机重启策略来提高算法的寻优性能，进一步实现车间节能减排㊂通过对多组标准案例和车间实例进行测试验算，验证了ＮＳＧＡ－Ⅱ算法改进策略的有效性，也表明该算法可以有效的解决考虑运输时间的柔性作业车间调度问题㊂参考文献［１］ＤＡＩＭ，ＴＡＮＧＤ，ＧＩＲＥＴＡ，ｅｔａｌ．Ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅｏｐｔｉｍｉｚａｔｉｏｎｆｏｒｅｎｅｒｇｙ－ｅｆｆｉｃｉｅｎｔｆｌｅｘｉｂｌｅｊｏｂｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｗｉｔｈｔｒａｎｓｐｏｒｔａｔｉｏｎｃｏｎｓｔｒａｉｎｔｓ［Ｊ］．ＲｏｂｏｔｉｃｓａｎｄＣｏｍｐｕｔｅｒＩｎｔｅｇｒａｔｅｄＭａｎｕｆａｃｔｕｒｉｎｇ，２０１９，５９：１４３－１５７．［２］ＢＲＵＣＫＥＲＰ，ＳＣＨＬＩＥＲ．Ｊｏｂ－ｓｈｏｐｓｃｈｅｄｕｌｉｎｇｗｉｔｈｍｕｌｔｉ－ｐｕｒｐｏｓｅｍａｃｈｉｎｅｓ［Ｊ］．Ｃｏｍｐｕｔｉｎｇ，１９９０，４５（４）：３６９－３７５．［３］ＤＩＮＧＨ，ＧＵＸ．Ｉｍｐｒｏｖｅｄｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｎｏｖｅｌｅｎｃｏｄｉｎｇａｎｄｄｅｃｏｄｉｎｇｓｃｈｅｍｅｓｆｏｒｆｌｅｘｉｂｌｅｊｏｂｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍ［Ｊ］．ＣｏｍｐｕｔｅｒｓａｎｄＯｐｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈ，２０２０，１２１：１０４９５１．［４］王玉芳，缪昇，葛嘉荣．面向柔性作业车间调度的改进混合蛙跳算法［Ｊ］．组合机床与自动化加工技术，２０２２，５７９（５）：１８７－１９２．［５］赵小惠，卫艳芳，王凯峰，等．改进蚁群算法的柔性作业车间调度问题研究［Ｊ］．组合机床与自动化加工技术，２０２２，５７６（２）：１６５－１６８．［６］李宝帅，叶春明．混合鲸鱼优化算法求解柔性作业车间调度问题［Ｊ］．计算机系统应用，２０２２，３１（４）：２４４－２５２．［７］杜凌浩，向凤红．改进多邻域候鸟优化算法的柔性作业车间调度研究［Ｊ］．兵器装备工程学报，２０２２，４３（１２）：２９９－３０６．［８］ＬＩＪ，ＰＡＮＱ．Ｃｈｅｍｉｃａｌ－ｒｅａｃｔｉｏｎｏｐｔｉｍｉｚａｔｉｏｎｆｏｒｆｌｅｘｉｂｌｅｊｏｂ－ｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｓｗｉｔｈｍａｉｎｔｅｎａｎｃｅａｃｔｉｖｉｔｙ［Ｊ］．ＡｐｐｌｉｅｄＳｏｆｔＣｏｍｐｕｔｉｎｇ，２０１２，１２（９）：２８９６－２９１２．［９］吴秀丽，刘夏晶．差分进化算法求解分布式柔性作业车间调度问题［Ｊ］．计算机集成制造系统，２０１９，２５（１０）：２５３９－２５５８．［１０］王亚昆，刘应波，吴永明，等．改进ＮＳＧＡ－ＩＩ算法求解考虑运输约束的柔性作业车间节能调度问题［Ｊ］．计算机集成制造系统，２０２３，２９（９）：３０２８－３０４０．［１１］张国辉，吴立辉．求解柔性作业车间调度的ＧＡＴＯＣ混合方法［Ｊ］．计算机工程与应用，２０１５，５１（２３）：２６６－２７０．［１２］孟磊磊．面向高效节能的柔性作业车间调度问题建模与优化［Ｄ］．武汉：华中科技大学，２０２０．［１３］ＪＩＡＮＧＥＤ，ＷＡＮＧＬ，ＰＥＮＧＺＰ．Ｓｏｌｖｉｎｇｅｎｅｒｇｙ－ｅｆｆｉｃｉｅｎｔｄｉｓｔｒｉｂｕｔｅｄｊｏｂｓｈｏｐｓｃｈｅｄｕｌｉｎｇｖｉａｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅｅｖｏｌｕｔｉｏｎａｒｙａｌｇｏｒｉｔｈｍｗｉｔｈｄｅｃｏｍｐｏｓｉｔｉｏｎ［Ｊ］．ＳｗａｒｍａｎｄＥｖｏｌｕｔｉｏｎａｒｙＣｏｍｐｕｔａｔｉｏｎ，２０２０，５８：１００７４５．［１４］张洪亮，徐公杰，鲍蔷，等．考虑运输时间的分布式柔性作业车间绿色调度［Ｊ］．中国机械工程，２０２２，３３（２１）：２５５４－２５６３，２６４５．［１５］ＫＡＣＥＭＩ，ＨＡＭＭＡＤＩＳ，ＢＯＲＮＥＰ．Ｐａｒｅｔｏ－ｏｐｔｉｍａｌｉｔｙａｐｐｒｏａｃｈｆｏｒｆｌｅｘｉｂｌｅｊｏｂ－ｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｓ：ｈｙｂｒｉｄｉｚａｔｉｏｎｏｆｅｖｏｌｕｔｉｏｎａｒｙａｌｇｏｒｉｔｈｍｓａｎｄｆｕｚｚｙｌｏｇｉｃ［Ｊ］．ＭａｔｈｅｍａｔｉｃｓａｎｄＣｏｍｐｕｔｅｒｓｉｎＳｉｍｕｌａｔｉｏｎ，２００２，６０（３－５）：２４５－２７６．［１６］栾飞，蔡宗琰，吴书强，等．求解低碳车间调度问题的改进鲸鱼算法［Ｊ］．机械科学与技术，２０２０，３９（５）：７２１－７２８．［１７］ＭＯＨＳＥＮＺ．Ａｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｓｏｌｖｉｎｇｆｌｅｘｉｂｌｅｊｏｂｓｈｏｐｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍ［Ｊ］．ＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌｏｆＡｄｖａｎｃｅｄＭａｎｕｆａｃｔｕｒｉｎｇＴｅｃｈｎｏｌｏｇｙ，２０１４，７１（１－４）：５１９－５２８．［１８］李旻运．基于改进的ＮＳＧＡ－Ⅱ算法的多目标柔性车间调度问题的研究及应用［Ｄ］．湖州：湖州师范学院，２０２２．［１９］杨幸博，罗国富，宋俊杰，等．多目标柔性作业车间低碳调度研究［Ｊ］．轻工学报，２０２０，３５（６）：９３－９９．［２０］中华人民共和国生态环境部．２０１９年度减排项目中国区域电网基准线排放因子［ＥＢ／ＯＬ］．［２０２２－９－２９］．［２１］ＤＵＭＡＮＥ，ＵＹＳＡＬＭ，ＡＬＫＡＹＡＡＦ．Ｍｉｇｒａｔｉｎｇｂｉｒｄｓｏｐｔｉｍｉｚａｔｉｏｎ：Ａｎｅｗｍｅｔａｈｅｕｒｉｓｔｉｃａｐｐｒｏａｃｈａｎｄｉｔｓｐｅｒｆｏｒｍａｎｃｅｏｎｑｕａｄｒａｔｉｃａｓｓｉｇｎｍｅｎｔｐｒｏｂｌｅｍ［Ｊ］．ＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅｓ，２０１２，２１７（２４）：６５－７７．９３１第２期冯旭青，等：考虑运输时间的柔性作业车间调度问题研究。
基于混合遗传算法的车辆路径问题作者：刘超来源：《城市建设理论研究》2013年第32期摘要：遗传算法可以很好的解决路径选择问题，但简单的遗传算法存在过早收敛问题。
在自然界中远亲交配具有更好的遗传优势，本文据此理论改进车辆路径选择问题中的遗传算法，提高求解性能。
关键词：混合遗传算法；车辆路径选择，远亲交叉策略中图分类号：U27文献标识码：A遗传算法简称GA(Genetic Algorithm)是一种模拟自然界中遗传和选择机制的寻找最优解的方法。
他的基本原理源自达尔文的生物进化论和盂德尔的基因学说。
遗传算法模拟自然界的遗传，变异和进化法则，逐步修订解决问题的方案使之接近完美。
遗传算法的优势在于将搜索过程作用在编码后的字符串上．不直接作用在优化问题的具体变量上，这样可以绕过复杂的数学推演而采用最直接的方式在有限的结果集中搜索更优的结果。
遗传算法通过设定一个初始种群，即一个预设的结果。
并对这个初始种群进行基因突变和杂交，留下好的基因，改变不好的基因，使种群不停的进化，最后得到一组最优的或趋进于最优的结果，给人更大的选择余地。
遗传算法有很好的易修改性和可并行性，在处理大规模复杂问题上更有优势。
但普通的遗传算法存在“早熟”问题，即容易收敛于局部最优解，在自然界中远亲交配具有更好的遗传优势，本文据此理论改进车辆路径选择问题中的遗传算法，并以有车载限制单配中心VRP的求解加以说明。
这种交叉策略虽然使遗传算法的收敛速度稍有减缓，但使算法具有很好的求解性能。
具体步骤如下：(1)混合遗传算法的编码规则应用遗传算法求解的首要问题是对所求问题解的编码。
一个解的编码称为一个染色体，组成编码的元素称为基因。
混合遗传算法采用路径编码方法。
每个染色体由区间「1,m+n-1」中互不相同的自然数序列构成，其中n为客户数目，m为运输车数量，前面1～n为客户编号，n+1～n+m-1表示配送中心。
例如，若有3辆运输车和12个客户，则一个染色体为{2,1,3,13,5,4,6,10,14,8,7,9,11,12}，其中13，14表示配送中心以区分开3辆车所运输的客户编组。
第22卷第7期V ol.22No.7控 制 与 决 策Contr ol andDecision2007年7月July 2007收稿日期:2006 02 18;修回日期:2006 06 12.基金项目:国家自然科学基金项目(60204008,60374060,60574072);国家973计划项目(2002CB312200).作者简介:刘波(1979 ),男,山西朔州人,博士生,从事进化算法等研究;王凌(1972 ),男,江苏武进人,副教授,博士,从事优化理论与方法等研究.文章编号:1001 0920(2007)07 0721 09差分进化算法研究进展刘 波,王 凌,金以慧(清华大学自动化系,北京100084)摘 要:作为一种简单而有效的新兴计算技术,差分进化算法(DE)已受到学术界和工程界的广泛关注,并取得了许多成功应用.为此,围绕差分进化算法的原理、特点、改进及其应用等方面进行全面综述,重点介绍了针对复杂环境的差分进化算法研究内容,包括多目标、约束、离散和噪声环境下的优化等.最后提出了有待进一步研究的若干方向.关键词:差分进化;多目标优化;约束优化;离散优化;噪声优化中图分类号:T P18 文献标识码:AAdvances in differential evolutionL I U B o,WA N G L ing ,J I N Yi hui(Depar tment of A ut omatio n,T sing hua U niver sity,Beijing 100084,China.Cor respondent:W A NG L ing,E mail:w ang ling@mail.t sing )Abstract:As a nov el evo lutio nar y computing technique,differ ential evolut ion (DE)is simple and effect ive,w hich is paid wide att ention and research in both academic and indust ry fields and achieves many successful applications.A complet e surv ey on DE is presented in aspect o f mechanism,feature,impro vements and a pplicat ions.T he studies o n DE aiming at complex envir onment ar e especia lly intro duced including multi o bject ive,constrained,discrete and no isy o ptimization.Finally,the futur e research direction and contents are pointed out.Key words:Differ ent ial ev olution;M ult i objectiv e optimizatio n;Co nstr ained o ptimization;D iscrete optimization;N o isy optim izat ion1 引 言差分进化算法(Differ ential Evo lution,DE)[1,2]是一种新兴的进化计算技术.它是由Storn 等人于1995年提出的,最初的设想是用于解决切比雪夫多项式问题,后来发现DE 也是解决复杂优化问题的有效技术.DE 与人工生命,特别是进化算法有着极为特殊的联系.DE 和微粒群算法(PSO,也称粒子群算法)[3]一样,都是基于群体智能理论的优化算法,通过群体内个体间的合作与竞争产生的群体智能指导优化搜索.但相比于进化算法,DE 保留了基于种群的全局搜索策略,采用实数编码、基于差分的简单变异操作和一对一的竞争生存策略,降低了遗传操作的复杂性.同时,DE 特有的记忆能力使其可以动态跟踪当前的搜索情况,以调整其搜索策略,具有较强的全局收敛能力和鲁棒性,且不需要借助问题的特征信息,适于求解一些利用常规的数学规划方法所无法求解的复杂环境中的优化问题.因此,DE 作为一种高效的并行搜索算法,对其进行理论和应用研究具有重要的学术意义和工程价值.目前,DE 已经在许多领域得到了应用,譬如人工神经元网络、化工、电力、机械设计、机器人、信号处理、生物信息、经济学、现代农业、食品安全、环境保护和运筹学等.然而,尽管DE 获得了广泛研究,但相对其他进化算法而言,其研究成果相当分散,缺乏系统性,尤其在理论方面还没有重大突破.因此,本文对DE 及其最新研究成果进行较全面的综述,重点介绍了复杂环境下DE 的若干研究内容,并指出未来值得关注的研究内容和方向.2 标准差分进化算法DE [1]是一种基于群体进化的算法,具有记忆个体最优解和种群内信息共享的特点,即通过种群内个体间的合作与竞争来实现对优化问题的求解,其本质是一种基于实数编码的具有保优思想的贪婪遗传算法.算法首先在问题的可行解空间随机初始化控 制 与 决 策第22卷种群X0=[x01,x02, ,x0NP],N P为种群规模.个体x0i=[x0i,1,x0i,2, ,x0i,D]用于表征问题解,D为优化问题的维数.算法的基本思想是:对当前种群进行变异和交叉操作,产生另一个新种群;然后利用基于贪婪思想的选择操作对这两个种群进行一对一的选择,从而产生最终的新一代种群.具体而言,首先通过式(1)对每一个在t时刻的个体x t i实施变异操作,得到与其相对应的变异个体v t+1i,即v t+1i=x t r1+K(x t r2-x t r3).(1)其中:r1,r2,r3 {1,2, ,N P}互不相同且与i不同;x t r1为父代基向量;(x t r2-x t r3)称作父代差分向量;K为缩放比例因子.然后,利用式(2)对x t i和由式(1)生成的变异个体v t+1i实施交叉操作,生成试验个体u t+1i,即u t+1i,j=v t+1i,j,If(rand(j) CR)o r j=rnbr(i);x t i,j,Otherw ise.(2)其中:rand(j)为[0,1]之间的均匀分布随机数;CR 为范围在[0,1]之间的交叉概率;rnbr(i)为{1,2, ,D}之间的随机量.利用式(3)对试验个体u t+1i和x t i的目标函数进行比较,对于最小化问题,则选择目标函数值低的个体作为新种群的个体x t+1i,即x t+1i=u t+1i,If f(u t+1i)<f(x t i);x t i,Otherw ise.(3)其中f为目标函数.上述过程是标准版本的DE,表示为DE/rand/1/bin.文献[4]中提供了其余有关DE的变种.DE算法的搜索性能取决于算法全局探索和局部开发能力的平衡,而这在很大程度上依赖于算法的控制参数的选取,包括种群规模、缩放比例因子和交叉概率等.相对其他进化算法而言,DE所需调节的参数较少.合理的参数选择指导参见文献[1,5].归纳起来,DE算法具有如下优点:1)算法通用,不依赖于问题信息;2)算法原理简单,容易实现;3)群体搜索,具有记忆个体最优解的能力;4)协同搜索,具有利用个体局部信息和群体全局信息指导算法进一步搜索的能力;5)易于与其他算法混合,构造出具有更优性能的算法.3 DE的算法研究及改进迄今,对DE的研究和改进主要归纳为如下几个方面.3.1 改进DE的操作算子Feoktistov等[6]提出一种广义的变异策略框架,方便用户选择合适的变异操作类型,同时也为开发新的变异操作算子提供了便利.Kaelo等[7]利用锦标赛竞争选择机制来选取进行变异操作的父代基向量,同时在试验个体和种群内最好个体之间的区域,利用反射和收缩操作来实施局部搜索.Berg ey 等[8]引入选择压力控制参数,通过对根据适配值排序个体的一系列柏努利试验,挑选满足选择压力控制参数的父代基向量.Lee等[9]提出一种基于适应性步长的局部搜索来确定合适的缩放比例因子,从而加速算法搜索的进程.Fan等[10]在DE中引入三角法变异,将个体看作一个超三角形的中心点,沿着由3组加权差分向量所构成的超三角形的3条边,分别以不同的步长移动来产生新的变异个体,从而增加了算法跳出局部极小点的概率.Liu等[11]提出模糊自适应DE,利用模糊逻辑控制器来调整变异和交叉操作的控制参数.谢晓锋等[5]将缩放比例因子由固定数值转化为随机函数,仿真试验表明了该方法相对固定值缩放比例因子具有优势.Chiou 等[12]提出一种可变缩放比例因子,有效克服了固定或者随机比例因子的缺陷,无须选择变异操作的类型,同时提高了算法的性能.3.2 加入新的操作Wang等[13]在DE中引入加速和迁移操作,其中加速操作利用梯度信息将最优个体引向更优的区域,而为了防止算法早熟收敛,当种群的分散度低于一定的阈值时,利用迁移操作在最优个体附近区域重新产生新个体,并替换旧个体,从而维持了种群的多样性.在此基础上,Lin等[14]提出一类协进化DE,整数量和实数量单独进行DE进化,解决了混合整数非线性规划问题.Cheng等[15]在DE中引入搜索空间扩展机制,有效增强了算法的全局收敛能力,并将该算法用于解决线性系统最优近似问题.宋立明等[16]提出一种自适应差分进化算法,根据种群熵的变化,自适应减小种群的搜索范围,节约了算法搜索时间.T homsen[17]提出基于拥挤机制的小生境DE来求解多极值函数优化问题,通过删除小生境中相似的个体,使得算法具有继续追踪和维护多个极值点的能力.Sun等[18]提出一种描述最优解分布的概率模型,通过对其采样产生新解来引导DE的搜索.Lin等[19]通过引入种群分散度评价来判断是否需要对种群进行迁移,从而可以通过较小的种群实现对复杂优化问题的求解,同时使用混合整数编码以及凑整操作,使该方法可用于解决混合整数非线性规划问题.Zaharie[20]建立了算法控制参数和由该组控制参数所引发的种群多样性的关系,提出了一种新的控制参数,用于补偿因之前的操作而带来722第7期刘波等:差分进化算法研究进展的对种群多样性的影响.通过实时选择该控制参数,可以对种群的多样性进行控制,从而影响算法的收敛行为.3.3 多种群Zaharie[21]提出了多种群DE,并用于求解多极值的优化问题.Qing[22]将DE分成多个子种群,各个子种群独立寻优,同时利用跨种群间的竞争算子来实现种群间信息共享,并利用该算法解决多个超导柱体电磁反转散射问题.Plagianakos等[23]提出并行DE,各个子种群独立进化,并利用环形网络拓扑来实现子种群之间的通信.多种群法的缺点是初期的搜索效率低于标准DE,且多个子种群的引入,加大了算法的计算量.3.4 混合算法Chiou等[24]利用蚁群搜索算法,实时地从多种变异算子中为DE选择合适的变异操作算子,以加速算法的寻优过程.H r stka等[25]将遗传算法的部分染色体通过DE的变异操作产生,同时利用二进制竞争选择策略选择子代.方强等[26]在DE中加入单纯形寻优操作和重布操作,提高了单纯形方法的收敛速度,同时提高了DE算法的搜索精度.Wang 等[27]将DE与序贯二次规划SQ P相结合,同时利用DE的并行全局探索能力与SQP的局部开发能力,克服了SQ P需要依赖问题梯度信息的缺点.3.5 其 他Ali等[28]首先在DE中引入自适应缩放比例因子,该因子可以使算法在早期具有较强的分散探索能力,在后期具有较强的集中开发能力;其次,在DE中使用了预先计算好的差分向量,减少了每次迭代中差分向量的计算量,同时增强了算法在后期保持种群多样性的能力;再次,增加了辅助解集,用于保存在选择过程中被拒绝的潜在试验解,在算法经过一段迭代之后,用辅助解集中的若干较好的解替代当前解集中的较差解;最后,加入局部搜索环节,对个体实行单纯型搜索,进而提高解的精度. Teo[29]将种群规模作为决策变量,随着搜索的进行实时自适应调整种群规模.4 复杂环境下DE的研究目前,DE的研究和应用主要集中于连续、单目标、无约束的确定性优化问题.近年来,DE在多目标、约束、离散和噪声等复杂环境下的优化也得到了一些发展.4.1 多目标优化相对传统多目标优化方法,DE在求解多目标问题上具有很大优势.首先,DE的高效搜索能力有利于得到多目标意义下的最优解;其次,DE通过代表整个解集的种群按内在的并行方式同时搜索多个非劣解,因而容易搜索到多个Par eto最优解;再则, DE的通用性使其适合于处理所有类型的目标函数和约束;另外,DE很容易与传统方法相结合,进而提出解决特定问题的高效方法.就DE本身而言,为了更好地解决多目标优化问题,一方面要求算法具有较好的收敛速度,另一方面要求所得解在Pareto 边界上具有一定的分散性.对于DE的选择操作而言,则要求较小的计算复杂性,即仅通过较少的比较次数达到非劣解的更新.迄今,基于DE的多目标优化主要有以下几种思路.4.1.1 Pareto竞争Abbass等[30]提出一种基于Pareto竞争的方法,子代与参与交叉操作的父代基向量进行比较,如果子代个体不被支配,则子代代替父代进入种群,反之父代被保留.如果非支配解的数目超过一定的阈值,则利用基于最近邻域法的小生境技术,删除具有最小邻域距离的非支配解.为了进一步提高算法对于控制参数的鲁棒性,Abbass[31]在此基础上引入了自适应交叉和变异概率,仿真结果表明上述自适应算子的引入可以使所求得的Pareto解更好地逼近真实的Pareto界,同时提高了Pareto解在Pareto 界上的分散度.在Robic等[32]提出的基于Pareto竞争的方法中,利用非支配排序和基于拥挤距离法的小生境技术,删除具有最小邻域距离的非支配解.基于上述算法,提出了两种小生境技术,分别是子代个体在决策变量空间与最相近的个体比较,从而决定取舍,以及子代个体在判据空间与最相近的个体比较来决定取舍.由于这两种变种要在基本算法的基础上增加在决策和判决空间搜寻最相近的解的过程,提高了算法的计算量.4.1.2 Pareto排序M adavan[33]在DE中引入Deb等[34]提出的快速非支配排序和基于排序的选择策略,对包含父代和子代的种群进行非支配排序,利用精英保留和小生境分散度维持策略,并对非支配排序最高的父代集实施交配限制,从而使种群分布在多个最优区域,在维持解多样性的同时加快了算法向Pareto界的收敛速度.Jensen[35]提出一种基于非支配排序的适配值分配机制,降低了多目标优化算法计算复杂度,同时提出了可以显著加速多目标优化算法速度的小生境技术,并将这些技术运用于Abbass等提出的多目标DE[30].Xue等[36]利用基于Pareto排序的适应值分配方法,利用小生境Pareto的概念确定个体适应值降低的程度,同时使用了精英解保留策略和723控 制 与 决 策第22卷分散度维持策略.在此基础上,Xue等[37]引入贪婪概率、变异概率和交叉概率,将其拓展用于解决离散多目标优化问题,并用该算法解决了商用电路板设计、供应和制造计划问题.Chang等[38]提出一种类似于Zitzler等[39]的基于Pareto排序的方法,分别将遗传算法、PSO和DE3种基于种群的进化算法作为核心算法,用于解决M RT地铁系统的调度问题.4.1.3 多种群基于Madav an[33]提出的多目标DE,Zaharie 等[40]通过引入文献[20]中建立的算法控制参数与种群多样性的关系,提出了一种自适应多目标DE 算法.该算法可以对种群的多样性进行控制,从而提高算法在Pareto界上的分散度.Zaharie等[40]进一步将该算法并行化,每个子种群单独进行DE运算,各个子种群之间通过信息交换来搜索Pareto最优解.但是,由于需要增加个体数目而增加了计算量.4.1.4 改进操作算子Kukkonen等[41]在广义DE[42]中引入了新的选择操作算子,用于解决多目标且带约束的函数优化问题.为了维持非支配解在Pareto前沿的分散度,只有当试验个体与父代相当或者能够支配父代个体时,试验个体才替代父代个体.如果两个个体都是可行且互相不支配,则具有较小小生境数的个体被选择.该方法需要对所有可行解在所有目标上进行评价,因而增加了算法的计算时间.Iorio等[43]利用Deb等[33]在N SGA II中提出的交叉和变异算子,替代DE中的相应操作算子来解决多目标优化问题.4.1.5 向量评价法Parso poulos等[44]提出一种向量评价DE,该方法采用向量形式的适应值来度量并产生下一代.将种群分为若干个子种群,每个子种群对应于其中一个目标,在每次循环过程中,各子种群根据各自的目标选出下一代的优秀个体(即子种群);然后,在种群间引入迁移算子,促进不同子种群间的交配.这种方法有助于保留在单个目标上最优秀的个体,同时为那些在多个目标上优于平均适应值的个体提供了被选择的机会.4.2 约束优化近年来,DE算法在约束优化方面也取得了一定进展.基于DE的约束优化工作主要分为3类. 4.2.1 罚函数法Lam pinen等[45]利用静态罚函数方法,将约束优化问题转化为易于求解的无约束问题,缺点在于需要仔细调节罚因子.Lampinen[42]通过增大使不可行解朝约束违背少的方向的选择压力,提高了算法向可行域收敛的速度.该方法尽管避免了传统罚函数法在选择罚因子方面的弱点,但其罚函数的设计过于复杂.4.2.2 设计特定的进化操作或约束修正因子来保持解的可行性M ezura Mo ntes等[46]提出了3种基于维持解可行性的选择标准来指导搜索向可行域方向进行. Storn[2]提出一种维持解可行性的自适应机制来松弛约束,从而使得所有初始解可行;然后收缩被松弛的伪可行域,直到它与真实的可行域匹配,同时利用了基于衰老因子和重复生成子代的策略.4.2.3 混合方法Becer ra等[47]将文化算法中的信任空间的知识源引入DE算法,并用于解决约束优化问题.由于算法的信任空间会对算法的搜索产生较高的选择压力,算法在后期容易丧失种群多样性,导致早熟收敛.因此,如何有效利用知识源,以及设计合适的信任空间接受准则,对于优化进程具有很重要的影响. Sarimveis等[48]提出一种排列DE算法,利用增广拉格朗日方法处理约束,根据算法的进程调节罚因子和拉格朗日乘子,同时根据个体的适配值在整个种群中的排序确定DE交叉变异的程度.Chiou等[49]利用增广拉格朗日函数将约束优化问题转换为m in m ax问题,在最小化阶段,利用Wang等[13]提出的混合DE求解固定拉格朗日乘子的函数优化问题,而在最大化阶段,则利用最小化阶段得到的最优决策量来更新拉格朗日乘子.4.3 离散优化对于离散优化而言,解空间是离散点的集合,而非连续区域,因此利用DE解决离散优化问题就必须将基于实数编码的传统DE算法影射到离散编码空间,或对问题进行变形.目前,基于DE的离散优化研究主要集中于前者,即直接将用于解决连续优化问题的DE算法用于处理离散优化问题. Lampinen等[45]讨论了如何通过修改DE来求解混合整数问题,即DE在连续空间进行搜索,通过保留浮点数的整数部分对目标函数进行评价.Onw ubolu 等[50]利用前向转化机制将整数变量转化为便于DE 处理的连续变量,利用后向转化机制将连续变量转化为可以进行目标评价的整数量.4.4 噪声环境下的优化在许多实际工程问题中,优化的环境是不确定或动态的,因此优化算法必须具备随环境动态变化而对最优解作出相应调整的能力,即算法需要具有一定的鲁棒性.Krink等[51]利用多次采样机制,初步724第7期刘波等:差分进化算法研究进展研究了DE在噪声环境下的函数优化问题,然而其性能表现相比于确定性环境下仍有待提高.因此,为了提高DE在噪声环境下的优化性能,可通过改进选择或变异算子来提高算法在噪声环境下平衡开发与探索的能力,或引入其他有效处理噪声的技术来提高DE在噪声环境下解决优化问题的能力.尽管目前该方面的研究成果较少,但这是一项重要的研究内容.5 DE的应用鉴于DE的优越性,DE已在诸多领域得到应用,简单归纳如下.5.1 人工神经网络Liu等[52]将PSO,DE与混沌搜索相结合来训练多层前馈神经网络;Abbass[53]利用基于BP和DE学习的神经元网络来预测乳腺癌.应用结果均显示,利用DE设计神经元网络是一种快速、高效并具有潜力的方法.5.2 化工领域Kir anmai等[54]利用DE确定固定薄膜生物反应器的机理参数.Kapadi[55]等利用DE解决间歇发酵最优控制和参数选择问题.Chaitali等[56]通过DE 为黄原胶发酵过程选择合适的初始反应器物质体积以及进料浓度.方强等[26]应用DE估计基于低温硫酸催化剂的二氧化硫氧化反应的模型参数.Lee 等[9]提出一种基于改进DE的动态优化方法来确定连续甲基异丁烯酸盐和乙烯基醋酸盐共聚合反应过程的最优控制变量轨迹,从而最小化反应启动时间和等级变化操作的过渡时间.Chakraborti等[57]基于热传递模型,利用DE对钢厂重加热炉进行优化配置,并通过调节轧钢速度,使得所得到的温度曲线满足轧钢退温约束.Wang等[13]将间歇燃料酒精发酵生产过程的最优加料策略转变为一个模糊决策分析问题,同时利用混合DE解决上述的最大化决策问题,求得最优加料策略.H uang等[58]将多产品间歇化工过程的多目标最优设计问题转化为一个增广Minimax模糊目标优化问题,利用Lin等[14]提出的基于DE的混合整数规划方法来解上述的非线性规划问题.Chiou等[49]利用文献[13]提出的改进DE 算法解决间歇发酵过程的最优控制和最优参数选择问题.Wang等[27]结合DE和SQP解决间歇苯乙烯聚合的最优温度控制问题,通过选择合适的单体浓度和聚合过程温度趋势,在减少间歇反应时间的同时获得高的单体转化率和规定的聚合体特性.5.3 电力系统Chang等[59]利用改进DE优化设计大规模多总线被动谐波滤波器,同时考虑了滤波器参数和加热炉负荷的不确定性.Chang等[60]通过将DE与多梯度方法结合,提出了一种有效解决带动力线调节装置的分布式电力系统谐波电压扰动问题.Chiou 等[12]利用文献[13]提出的改进DE确定在一定负荷模式下的合适的电网拓扑结构来有效解决电网重新配置问题,在降低电能损耗的同时使得分布式系统的电压满足约束限制.Kannan等[61]系统考察了多种流行的现代启发式算法(包括遗传算法、进化规划、进化策略、蚁群算法、PSO、禁忌搜索、模拟退火和DE等)在解决最低成本发电扩张计划问题(GEP)上的性能表现,其中DE在该问题上的性能要好于其他方法.Chiou等[24]利用基于蚁群搜索算法的DE求解分布式电力系统中大规模电容器配置问题,有效降低了系统电能损耗.Cr utchley等[62]利用DE来寻找非线性电路的直流操作点.陈晨等[63]运用DE对永磁同步电机进行优化设计,减小了永磁体使用量,抑制了脉动转矩,使电机达到了较高的性能指标.5.4 机械设计宋立明等[16]利用自适应DE,结合曲面造型法,提出了一种叶轮机械三维气动优化设计方法.杨晓明等[64]利用DE进行盘式制动器的全性能优化设计.Doy le等[65]利用DE自动设计照明器反射镜.张吴明等[66]将传统分步标定Tsai方法与DE相结合,提出了一种新的相机标定方法.5.5 机器人领域Ay din等[67]将DE与模糊推理相结合,用于解决机器人最优路径规划问题.Shiako las等[68]利用DE优化设计机器人连续操纵器和铰接处理器,使得机器人在满足物理链接特性的约束下,完成特定动作所需要的扭矩最小.Joshi等[69]利用DE解决多传感器融合的最小表达问题,用于复杂环境下的机器人系统的计划和控制问题.5.6 信号处理领域Storn[70]利用DE设计滤波器.Shan等[71]利用基于DE的频率域模型优化超宽带无线电系统的源脉冲和探测模型,使得自由空间的功率和接收端的相关检测输出最大.Caor si等[72]利用混合整数编码的DE优化设计单脉冲天线的差异模式.Yang 等[73]利用DE确定静态激励幅度分布,从而有效地降低了相中心移动天线阵的带内旁瓣电平.Li等[74]利用DE和New ton Raphso n法,通过电阻抗X线断层摄影来重建脑部图像.5.7 生物学领域T sai等[75]利用DE对非线性生物动力系统进行结构辨识和参数估计.M oloi等[76]利用DE寻找725。
遗传算法在调度问题中的应用研究概述：遗传算法是模拟自然界遗传和进化原理的一种优化算法，具有广泛的应用领域。
调度问题作为一类NP-hard问题，是实际生活中非常重要的问题之一。
本文将探讨遗传算法在调度问题中的应用研究，包括调度问题的定义、遗传算法的基本原理以及遗传算法在调度问题中的具体应用。
一、调度问题的定义：调度问题是指在给定的约束条件下，合理安排任务的开始时间、结束时间和资源分配，以达到最优的目标，如最小化等待时间、最小化资源消耗、最大化资源利用率等。
常见的调度问题包括作业调度、车辆路径规划、生产调度等。
二、遗传算法的基本原理：遗传算法是一种基于自然选择和进化论原理的优化算法。
基本原理包括个体表示、适应度评价、选择、交叉和变异。
首先，将问题抽象为个体，个体的基因表示问题的解。
然后，通过适应度函数对每个个体进行评价，衡量个体的优劣。
接下来，根据适应度大小选择优秀的个体作为父代，进行交叉和变异操作产生新的个体。
最后，反复迭代进行选择、交叉和变异，使种群中的个体逐渐趋于最优解。
三、遗传算法在调度问题中的应用：1. 作业调度：作业调度是指对一组作业进行合理的排序和分配资源，以最小化作业完成时间或最大化资源利用率。
遗传算法可以通过将作业表示为基因，对基因进行交叉和变异操作来生成新的调度方案，然后根据适应度函数对调度方案进行评价和选择。
通过多次迭代，最终获得最优的作业调度方案。
2. 车辆路径规划：车辆路径规划是指在给定的起始点和终止点之间，找到一条最短路径以最优方式分配车辆的行驶路线。
遗传算法可以将路径表示为基因，利用选择、交叉和变异操作生成新的路径，并通过适应度函数评价路径的优劣。
通过多次迭代，可以得到最优的车辆路径规划方案。
3. 生产调度：生产调度是指合理分配生产资源和工序，以最大化生产效率和资源利用率。
遗传算法可以将生产工序表示为基因，利用交叉和变异操作生成新的调度方案，并通过适应度函数评价方案的优劣。
基于遗传算法的流水车间调度问题中文摘要流水车间调度问题是研究多个工件在若干个机器上的加工次序的问题，有效的调度算法对企业提高生产效率有着重要作用。
本文使用遗传算法求解流水车间调度问题，把一个染色体编码成若干个自然数，表示相应工件的排序权值；通过简单交换两个父代的若干相同位置的基因，产生能够继承父代优良特性的子代；并且采用均匀变异，更好地保持种群中的基因的多样性。
实验表明，该方法能取得较好的效果。
关键字：遗传算法，流水车间调度方法，实数编码，基因链码，群体，适应度。
外文摘要Abstract: Flow-shop scheduling problem study the problem the processing sequence of A plurality of workpieces on some working machine,and it makes good effects on proving production efficiency to the industries with effective methods.In the case,we deal with flow-shop scheduling problem using a algorithm,the Genetic Algorithm.There is a chromosome we've just coded into some natural numbers to represent the weight order of these workpieces; exchanging simply two fathers' places of some gene to produce new children that carried good feature on two fathers;we also use the Uniform Mutation,and it keeps its diversity of gene on the population.This experiment show this method can achieve good results.Key Words: Genetic Algorithm, Flow-shop scheduling problem，natural number coding，genic bar code,group，fitness.目录中文摘要 (1)外文摘要 (2)目录 (3)1 引言 (4)1.1 论文的发展背景及重要性 (4)1.1.1 时代背景 (4)1.1.2 论文研究的重要性 (4)1.2 论文的研究问题及解决方法 (4)2 FSP问题描述 (5)2.1 排序问题的基本概念 (5)2.1.1 名词术语 (5)2.1.2 条件假设 (5)2.2车间作业排序问题的特点 (6)2.3 车间作业排序问题 (6)2.3.1 目标函数 (6)2.3.2 车间调度问题的分类 (7)3 遗传算法理论 (7)3.1 遗传算法的产生和发展 (7)3.2 遗传算法的基本思想 (8)3.2.1 基本概念 (8)3.2.2 遗传算法的基本思想 (9)4 基于遗传算法的流水车间调度方法 (11) 4.1 问题的提出 (11)4.2 遗传算法基本步骤 (11)4.2.1 编码 (11)4.2.2 初始群体生成 (12)4.2.3 适应度计算 (12)4.2.4 选择 (14)4.2.5 交叉 (15)4.2.6 变异 (17)4.2.7 终止 (19)5. 研究成果 (20)5.1 算法求解与分析 (20)5.2 实验结果 (21)参考文献 (22)附录 (23)1 引言1.1 论文的发展背景及重要性1.1.1 时代背景从第一次工业革命起，由于科技的进步人类社会就开始了一个经济腾飞的大时代。
混合流水车间调度问题的IPSO算法李解;任魏翔;秦永彬【期刊名称】《计算机与数字工程》【年(卷),期】2016(0)6【摘要】混合流水车间调度问题又称柔性流水车间调度问题,广泛存在于现代工业之中.它是对传统流水车间的扩展.其中,每道工序可能有多台机器负责处理.针对混合流水车间调度问题,论文以最小化最大完成时间为目标建立整数规划模型,将经典粒子群优化算法进行改进,并同教与学算法(Teaching Learning Based Optimation,TLBO)相结合,提出了一种用于解决该问题的改进的粒子群算法(Improved Particle Swam Optical Algorithm,IPSO).算法在产生初始种群的过程中,首先将原问题转化为一系列置换流水车间调度问题,并求得其解.之后,将得到的解作为初始种群的一部分.由于现有的粒子群算法具有易收敛于局部最优解的缺点.因此为防止算法收敛于局部最优解,引入变异操作.此外,在粒子群优化算法的基础上引入适用于求解混合流水车间的TLBO算法的老师阶段和学生阶段.设计正交试验对算法参数设置进行分析,并确定了较优的参数组合.通过基于算例的仿真实验,并与现有的解决混合流水车间调度问题的算法进行比较,验证所提出IPSO算法是有效的.【总页数】7页(P985-991)【作者】李解;任魏翔;秦永彬【作者单位】贵州大学计算机科学与技术学院贵阳550025;贵州大学计算机科学与技术学院贵阳550025;贵州大学计算机科学与技术学院贵阳550025【正文语种】中文【中图分类】TP312【相关文献】1.带多处理器混合流水车间调度问题的混合鱼群算法 [J], 蔡芸;邓勇;张波;张利平2.新型混合改进遗传算法求解零等待流水车间调度问题 [J], 裴小兵;李依臻3.改进PSO-GA算法求解混合流水车间调度问题 [J], 于蒙;刘德汉4.基于激素调节机制IPSO算法的相同并行机混合流水车间调度问题 [J], 顾文斌;李育鑫;钱煜晖;肖紫涵;秦展鹏5.帝国竞争算法求解资源约束混合流水车间调度问题 [J], 李俊青;李荣昊;陶昕瑞;曾清清;耿雅典因版权原因，仅展示原文概要，查看原文内容请购买。
基于遗传算法的多目标混合流水线优化问题研究一、引言多目标混合流水线问题是一类NP难问题，因为其具有大规模、复杂性高和求解时间长等特点，难以通过传统的优化方法来求解。
而遗传算法是一个能够处理复杂的问题和不确定性因素的有效工具，也被广泛用于求解多目标优化问题。
二、多目标混合流水线问题多目标混合流水线问题是指在一个生产线之中，工件的加工顺序是不同的，并且加工时间也是不同的。
该问题的目标是确定各个加工工序的时间和顺序，以最小化生产线的空闲时间和最大化生产的产量。
混合流水线问题引入了不确定性，并给流水线排程造成种种不利影响。
因此解决多目标混合流水线问题具有重要的理论和现实意义。
三、遗传算法遗传算法是以生物进化的自然选择和遗传机制为基础的一种优化算法，它模拟自然界中生物群体的进化过程，利用遗传操作和进化策略来搜索全局最优解。
遗传算法的优势在于可以跨越局部极值，并且适用于求解大规模和复杂问题。
四、基于遗传算法的多目标混合流水线优化模型遗传算法可以表示为一个优化问题，即求解一个代表所有种群个体的值域向量，使得该向量在约束条件下满足多个目标函数的最小值或最大值。
基于遗传算法的多目标混合流水线优化问题的模型如下：目标函数：其中，f1表示流水线的加工时间，f2表示流水线的空闲时间，f3表示流水线的总和加工时间。
约束条件：工件顺序必须相同。
因此，基于遗传算法的多目标混合流水线优化问题可以被看作是一个三维的多目标问题，包含连续和离散的变量。
遗传算法的目标是在搜索空间中找到一组个体，使得它们能够满足所有的约束条件，并且较好地优化目标函数。
五、算法实现实现基于遗传算法的多目标混合流水线优化问题，需要先确定以下参数：1.种群大小：种群规模的大小直接影响到算法的性能和搜索质量。
在实际应用中，种群大小一般在20-50之间选择。
2.交叉率和变异率：交叉率用于控制交叉算子的使用程度，变异率用于控制变异算子的使用程度。
一般情况下，交叉率设置为0.6-0.8，变异率设置为0.05-0.1。
车间作业调度问题综述随着加入WTO，市场竞争越来越激烈，对制造企业来说，为了能够在竞争中立于不败，降低成本是不得不面临的问题，而确保生产车间较高的生产能力和效率，是当务之急。
此外，有效的调度方法已经成为先进制造技术实践的基础和关键，所以对它的研究具有重要的理论和实用价值。
1 车间调度问题表述1.1 调度问题表述总的来，车间调度就是对一个可用的加工机床集在时间上进行加工任务集分配，以满足一个性能指标集。
从数学规划的角度看，车间调度问题可表示为在等式或不等式约束下，对目标函数的优化。
典型的车间调度问题包括一个要完成的作业集，每个作业由一个操作集组成，各操作的加工需要占用机床或其它资源，并且必须按一些可行的工艺次序进行加工；每台机床可加工工件的若干操作，并且在不同的机床上能加工的操作集可以不同。
调度的目标是将作业合理地安排到各机床，并合理地安排作业的加工次序和加工开始时间，使约束条件被满足，同时优化一些性能指标。
实际制造系统，还要考虑刀具、托盘和物料搬运系统的调度问题。
1.2 车间调度问题的分类和特点按照不同的标准，可以将调度问题分为6种类型：1）开环和闭环车间；2）单处理机、多处理机、Flow Shop（各工件加工路径一致）和Job Shop（各工件加工路径不一致）；3）基于调度费用和基于调度性能的指标；4）确定性调度、随机性调度；5）静态调度、动态调度；6）有序加工、无序加工等。
而现代车间调度问题多是Job Shop型，其调度问题有如下特点：1）建模复杂性；2）计算复杂性；3）动态随机性；4）多约束性；5）多目标性。
2 研究现状与方法在1954年，Johnson对两台机床的Flow Shop型调度问题进行了研究后，便开始了对调度问题的广泛研究。
经过近50年的发展，车间调度问题的研究方法经历了从简单到复杂、从单一到多元的过程，大体有如下几种类型。
2.1 数学规划方法（mathematical programming）数学规划法在车间调度中被广泛应用，调度问题可以用整数规划法、混合整数规划法和动态规划法来描述。
车间作业调度(JSSP)技术问题简明综述l 引言生产调度是CIMS 研究领域生产管理的核心内容和关键技术，车间作业调度问题(JSSP)是最困难的约束组合优化问题和典型的NP 难问题，其特点是没有一个有效的算法能在多项式时间内求出其最优解． 现代经济日益强化的竞争趋势和不断变化的用户需求要求生产者要重新估价生产制造策略，如更短的产品生产周期和零库存系统等，而JSSP 生产环境最适宜满足现有经济和用户的需求． 利用有限的资源满足被加工任务的各种约束，并确定工件在相关设备上的加工顺序和时间，以保证所选择的性能指标最优，能够潜在地提高企业的经济效益，JSSP 具有很多实际应用背景，开发有效而精确的调度算法是调度和优化领域重要的课题．研究JSSP 问题最初主要采用最优化方法，但计算规模不可能很大，且实用性差．近年来，基于生物学、物理学、人工智能、神经网络、计算机技术及仿真技术的迅速发展，为调度问题的研究开辟了新的思路． 本文根据JSSP 问题的大量文献，对研究理论与方法进行系统的分类并介绍这一领域的最新进展，讨论进一步的研究方向．2 JSSP 问题的一般框架2．1 问题描述JSSP 问题可描述为：m 台机器(用集合()m j j M M 1==表示)加n 个工件(用集合|()ni i J J 1== 表示)，每个工件包含由多道工序组成的一个工序集合． 工件有预先确定的加工顺序，每道工序的加工时间t 在给定的时间每个机器只能加工一个工件，并且每个工件只能由一台机器处理． 不同工件的加工顺序无限制，工序不允许中断；要求在可行调度中确定每个工序的开始时间ij s 使总完工时间max C 最小，即(){}M M J J t s C C j i ij ij ∈∈∀+==,:max min )min(max *max 求解满足以上条件的工件加工顺序即构成JSSP 调度问题．流水作业调度问题(FSSP)是JSSP 问题的特殊形式(即所有工件有相同的加工工序)． 此外目标函数可选取等待时间、流程时间和延期时间的平均值或者最大值等，或多个目标组合形成的多目标问题．2．2 JSSP 的模型表示2．2．1 整数规划(IP)模型整数规划模型由Baker 提出，需要考虑两类约束：工件工序的前后约束和工序的非堵塞约束． 用jk t 和 jk c 分别表示工件 j 在机器k 上的加工时间和完工时间．如果机器h 上的工件加工工序先于机器K （用k h J J <表示），则有关系式jh jk jk c t c ≥-；反之，如果h k J J <，有jk jh jh c t c ≥-。
第１３卷㊀第７期Ｖｏｌ．１３Ｎｏ．７㊀㊀智㊀能㊀计㊀算㊀机㊀与㊀应㊀用ＩｎｔｅｌｌｉｇｅｎｔＣｏｍｐｕｔｅｒａｎｄＡｐｐｌｉｃａｔｉｏｎｓ㊀㊀２０２３年７月㊀Ｊｕｌ．２０２３㊀㊀㊀㊀㊀㊀文章编号：２０９５－２１６３（２０２３）０７－００５８－０６中图分类号：ＴＰ３９１．４１文献标志码：Ａ基于遗传算法求解ＴＳＰ问题的研究及Ｍａｔｌａｂ实现杨锦涛，赵春香，杨成福（云南师范大学信息学院，昆明６５０５００）摘㊀要：ＴＳＰ问题属于组合优化问题，同时也是一个ＮＰＣ问题，因此人们一直致力于为其寻找有效的近似求解算法㊂遗传算法是模仿生物进化而构建的一种随机搜索方法，具有较强的全局搜索能力㊁潜在的并行性以及良好的可扩展性，能有效求解ＴＳＰ问题㊂然而，如何确定遗传参数和选择遗传操作一直是一个难题，本文针对ＴＳＰ问题的求解构建完整的遗传算法体系，选择合适的参数，设计多组交叉算子和变异算子，分别对ＴＳＰ问题进行求解㊂通过多次实验以及对实验结果的分析比较，探究不同的交叉算子和变异算子求解ＴＳＰ问题的效果，为遗传操作中交叉算子和变异算子的选择提供一定的参考㊂关键词：ＴＳＰ问题；组合优化；遗传算法ＲｅｓｅａｒｃｈｏｎｓｏｌｖｉｎｇＴＳＰｐｒｏｂｌｅｍｂａｓｅｄｏｎｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍａｎｄＭａｔｌａｂｉｍｐｌｅｍｅｎｔａｔｉｏｎＹＡＮＧＪｉｎｔａｏ，ＺＨＡＯＣｈｕｎｘｉａｎｇ，ＹＡＮＧＣｈｅｎｇｆｕ（ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎ，ＹｕｎｎａｎＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｋｕｎｍｉｎｇ６５０５００，Ｃｈｉｎａ）ʌＡｂｓｔｒａｃｔɔＴｈｅＴＳＰｐｒｏｂｌｅｍｂｅｌｏｎｇｓｔｏｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓａｎｄｉｓａｌｓｏａｎＮＰＣｐｒｏｂｌｅｍ，ｓｏｐｅｏｐｌｅｈａｖｅｂｅｅｎｔｒｙｉｎｇｔｏｆｉｎｄｔｈｅｃｏｒｒｅｓｐｏｎｄｉｎｇｅｆｆｅｃｔｉｖｅａｐｐｒｏｘｉｍａｔｉｏｎｓｏｌｖｉｎｇａｌｇｏｒｉｔｈｍｓ．Ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｉｓａｒａｎｄｏｍｓｅａｒｃｈｍｅｔｈｏｄｂｕｉｌｔｔｏｉｍｉｔａｔｅｂｉｏｌｏｇｉｃａｌｅｖｏｌｕｔｉｏｎ，ｗｉｔｈｓｔｒｏｎｇｇｌｏｂａｌｓｅａｒｃｈａｂｉｌｉｔｙ，ｐｏｔｅｎｔｉａｌｐａｒａｌｌｅｌｉｓｍａｎｄｇｏｏｄｓｃａｌａｂｉｌｉｔｙ，ｗｈｉｃｈｃａｎｅｆｆｅｃｔｉｖｅｌｙｓｏｌｖｅＴＳＰｐｒｏｂｌｅｍｓ．Ｈｏｗｅｖｅｒ，ｈｏｗｔｏｄｅｔｅｒｍｉｎｅｇｅｎｅｔｉｃｐａｒａｍｅｔｅｒｓａｎｄｓｅｌｅｃｔｇｅｎｅｔｉｃｍａｎｉｐｕｌａｔｉｏｎｈａｓａｌｗａｙｓｂｅｅｎａｄｉｆｆｉｃｕｌｔｐｒｏｂｌｅｍ．Ｉｎｔｈｉｓｐａｐｅｒ，ａｃｏｍｐｌｅｔｅｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓｙｓｔｅｍｉｓｃｏｎｓｔｒｕｃｔｅｄｆｏｒｔｈｅｓｏｌｕｔｉｏｎｏｆＴＳＰｐｒｏｂｌｅｍｓ，ａｐｐｒｏｐｒｉａｔｅｐａｒａｍｅｔｅｒｓａｒｅｓｅｌｅｃｔｅｄ，ａｎｄｍｕｌｔｉｐｌｅｓｅｔｓｏｆｃｒｏｓｓｏｐｅｒａｔｏｒｓａｎｄｍｕｔａｔｉｏｎｏｐｅｒａｔｏｒｓａｒｅｄｅｓｉｇｎｅｄｔｏｓｏｌｖｅＴＳＰｐｒｏｂｌｅｍｓｓｅｐａｒａｔｅｌｙ．Ｔｈｒｏｕｇｈｍｕｌｔｉｐｌｅｅｘｐｅｒｉｍｅｎｔｓａｎｄｔｈｅａｎａｌｙｓｉｓａｎｄｃｏｍｐａｒｉｓｏｎｏｆｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓ，ｔｈｅｅｆｆｅｃｔｏｆｄｉｆｆｅｒｅｎｔｃｒｏｓｓｏｖｅｒｏｐｅｒａｔｏｒｓａｎｄｍｕｔａｔｉｏｎｏｐｅｒａｔｏｒｓｉｎｓｏｌｖｉｎｇＴＳＰｐｒｏｂｌｅｍｓｉｓｅｘｐｌｏｒｅｄ，ｗｈｉｃｈｐｒｏｖｉｄｅｓａｃｅｒｔａｉｎｒｅｆｅｒｅｎｃｅｆｏｒｔｈｅｓｅｌｅｃｔｉｏｎｏｆｃｒｏｓｓｏｖｅｒｏｐｅｒａｔｏｒｓａｎｄｍｕｔａｔｉｏｎｏｐｅｒａｔｏｒｓｉｎｇｅｎｅｔｉｃｏｐｅｒａｔｉｏｎｓ．ʌＫｅｙｗｏｒｄｓɔＴＳＰｐｒｏｂｌｅｍ；ｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉｍｉｚａｔｉｏｎ；ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ基金项目：云南师范大学博士科研启动基金（２０２１ＺＢ０１９）㊂作者简介：杨锦涛（２００２－），女，本科生，主要研究方向：深度学习；赵春香（２０００－），女，本科生，主要研究方向：深度学习；杨成福（１９８６－），男，博士，讲师，硕士生导师，主要研究方向：信息超材料㊁深度学习㊁人工智能㊂通讯作者：杨成福㊀㊀Ｅｍａｉｌ：ｙａｎｇｃｈｅｎｇｆｕ＠ｙｎｎｕ．ｅｄｕ．ｃｎ收稿日期：２０２２－１２－１８０㊀引㊀言ＴＳＰ问题㊁即巡回旅行商问题，是组合优化领域中的一个典型问题㊂现实生活中的很多实际应用问题都可以简化为ＴＳＰ问题㊂ＴＳＰ问题可以用图论描述为：已知带权完全图Ｇ，求一条使得路径总和最小㊁且经过所有顶点的回路㊂ＴＳＰ问题虽然描述简单㊁容易理解，但是求解是很困难的㊂当问题的规模较小时，仅使用枚举法就能找到一条最优路径，但当城市数量较多时，即使用计算机也无法将解全部列举，要求出ＴＳＰ问题的最优解是不可能的㊂遗传算法是一种自组织㊁自适应的全局寻优算法，因其潜在的并行性㊁较高的鲁棒性，在应用研究方面取得了很多可观的成果，被广泛应用于函数优化㊁组合优化㊁生产调度㊁自适应控制㊁图像处理㊁机器学习㊁数据挖掘㊁人工生命㊁遗传编程等领域㊂１９７５年，Ｈｏｌｌａｎｄ［１］受生物学中生物进化和自然选择学说的启发，提出了著名的遗传算法㊂２００６年，何燕［２］对遗传算法进行改进，将其应用到车间调度领域㊂２０１０年，蒋波［３］将遗传算法应用于车辆路径优化问题，指出遗传算法求解该问题的优越性，并对其做出了改进，实验证明改进后的遗传算法能Copyright ©博看网. All Rights Reserved.够有效解决此类问题㊂２０１３年，乔阳［４］将遗传算法和Ｏｓｔｕ图像分割法进行改进后结合在一起进行图像分割实验，得到了满意的结果㊂遗传算法是模拟生物进化的过程发展而来的一种算法，从一定规模的解集（初始种群）开始，通过选择㊁交叉和变异，将适应度低的解（个体）淘汰掉，将适应度高的解（个体）保留下来，并产生新的解（个体），生成新的解集（种群），通过不断地迭代，使解集（种群）中的解（个体）越来越接近问题的最优解㊂生物学和遗传算法概念之间的对应关系见表１㊂表１㊀生物学和遗传算法概念对照Ｔａｂ．１㊀Ｃｏｍｐａｒｉｓｏｎｏｆｂｉｏｌｏｇｉｃａｌａｎｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｃｏｎｃｅｐｔｓ生物学遗传算法外界环境约束条件个体问题的一个可行解个体对环境的适应度可行解的质量种群一定数量可行解的集合生物的繁衍算法的迭代种群的进化过程可行解的优化过程㊀㊀本文针对ＴＳＰ问题构建完整的遗传算法体系，将求解ＴＳＰ问题几种常用的交叉算子和变异算子两两组合在一起，分别对具体的ＴＳＰ问题实例进行求解，从所得的最优解和求解的时间两方面对实验结果进行分析和总结，探究使用不同的交叉算子和变异算子时遗传算法求解对称式ＴＳＰ问题的效果［５］㊂１㊀遗传算法求解ＴＳＰ问题１．１㊀编码编码是指按照一定的构造方法，将问题的可行解转变为遗传算法能直接处理的个体㊂常用的编码方式有二进制编码㊁近邻编码㊁次序编码㊁路径编码［６］㊂使用路径编码求解ＴＳＰ问题，不仅编码过程简单易操作，而且编码结果非常直观，即首先对城市进行编号，然后以城市编号作为城市的编码，因此本文选择使用路径编码方式对城市进行编码㊂１．２㊀初始种群一般地，初始种群采用随机方法生成，如果种群规模为Ｍ，则随机生成Ｍ个个体㊂１．３㊀适应度函数适应度函数用于对种群中的个体进行优劣程度的评价，由于算法在搜索最优解的过程中主要以个体的适应度作为依据，所以如果适应度函数构建不当，很可能导致算法的收敛速度缓慢㊁甚至无法收敛，即适应度函数直接决定着算法的收敛能力和寻优能力㊂对于ＴＳＰ问题，适应度函数一般取路径总和的倒数，具体定义公式见如下：ｆ（ｘ）＝１ðｎ－１ｉ＝１ｄ（ｔｉ，ｔｉ＋１）＋ｄ（ｔｎ，ｔ１）（１）㊀㊀其中，ｎ表示城市的数量；Ｔ＝（ｔ１，ｔ２， ，ｔｎ）为种群中的一个个体；ｄ（ｔｉ，ｔｊ）表示城市ｉ到城市ｊ的距离㊂ＴＳＰ问题为最小值问题，由适应度函数可知，路径总和与个体适应度呈倒数关系㊂１．４㊀遗传操作１．４．１㊀选择算子选择是用选择算子对个体进行筛选的过程，这一过程中，差的个体被保留下来的概率小，好的个体被保留下来的概率大，会使种群中的个体向最优解进化㊂常用的选择算子有轮盘赌选择㊁最佳个体保存选择㊁锦标赛选择和排序选择［７］㊂轮盘赌选择是ＴＳＰ问题求解最常用的选择算子，即使用适应度值计算出每个个体被选择的概率，并根据该概率值对种群中的个体进行选择㊂本文也使用轮盘赌选择作为选择算子，并在轮盘赌的基础上添加最佳个体保存选择，即把种群中出现过的适应度值最高的个体保留下来，避免种群中优秀的个体在遗传操作中被淘汰或破坏㊂１．４．２㊀交叉算子个体交叉是为了实现种群的更新，而交叉算子是进行交叉的手段，定义了个体之间以怎样的方式交叉㊂对于不同问题，由于编码方式的不同，交叉算子也有所不同㊂对此拟做研究分述如下㊂（１）部分匹配交叉（ＰＭＸ）：首先采用随机方式在父体中确定２个位置，由２个位置确定一个交叉段，然后将２个父体的交叉段进行交换，最后根据交叉段之间的映射关系消除子代中的重复基因㊂（２）顺序交叉（ＯＸ）：首先从父体中随机选择２个位置，由２个位置确定一个基因段，然后将父体Ａ的该基因段复制到子代Ａ 的对应位置，最后将父体Ｂ除父体Ａ被选择的基因段之外的基因依次复制到子代Ａ 的其余位置，同理可得到子代Ｂ ㊂（３）循环交叉（ＣＸ）：首先将父体Ａ的第一个基因复制到子代，然后在父体Ｂ中的相同位置查看基因，随后在父体Ａ中找到该基因复制到子代的相同位置，并在父体Ｂ中查看相同位置的基因，重复此步骤，直到在父体Ｂ中找到的基因已经在子代中，停止循环，在父体Ｂ中找到剩余的基因，并按照顺序复制到子代中的剩余位置㊂９５第７期杨锦涛，等：基于遗传算法求解ＴＳＰ问题的研究及Ｍａｔｌａｂ实现Copyright©博看网. All Rights Reserved.１．４．３㊀变异算子变异操作的主要目的是维持种群多样性，在遗传算法后期，个体交叉产生新个体的能力弱，通过个体变异可以进一步产生新个体，扩大搜索空间㊂接下来给出剖析论述如下㊂（１）对换变异㊂首先用随机方式在父体中确定２个位置，然后交换这２个位置上的基因㊂（２）倒位变异㊂用随机方式在父体中确定２个位置，以确定一个基因段，然后将其进行逆序排列㊂（３）插入变异㊂用随机方式在父体中确定一个位置，以确定一个待插入的基因，再用随机方式确定２个位置，以确定插入点，最后将待插入的基因放入插入点㊂１．５㊀遗传算法求解ＴＳＰ问题具体步骤根据上文选择的实现技术构建完整的遗传算法体系后，对ＴＳＰ问题实例进行求解的具体步骤如下：Ｓｔｅｐ１㊀获取城市数据，对城市进行编号㊂Ｓｔｅｐ２㊀初始化种群㊂Ｓｔｅｐ３㊀适应度评价㊂Ｓｔｅｐ４㊀执行选择操作，采用轮盘赌选择对个体进行筛选，选出足够数量的个体㊂Ｓｔｅｐ５㊀执行交叉操作，将选择操作中选出的个体两两组合作为父染色体，判断是否进行交叉，如果进行交叉，则按照选定的交叉算子进行交叉㊂Ｓｔｅｐ６㊀执行变异操作，将执行交叉操作后的每个个体作为父染色体，判断是否进行变异，如果进行变异，则按照选定的变异算子进行变异㊂Ｓｔｅｐ７㊀完成变异后，执行最佳个体保存策略，判断当前种群中的最优解是否优于历史最优解㊂如果是，更新历史最优解，否则找出种群中最差的解，用最优解将其替换掉㊂Ｓｔｅｐ８㊀判断是否继续进行迭代，若是，回到Ｓｔｅｐ３；否则，结束迭代，输出最优解㊂㊀㊀将前述的３种交叉算子和３种变异算子两两组合在一起，共有９种组合方式，见表２㊂基于表２中列出的９种组合，重复对ＴＳＰ问题进行求解㊂表２㊀９组交叉算子和变异算子Ｔａｂ．２㊀９ｓｅｔｓｏｆｃｒｏｓｓｏｖｅｒａｎｄｍｕｔａｔｉｏｎｏｐｅｒａｔｏｒｓ组合编号交叉算子变异算子第一组部分匹配交叉对换变异第二组部分匹配交叉倒位变异第三组部分匹配交叉插入变异第四组循序交叉对换变异第五组循环交叉倒位变异第六组循环交叉插入变异第七组顺序交叉对换变异第八组顺序交叉倒位变异第九组顺序交叉插入变异２㊀实验及结果分析２．１㊀实验仿真本文使用Ｍａｔｌａｂ实现上文构建的遗传算法，从ＴＳＰＬＩＢ中选择测试样例进行具体分析㊂ＴＳＰＬＩＢ是包含对称旅行商问题㊁哈密顿回路问题㊁以及非对称旅行商问题的多种实例数据的文件库，数据规模多样㊂本文在对每个测试样例进行求解时，改变算法的交叉算子和变异算子，进行多次重复的实验，从问题的最优解和求解时间两方面对几组交叉算子和变异算子求解ＴＳＰ问题的效果进行分析比较㊂在完成算法的编程后，初步设置参数，对实例Ｏｌｉｖｅｒ３０进行求解，根据实验结果对算法的参数进行调整，最终选定迭代次数Ｇ为５００，交叉概率Ｐｃ为０．９，变异概率Ｐｍ为０．２，种群规模Ｍ根据待求解问题的规模来确定㊂一般地，城市个数越多，种群规模越大，对３０个城市的实例Ｏｌｉｖｅｒ３０，种群规模取１００㊂用上述９组交叉算子和变异算子分别对Ｏｌｉｖｅｒ３０求解１０次的结果见表３㊂表３㊀遗传算法求解Ｏｌｉｖｅｒ３０Ｔａｂ．３㊀ＧｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒＯｌｉｖｅｒ３０序号第一组第二组第三组第四组第五组第六组第七组第八组第九组１５１１．９８４２５．１０５２６．４０５１０．０３４２５．４８４９６．３４５３２．７５４２５．７２４７２．３６２５６５．５６４２９．６２４５１．６９５３８．１０４２３．７４４７９．０１５０１．０９４２８．０４４９５．３５３４９５．８０４３２．６６４６８．３２４９６．６５４７６．１２４９５．１９５１４．３０４２８．８４４７６．０９４４９６．８４４２５．１０４３３．０９５３４．１４４２４．１２４５７．７３５０１．５４４３１．７１４５７．７４５５４１．８０４６０．１７４６４．９１５３６．８９４５１．７２４４５．９７４９６．２４４３５．３１４７４．２１６５００．８８４２９．８３４９４．４５５２５．４４４３８．３８４８３．９２５０７．５７４５０．４１４７８．８０７５０１．９２４３２．６６５２１．３３５１４．３０４２５．２７４６６．６５５６１．８５４２８．４６４６０．７４８５１４．９０４５０．６９４９７．４６４８８．２１４２５．３１４８４．１８５１５．１３４２３．７４４７４．７３９５２９．０６４４７．２１４８７．６０４８２．６１４３４．６１５００．１８５７１．７９４３１．７６４６６．６９１０５５６．３１４２５．７３５０７．６４５１０．６１４３３．５４４７１．１８４５６．７９４３８．３８４８３．２７０６智㊀能㊀计㊀算㊀机㊀与㊀应㊀用㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀第１３卷㊀Copyright©博看网. All Rights Reserved.㊀㊀以文献［８］中求得的最优解４２３．７４作为参考值，从表３可以看出第２组㊁第５组㊁第８组交叉算子和变异算子的求解结果都比较接近参考最优解，且较稳定，说明参数设置较合理㊂其中一次求解的收敛曲线如图１所示，最优路线如图２所示㊂其中，以圆圈标记的点为路线起点，其与路线终点用虚线相连，其余路线用实线连接㊂12001000800600400200400600迭代次数最优解图１㊀Ｏｌｉｖｅｒ３０收敛曲线Ｆｉｇ．１㊀ＣｏｎｖｅｒｇｅｎｃｅｃｕｒｖｅｏｆＯｌｉｖｅｒ３０1008060402020406080100城市横坐标城市纵坐标图２㊀Ｏｌｉｖｅｒ３０最优路线图Ｆｉｇ．２㊀ＯｐｔｉｍａｌｒｏａｄｍａｐｏｆＯｌｉｖｅｒ３０２．２㊀实验结果从ＴＳＰＬＩＢ中选择测试样例进行求解，本文总共选择了５个实例，分别是ｕｌｙｓｓｅｓ１６㊁ｄａｎｔｚｉｇ４２㊁ｅｉｌ５１㊁ｅｉｌ７６㊁ｅｉｌ１０１，根据问题的规模为每个实例设置合适的种群规模（Ｍ）㊂其中，ｕｌｙｓｓｅｓ１６㊁ｄａｎｔｚｉｇ４２㊁ｅｉｌ５１实例的种群规模取１００，ｅｉｌ７６实例的种群规模取１５０，ｅｉｌ１０１实例的种群规模取２００，分别用上述９组交叉算子和变异算子求解１０次，记录１０次求解结果的最好值（Ｂｅｓｔ）㊁平均值（ＡＶＲ）和偏差率（Ｄｒ），以及求解的平均时间（Ｔｉｍｅ），这里的偏差率可由式（２）来计算：Ｄｒ＝Ｂｅｓｔ－ＯｐｔＯｐｔ（２）㊀㊀其中，Ｏｐｔ是ＴＳＰＬＩＢ数据集提供的最优解㊂实验结果见表４ 表８㊂表４㊀遗传算法求解ｕｌｙｓｓｅｓ１６Ｔａｂ．４㊀Ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｕｌｙｓｓｅｓ１６序号ＡＶＧＢｅｓｔＯｐｔＤｒＴｉｍｅ／ｓ第１组第２组第３组第４组第５组第６组第７组第８组第９组７５．０１７４．０１７４．２４７４．３６７４．０５７４．２０７４．６０７４．０９７４．２８７４．００７３．９９７３．９９７３．９９７３．９９７３．９９７３．９９７３．９９７３．９９７４０．０００．０００．０００．０００．０００．０００．０００．０００．００１．２１．１１．４０．７０．７０．７０．５０．５０．５表５㊀遗传算法求解ｄａｎｔｚｉｇ４２Ｔａｂ．５㊀Ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｄａｎｔｚｉｇ４２序号ＡＶＧＢｅｓｔＯｐｔＤｒＴｉｍｅ／ｓ第１组第２组第３组第４组第５组第６组第７组第８组第９组１０２２．３４７５６．４９９１５．６９９４４．０２７３３．００８９４．３２１０６１．２１７６０．７３９３７．２２８６４．８９７１３．９９８３８．３８８５８．２６６９８．９８７９４．０２８９３．３５７２５．３７８４６．４１６９９０．２４０．０２０．２００．２３０．０００．１４０．２８０．０４０．２１１．４１．６２．８１．０１．０１．００．７０．６０．７表６㊀遗传算法求解ｅｉｌ５１Ｔａｂ．６㊀Ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｅｉｌ５１序号ＡＶＧＢｅｓｔＯｐｔＤｒＴｉｍｅ／ｓ第１组第２组第３组第４组第５组第６组第７组第８组第９组６４２．６６５１６．３５５９２．００６４６．０９５０３．９７５８０．３９６５７．４８５１１．９１６０７．４２６１３．８７４８７．９５５３２．９０５５９．６８４８１．６７５３４．４１６０４．８１４６５．２８５５１．７０４２６０．４４０．１５０．２５０．３１０．１３０．２５０．４２０．０９０．３０１．４１．８３．６１．１１．１１．１０．７０．７０．７１６第７期杨锦涛，等：基于遗传算法求解ＴＳＰ问题的研究及Ｍａｔｌａｂ实现Copyright ©博看网. All Rights Reserved.表７㊀遗传算法求解ｅｉｌ７６Ｔａｂ．７㊀Ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｅｉｌ７６序号ＡＶＧＢｅｓｔＯｐｔＤｒＴｉｍｅ／ｓ第１组第２组第３组第４组第５组第６组第７组第８组第９组１０３７．９４８８０．６４１００２．０１１０１２．３２８３５．３７９９３．６９１０７３．７８８３３．７７９９２．８９９７１．９６８０６．５３９１６．５２９４９．１７７９２．３９９２５．７４１０１４．８６７８１．８８８９４．４７５３８０．８１０．５００．７００．７６０．４７０．７２０．８９０．４５０．６６２．２３．２９．５１．８１．８１．８０．９１．０１．０表８㊀遗传算法求解ｅｉｌ１０１Ｔａｂ．８㊀Ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｅｉｌ１０１序号ＡＶＧＢｅｓｔＯｐｔＤｒＴｉｍｅ／ｓ第１组第２组第３组第４组第５组第６组第７组第８组第９组１４７０．９４１３４０．３３１４５２．０２１４６８．１７１１９４．４９１４０８．３３１４７９．１２１２３８．６８１４３８．３９１３６１．７８１２８６．６４１３６３．６７１３５２．２４１１４２．１９１２９７．４３１３９７．６９１１６８．２５１３４０．９３６２９１．１６１．０５１．１７１．１５０．８２１．０６１．２２０．８６１．１３３．２５．３２０．４２．７２．７２．７１．２１．２１．２㊀㊀为了方便对比，将每个实例求解结果中的偏差率（Ｄｒ）和求解的平均时间（Ｔｉｍｅ）分别统计在一起，由于实例ｕｌｙｓｓｅｓ１６问题规模小，坐标数据也容易处理，不管选择哪种交叉算子和变异算子，求解结果都很接近最优解，因此在进行偏差率的比较时不将其考虑在内，具体见表９㊁表１０㊂表９㊀偏差率对比Ｔａｂ．９㊀Ｄｅｖｉａｔｉｏｎｒａｔｅｃｏｍｐａｒｉｓｏｎ序号ｄａｎｔｚｉｇ４２ｅｉｌ５１ｅｉｌ７６ｅｉｌ１０１第１组第２组第３组第４组第５组第６组第７组第８组第９组０．２４０．０２０．２００．２３０．０００．１４０．２８０．０４０．２１０．４４０．１５０．２５０．３１０．１３０．２５０．４２０．０９０．３００．８１０．５００．７００．７６０．４７０．７２０．８９０．４５０．６６１．１６１．０５１．１７１．１５０．８２１．０６１．２２０．８６１．１３表１０㊀求解平均时间对比Ｔａｂ．１０㊀Ｃｏｍｐａｒｉｓｏｎｏｆａｖｅｒａｇｅｓｏｌｖｉｎｇｔｉｍｅ序号ｕｌｙｓｓｅｓ１６ｄａｎｔｚｉｇ４２ｅｉｌ５１ｅｉｌ７６ｅｉｌ１０１第１组第２组第３组第４组第５组第６组第７组第８组第９组１．２１．１１．４０．７０．７０．７０．５０．５０．５１．４１．６２．８１．０１．０１．００．７０．６０．７１．４１．８３．６１．１１．１１．１０．７０．７０．７２．２３．２９．５１．８１．８１．８０．９１．０１．０３．２５．３２０．４２．７２．７２．７１．２１．２１．２３㊀实验结论根据上述实验结果，可以得出如下结论：（１）表９中的偏差率描述了采用不同的交叉算子和变异算子时，所求得的最优解与ＴＳＰＬＩＢ中给出的最优解的差距，偏差率越小，说明算法求得的结果越接近最优解，算法的寻优能力越好㊂从表９中可以看出，第２组数据总是小于第１组和第３组㊁第５组数据总是小于第４组和第６组㊁第８组数据总是小于第７组和第９组，这说明每种交叉算子和逆转变异组合在一起时，问题的求解结果总是比与对换变异和插入变异组合在一起时更接近最优解㊂由此可知，遗传算法使用逆转变异作为变异算子时比选择对换变异和插入变异作为变异算子的寻优能力更强㊂（２）表１０是采用每组交叉算子和变异算子求解每个实例１０次所花时间的平均值，所花的时间越少，说明算法的搜索速度越快，执行效率越高，由于变异操作比较简单，所以遗传算法的执行效率主要由交叉操作决定㊂从表１０中可以看出，遗传算法采用顺序交叉和循环交叉时，即使采用不同的变异算子，所花的时间也基本相同，但是采用部分匹配交叉所花的时间会因为变异算子的不同而有所不同㊂对于每一个实例，在得到的解的质量差别不大的情况下，遗传算法使用部分匹配交叉所花的时间最多，使用循环交叉所花的时间最少㊂综上所述，对于比较简单的ＴＳＰ问题，由于使用遗传算法总能求得与最优解很接近的解，所以选择何种交叉算子和变异算子对算法的寻优能力影响不大，但是使用部分匹配交叉会花费比较多的时间，会导致算法的执行效率低，因此交叉算子选择循环２６智㊀能㊀计㊀算㊀机㊀与㊀应㊀用㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀第１３卷㊀Copyright©博看网. All Rights Reserved.交叉比较合适㊂对于不是总能求得最优解的ＴＳＰ问题，与对换变异和插入变异相比，使用逆转变异会使算法具有更强的寻优能力，找到的最优解更接近最优解，使用部分匹配交叉和顺序交叉会花费比循环交叉更多的时间，使算法的执行效率变低，而且找到的最优解也不会更优㊂４ 结束语本文对几种常用的交叉算子和变异算子求解ＴＳＰ问题的效果进行了研究㊂实验结果表明，在几种常用的交叉算子和变异算子中，选择循环交叉和逆转变异算法的执行效率最高，寻优能力最好，这能为遗传算法中交叉算子和变异算子的选择提供一定的参考，同时有利于设计出更好的交叉算子和变异算子，提高算法的性能㊂参考文献［１］ＨＯＬＬＡＮＤＪ．Ａｄａｐｔａｔｉｏｎｉｎｎａｔｕｒａｌａｎｄａｒｔｉｆｉｃｉａｌｓｙｓｔｅｍｓ：ａｎｉｎｔｒｏ⁃ｄｕｃｔｏｒｙａｎａｌｙｓｉｓｗｉｔｈａｐｐｌｉｃａｔｉｏｎｔｏｂｉｏｌｏｇｙ［Ｊ］．ＣｏｎｔｒｏｌＡｒｔｉｆｉｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅ，１９７５．［２］何燕．基于遗传算法的车间调度优化及其仿真［Ｄ］．武汉：武汉理工大学，２００６．［３］蒋波．基于遗传算法的带时间窗车辆路径优化问题研究［Ｄ］．北京：北京交通大学，２０１０．［４］乔阳．基于改进遗传算法的图像分割方法［Ｄ］．成都：电子科技大学，２０１３．［５］张家善，王志宏，陈应显，等．一种求解旅行商问题的改进遗传算法［Ｊ］．计算机系统应用，２０１２，２１（０９）：１９２－１９４，１９１．［６］王娜．求解ＴＳＰ的改进遗传算法［Ｄ］．西安：西安电子科技大学，２０１０．［７］于丰瑞．基于改进的遗传算法求解ＴＳＰ问题［Ｄ］．呼和浩特：内蒙古农业大学，２０１６．［８］闫茹．基于改进遗传算法的旅游路线优化研究与应用［Ｄ］．银川：北方民族大学，２０２１．（上接第５７页）［３］田浩杰，杨晓庆，翟晓雨．基于深度学习的线圈炮缺陷自动检测与分类［Ｊ］．现代计算机，２０２２，２８（１０）：８６－９１．［４］张浩，吴陈，徐影．基于深度学习在海缆表面缺陷检测中的应用［Ｊ］．电脑知识与技术，２０２２，１８（１５）：８８－９１．［５］陈宗仁，谢文达，余君，等．基于深度学习的金属机械零件表面缺陷检测方法［Ｊ］．制造业自动化，２０２１，４３（１２）：１７０－１７３．［６］王昊，李俊峰．基于深度学习的车载导航导光板表面缺陷检测研究［Ｊ］．软件工程，２０２２，２５（０３）：３４－３８，１６．［７］刘瑞珍，孙志毅，王安红，等．基于深度学习的偏光片缺陷实时检测算法［Ｊ］．太原理工大学学报，２０２０，５１（０１）：１２５－１３０．［８］王鸣霄，范娟娟，周磊，等．基于深度学习的排水管道缺陷自动检测与分类［Ｊ］．给水排水，２０２０，４６（１２）：１０６－１１１．［９］施恺杰，王颖，王嘉璐，等．基于深度学习的电子换向器表面缺陷检测［Ｊ］．网络安全技术与应用，２０２１（０６）：１１３－１１５．［１０］于宏全，袁明坤，常建涛，等．基于深度学习的铸件缺陷检测方法［Ｊ］．电子机械工程，２０２１，３７（０６）：５９－６４．［１１］ＬＥＣＵＮＹ，ＢＯＴＴＯＵＬ，ＢＥＮＧＩＯＹ，ｅｔａｌ．Ｇｒａｄｉｅｎｔ－ｂａｓｅｄｌｅａｒｎｉｎｇａｐｐｌｉｅｄｔｏｄｏｃｕｍｅｎｔｒｅｃｏｇｎｉｔｉｏｎ［Ｊ］．ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＩＥＥＥ，１９９８，８６（１１）：２２７８－２３２４．［１２］ＫＲＩＺＨＥＶＳＫＹＡ，ＳＵＴＳＫＥＶＥＲＩ，ＨＩＮＴＯＮＧＥ．Ｉｍａｇｅｎｅｔｃｌａｓｓｉｆｉｃａｔｉｏｎｗｉｔｈｄｅｅｐｃｏｎｖｏｌｕｔｉｏｎａｌｎｅｕｒａｌｎｅｔｗｏｒｋｓ［Ｊ］．ＣｏｍｍｕｎｉｃａｔｉｏｎｓｏｆｔｈｅＡＣＭ，２０１７，６０（６）：８４－９０．［１３］ＳＩＭＯＮＹＡＮＫ，ＺＩＳＳＥＲＭＡＮＡ．Ｖｅｒｙｄｅｅｐｃｏｎｖｏｌｕｔｉｏｎａｌｎｅｔｗｏｒｋｓｆｏｒｌａｒｇｅ－ｓｃａｌｅｉｍａｇｅｒｅｃｏｇｎｉｔｉｏｎ［Ｊ］．ａｒＸｉｖｐｒｅｐｒｉｎｔａｒＸｉｖ：１４０９．１５５６，２０１４．［１４］ＳＺＥＧＥＤＹＣ，ＬＩＵＷｅｉ，ＪＩＡＹａｎｑｉｎｇ，ｅｔａｌ．Ｇｏｉｎｇｄｅｅｐｅｒｗｉｔｈｃｏｎｖｏｌｕｔｉｏｎｓ［Ｃ］／／ＩＥＥＥＣｏｎｆｅｒｅｎｃｅｏｎＣｏｍｐｕｔｅｒＶｉｓｉｏｎａｎｄＰａｔｔｅｒｎＲｅｃｏｇｎｉｔｉｏｎ（ＣＶＰＲ）．Ｂｏｓｔｏｎ，ＭＡ，ＵＳＡ：ＩＥＥＥ，２０１５：１－９．［１５］ＨＥＫａｉｍｉｎｇ，ＺＨＡＮＧＸｉａｎｇｙｕ，ＲＥＮＳｈａｏｑｉｎｇ，ｅｔａｌ．Ｄｅｅｐｒｅｓｉｄｕａｌｌｅａｒｎｉｎｇｆｏｒｉｍａｇｅｒｅｃｏｇｎｉｔｉｏｎ［Ｃ］／／ＩＥＥＥＣｏｎｆｅｒｅｎｃｅｏｎＣｏｍｐｕｔｅｒＶｉｓｉｏｎａｎｄＰａｔｔｅｒｎＲｅｃｏｇｎｉｔｉｏｎ（ＣＶＰＲ）．ＬａｓＶｅｇａｓ，ＮＶ，ＵＳＡ：ＩＥＥＥ，２０１６：７７０－７７８．３６第７期杨锦涛，等：基于遗传算法求解ＴＳＰ问题的研究及Ｍａｔｌａｂ实现Copyright©博看网. All Rights Reserved.。
万方数据万方数据万方数据万方数据万方数据万方数据万方数据万方数据差分进化算法综述作者：杨启文， 蔡亮， 薛云灿， YANG Qi-Wen， CAI Liang， XUE Yun-Can作者单位：河海大学常州校区,计算机与信息工程学院,常州,213022刊名：模式识别与人工智能英文刊名：PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE年，卷(期)：2008，21(4)被引用次数：1次1.Lopoz C I L.van Willigenburg L G.van Straten G Efficient Differential Evolution Algorithms for Muhimodal Optimal Control Problems 2003(02)2.Store R.Price K Differential Evolution-A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces 1997(04)3.Storn R.Price K Differential Evolution-A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces[Technical Report,TR-95-012] 19954.刘明广差异演化算法及其改进[期刊论文]-系统工程 2005(02)5.谢晓锋.张文俊.张国瑞差异演化的实验研究[期刊论文]-控制与决策 2004(01)6.Vesterstrom J.Thomsen R A Comparative Study of Differential Evolution Particle Swarm Optimization and Evolutionary Algorithms on Numerical Benchmark Problems 20047.Kim H K.Chong J K.Park K Y Differential Evolution Strategy for Constrained Global Optimization and Application to Practical Engineering Problems 2007(04)8.Omran M G H.Engelbrecht A P Serf-Adaptive Differential Evolution Methods for Unsupervised Image Classification 20069.Zhang Renqian.Ding Jianxun Non-Linear optimal Control of Manufaeturing System Based on Modified Differential Evolution 200610.Dhahri H.Alimi A M The Modified Differential Evolution and the RBF(MDE-RBF)Neural Network for Time Series Prediction 200611.Yang Shiwen.Gan Y B.Qing Anyong Sideband Suppression in Time-Modulated Linear Arrays by the Differential Evolution Algorithm 2002(01)12.Masza A.Pastorino M.Randazzo A Optimization of the Directivity of a Monopulse Antenna with a Subarray Weishting by a Hybrid Differential Evolution Method 2006(01)13.范瑜.金荣洪.耿军平基于差分进化算法和遗传算法的混合优化算法及其在阵列天线方向图综合中的应用[期刊论文]-电子学报 2004(12)14.吴亮红.王耀南.袁小芳自适应二次变异差分进化算法[期刊论文]-控制与决策 2006(08)15.Su C T.Lee C S Network Reconfiguration of Distribution Systems Using Improved Mixed-Integer Hybrid Differential Evolution 2002(12)16.翟捷.王春峰.李光泉基于差分进化方法的投资组合管理模型[期刊论文]-天津大学学报(自然科学与工程技术版) 2002(03)17.Onwubolu G C.Babu B V New Optimization Techniques in Engineering 200418.杨启文.蒋静坪.曲朝霞应用逻辑操作改善遗传算法性能[期刊论文]-控制与决策 2000(04)19.Storn R On the Usage of Differential Evolution for Function Optimization 199620.Chang C S.Xu D Y Differential Evolution Based Tuning of Fuzzy Automatic Train Operation for Mass Rapid Transit System 2000(03)21.Mendes R.Mohais A S DynDE:A Differential Evolution for Dynamic Optimization Problems 200522.Tomislav (S)Sensitivity of Differential Evolution Algorithm to Values of Control Parameters 200223.Das S.Konar A.Chakraborty U K Improved Differential Evolution Algorithms for Handling Noisy Optimization Problems 200524.Brest J.Zumer V.Mancec M S Self-Adaptive Differential Evolution Algorithm in Constrained Real-Parameter Optimization 200625.Nobakhti A.Wang Hong Co-Evolutionary Self-Adaptive Differential Evolution with a Uniform-Distribution Update Rule 200626.Nohakhti A.Wang Hong A Serf-Adaptive Differential Evolution with Application on the ALSTOM Gasifier 200627.Liu mpinen J A Fuzzy Adaptive Differential Evolution Algorithm 2005(06)28.Fan mpinen J A Trigonometric Mutation Operation to Differential Evolution 2003(01)29.Schmidt H.Thierauf G A Combined Heuristic Optimization Technique 2005(01)30.Blackwell T.Branke J Multi-Swarm Optimization in Dynamic Environments 200531.Lin Y C.Wang Fengsheng.Hwang K S A Hybrid Method of Evolutionary Algorithms for Mixed-Integer Nonlinear Optimization Probleras 199932.Ali M M Differential Evolution with Preferential Crossover 2007(03)33.Tasgetiren M F.Suganthan P N A Multi-Populated Differential Evolution Algorithm for Solving Constrained Optimization Problem 200634.Parsopoulos K E.Tasoulis D K.Pavlidis N G Vector Evaluated Differential Evolution for Multi-Objective Optimization 200435.Wang Yongjun.Zhang Jiangshe.Zhang Galying A Dynamic Clustering Based Differential Evolution Algorithm for Global Optimization 2007(01)36.Ahuja R K.Odin J B Developing Fitter Genetic Algorithms 1997(03)37.Kaelo P.All M M A Numerical Study of Some Modified Differential Evolution Algorithms 2006(03)38.Yan Jingyu.Ling Qing.Sun Detain A Differential Evolution with Simulated Annealing Updating Method 200639.Chakraborty U K.Das S.Konar A Differential Evolution with Local Neighborhood 200640.Chiou J P.Chang C F.Su C T Ant Direction Hybrid Differential Evolution for Solving Large Capacitor Placement Problems 2004(04)41.Bergey P K.Ragsdale C Modified Differential Evolution:A Greedy Random Strategy for Genetic Recombination 2005(03)1.期刊论文蔡亮.杨启文.岳兴汉.CAI Liang.Yang Qi-wen.YUE Xing-han一种基于混合差分策略的改进差分进化算法-河海大学常州分校学报2007,21(4)对启发式优化算法中的差分进化算法进行改进.在进化过程中并行交叉采用DE/rand/1/exp和DE/beat/1/exp差分策略,应用聚集度因子进行种群重构,缩小了种群重构后的搜索范围,有效避免了种群重构的随机性.仿真结果表明,改进算法与使用单一差分策略的差分进化算法及PSO算法相比,寻优能力得到了显著提高.1.李丽莉.章卫国.刘小雄.章萌基于混沌差分进化FCM算法的舵回路故障诊断[期刊论文]-测控技术 2009(5)本文链接：/Periodical_mssbyrgzn200804013.aspx授权使用：都晓东(wfqinghua)，授权号：677efca8-9058-46a5-83a9-9dff01003ba5下载时间：2010年9月28日。
