两阶段遗传算法和贪心策略相结合的多约束排样优化方法.pdf
《两阶段遗传算法和贪心策略相结合的多约束排样优化方法.pdf》由会员分享,可在线阅读,更多相关《两阶段遗传算法和贪心策略相结合的多约束排样优化方法.pdf(9页珍藏版)》请在咨信网上搜索。
1、第 31 卷 第 3 期厦门理工学院学报Journal of Xiamen University of TechnologyVol.31 No.32023 年 6 月Jun.2023两阶段遗传算法和贪心策略相结合的多约束排样优化方法马英钧,钟俊江*(厦门理工学院数学与统计学院,福建 厦门 361024)摘 要为了提升产品排样问题的板材利用率,降低生产成本,同时满足切割过程中的“齐头切”和“阶段数不超过3”的约束,分别建立产品和条带组合优化的数学模型;引入序号编码、部分交叉映射,设计局部最优解码方案,进而建立两阶段遗传算法模型。基于贪心策略分别建立产品和条带余料再利用算法来提升利用率,提出一种两
2、阶段遗传算法和贪心策略的排样优化方法。5个基准数据集验证的结果表明:与其他排样优化模型相比,多阶段遗传算法和贪心策略的排样结果不仅满足“齐头切”和“阶段数”的约束,同时板材的利用率更高,在5个数据集上的板材利用率基本上都可保持在80%以上。关键词排样优化;遗传算法;贪心策略;板材利用率中图分类号O221.2 文献标志码A 文章编号1673-4432(2023)03-0079-09Layout Optimization Based on Two-Stage Genetic Algorithm and Greedy StrategyMA Yingjun,ZHONG Junjiang*(School
3、 of Mathematics&Statistics,Xiamen University of Technology,Xiamen 361024,China)Abstract:To improve the plate utilization rate,reduce cost,and satisfy the constraints of“straight and edge cutting”and“no more than 3 stages”in the cutting process,a model of a two-stage genetic algorithm with the greedy
4、 strategy was proposed to optimize the layout.To accomplish this,mathematical models of product and strip combination were first introduced with serial number coding,partial cross mapping and local optimal decoding schemes to develop the two-stage genetic algorithm model,and the greedy strategy used
5、 to develop the algorithm for product and strip residual material reuse to improve the utilization rate.The results verified by five benchmark data sets show that compared with other layout optimization models,the layout results of the two-stage genetic algorithm with the greedy strategy meet the co
6、nstraints of“straight and edge cutting”and“no more than 3 stages”,and have a higher plate utilization rate,marking basically 80%or more on all five data doi:10.19697/ki.1673-4432.202303012收稿日期:20221109 修回日期:20230224基金项目:福建省自然科学基金项目(2021J05260,2023J011433);教育部人文社会科学研究青年基金项目(21YJC910011);福建省中青年教师教育科研项
7、目(JAT200474)通信作者:钟俊江,男,副教授,博士,研究方向为应用统计、统计计算,E-mail:。引文格式:马英钧,钟俊江.两阶段遗传算法和贪心策略相结合的多约束排样优化方法 J.厦门理工学院学报,2023,31(3):79-87.Citation:MA Y J,ZHONG J J.Layout optimization based on two-stage genetic algorithm and greedy strategyJ.Journal of Xiamen University of Technology,2023,31(3):79-87.(in Chinese)厦门理工
8、学院学报2023 年sets.Key words:layout optimization;genetic algorithm;greedy strategy;board utilization rate排样优化问题本质上也称切割填充问题,优化的目的是合理规划方形产品在板材上的布局,减少下料过程中的板材浪费,简化切割过程。下料作为众多制造企业生产链中产品及零部件生产的第一道工序,消耗的材料和资源不容小觑,如何提高材料利用率,降低原材料消耗,是企业减少资源和能源浪费,承担环境保护责任所要解决的关键问题。针对排样优化问题,当前已提出一些计算模型。王竹婷等1将层次聚类思想引入矩阵排样优化问题中,通过计
9、算矩形组件间的结合度,将结合度最高的组件进行合并,并重复该过程来实现优化方案设计。王伟等2提出了一种基于捕食策略的遗传算法,通过对编码、遗传算子和适应度算子进行改进,并结合最低轮廓线搜索算法来获得最优布局。曾晓亮等3利用六元数组对矩形组件进行表征,并利用多岛遗传算法来设计排样方案,结果表明,该方案具有较高的利用率和稳定性。近年来,陈仕军等4提出反悔算子、距离受限邻域算子、满足容忍度3种策略来改进传统的邻域搜索算法,通过与以往方法的结果对比发现,该方法具有很高的求解效率。吴继聪等5介绍了多种Meta-Heuristic算法在排样优化研究中的应用,并分析不同算法的性能和适用场景。与之前的方形组件的
10、排样优化研究不同,张闯等6研究二维椭圆零件的排样优化问题,提出了一种在仿射坐标系下的变换,并建立整数规划模型。以上成果虽然推动了排样优化问题的研究,但是它们仅考虑如何排样以使材料最省,很少考虑到机器的具体切割限制,比如每次的切割可以保证板材分离及切割的次数不能过多的限制等。基于此,针对多约束排样优化问题的特点,本文提出了一种两阶段遗传算法和贪婪策略相结合的排样优化方法,建立产品布局和条带布局的数学模型,利用一种两阶段遗传算法来进行模型求解,并设计有效的解码方案提升模型的求解效率。同时,为了进一步提升利用率,针对“条带余料”和“板材余料”建立2种基于贪婪策略的算法模型,并在多个数据集上执行计算,
11、以验证本文算法的有效性。1问题分析本研究的问题引自2022年“中国光谷华为杯”研究生数学建模竞赛B题第一问。本问题中的切割需要满足以下条件:1)只考虑“齐头切”的切割方式(直线切割、切割方向垂直于板材一条边,并保证每次直线切割板材可分离成2块);2)切割阶段数不超过3,同一个阶段切割方向相同;3)假定板材原片仅有一种规格且数量充足;4)排样方案不用考虑锯缝宽度(即切割的缝隙宽度)影响;5)最终切割生成的产品项是完整的,非拼接而成。图1是一种有效的3阶段切割方式及其生成的模块。图1一种3阶段切割方式及其生成模块简图Fig.1A three-stage cutting mode and modul
12、es it generated80第 3 期马英钧,等:两阶段遗传算法和贪心策略相结合的多约束排样优化方法图1中:实竖线表示第一次切割得到两个模块分别是条带1和条带2;长横虚线表示对于条带的切割(即第二次切割)得到6个栈分别是栈1、栈2、栈3、栈4、栈5和栈6;短竖虚线表示对于栈的切割(即第三次切割)最终获得17个产品。由图1可以看出,以上的每次切割都是沿着板材的一条边进行的,并且每次切割都将板材分成2段。对于该问题直接进行二维布局,不仅计算复杂度高,而且很有可能导致不满足“切割阶段不超过3”的约束。由图1可知,第二刀切割会产生多个栈,每个栈都是由边长相等的产品组成的,因此,研究等边长的产品可
13、以在一定程度上提升板材的利用效率。为了减少切割的次数,先将边长相等的产品拼接为条带,并将条带沿着板材的长边放置。因此,根据产品的边长特点,将其分为3个类别:1)类别1包含有相等的边长,并且相等边长小于W(板材的宽)的产品;2)类别2包含边长大于W的产品;3)类别3包含与其他产品的边长都不相等的产品。对于类别1,建立一阶段模型来实现产品组合为条带优化;对于类别1得到的条带和类别2的产品(每个作为一个条带),建立二阶段模型来实现条带在板材上的布局优化;对于边长不相等的产品(类别3),利用前两步的废料和新板材,执行余料再利用。具体求解框架见图2。2基于两阶段遗传算法的产品布局优化本节主要通过两阶段遗
14、传算法来实现类别1和类别2的产品在板材上的优化布局,主要包含3个步骤:1)建立产品组合优化数学模型;2)建立条带优化数学模型;3)构建两阶段遗传算法来初步实现两类产品在板材上的最优布局。2.1产品组合优化数学模型的建立对于物品很少的分组,如果直接组合为条带,可能会导致空间的浪费。因此,设置阈值,对边长相等的物品数大于的那些分组拼接为条带。令M1表示需要拼接的物品的个数,li表示第i产品的另一边(除了相等边长的另一边)的长度,M2表示预估需要的条带个数,xij表示第i产品是否放置于条带j中,当第i产品置于条带j中时,xij=1,反之,xij=0。为了使得用料最省,要求在不超过每个条带的限制长度L
15、(板材的长边)情况下,使得所用的条带的数量尽可能少。此时,其模型为argminx j=1M2(i=1M1xij),s.t.i=1M1xij li L,j=1,M2;j=1M2xij=1,i=1,2,M1;xij0,1,i=1,M1,j=1,M2。(1)图2多约束排样优化问题的整体求解框架Fig.2Solution framework for multi-constraint layout optimization81厦门理工学院学报2023 年在式(1)的目标函数中:argminx()表示最小目标函数下变量x的值;(x)为判断函数,当x0 时,(x)=1,当x=0时,(x)=0。由式(1)可以
16、看出,目标函数要求选取的条带数尽可能小。第一个约束条件要求,每个条带剪裁的产品项的总长度小于原片的最大长度L。第二个约束要求每个产品必须有一个条带来剪裁。第三个约束条件要求xij是01决策变量。需要注意的是,以dataA1的边长为58的产品为例,其84个产品另一边长的总和为100 830,而每个条带的最大长度为2 440,因此,M 100 830/2 440 41.32。对于式(1)描述的混合01规划问题,变量的个数至少为84 42。2.2条带组合优化数学模型的建立本节主要介绍条带在板材上最优布局的数学模型的建立。令wiN1i=1表示类别1得到的N1个条带宽的集合,wiN2i=1表示类别 2的
17、N2个的产品(即条带)的较短边长度的集合。此时,一共有N3=(N1+N2)个条带,这些条带的宽组成的集合可记为wiN3i=1。令N4表示预估需要的板材个数。yij表示第i个条带是否放置于板材j中,当第i个条带放置于板材j中时,yij=1,反之,yij=0。根据板材数量最小的目标,以及每个板材中条带宽度和不超过W(即板材宽度)的约束,可以得到如下约束优化问题argminy j=1N4(i=1N3yij),s.t.i=1N3yij wi W,j=1,2,N4;j=1N4yij=1,i=1,2,N3;yij0,1,i=1,N3,j=1,N4。(2)式(2)中:(x)为判断函数,与式(1)中的定义类似
18、。由式(2)可以看出,目标函数要求选取的板材数尽可能小。第一个约束条件要求每个板材剪裁的条带的总宽度小于板材的宽度W,第二个约束要求每个条带必须有一个板材来剪裁,第三个约束条件要求yij是01决策变量。需要注意的是,以dataA1和阈值=10为例,根据类别1拼接得到108个条带和类别2的102个条带,一共得到 210 个条带。这些条带的总宽度为71 754,因此,至少需要的板材数量N=71 754/1 220 59。也就是说,式(2)描述的模型中决策变量的个数至少为210 59。2.3基于两阶段遗传算法的模型求解节2.1和节2.2描述的问题都是混合01规划模型,并且模型中决策变量的个数都比较多
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 阶段 遗传 算法 贪心 策略 相结合 约束 优化 方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。