基于柯西游走的改进灰狼算法求解FJSP.pdf
《基于柯西游走的改进灰狼算法求解FJSP.pdf》由会员分享,可在线阅读,更多相关《基于柯西游走的改进灰狼算法求解FJSP.pdf(8页珍藏版)》请在咨信网上搜索。
1、DOI:10.13876/J.cnki.ydnse.230027第 43 卷 第 1 期2024 年 3 月延安大学学报(自然科学版)Journal of Yanan University(Natural Science Edition)Vol.43 No.1Mar.2024基于柯西游走的改进灰狼算法求解FJSP齐娅惠,田云娜*,田园,何雨欣,韩小颖(延安大学 数学与计算机科学学院,陕西 延安 716000)摘要:为了提高生产资源的利用率和调度效率,提出了一种基于柯西游走的灰狼优化算法,将其应用于求解柔性作业车间调度问题(FJSP)。在经典灰狼算法的基础上,加入柯西游走策略跳出局部最优;引入非
2、线性收敛因子a控制算法的广度搜索与深度搜索程度;采用混合生成新解的种群更新策略适当增强种群多样性。通过在不同规模的测试用例上进行仿真实验和分析比较,实验结果表明,基于柯西游走的灰狼算法寻优性能稳定,在平衡算法的全局搜索和局部搜索程度方面表现较为出色。关键词:灰狼优化算法;柯西分布;非线性收敛;柔性作业车间调度中图分类号:O22 文献标识码:A 文章编号:1004-602X(2024)01-0064-08生产调度是制造系统设计与运行中最为关键的环节之一,合理有效的调度方案能够有效提高制造业的生产效率。柔性作业车间调度问题(Flexible Job-Shop Scheduling Problem,
3、FJSP)是生产调度中常见且更为复杂的NP-hard优化问题1。众多学者围绕该问题,考虑不同的约束因素,从简单到复杂,展开了广泛而深入的研究2-7。近年来,随着信息技术和群智能优化算法的发展,众多学者利用群智能优化算法来求解 FJSP 问题。其中,孔飞等8在粒子群优化算法中加入停滞阻止策略和凹函数递减策略,提出改进双层粒子群优化算法,提高了算法收敛速度。张闻强等3为了避免算法陷入局部最优,将传统粒子群优化算法与遗传算法相结合,提出了混合粒子群优化算法。赵文超等9为了更好地平衡算法的广度和深度搜索程度,在追随者位置更新公式中引入自适应惯性权重,提出了改进的樽海鞘群算法。YUAN等10提出混合差分
4、进化算法,在DE的基础上嵌入基于关键路径的局部搜索算法来平衡搜索的广度与深度。王玉芳等11设计了自适应灰狼优化算法,采用改进离散搜索算子的狼群捕猎和均衡机器负载方式,对附属狼进行遍历,有效提高了算法的全局探索能力。陶婷婷等12引入局部选择和全局选择两种有效的初始解生成方案,设计了一种改进的飞蛾扑火优化算法,保证种群的多样性和质量。可以发现,为了提高算法的优化性能,学者们在群智能优化算法的基础上,均进行了研究和改进,以更好的平衡算法的广度和深度搜索程度。灰狼优化(Grey Wolf Optimization,GWO)算法是由MIRJALILI等13人在2014年提出的一种群智能优化算法。该算法具
5、有控制参数少、搜索能力强、求解速度快的特征,基于这些显著特征,近年来诸多学者运用 GWO 来解决各种实际问题。罗佳等14将GWO应用到解决连续函数优化问题中。龙文等15用GWO来解决无约束优化问题。PRADHAN等16用GWO解决经济负荷最优分配问题。游达章等17用GWO求解移动机器人的路径规划问题。胡小平等18将GWO应用于求解无线传感网络节点的优化覆盖问题。田云娜等19运用GWO来求解FJSP问题。在众多研究中,学者们就GWO的算法寻优收稿日期:2023-03-21基金项目:国家自然科学基金项目(61763046,62041212);国家大学生创新创业训练计划创新训练项目(20221071
6、9041);延安大学研究生教育创新计划项目(YCX2023007,YCX2023004,YCX2022071,YCX2021053);延安大学大学生创新创业训练计划创新训练项目(D2021147)作者简介:齐娅惠(1999),女,陕西榆林人,延安大学硕士研究生。*通信作者第 1 期齐娅惠 等:基于柯西游走的改进灰狼算法求解FJSP缺陷对其进行改进。本文在文献 19 所提算法的基础上,提出一种基于柯西游走的灰狼算法(Grey Wolf Optimization with Cauchy Distribution Walk,CGWO)解决 FJSP。为避免算法在迭代后期陷入局部最优,加强算法的局部搜
7、索能力,CGWO采用基于三个最优个体的柯西游走策略;引入非线性收敛因子a为更好的满足算法需求;采用混合生成新解的策略进行种群更新,以保证种群质量、维护种群多样性。1FJSP问题的数学描述和模型建立1.1问题描述n个工件在m台机器上加工,每个工件有k道工序,每道工序可在若干台机器上加工,工件中工序加工顺序和在机器上的加工时间已知。调度优化目标是在满足各项约束条件的情况下,确定各工件的加工机器和各机器上的加工顺序,使得最大完工时间性能指标达到最优19。本文所考虑的假设总结如下:(1)所有工件和机器在零时刻均就绪且可用;(2)同一机器在同一时刻只允许加工一道工序;(3)加工一旦开始就不允许中断;(4
8、)不同工件间工序优先级相同;(5)不考虑机器故障,且忽略机器准备时间。1.2模型建立目标函数:s.t minCmax=min max(Ci),1 i n,Cmax Ci,i=1,2,n;(1)spqk fijk-(1-yijpqk)L;(2)k Mi()j+1si()j+1 kk Mijfijk;(3)k Mijxijk=1;(4)Ci 0,i=1,2,n;(5)sijk 0,fijk 0,i=1,2,n,k=1,2,m,j=1,2,l。(6)其中,式(1)定义最大完工时间,式(2)表示在同一时刻一台机器只能加工一道工序,式(3)决定了加工次序,即每一工件的前一道工序加工结束后下一道工序才可开
9、始加工;式(4)表示每台机器仅会被分配在一道工序上,式(5)和式(6)表示决策变量的取值范围。本文使用的一些符号列举和说明如表1所示。2灰狼优化算法在灰狼优化算法中,将灰狼种群划分为、和四种狼,其中、为适应度值最优的前三个个体,狼称为头狼,主要负责领导整个狼群;狼主要负责协助狼做决定;狼听从于、狼的指令,同时也负责指挥普通灰狼个体。灰狼捕猎的过程即为灰狼优化算法寻找最优解的过程,分为3个阶段:包围猎物、靠近猎物和攻击猎物。1)包围猎物D=|C Xp(t)-X(t)|,(7)X(t+1)=Xp(t)-A D,(8)A=2a r1-a,(9)C=2 r2,(10)a=2-t 2T。(11)式(7)
10、式(11)表示灰狼包围猎物。其中,D表示灰狼个体与猎物的距离;Xp(t)和X(t)分别为猎物位置和灰狼位置;A、C为系数向量;a为从2递减到0的向量;t为当前迭代次数;T为最大迭代次数;r1、r2为 0,1 中的随机数。2)靠近猎物表1符号列举和说明符号nmOij(i=1,2,n;j=1,2,l)MijPijk(k=1,2,m)LCiCmaxsijkfijkxijkyijpqk符号变量描述说明工件总数机器总数工件i的第j道工序工件Oij的可选机器集工件Oij在机器k上的加工时间一个无穷大的正数工件i的完工时间最大完工时间工件Oij在机器k上的开始加工时刻工件Oij在机器k上的完成加工时刻 1,
11、工序Oij在机器k上加工0,其他情况 1,工序Oij在工序Opq之前在机器k上加工0,其他情况65延安大学学报(自然科学版)第 43 卷 D=|C1 X(t)-X(t)|,D=|C2 X(t)-X(t)|,D=|C3 X(t)-X(t)|。(12)X1=X(t)-A1 D,X2=X(t)-A2 D,X3=X(t)-A3 D。(13)X(t+1)=X1+X2+X33。(14)式(12)式(14)表示灰狼靠近猎物。其中,D、D、D分别为种群中、狼与猎物的距离,A1、A2、A3和C1、C2、C3分别对应、狼的系数向量,X、X、X分别为、狼的个体位置,X1、X2、X3均为中间向量。在靠近猎物的过程中,
12、先由式(12)式(14)计算出、狼的距离,然后由式(14)来确定猎物的移动方向。3)攻击猎物当猎物停止移动时,灰狼将对猎物发起攻击和捕食,这一过程由参数A来控制,当|A|1时,灰狼远离猎物,进行广度搜索以求找到更好的解,即全局搜索;当|A|1时,灰狼对猎物发起攻击,进行深度搜索,即局部搜索。3改进的灰狼优化算法FJSP是一种离散组合优化问题,本文所提算法采用参考文献 19 的编码解码方式,基于离散编码进行寻优,在全局搜索、收敛因子a和种群更新三个方面进行了改进,在避免算法陷入局部最优的同时,尽可能提升算法的收敛速度和寻优能力。3.1柯西游走策略经典GWO中,由、三个最优个体来指导普通灰狼个体的
13、位置更新,这使得算法在前期有可能陷入局部最优,不利于继续实现种群进化。为此,GUPTA等20提出随机游走灰狼优化算法解决该问题。为了避免算法在迭代后期陷入局部最优,本文在此基础上改进了、的游走方式,将原本基于正态分布的随机游走更改为基于柯西分布的游走,游走的过程如图1所示。针对FJSP的两个子问题,柯西游走分为两部分进行。在机器分配部分,首先对事先赋予每个机器的权值编码根据公式(15)进行更新;然后对更新后的编码进行归一化处理,以保证每道工序对应的不同机器的权值之和等于1。w*=w+*s,(15)其中,w*表示更新后的权值,w表示更新前的权值,为服从标准正态分布的随机数,s为柯西游走步长,它是
14、一个服从柯西分布的随机数。标准正态分布函数、标准柯西分布函数 s 和*s的图像分别如图2中的2A、2B和2C所示。*s函数在x=0的左右侧均为先单调递增,后单调递减的函数,这使得、狼在进行游走的过程中,游走步长以较大概率在一定范围内进行大幅度变化,使得、狼具有跳出局部最优的能力,避免算法陷入局部搜索。从算法整体搜索过程来看,*s函数对、进行跳跃式干扰,使得算法能够跳出局部最优,全局搜索能力增强。在工序排序部分,对个体进行 d次交换操作,其中d的取值取决于柯西游走步长s。图3以一个简单的编码为例解释柯西游走中工序排序,灰狼个体的编码Z=0.4,0.2,0.5,0.4,0.2,0.3,0.1,编码
15、长度pl=7,根据柯西游走步长s计算得到d=3,在 0,7)之间随机选取 3个整数(代表在编码中的位置)为一组,一共取两组,即 X=0,2,5 和 Y=2,3,6,然后将X和Y中的数字一一对应,交换相应位置的权值。可以看出,、在每一次寻优过程中,都有一次近似于随机搜索的机会。步长s变化值是服从柯西分布的随机数,将标准正态分布与柯西分布两种函数进行叠加,扩大随机搜索的突变值域,增加、三个最优个体跳出局部最优的能力。图1基于、的柯西游走66第 1 期齐娅惠 等:基于柯西游走的改进灰狼算法求解FJSP3.2收敛因子非线性调整非线性收敛因子a在迭代初期全局搜索能力较强,在迭代后期局部搜索能力较强,能更
16、好地平衡算法的全局和局部搜索程度。在GWO中,参数A决定着算法对解空间的搜索程度,其本质上是由距离收敛因子a控制的。CHIU等21已经证明线性策略通常不是最有效的。为此,本文参考魏政磊等22提出的一种收敛因子调整策略,对收敛因子a进行如下式(16)的非线性分布调整:a=2-2(t/T)2,(16)其中,t和 T分别表示当前迭代次数和最大迭代次数。收敛因子改进前后的变化曲线如图4所示。其中黑色虚线表示经典GWO的线性收敛因子变化趋势,红色实线表示CGWO的非线性收敛因子变化趋势。由图4可知,改进后的非线性收敛因子在迭代初期,收敛速度变化相对平缓,灰狼将包围圈扩大进行充分全面的广度搜索,以求找到更
17、好的猎物,此时算法的全局搜索能力更强;在迭代后期,收敛速度加快,灰狼开始攻击并捕食猎物,此时算法局部搜索能力逐渐增强。这种非线性的收敛方式更适用于求解非线性优化问题。图4两种收敛因子对比图3柯西游走中的交换操作图2三个函数的图像67延安大学学报(自然科学版)第 43 卷 3.3混合种群更新策略CGWO在每次迭代结束时,淘汰掉R个种群中适应度较差的解(R 依赖于随机游走率),再产生R个随机且无导向性的新解。这种更新方式既保证种群规模不变,又可以提高种群质量。本文采用混合生成新解的策略进行种群更新,该策略综合了最优个体和随机生成两种产生新解的方式。该策略在进行算法迭代时,需要从列表c=0,1,2,
18、3中随机等概率的选择一个数,作为判定种群更新方式的依据。方式1:当c取0、1、2时,种群分别在、附近产生新解;方式 2:取c=3时,随机生成新解更新种群。取种群适应度值前10%、30%、50%分别作为、下一次迭代的取值范围。如图5所示,该策略通过在、三个最优个体附近和随机产生新解的方式进行种群更新。每种新解产生方式被等概率选择,这样既保证了新解的质量,又能维护种群多样性。4CGWO算法步骤CGWO的算法流程图如图6所示。所提CGWO的算法步骤如下:Step1:初始化种群,确定各参数值。Step2:计算种群中个体的适应度值,确定、。Step3:、三个最优个体进行柯西游走,除、以外的其余普通灰狼个
19、体按照文献 19 的游走方式进行局部搜索。Step4:根据式(14)更新个体位置信息。Step5:分别根据式(16)、式(9)和式(10)更新a、A和C。Step6:依据混合生成新解的种群更新策略进行种群更新。Step7:判断算法是否达到终止条件。若达到,则输出当前解;否则,转到Step2。5实验结果与分析本文所提的 CGWO 算法采用 Python 语言仿真实验,在 Win10 系统下内存 16G 的 i7-4790 CPU 3.60GHz,3.60GHz仿真实验的算法具体参数设置:种群规模为100,最大迭代次数为400,游走次数为5,游走步长因子为0.4,随机游走率为0.5。采用 BRAN
20、DIMARTE23基准算例上进行仿真实验,为了验证本文所提的CGWO算法在解决FSJP问题方面的有效性,首先与GWO及相关改进算法进行对比,然后与文献中其他智能优化算法进行对比。5.1与GWO及相关改进算法对比为验证算法的寻优能力,将本文所提的CGWO算法与经典GWO算法、JIANG等24人提出的DGWO算法、WANG等25 人提出的GIWO算法以及田园等19 人提出的RGWO算法进行对比,算法针对不同算例分别独立运行20次后比较计算结果,并根据式(17)计算在各算例下CGWO的Gap值。Gap=(Best-Min)/Min)100%。(17)算法最佳求解结果和 Gap 值的对比结果见表2,其
21、中黑体表示各算例下的最佳结果。表2是CGWO与其他GWO相关的4种算法对比结果。其中,与DGWO和GIWO算法对比,在10个标准算例下GIWO取得4个最优结果,DGWO取得5个最优结果,而CGWO算法取得了8个最优结果;相较于RGWO图5尾部淘汰策略图6CGWO算法流程图68第 1 期齐娅惠 等:基于柯西游走的改进灰狼算法求解FJSP算法,CGWO算法在每个算例中都能得到更优的结果。由于较小规模的算例数据简单,所以更有利于算法寻优,在前5个规模较小的算例下,这4种算法的寻优结果无明显差别,均能够取得小规模算例下的较优解;大规模的算例数据量较大,在寻优能力和收敛速度方面对算法有着较高要求。CGW
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 西游 改进 灰狼 算法 求解 FJSP
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。