改进离散麻雀搜索算法求解柔性作业车间调度问题.pdf

先进制造系统管理运作现代制造工程()年第 期改进离散麻雀搜索算法求解柔性作业车间调度问题李峥峰丁其聪张东方张国辉(中原工学院机电学院郑州 郑州航空工业管理学院管理工程学院郑州)摘要:针对最小化最大完工时间的柔性作业车间调度问题()提出了一种改进离散麻雀搜索算法()首先采用了两段式编码方式针对两段编码分别设计了有效的编码转化方式实现了麻雀搜索算法()连续搜索空间与 离散决策空间之间的映射 其次设计了一种随机与组合启发规则相结合的初始化方法在保证了麻雀初始种群分散广度的同时提高了麻雀个体的质量加快麻雀搜索算法的收敛速度 再次融合一种基于关键路径的变邻域搜索策略对发现者进行深度发掘提高种群引领者的质量 此外为了维持 种群多样性设计了自适应柯西高斯变异策略提升算法全局搜索能力和跳出局部极值的能力 最后使用 和 系列 个基准算例与多种算法进行仿真实验实验结果证明了 的有效性和求解 的优越性关键词:柔性作业车间调度麻雀搜索算法变邻域搜索策略柯西高斯变异中图分类号:文献标志码:文章编号:():./.():()().().:引言与 作 业 车 间 调 度 问 题()相比柔性作业车间调度问题()突破了加工机器唯一的限制更加符合当前实际生产情况是近年来车间调度领域的研究热点引起了学者的广泛关注柔性作业车间调度问题求解规模大、计算复杂度国家自然科学基金联合基金项目()河南省科技攻关项目()教育部人文社会科学规划基金项目()河南省高校科技创新团队项目()河南省高等学校重点科研计划项目()李峥峰等:改进离散麻雀搜索算法求解柔性作业车间调度问题 年第 期高是复杂的 问题 目前常用的求解方法主要为启发式算法、遗传算法()、禁忌搜索()算法、粒子群优化()算法和蚁群优化()算法等 这些算法在求解 上取得了良好的效果但学者们仍在不断积极探索新方法以求更高效地解决 近几年来涌现了一批诸如灰狼优化算法、人工蜂群算法、萤火虫算法、鲸鱼群算法和麻雀搜索算法等新兴元启发式算法这些新算法为解决 提供了新的动力和思路 姜天华针对将变邻域搜索算法嵌入到灰狼优化算法中提出了一种混合灰狼优化算法大大提高了灰狼优化算法求解精度 等人针对 在灰狼优化算法的基础上嵌入了入侵杂草优化算法以提高灰狼优化算法的全局搜索和局部搜索能力 等人在人工蜂群算法中引入了强化学习算法有效地提高了人工蜂群算法的收敛速度和精度并将其应用于求解 等人引入了自适应机制以改进人工蜂群优化算法中的邻域搜索用来求解 等人针对多目标 实现了萤火虫算法的离散化并对几个问题实例进行了验证王思涵等人对鲸鱼群算法进行了改进使其能够应用于求解 麻雀搜索算法()是一种基于群体的新兴元启发式算法其参数设置简单、寻优能力强并且易于实现在求解优化问题时表现出了良好的性能到目前为止已经被应用于路径规划、故障诊断、脑肿瘤检测、网络数据恢复和电网能量优化等领域 目前利用 求解车间调度的研究还比较少见刘丽娜等人引入量子计算、多邻域搜索和高斯扰动等策略对 进行改进并将其应用于求解 周宁等人成功将 应用于混合流水车间调度问题并引入粗糙数据推理理论对算法进行改进 等人将标准 应用于求解 中并与其他元启发式算法进行对比结果表明 求解 具有一定的优势 等人引入混合搜索方法对 种群质量进行了优化集成了量子旋转门和正余弦算法协调 全局搜索和局部开发能力对 的能耗优化问题进行了求解综上所述目前采用 求解 车间调度方案的文献比较稀少仅有少量几篇 为了探究 在 的求解效率综合考虑 的优缺点和 的特点本文设计了改进离散麻雀搜索算法()用于求解 在 具有较好的收敛速度和寻优能力的基础上结合 的特点针对 在初始种群、发现者质量和种群多样性等方面进行改进从而提高算法的求解效率本文设计的算法基本步骤如下)根据 的机器分配和工序排序的特点采用了两段式编码方式并设计了连续空间与离散空间的编码转换方式实现了算法连续解空间与离散调度解之间的转换使 能够用于求解)设计了一种随机与组合启发规则相结合的种群初始化方法提高初始种群的质量)设计基于关键路径的变邻域搜索()从而提高局部搜索能力提高发现者质量使得发现者能更好地引领其他个体进行搜索)此外本文设计了自适应柯西高斯变异策略维持麻雀种群个体多样性)最后通过基准算例验证算法的有效性 柔性作业车间调度问题.问题描述假设某车间有 个需要加工的工件和 台加工机器每个工件需要经过 道加工工序 每道工序的可加工机器有若干台同一道工序在不同机器上的加工时间不同本文优化目标是为工序分配合适的加工机器并对各机器上的工序进行合理安排使工件最大完工时间最小.符号定义 变量符号设置如下 为工件集合其中 为第 个工件为工件 的工序集合其中 为第 个工件的第 道工序 为机器集合 其中 为第 台加工机器为工序 可用机器集合工序 由机器 加工否则为工序 在机器 上的加工时间为工序 的开始加工时间 年第 期现代制造工程()为工序 的完工时间为最大完工时间为工件 的完工时间 为一个足够大的正数与 同在 上加工且 先加工否则为第 个工件的第 道工序其中.优化模型以最小化最大完工时间为目标函数则有:()()存在以下约束条件)所有工件都可以在 时刻开始加工则有:()一台机器一次只能加工一个工件则有:()()()()()一道工序只能在一台机器上加工则有:()工序加工过程中不能中断则有:()同一工件的工序加工先后顺序约束则有:()()麻雀搜索算法麻雀搜索算法是于 年提出的一种基于群体的元启发式算法该算法模拟了麻雀种群在搜寻食物时的行为 在算法迭代过程中为了模拟麻雀种群的情况将种群中的个体按照适应度值从大到小排序分成两类 将种群中适应度值较大的一类个体称为发现者大约占种群的 其余个体为加入者所有个体都有 的可能进行侦查预警行为 由于原始文献中更新公式存在下标及维度混乱的情况故对其进行如下修改发现者位置更新公式为:/其他()式中:为当前迭代次数 为麻雀种群中的个体数量为第 次迭代时发现者中的最优个体第 维的值为第 次迭代时全局最差个体第 维的值 为问题的维度式()表示种群适应度靠后的/只麻雀个体加入者得不到食物会在自身与全局最差个体之间寻找食物其他加入者向发现者中最优个体靠拢侦察预警行为更新公式为:()()式中:为当前迭代次数为第 次迭代时全局最优个体第 维的值 和 均为调整步长的参数其中 为服从正态分布的随机数 为区间内的随机数为当前麻雀个体的适应度值和 分别为全局最优和最差个体的适应度值 为无限趋近于 的常数式()表示若侦查预警的个体与全局最优个体的适应度值相等则将其进行小范围搜索否则向全局最优个体靠近由于篇幅限制详细算法步骤可参见文献 改进离散麻雀搜索算法标准的麻雀搜索算法解空间是连续空间无法直接用于求解离散问题针对这个缺点本文设计了编码的连续空间向离散空间的转换方式从而使得 李峥峰等:改进离散麻雀搜索算法求解柔性作业车间调度问题 年第 期可用于求解 通过在解空间中随机产生初始种群来保证全局搜索范围但初始种群质量得不到保障影响算法的寻优效率 为了提高初始解的质量本文设计了种群随机与组合启发规则相结合的初始化策略保证算法的全局搜索范围同时提高初始种群的质量加快算法收敛速度 在 中发现者引领整个种群的搜索方向对最终的搜索寻优质量有很大的影响为提高发现者的质量本文设计了基于关键路径的变邻域搜索以深度挖掘发现者的潜力提高算法深度搜索的能力 搜索迭代后期种群个体迅速聚集种群多样性减少导致算法陷入局部最优故采用自适应柯西高斯变异策略保持麻雀种群的个体多样性从而增强算法搜索全局最优解的能力和摆脱局部极值的能力.编码机制 为离散问题可以分为工序排序和机器分配(又称机器选择)个子问题因此采用基于机器分配和工序排序的两段式整数编码两段编码的长度均为总工序数且分别对应机器分配方案和工序排序方案 第一部分为基于机器的编码()按照所有工序的自然顺序进行编码第二部分为基于工序的编码()即包含所有工件所有工序的序列随机产生的一个调度解的结构其调度方案编码如图 所示图 中 表示基于机器的编码 表示基于工序的编码 部分中的元素表示在该工序可选机器集中的机器顺序号即 使用可选机器集中的第 台机器使用可选机器集中的第 台机器以此类推 部分中的元素表示工件号工件号从左到右数出现几次就代表是该工件的第几道工序图 调度方案编码.转换机制标准的 采用实数编码个体位置向量元素为连续值而柔性作业车间调度解为离散值 并不能直接应用于求解 因此需要实现连续解空间与离散问题空间之间的转换 为了解决该问题本文针对两段编码分别设计了不同的转化方式.连续空间向离散空间的转换连续空间向离散空间转换的两部分编码转化方式分别如下)机器分配部分:将麻雀个体位置元素值代入式()即可得到对应工序分配的机器的序号()()()()式中:()为麻雀个体位置上第 个元素(为编码长度)的元素值 为取值上限()()为第 个元素对应的工序可以选择的机器数量()为第 个元素对应的工序可以选择的机器序号()()为向上取整函数)工序排序部分:基于文献中的升序排序规则()规则将连续的位置元素转换成离散的工序排序方案 个体位置转换成工序排序如图 所示图 个体位置转换成工序排序图 中位置元素均为内的随机数其构成了麻雀个体 首先将麻雀个体的所有位置元素按照从小到大的顺序进行排列即升序排序为每个元素按照自然顺序分配唯一的 值(即升序排序后的元素标号)并与工序的顺序编号一一对应然后根据原来的元素位置重新排列 值即可构造工序排序方案.离散空间向连续空间的转换离散空间向连续空间转换的两部分编码转化方式分别如下)机器分配部分:按照式()的逆操作执行如式()所示 年第 期现代制造工程()()()()()()工序排序部分:与连续空间向离散空间的转换方式相似首先在区间内生成一组编码长度为 的随机数组然后对随机数组排序并分配 值和工序编号根据工序排序方案重排 值即可确定麻雀个体位置元素值 工序排序转换成个体位置过程如图 所示图 工序排序转换成个体位置过程.种群初始化柔性作业车间调度问题属于大规模 问题此类问题搜索空间大对初始种群的质量要求更高标准的 中采用的是随机初始化种群随机初始化方法虽然简单易行但随机初始化的种群质量较低导致算法早期收敛速度缓慢算法的搜索效率不高 而且在麻雀搜索算法寻优过程发现种群个体的质量对算法寻优精度的高低有非常大的影响因此需要设计合适的初始化方法提高初始种群的质量加快优化速度提高求解精度为有效提高初始种群的质量本文设计了种群随机和组合启发规则相结合的初始化方法 对种群中 的麻雀个体采用随机初始化方法等概率随机初始化能使初始搜索点均匀分布在整个解空间保证算法全局搜索范围另外 的麻雀个体使用组合启发规则进行初始化提高种群的质量针对机器选择子问题采用最短工序加工时间()调度规则初始化即为工序分配加工时间最短的机器使每道工序的加工时间尽可能短减小最大完工时间针对工序排序子问题采用最长剩余加工时间()调度规则初始化即优先调度这组工件中剩余所有工序总加工时间最长的工件使工序加工尽可能均衡.变邻域搜索在麻雀搜索算法寻优的过程中发现者通过式()更新自己的位置进行广泛搜索而加入者主要跟随发现者更新自己的位置发现者质量对种群质量有很大的影响因此要提高算法的性能需要对引领种群搜索方向的发现者进行深度挖掘提高种群中发现者的质量 而变邻域搜索算法具有扩大邻域搜索范围、增强局部搜索能力的作用故在算法中嵌入变邻域搜索算法在每一次迭代中作用于更新后发现者中的最优个体以提高算法找到全局最优解的可能性有研究指出改变关键路径的邻域结构能有效地减小最大完工时间因此设计正确的邻域结构能为算法的搜索提供科学有效的方向 故本文针对 两段编码分别设计了不同的基于关键路径的邻域结构 按照设计的邻域结构依次对初始解进行扰动搜索更好的解针对工序序列的邻域结构:按照顺序遍历关键路径上的所有关键块根据关键块的大小选择不同的邻域结构进行搜索)如果一个关键块中有 道关键工序则采取 结构进行搜索即随机选择块首或块尾相邻的 道关键工序进行交换 这种邻域结构操作简单能对调度解进行较小的扰动对小规模问题非常有效)如果一个关键块中包含 道及以上关键工序则在交换块首或块尾相邻的 道关键工序的同时再随机交换块内 对工序 这是因为随着关键块工序数量的增加意味着问题规模变大只采用 结构方式其搜索扰动小、搜索能力受限这就需要通过移动关键块中更多数量的工序来进一步提升邻域结构的性能针对机器序列的邻域结构:在关键路径上随机选择一道工序将该工序重新分配到其他可用机器上不改变工序排序为寻找关键路径需要建立析取图模型将麻雀个体解码出的甘特图与析取图模型相结合依据主动解码得到的每台机器上的加工任务顺序生成非循环有向图 在非循环有向图中从开始到结束的最长路径即为关键路径关键路径上的工序即为关键工序 通过移动关键工序就能改变最大完工时间建立析取图模型的步骤和确定关键工序的方法详见文献若可行方案有多条关键路径则需要对每条关键路径都进行移动李峥峰等:改进离散麻雀搜索算法求解柔性作业车间调度问题 年第 期.自适应柯西高斯变异策略在算法迭代前期算法进行广泛搜索此时应维持种群多样性 柯西分布算子具有较强的扰动能力可以维持种群多样性增强全局搜索能力在算法迭代后期当发现者搜索到局部最优位置时大量加入者会迅速聚集在该位置寻找食物 此时发现者和整个种群停滞种群多样性降低使算法陷入局部最优 而高斯分布算子能增强局部发掘能力可以有效地提高算法摆脱局部极值的能力因此本文设计了自适应柯西高斯混合变异策略迭代前期侧重于柯西扰动维持种群多样性广泛地进行全局搜索 迭代后期侧重于高斯扰动帮助算法跳出局部最优 在每次迭代中对当前全局最优麻雀个体进行柯西高斯变异对比变异前后的位置选择更好的位置替换原来的位置自适应柯西高斯变异公式为:()()()其中:/()/()式中:为当前迭代次数为第 次迭代时全局最优个体的位置为第 次迭代时全局最优个体变异后产生的新位置为自适应柯西高斯变异的最大迭代次数()为满足标准柯西分布函数的随机变量()为满足标准高斯分布函数的随机变量和 均为随迭代次数动态调整的自适应参数.步骤 算法流程图如图 所示图 中 大致的流程依次为种群初始化、编码转换、发现者位置更新、变邻域搜索、加入者位置更新及侦察预警行为、种群替换和自适应柯西高斯变异 其中初始化的种群为离散调度解通过编码转换机制转换为连续麻雀个体代入算法进行迭代每次计算适应度值时需将连续麻雀个体转换为离散调度解 实验分析为了验证本文提出的 求解 的有效性以及算法的性能分别针对 系列基准算例(、这 个基准算例)和 系列基准算例(这 个基准算例)进行验图 算法流程图证 系列算例 为部分柔性调度问题算例 为全部柔性调度问题 系列基准算例 中工件数量为 个之间机器数量为 台之间所选算例具有一定的代表性本文算法程序采用 软件进行编写设置种群大小 变邻域搜索最大迭代次数设置为.算法改进策略分析采用 系列基准算例对算法中几种改进策略的有效性进行验证其中包括随机与组合启发规则混合初始化策略、基于关键路径的变邻域搜索策略以及自适应柯西高斯变异策略 改进策略对比(无量纲)如表 所示表 中 表示标准的麻雀搜索算法 表示 经过随机与组合启发规则混合初始化策略改进之后的算法 表示 加上变邻域搜索的算法 表示本文算法即标准的 经过初始化、变邻域搜索和自适应柯西高斯变异改进之后得到的算法 为各算法求得所有算例的相对百分比偏差 的平均值 年第 期现代制造工程()每种算法重复运行 次记录每种算法求得的最好值 和平均值 计算当前算法求得的最优值与所有算法求得的解中的最优值的相对百分比偏差其计算公式为:()/式中:为所有算法求得的解中的最优值表 改进策略对比算例/.由表 数据可看出 经过随机与组合启发规则混合初始化方法改进后 求得的大部分算例的 值明显更好其 值比 的 值要小说明本文设计的初始化方法可以有效提高算法的求解效率在加入变邻域搜索后 的求解精度进一步提升所有算例的 值都得到不同程度的改善变邻域搜索的引入明显增强了算法局部搜索能力 从表 中可看出 求解的结果最好其 值在所有算法中最小与 相比其 值有进一步改进说明算法跳出局部最优的能力得到增强搜索的效果更好此外 具有更好的 值说明柯西高斯变异的引入可以提高算法全局搜索和摆脱局部极值的能力提高了算法的稳定性本文选取了具有代表性的四组算例绘制了迭代曲线图改进策略有效性对比图如图 所示图 中对比了经过每一种策略改进后的算法性能图 改进策略有效性对比图李峥峰等:改进离散麻雀搜索算法求解柔性作业车间调度问题 年第 期 从图 可以看出经过随机与组合启发规则混合初始化方法改进后的寻优曲线 明显位于 寻优曲线的左下方说明改进后的初始化方法较大的提高了搜索的效率和搜索速度在嵌入变邻域搜索后 曲线迅速收敛 代内就搜索到了较优的解说明该策略可以较大的提高发现者的质量从而大幅度提高算法的搜索效率和搜索速度 在引入柯西高斯变异后可以明显看出在搜索的后期算法摆脱了局部极值提高了搜索的深度和广度得到了更好的解.算法有效性验证在 系列 和 基准算例上将 与启发式()算法、灰狼入侵杂草优化混合()算 法、分 布 式 粒 子 群 优 化()算法、改进非支配排 序 生 物 地 理 学 优 化()算法进行比较 和 基准算例对比如表 所示表 中数据显示在 和 这 个算例中 均能获得最优解然后在 系列基准算例上将 与混合灰狼优化算法()、算法、改进粒子群优化算法()和年龄分层人口结构遗传算法()进行比较系列基准算例对比如表 所示在 系列 个基准算例中除了 和 外 均求得了所列算法中的最优解个数明显多于其他算法体现出本文所提算法在求解 精 度 方 面 优 越 的 性 能 算 例 的最优调度甘特图如图 所示 算例 和 未求得最优解说明 在求解大规模调度问题上仍存在不足有进一步改进的空间表 和 基准算例对比算例各算法运行结果算法 算法 算法算法表 系列基准算例对比算例各算法运行结果算法算法算法图 算例 的最优调度甘特图 为进一步说明 的优越性能本文计算了不同算法与本文算法在 系列 个基准算例的 值及 值算法 值对比如表 所示由表 中数据可知本文 的 值为.年第 期现代制造工程()明显优于另外几个算法这说明本文所提算法的寻优性能还是较好的表 算法 值对比算例各算法 值运行结果/算法算法算法.结语本文根据 特点对经典的麻雀搜索算法进行改进提出一种改进离散麻雀搜索算法)实现了算法连续解空间与离散调度解之间的转换)设计了种群随机与组合启发规则相结合的初始化策略改进初始解的质量从而提高算法收敛速度)引入基于关键路径的变邻域搜索以深度挖掘发现者的潜力提高发现者的质量从而提高搜索的深度)利用柯西高斯变异策略维持种群多样性提高算法跳出局部最优的能力提高 求解 的精度最后使用基准算例进行仿真实验验证了算法改进策略的有效性和算法求解 的有效性 接下来会将麻雀搜索算法应用于求解更大规模更复杂的车间调度问题并结合问题特点进一步改进算法参 考 文 献:.():.():.():.:.:.():.():.张于贤丁修坤薛殿春等.基于记忆曲线模型的蚁群算法在柔性作业车间的调度优化.现代制造工程():.姜天华.混合灰狼优化算法求解柔性作业车间调度问题.控制与决策():./:.:.:():.():.:():.王思涵黎阳李新宇.基于鲸鱼群算法的柔性作业车间调度方法.重庆大学学报():.:.():.():.李峥峰等:改进离散麻雀搜索算法求解柔性作业车间调度问题 年第 期 .():.:.:.:():.():.:.刘丽娜南新元石跃飞.改进麻雀搜索算法求解作业车间调度问题.计算机应用研究():.周宁张嵩霖张晨.融合粗糙数据推理的离散麻雀搜索算法求解混合流水车间调度问题.电子科技大学学报():./:.:.():.王凌刘波.微粒群优化与调度算法.北京:清华大学出版社:.张国辉高亮李培根等.改进遗传算法求解柔性作业车间调度问题.机械工程学报():.:.():.赵诗奎.作业车间调度问题的多工序联动邻域结构研究.机械工程学报():.高晨峰陈家清石默涵.融合黄金正弦和曲线自适应的多策略麻雀搜索算法.计算机应用研究():.()():.():.():.().:.:.江厚民李少波王巾侠等.求解柔性作业车间调度问题.计算机仿真():.作者简介:李峥峰通信作者高级工程师博士硕士研究生导师主要研究方向为智能优化、车间调度丁其聪硕士研究生主要研究方向为生产调度、智能制造等张东方硕士研究生主要研究方向为生产调度、智能制造等张国辉教授博士硕士研究生导师主要研究方向为智能算法、车间调度:.收稿日期:致本刊作者现代制造工程已被中国科学引文数据库、中国学术期刊文摘、中国学术期刊综合评价数据库、中国学术期刊(光盘版)数据库、中国期刊网、万方数据库等收录 本刊所付给作者的稿酬中已包含网络出版稿酬本刊不再另行支付费用 若作者不愿被上述媒介转载务请在投稿时以书面形式说明本刊文责自负版权所有未经许可不得转载使用现代制造工程编辑部