基于改进麻雀算法的铜带排样优化应用.pdf

第39卷第4期2023年8月山西大同大学学报（自然科学版）Journal of Shanxi Datong University(Natural Science Edition)Vol.39 No.4Aug.2023基于改进麻雀算法的铜带排样优化应用顾雨娟，李学兵*（湖北汽车工业学院 电气与信息工程学院，湖北 十堰 442000）摘要：剪切工序既是小批量多品种的铜板带生产企业产品交付的瓶颈，也是企业追求高成材率关键工序。以湖北精益高精铜板带有限公司剪切生产为研究对象建立优化排样模型，基于匀质块的思想处理剪切生产中的“一刀切”约束，并使用罚函数处理单卷长度浮动约束，再用改进麻雀算法自动生成排样方案。该算法采用Singer混沌序列提高初始种群多样性并且结合柯西变异提升后期寻优精度，卷料利用率高于其他算法。基于剪切优化排样模型方案的滚动排产很好解决了产品交付和高成材率的矛盾，为类似企业剪切生产提供了很好的借鉴意义。关键词：排样优化；成材率；长度浮动；一刀切；麻雀搜索算法中图分类号：TP391文献标识码：Adoi：10.3969/j.issn.1674-0874.2023.04.025具有多品种小批量市场供货特点的铜加工企业的铜带产量和铜带消费量巨大，成材率的提高对此类企业降低生产成本、提高竞争实力十分重要。目前在铜合金的成分设计和制备加工工艺等方面已经取得了一定的研究成果，铜带的质量得到保证，所以影响成材率的关键工序在于剪切工序，选取的排样方案直接决定产出成品的多少1。铜加工企业大多生产以订单为导向的定制产品，一卷母带原料会根据不同的订单需求剪切出十几种子卷，不合理的排样方案会直接导致后续包装工序工作量增加，难以及时交付成品。因此，寻找一个高效的排样方案对剪切工序来说至关重要，剪切工序排产优化实际成为在最优排样方案下的排产问题。优化剪切工序的排样模型方案属于一种具有较高计算复杂度的NP-hard带有工艺约束的矩形件排样优化问题，目前的研究虽然都以提高成材率为目标，但未能同时解决涉及剪切工序的“一刀切”约束和长度浮动约束的问题2-5。采用匀质块的思想和罚函数处理这两种约束，最后采用Singer混沌序列提高初始种群多样性结合柯西变异提升后期寻优精度，自动生成排样方案，在保证交付期限的情况下提高了成材率。1 问题描述与数学模型1.1 问题描述剪切工序可以分为两个阶段：第1阶段使用圆盘剪，根据排样方式对母带铜卷进行排刀横向剪切；第2 阶段使用切头剪，纵向剪切母带后分切出若干子卷。其中，第2阶段纵剪母带至完全切断即为“一刀切”工艺约束，剪切排样示例图如图1。将n种宽度、长度无限长的卷材，剪切出m种长度为li、宽度为wi、需求量为bi的矩形毛胚，母带卷料剪切得来的子卷宽度固定，长度在一定范围内浮动，要求在约束条件内，寻找一个剪切优化排样模型方案使消耗的卷材面积最小。.子卷子卷子卷子卷子卷回炉废料切头剪切头剪切头剪切头剪圆盘剪母卷图1 剪切排样示例图1.2 数学模型一个排样模型方案由多种排样方式组合而成，且每种排样方式均有相应的使用次数，通过限制每种排样方式的最大使用次数来处理对各个成品需求量的约束，同时防止因过量生产占用过多仓库库存。设共有m种待剪矩形毛胚，n种可供排样选择的收稿日期：2023-02-10基金项目：教育部产学合作协同育人项目202101355003作者简介：顾雨娟（1998-），女，江苏盐城人，硕士研究生，研究方向：制造执行系统和铜带剪切优化。李学兵（1970-），湖南浏阳人，硕士，副教授，通信作者。E-mail：文章编号：1674-0874（2023）04-0128-052023年卷材，e种待考察的排样方式，建立数学模型：minZ=j=1ecjxj（1）S.T.AX B0 X Q（2）式（1）表示目标函数是使所消耗的卷材面积最小；式（2）第一条表示剪切卷材得来的毛胚数量需满足订单需求的数量，第二条表示每种排样方式的最大使用次数约束。符号定义：Z为下料方案中消耗卷材的总面积；C=c1,c2,ceT，cj为按照第j种排样方式剪切矩形毛胚使用卷材的面积，1 j e；X=x1,x2,xeT，xj为按照第j种排样方式剪切矩形毛胚的使用次数，1j e；Q=q1,q2,qeT，qj为按照第j种排样方式剪切矩 形 毛 胚 的 使 用 次 数 上 限，1 j e；B=b1,b2,beT，当1 i m时，bi表示第i种毛坯的需求数量，当(m+1)i (m+n)时，考虑到不限制每 种 可 供 排 样 卷 材 的 使 用 次 数，令bi=0，故i=m+1m+nbi=0；A：m行e列矩阵，当1 i m时，aij为按照第j种排样方式剪切卷料时得到第i种毛坯的数量；当(m+1)i (m+n)时，aij为按照第j种排样方式剪切矩形毛胚使用第（i-m）种卷材，考虑到一种排样方式只能使用一种卷材，i=m+1m+naij=1，1 j e。2 剪切排样方案设计2.1 获取排样方式采用普通两阶段排样方式（图2）虽然也可以满足“一刀切”的工艺约束，但后续仍需要进一步剪切加工为成品矩形毛胚，无疑会给企业增加更多的切割成本同时延长交付时间。w5612543726413回炉废料l5l4w6w1w7w2图2 普通两阶段排样方式实际剪切生产环境中，子卷被剪切后需要立即完成包装操作，不同规格的成品由不同的箱子进行装箱，这种排样方式也会增加包装工序的复杂性。求解模型算法需要调用本节算法获取排样方式，每种排样方式选取的待排毛胚种类过多会影响算法的整体性能。采用普通两阶段排样方式“一刀切”下来会产生较多的废料，不利于提高成材率。为了简化实际生产中的切割工艺并减少剪切卷材后续的包装工序的操作复杂度，同时提升求解算法性能且尽量减少废料面积，采用匀质块的思想进行矩形毛胚的排样布局（图3），各个匀质块中仅含同有一种规格的矩形毛胚，由切头剪竖直“一刀切”下来的待剪毛胚最多两种最少一种，当前用来排样的卷材的剩余的不可使用宽度小于当前待排毛胚的最小宽度，并规定卷材的宽度利用率达到90%以上。111111666666661l1l1l6w1w1w1w6w6回炉废料图3 匀质块两阶段排样方式设：可 供 排 样 的 卷 材 宽 度 有 n 种 宽 度，N=W1,W2,Wn；待 排 毛 坯 宽 度 有 m 种 宽 度，M=w1,w2,wm；当 前 待 排 毛 胚 的 最 小 宽 度 为w(w M)；当 前 使 用 排 样 的 卷 材 宽 度 为W(W N)。当排样方式仅含有一种毛胚，设第j种排样方式由第1种毛坯剪切，则第j种排样方式使用次数上限由式（3）求出，其中 ceil()函数为向上取整函数。qj=ceil()b1a1j（3）式（4）表示设第j种排样方式只剪第1种毛胚时的数量约束。0.9W a1jw1 W,a1j N+W-a1jw1 w,a1j N+（4）当排样方式含有两种毛胚，设第j种排样方式由第1、2种毛坯剪切，则第j种排样方式使用次数上限由式（5）求出。qj=maxceil()b1a1j,ceil()b2a2j（5）顾雨娟等：基于改进麻雀算法的铜带排样优化应用129山西大同大学学报(自然科学版)2023年式（6）表示设第j种排样方式剪第1、2种毛胚各自的数量约束。0.9W a1jw1+a2jw2 W,a2j N+W-(a1jw1+a2jw2)w,a2j N+(6)在实际生产环节中，包装工序同时进行单卷卷称重，工人根据子卷的卷重是否在订单要求的最低卷重和最高卷重范围之间判断是否可以发货，所以在拿到订单时需要对相关数据进行预处理，根据母带卷料的铜合金密度、卷料厚度，计算出每种规格的成品交付时的最大长度和最小长度，即实际长度在最小长度和最大长度范围内即可。为了求取各个排样方式的有效长度，首先求出各个排样方式的下限长度U=u1,u2,ue，上限长度V=v1,v2,ve，对二者取交集得出每种排样方式的长度范围。3 求解算法首先根据 2.1节排样算法获取每种排样方式的待剪毛胚种数、待剪毛胚数量以及排样方式长度范围，然后以改进麻雀搜索算法作为求解算法。3.1 问题编码与解码将每种排样方式使用对应卷材的总面积(每种排样方式使用卷材的面积C 每种排样方式的使用次数 X)作为决策变量，其中一个解可以表示为P=p1,p2,pe，pj表示第j种排样方式剪切卷材的总面积，则pj需要同时满足式（7）和式（8），其中1 j e,1 t n,k N+，Wt为第 j种排样方式使用的卷材宽度。0 pj WtVjqj（7）WtVjpjk WtUj（8）式（7）为P的可行解范围，式（8）为矩形毛胚的长度浮动约束，以及限制排样方式的使用次数必须为整数。3.2 适应度函数设计f=j=1e(cjxj+yj)=j=1e(pj+yj)（9）f为适应度函数值，f越小，下料方案使用卷材的总面积越少，卷料利用率越高，适应度越好。对于不满足式（7）和式（8）约束的解，将会生成一个罚函数，将第j种排样方式生成的罚函数值设为为yj，令yj pj，罚函数加到原适应度函数值上，通过比较原适应度函数的值，不符合约束的将会成为劣解并被淘汰。3.3 改进麻雀搜索算法标准麻雀搜索算法(SSA)是受麻雀群体觅食行为启发而来6，模拟其在自然环境中寻找食物和避开天敌的行为以寻找最优解，可简单抽象为寻找者跟随者模型。寻找者在种群中引领搜寻食物的方向，跟随者时刻监视寻找者的方向并跟随移动，二者身份动态变化，在麻雀群体中随机选取 10%20%为预警者，一旦发现有天敌靠近，则向安全区域移动。SSA算法原理为：Xt+1i,j=Xti,jexp()-iT,R n2XtP+|Xti,j-Xt+1i,jA+L,i n2（11）Xt+1i,j=Xtbest+|Xti,j-Xtbest,fi fgXti,j+KXti,j-Xtworst()fi-fw+,fi=fg（12）式（10）为发现者位置更新方式。t和T分别为当前迭代次数和最大迭代次数，为0到1之间的随机数，Q为服从正态分布的随机数，R和ST分别为捕食过程中的预警值和安全值，R 0,1和ST 0.5,1。当R n2时，群体需要扩大捕食范围飞到适应度较高的地方寻找食物；当i n2时，群体在发现者附近寻找食物。式(12)为预警者位置更新方式。Xtbest为当前迭代次数全局中最优解的位置，为步长参数，取值为一个服从均值是0的方差是1的正态分布的随机数，K取值为-1,1的一个随机数，fg为当前迭代次数全局中最优解的位置的适应度值，fw为当前迭代次数全局中最差解的位置的适应度值，无限接近于 0。当fi fg时，该群体发现天敌，需要向最优解的位置移动；当fi=fg时，可通过预警改变寻找路线，避免被捕食。3.3.1 Singer混沌Singer映射是一种典型的混沌映射，相比于其他1302023年混沌映射，其数学表达式简单，参数较少，可使初始解更加均匀地分布，在一定程度上提升种群多样性，并且在迭代初期加快搜索速度，其表示形式为：Xk+1=(7.86Xk-23.31X2k+28.75X3k-13.302875X4k)（13）其中，x 0,1，(0.9,1.08)。3.3.2 柯西变异机制麻雀群体在寻找食物的过程中，跟随者往往在具有较高适应度值的发现者附近食，进而转换身份成为发现者，这就会导致算法陷入局部最优，降低算法寻找最优解的精度。为了避免这种情况，在标准麻雀搜索算法中引入柯西变异机制跳出局部最优解，跟随者位置更新变异公式为：Xt+1i,j=Xbest()t+cauchy()0,1 Xbest()tcauchy=tan(rand-0.5)（14）3.4 算法步骤步骤：初始化各个生产参数、麻雀算法参数，调用2.1节算法获取排样方式组合A，单卷使用卷材长度下限U、上限V，排样方式使用次数上限Q。步骤2：用公式（13）对麻雀种群进行初始化，使之生成均匀分布的混沌序列。步骤 3：计算每个麻雀位置对应的适应度函数值，并记录全局最优解和全局最差解。步骤 4：对麻雀种群依据适应度函数值进行排序，选取排序值前30%的麻雀为发现者，其余为跟随者，用式（10）和式（11）更新发现者和跟随者位置。步骤5：在麻雀种群中随机选取15%个体为预警者，用式（12）对预警者进行位置更新，并更新全局最优解和全局最差解。步骤6：对跟随者按一定概率用式（14）进行柯西变异，若变异后适应度更高则替代原来位置，否则不变。步骤7：达到最大迭代次数，结束算法，否则继续迭代步骤3。4 实验结果与分析为了检验求解算法的合理性，测试了来源于湖北精益高精铜板带有限公司的实际生产数据，通过对客户订单数据进行预处理后得到单卷最小长度、最大长度、成品宽度和需求量见表1，可供排样的卷材为厚度0.1 mm，宽度分别为420 mm和350 mm，铜含量 99.95%以上，含氧量 0.01 以下，导电量大于98%IACS的TP2紫铜带。表1 生产实例中的订单需求数据订单序号12毛胚序号12345612345宽度/mm7260175145543002633772153200最小长度/m12591180142210801251139511641472155210971707最大长度/m13911304173811941529154111881566165012131741需求数量/卷6111391721181371216仿真实验运行在 MatlabR2022a上，设定种群大小为20，最大迭代次数500，分别独立运行5次，将遗传模拟退火算法(GASA)、基于排挤的小生境遗传算法(DC)8、改进麻雀搜索算法(SCSSA)三种算法在相同环境中进行对比运算，结果见表2。表2 排样求解结果订单序号第1组第2组算法GASADCSCSSAGASADCSCSSA最大使用面积/m223 040.6422 543.1421 843.4321 473.3720 753.5819 981.13最小使用面积/m220 691.3520 733.5817 444.8618 053.7417 473.3516 073.03使用面积均值/m221 701.9921 119.4619 487.2419 859.7318 772.1117 918.31卷材利用率均值/%78.3180.4787.2174.3978.7082.45顾雨娟等：基于改进麻雀算法的铜带排样优化应用131山西大同大学学报(自然科学版)2023年为了分析对比结果，卷料利用率迭代收敛曲线图如图 4。经过 Singer混沌结合柯西变异的改进麻雀算法SCSSA算法在卷材利用率、寻找最优解能力等方面明显高于另外两者算法，这是因为 GASA算法在寻找最优解后期有易陷入局部最优解的缺陷，DC算法在处理相似解的判断和替换能力上表现欠佳，而SCSSA引入的柯西变异机制能够限制陷入局部最优解，提高寻优能力。图4 迭代曲线收敛图5 结语针对基于剪切优化排样模型方案的滚动排产问题，以消耗最少母带卷料面积为目标建立了排样优化模型，依据排样结果来进行滚动排产。从排样方式上讲，基于一种匀质块的思想设计矩形毛胚的排入顺序，不仅有利于指导工人在实际生产中简化卷材剪切工艺，也减少了后续成品包装工序的操作复杂度，加快了交付进程；从求解算法上讲，使用改进的麻雀搜索算法进行求解，相比其他算法在卷料利用率方面有更优秀的表现，全局寻优和局部寻优能力更强。由于实际剪切工序在分剪时不可避免地出现带头带尾损耗，在今后的研究中将进一步通过数据分析，并在客户接受的一定程度内考虑成品卷重、数量超发减发的情况，建立相应的优化模型使成材率更加精确。参考文献1 姜业欣，娄花芬，解浩峰，等.先进铜合金材料发展现状与展望 J.中国工程科学，2020，22（5）:84-92.2 冯建云，刘祎.面向利用率的矩形排样分级进化遗传算法优化 J.机械设计与制造，2022（11）:11-16.3 张宇.二维多母板不规则排样研究 D.秦皇岛:燕山大学，2022.4 朱光宇，蒋起爽，林晓斌.基于最优觅食算法的增材制造中多种类零件分批排样研究 J/OL.计算机集成制造系统:1-152023-02-10.http:/ 沈孝龙，王吉芳，郭子昇.基于改进麻雀搜索算法的机械臂路径规划 J.组合机床与自动化加工技术，2023（1）:15-19.6 XUE J，SHEN B.A novel swarm intelligence optimization approach:Sparrow search algorithm J.Systems Science&ControlEngineering，2020，8（1）:22-34.7 黎凤洁，崔耀东，陈秋莲.面向可加工性的卷材优化下料方法 J.锻压技术，2020，45（2）:67-72.8 CHOU F I，HO W H，CHEN C H.Niche genetic algorithm for solving multiplicity problems in genetic association studies J.In-telligent Automation&Soft Computing，2020，26（3）:501-512.Optimization Application of Copper Strip Layout Based on Improved Sparrow AlgorithmGU Yu-juan,LI Xue-bing*(School of Electrical and Information Engineering,Hubei University of Automotive Technology,Shiyan Hubei,442000)Abstract:The cutting procedure is not only the bottleneck procedure of product delivery for small batches and varieties ofcopper plates and strips production enterprises,but also the key procedure for enterprises to pursue high material utilization.In thispaper,an optimized cutting layout model which takes the cutting procedure of Hubei Jingyi High Precision Copper Plates andStrips Co.,Ltd.as the research object is established.The guillotine constraint in cutting procedure is designed with homogeneousblocks and the single-volume length floating constraint is handled by the penalty function.Then the improved sparrow search algo-rithm is used to automatically generate the layout plan.The Singer chaotic sequence is used to improve the diversity of the initialpopulation,and combines Cauchy mutation to improve the accuracy of the later optimization.The coil utilization rate is higherthan other algorithms.The rolling type one day production planning based on the cutting optimization scheduling model schemesolves the contradiction between product delivery and high material utilization and provides a good reference for the cutting proce-dure of similar enterprises.Key words:layout optimization;material utilization;length floating;guillotine constraints;sparrow search algorithm责任编辑 王东132