矩形件排样问题的遗传模拟退火算法研究

发布时间：2020-06-03 07:11

【摘要】：排样优化问题广泛存在于现代工业生产加工行业中,如钢筋切割,布料裁剪,印刷排版以及机械制造等,是制造业自动化从设计到下料过程的关键环节。排样优化问题的研究旨在通过寻找一种合理有效的算法,以节省原材料的消耗,降低生产成本,提高企业经济效益。本文研究矩形件排样问题:在宽度固定长度不限的板材上,按照某种策略排入一定规格数量的矩形件,以充分利用原材料。该类问题在数学上属于NP完全问题,不能确保在有限的计算时间内得到最优解。因此,如何设计一种高效的求解算法用于矩形件排样问题,具有重要的研究意义与价值。本文提出一种自适应遗传模拟退火算法,将遗传算法和模拟退火算法相结合以确定矩形件的排放顺序,并改进一种定位算法以确定矩形件在板材中的摆放位置。本文的主要工作如下:1.提出基于匹配度的最低水平线启发式搜索算法。在排入过程中引入旋转和启发式判断,对无法排入最低水平线的矩形件进行旋转重排。若仍无法排入,则在后续待排矩形件序列中,通过匹配度函数中的主影响因子和次影响因子从全局优化上共同指导最优矩形件的选择,搜索出与最低水平线匹配度最高的矩形件并排入。改进后的算法可以有效利用空闲区域,减少板材的浪费。2.在遗传模拟退火算法中引入动态调整策略,根据当前个体适应值的大小自动调节交叉和变异概率,动态地控制收敛速度和搜索解的能力。同时采用环形交叉算子,交叉过程环绕染色体两端进行,以保证基因被选中的概率相等。对遗传操作后的所有个体按照状态产生函数生成新个体,并计算适应值,若满足接受概率,用新个体替换旧个体;否则,进行降温操作,并更新最优个体,直到达到最大迭代次数,完成模拟退火过程。多组算例的对比结果表明,本文提出的自适应遗传模拟退火算法在保证算法性能的同时具有较快的求解速度,可以有效提高板材的利用率。
【图文】：

一维排样问题通常只考虑原料为一个维度的条形材料，相比材料的长度而言，宽度逡逑往往可以忽略，比如线材切割、钢管切割。依照所需产品的种类，可以将其分为单一原逡逑材料排样和多种原材料排样。图１－１所示为一维线材排样示例图，其中阴影部分为需要逡逑在原材料上排放的线形毛坯。逡逑ｆｉｌｌ邋W逡逑Ｉ邋｜逦］［．逦．逡逑（ａ）逦（ｂ）逡逑１邋．逦逦１逦ｉ—逡逑（ｃ）逡逑图Ｍ邋—维线材排样示例（ａ）原材料（ｂ）所需毛坯（ｃ）排样方案逡逑Ｆｉｇ．邋１－１邋Ｅｘａｍｐｌｅ邋ｏｆ邋ｏｎｅ－ｄｉｍｅｎｓｉｏｎａｌ邋ｗｉｒｅ邋ｌａｙｏｕｔ邋（ａ）Ｍａｔｅｒｉａｌｓ邋（ｂ）Ｒｅｑｕｉｒｅｄ邋ｐａｒｔｓ邋（ｃ）Ｌａｙｏｕｔ邋Ｓｃｈｅｍｅ逡逑二维排样问题考虑毛坯在水平原材料上的布局，依据所需毛坯的属性，可以将其分逡逑为规则毛坯排样优化问题和不规则毛坯排样优化问题［３］。图１－２所示为二维矩形件排样逡逑示例图，其中排入的毛坯必须互不重叠，且正交排放。逡逑图１－２二维矩形件排样示例逡逑Ｆｉｇ．邋１－２邋Ｅｘａｍｐｌｅ邋ｏｆ邋ｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌ邋ｒｅｃｔａｎｇｌｅｓ邋ｌａｙｏｕｔ逡逑三维排样问题需要考虑毛坯在长、宽、高三个方位的布局，其中原材料和毛坯同为逡逑三维物体，需要将一定体积和重量的毛坯装入固定体积的原材料箱体中，且须同时满足逡逑体积和重量相关约束条件，在满足毛坯需求的同时，使得所使用箱体的总数最少或箱体逡逑空间利用率最大

