解决矩形件带排样问题的一种遗传算法

论文摘要

矩形件排样问题广泛存在于机械、家具、服装等国民经济行业,解决好该问题可以节省原材料,简化生产工艺,降低生产成本,增加企业效益。对于许多不规则零件的排样问题,也可通过计算机的图形处理技术将其转化为矩形件排样问题。矩形件带排样问题(RSPP)是指将给定的一定数量的矩形件P1 , P2 ,…, Pn排放在定宽无限高的板材Q中,使所占据板材的高度最小。它是计算机辅助排样的一个重要分支。但RSPP在理论上是属于高计算复杂性的NP完全问题,在问题规模较大时,很难用精确算法求得最优解。因此,研究RSPP具有重要的实用和理论价值。遗传算法是基于生物进化和随机选择的全局搜索优化计算技术,它模拟生物进化的基本过程,用数码基因串来类比生物中的染色体,通过选择、交叉、变异等遗传算子来仿真生物的基本进化过程,进化若干代以后,使最优异染色体所代表的问题解逼近问题的全局最优解或近优解。多种群遗传算法采用多个种群代替单一种群,其中每个子种群按各自不同的进化策略和遗传操作并行独立进化。进化过程中可以选取和保留每个子种群的优秀染色体,就可以在保持优秀染色体进化的稳定性的同时加快进化速度,避免单一种群进化过程中出现的过早收敛现象。基于上述考虑,本文以多种群遗传算法为基础,提出了一种基于遗传算法求解RSPP的新算法。通过大量的实例测试,验证了该算法的有效性。本文的主要工作和创新点如下:首先,改进了一种矩形件近似排样算法。对中外学者提出的四种近似排样算法进行比较和分析,在总结其优缺点的基础上,针对递减排序的矩形序列,对基于最低水平线的搜索算法进行了改进,称为基于最低水平线的择优插入算法。改进算法在零件排放过程中,将最低水平线的长度先与当前待排放矩形件的长度(本文定义矩形件平行X轴的方向称为长度,另一边称为宽度)比较,若最低水平线的长度大于矩形件的长度,将矩形件排放在此位置;否则将最低水平线的长度与当前矩形的宽度比较,若最低水平线的长度大于矩形件的宽度,将矩形件旋转90度排放在此位置。若最低水平线的长度均小于当前矩形件的长度和宽度,即说明当前矩形件不能放到最低水平线上,则在排样序列的当前位置向后搜索,选择一个满足排放条件并且长度或者宽度与最低水平线的长度最接近的矩形件(称为最优零件)进行合理排放;否则,更新最低水平线。将搜索到的最优零件直接插入到当前排放位置,不更改后续矩形的序列。算法可以使得零件之间排放紧凑,降低排样高度,在一定程度上提高材料利用率。其次,将基于最低水平线的择优插入算法和简化的多种群遗传算法结合,设计了一种采用两个种群并行进化的遗传算法求解RSPP的新算法。矩形件排样问题中如何产生排样序列是一个关键的问题,许多学者应用遗传算法,模拟退火算法等算法产生排样序列,再将产生的排样序列与某种矩形件近似排样算法结合求解矩形件排样问题,取得了较好的排样效果。多种群遗传算法是在基本遗传算法基础上改进的一种算法。本文分析了多种群遗传算法,应用两个规模相当的子种群进行并行进化,其中两个子种群采用不同的初始策略。产生两种不同性质的矩形零件递减序列,并设计了求解RSPP的相关操作,定义了求解RSPP的适应度函数。将遗传算法产生矩形件的递减序列,按照本文的基于最低水平线的择优插入算法和本文的适应度函数得到序列的适应度值,并生成排样图。通过矩形零件序列的适应度值的比较,从而得到一个较优的排样方案。然后,规划和设计了排样系统的基本功能模块,开发了一个基于遗传算法的矩形件优化排样系统。通过大量实验测试,并将实验结果与应用遗传算法、模拟退火算法、随机算法求解矩形件排样问题的实验结果进行了比较和分析,验证了该系统的算法的有效性。最后,论文对己完成的工作进行了总结,提出了需要进一步改进的工作。

论文目录

• 中文摘要
• Abstract
• 第一章 绪论
• 1.1 计算机辅助优化排样简介
• 1.2 矩形件排样问题的分类
• 1.3 矩形件排样问题的复杂性理论
• 1.4 课题的国内外研究动态
• 1.5 本文的研究内容
• 1.6 论文的章节组织
• 第二章 遗传算法
• 2.1 遗传算法的理论
• 2.2 遗传算法的基本步骤
• 2.2.1 编码问题
• 2.2.2 种群的初始化
• 2.2.3 适应度函数
• 2.2.4 遗传算子
• 2.3 遗传算法研究的进展
• 2.3.1 基本遗传算法的改进
• 2.3.2 混合遗传算法
• 第三章 基于遗传算法的矩形件带排样算法研究
• 3.1 基于遗传算法的矩形件带排样算法
• 3.1.1 BL 算法
• 3.1.2 下台阶算法
• 3.1.3 最低水平线算法
• 3.1.4 基于最低水平线的搜索算法
• 3.2 基于最低水平线的择优插入算法
• 3.2.1 择优策略
• 3.2.2 插入策略
• 第四章 解决矩形件带排样问题的遗传算法
• 4.1 遗传算法解决矩形件带排样问题的不足与改进
• 4.2 遗传算法基本流程
• 4.3 染色体编码方式
• 4.4 启发式初始种群生成策略
• 4.5 适应度计算
• 4.6 遗传算子
• 4.6.1 交叉算子
• 4.6.2 变异算子
• 4.6.3 选择算子
• 4.7 分配较优染色体
• 第五章 矩形件带排样系统的研制与实验计算
• 5.1 矩形件带排样系统的研制
• 5.2 实验计算
• 5.2.1 第一组例题
• 5.2.2 第二组例题
• 5.2.3 第三组例题
• 5.2.4 第四组例题
• 5.3 实验结果分析
• 第六章 总结与展望
• 参考文献
• 攻读硕士学位期间发表的论文
• 致谢