一维排样问题通常只考虑原料为一个维度的条形材料，相比材料的长度而言，宽度逡逑往往可以忽略，比如线材切割、钢管切割。依照所需产品的种类，可以将其分为单一原逡逑材料排样和多种原材料排样。图１－１所示为一维线材排样示例图，其中阴影部分为需要逡逑在原材料上排放的线形毛坯。逡逑ｆｉｌｌ邋W逡逑Ｉ邋｜逦］［．逦．逡逑（ａ）逦（ｂ）逡逑１邋．逦逦１逦ｉ—逡逑（ｃ）逡逑图Ｍ邋—维线材排样示例（ａ）原材料（ｂ）所需毛坯（ｃ）排样方案逡逑Ｆｉｇ．邋１－１邋Ｅｘａｍｐｌｅ邋ｏｆ邋ｏｎｅ－ｄｉｍｅｎｓｉｏｎａｌ邋ｗｉｒｅ邋ｌａｙｏｕｔ邋（ａ）Ｍａｔｅｒｉａｌｓ邋（ｂ）Ｒｅｑｕｉｒｅｄ邋ｐａｒｔｓ邋（ｃ）Ｌａｙｏｕｔ邋Ｓｃｈｅｍｅ逡逑二维排样问题考虑毛坯在水平原材料上的布局，依据所需毛坯的属性，可以将其分逡逑为规则毛坯排样优化问题和不规则毛坯排样优化问题［３］。图１－２所示为二维矩形件排样逡逑示例图，其中排入的毛坯必须互不重叠，，且正交排放。逡逑图１－２二维矩形件排样示例逡逑Ｆｉｇ．邋１－２邋Ｅｘａｍｐｌｅ邋ｏｆ邋ｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌ邋ｒｅｃｔａｎｇｌｅｓ邋ｌａｙｏｕｔ逡逑三维排样问题需要考虑毛坯在长、宽、高三个方位的布局，其中原材料和毛坯同为逡逑三维物体，需要将一定体积和重量的毛坯装入固定体积的原材料箱体中，且须同时满足逡逑体积和重量相关约束条件，在满足毛坯需求的同时，使得所使用箱体的总数最少或箱体逡逑空间利用率最大
【学位授予单位】：广西大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP18

【相似文献】

相关期刊论文 前10条

1 张瑞友;潘卫平;刘士新;;基于匀质块五块模式的矩形件非剪切排样算法[J];东北大学学报(自然科学版);2018年06期

2 董功云;陈进;王鸿超;;矩形件排样的流程和算法设计[J];轻工机械;2016年06期

3 易向阳;潘卫平;张俊晖;;基于五块模式的单一矩形件排样算法[J];图学学报;2015年04期

4 宋雪枫;陈江义;张明伟;;基于遗传算法的矩形件排样问题求解[J];煤矿机械;2011年05期

5 陈仕军;曹炬;;矩形件优化排样的一种启发式算法[J];计算机工程与应用;2010年12期

6 彭文;;一种快速的有约束矩形件优化排样模型[J];计算机工程与应用;2010年27期

7 邓冬梅;周来水;安鲁陵;王桂宾;;矩形件优化排样的研究[J];宇航材料工艺;2007年04期

8 马炫;张亚龙;;基于遗传算法的大规模矩形件优化排样[J];智能系统学报;2007年05期

9 宋连超;朱建良;张彤;;矩形件排样优化贪婪算法及系统开发[J];哈尔滨理工大学学报;2007年01期

10 黄红兵;一个矩形件排样的较优算法[J];东华理工学院学报;2005年03期

相关博士学位论文 前1条

1 岳琪;基于遗传退火算法板式家具大规模矩形件优化下料研究[D];东北林业大学;2005年

相关硕士学位论文 前10条

1 夏以冲;矩形件排样问题的遗传模拟退火算法研究[D];广西大学;2018年

2 宋仁坤;基于遗传算法的矩形件排样问题研究[D];广西大学;2017年

3 陆敏;多约束条件下的矩形件优化排样研究[D];浙江大学;2006年

4 陈仕军;矩形件下料优化算法研究[D];华中科技大学;2009年

5 赵晓东;矩形件优化排样算法的研究与实现[D];大连交通大学;2008年

6 李捷;基于遗传算法与蚂蚁算法的矩形件布局问题的研究与应用[D];南昌大学;2008年

7 龚志辉;基于遗传算法的矩形件优化排样系统研究[D];湖南大学;2003年

8 赵新芳;解决矩形件带排样问题的一种遗传算法[D];广西师范大学;2008年

9 任海;鞍钢中厚板矩形件自动排板系统的研究与应用[D];哈尔滨工业大学;2017年

10 张伟;矩形件排样与切割路径优化技术研究[D];南京航空航天大学;2010年

本文编号：2694482