1、第 卷第期 年月 收稿日期:基金项目:国家自然科学基金资助项目()作者简介:李志华(),男,山东烟台人,硕士研究生,研究方向为智能优化算法;俞建峰(),男,江苏宜兴人,教授,研究方向为机器人运动控制。基于双种群遗传算法的含缺陷矩形件排样优化研究李志华,俞建峰,钱陈豪,(江南大学机械工程学院,江苏 无锡 ;江苏省食品先进制造装备技术重点实验室,江苏 无锡 )摘要:结合缺陷约束的最低水平线算法与双种群遗传算法,对板材内部含缺陷时的情况进行矩形件排样优化。用双种群遗传算法对矩形件排样顺序进行寻优,将矩形件的排样顺序和旋转方式划分为个种群分别进行遗传迭代,并结合改进的初始种群生成策略,改善算法的搜索效
2、率及全局寻优能力。基于缺陷约束的最低水平线算法通过更新缺陷矩形轮廓信息与引入缺陷位置约束判断,使矩形件在根据优化顺序排样时可避开缺陷部位。通过算例运算测试可知,相比于经典遗传算法,所提算法在种不同数量缺陷的板材中,最优板材利用率与排样优化稳定性均有所提高。双种群遗传算法和基于缺陷约束的最低水平线算法可在含缺陷板材的排样问题中得到推广应用。关键词:矩形件排样;最低水平线算法;遗传算法;内部缺陷;板材利用率中图分类号:文献标志码:文章编号:(),(,;,):,:;()引言二维矩形件排样优化问题,是指将一定种类和数量的矩形件按一定方式排放到一个宽度固定、高度不限的矩形板材上,要求排放时不得超出板材边
3、界,且矩形件之间互不重叠,并使板材的利用率最大化。该问题广泛应用于钣金件、玻璃、木板、面料皮革以及液晶面板等切割领域。对矩形件排样优化问题的求解,主要可分为矩形件的排放顺序及矩形件的排放策略个方面进行综合研究。前者指矩形件在板材中排放的先后顺序,后者指矩形件被放入板材时的排放方式。由于该问题属于 完全问题,难以在较短时间内求得问题最优解,故目前多利用智能优化算法对矩形件在板材中的排放顺序进行寻优,并结合启发式算法实现矩形件在板材中按照优化顺序进行合理排放,以达到提高板材利用率的目的。目前主流的智能优化算法有遗传算法(,)、模拟退火算法(,)和粒子群算法(,)等。比较经典的启发式算法包括 算法及
4、改进的 算法。贾志欣等提出了一种基于最低水平线的排样策略,令矩形件优先在高度最低的水平轮廓线上进行排放。龚志辉提出最低水平线搜索算法,使水平轮廓线上可优先排入宽度小于等于当前水平线的矩形件。对于矩形件排样优化问题,黄岚等结合离散 与求解。杨卫波等用改进的自适应 通过引入适应度指标优化排样过程。但上述算法均只针对无缺陷的规则板材排样优化进行研究,无法解决工程实际中板材含缺陷情况下的矩形件排样问题。针对该问题,本文提出一种基于双种群遗传算法(,)的含缺陷矩形件优化方法。二维矩形件排样问题描述二维矩形件排样问题可以描述为:将组个宽度及高度已知的矩形件,排入到个宽度固定为,高度不限的板材中,在满足相应
5、约束条件的情况下,使板材利用率最高,以此达到节约原材料的目的。包含个矩形件的排样实例如图所示。图二维矩形件排样实例二维矩形件排样优化问题可表述为:寻找矩形件最优排样方案,以求得最大板材利用率 ,其数学表达式为 ()为板材利用率;为矩形件总数;与分别为矩形件的宽度与高度;为板材宽度;为矩形件排样结束后所构成的外轮廓线的最高水平线高度。且需满足以下约束条件:任一矩形件不可超出板材边界。各矩形件之间不能互相重叠。矩形件在排样时能以或 进行排放。缺陷约束最低水平线算法描述最早采用的矩形件排样策略为 等人提出的 算法。该算法实现简单,但因其最下最左的排样逻辑,使其存在无法合理利用排样凹槽处空白区域及容易
6、发生矩形件排样后左侧偏高等问题。提出了一种改进的 算法,可利用排样产生的空白区域,取得较好的排样效果,但是由于其时间复杂度过高,无法广泛应用。临界多边形算法 虽然在求解不规则多边形排样方面具有优势,但同样存在实现难度较大、复杂度较高等问题。本文采用文献 提出的最低水平线启发式排样算法进行解码。对于按排样顺序编码为,的个矩形件,其采用最低水平线法解码的排样过程如图所示。图中,序号序号代表矩形件排入的最低水平线优先顺序。图最低水平线法实现矩形件排样过程针对传统最低水平线算法无法处理工程应用中板材含缺陷时的排样问题,本文提出了一种适用于含缺陷板材排样的缺陷约束最低水平线排样算法。其本质在于将存在缺陷
7、近似为矩形,在排样之李志华等:基于双种群遗传算法的含缺陷矩形件排样优化研究研究与设计前,引入缺陷的位置与尺寸信息,将板材的缺陷部分视作排样位置固定的已排矩形件,在每一矩形件排入的过程中,需针对存在缺陷进行约束判断,使排入的矩形件与所有缺陷均不重叠,从而达到在含缺陷板材中进行排样的目的。然而,如图 及图 所示,矩形件在段可排入的水平线位置上均存在与板材缺陷 重叠的问题。按照算法的判断逻辑,此时无可供排样的位置,会被直接跳过。这样就导致算法在解码时出现矩形件丢失,无法排样完全的情况。本文改进算法读取缺陷矩形轮廓信息,并将之与排样矩形轮廓线信息更新集合合并。如此,在发生上述情况时,排样水平线位置就会
8、提升至缺陷矩形上边缘,如图 所示,防止了矩形件因无处可排而导致解码时丢失。图含缺陷板材矩形件排样示意改进后的缺陷约束最低水平线排样算法流程如图所示,具体步骤如下:图缺陷约束最低水平线算法流程 读取当前矩形件的尺寸信息,若编码为,矩形件不旋转;若为,矩形件旋转 ,宽高值互换。初始化排样起始点以及排样矩形轮廓线集合,设置变量。若存在缺陷,将缺陷矩形的轮廓信息合并入排样矩形轮廓线集合中,跳转至下一步;否则,直接跳转至步骤。对矩形件进行约束判断,直至其处于不超出板材宽度边界,且不与缺陷矩形重合的水平线相应排放位置上,跳转至下一步。对矩形件进行约束判断,直至其处于不超出板材宽度边界,且不与之前已排入的矩
9、形件重合的水平线相应排放位置上,跳转至下一步。完成当前矩形件的排样后,对于含缺陷的板材,重复执行步骤及步骤操作直至所有矩形件完成排样;对于无缺陷的板材,重复执行步骤操作直至所有矩形件完成排样。基于 的排样顺序优化 是一种鲁棒性较强的具备全局优化搜索能力的智能算法,适用于对较大规模的组合优化问题求解 。然而,经典存在着收敛过早、搜索效率较低等缺点。本文针对矩形件排样问题从以下方面对经典进行改进:首先,将影响矩形件排样的个关键因素,即排放顺序与旋转方式划分为个种群,分别进行遗传迭代,提高全局搜索能力;其次,改变初始种群生成策略,按照矩形件面积降序排列,及每个矩形件均不旋转的方式分别生成个初始种群的
10、前半部分。由经典生成初始种群的方式分别对个种群的后半部分随机生成。如此,既能保证初始种群的多样性,也使其具备较好的稳定性。个体编码及解码方式本文将需要进行排样优化的矩形件按照排样顺序和摆放角度划分为 和这个种群,使不同种群均有独立的变异、交叉方法与概率,从而提高随机性,增强算法的全局搜索能力。其中,种群表征矩形件序号,采用十进制编码方式;种群因只需表征排样矩形在和 间的旋转状态,故采用二进制编码即可,其中编码代表不旋转,编码代表矩形件 旋转。在每次迭代的交叉变异操作完成后,使种群 中每条染色体内的排样顺序编号与种群 染色体中的摆放角度按序一一对应。将编码结果采用最低水平线缺陷约束算法排样策略进
11、行运算解码,若种群中的序号对应种群中的编码为,与当前序号对应的矩形件不旋转。若对应编码为,则当前序号对应矩形件旋转 。输出本次迭代矩形件 ()排样结束后外轮廓线的最高水平线高度用于进行适应度计算。适应度函数建立通常在 中需要建立适应度函数对可行解进行评估。对于普通矩形件排样问题而言,可通过式()反映可行解的优劣。但对于表面含有缺陷的板材,由于缺陷面积的存在,无法直接应用上述的适应度函数评估问题的解。针对该情况,本文采用去除缺陷矩形面积后的板材利用率作为 的适应度函数,即()为板材内所有缺陷矩形面积之和,即()为板材上缺陷个数;与分别为缺陷矩形的宽度与高度。适应度函数取值区间范围为(,数值越大表
12、示板材利用率越高,排样效果越好。初始种群生成策略在人工排样的过程中,采取先排放大矩形后排放小矩形的方法,往往会取得较为不错的排样效果。其原因在于:小矩形件比大矩形件具有更好的排样灵活性。先排放大矩形件,排放产生的空白区域可由后续排放的小矩形件进行填充,一定程度上可以提高板材的利用率。本文结合上述分析,分别生成规模均为的、初始种群。对于种群的前部分,将矩形件按面积降序排列;后部分随机排序。对于种群的前部分,令各矩形件不旋转,即编码均为;而后部分随机旋转。其优点在于,既可以在初始时即获得板材利用率较高的个体,加速算法的搜索、收敛速度和寻优能力,同时也增强了初始种群多样性,使算法可跳出局部最优。遗传
13、算子描述 交叉操作种群 的交叉方式采用单点交叉,交叉概率为,将父代种群中的染色体两两进行随机配对,并随机在染色体上取一点断开,进行基因片段的交换。但由于种群采取的是十进制编码方式,故可能造成基因片段交叉后与交叉对象染色体另一部分的编码重复,导致解码时部分排样矩形重复或消失。因此,需要对种群交叉部分的基因逐个进行循环判断,将重复的部分与交叉片段对应位置的序号编码互换,再进行基因的交叉替换,直至循环结束,并在另一条染色体上执行相同操作。由于种群的染色体采取的编码方式为二进制编码,因此直接进行基因片段的单点交叉操作即可,交叉概率同样为。变异操作由于种群 的染色体采用十进制编码,每个基因都代表着独立而
14、不重复的待排矩形件序号。直接在变异时改变基因本身显然是不合理的。因此,种群 变异方法如下所述:对所有染色体生成其相对应的的随机数,选取随机数小于排样顺序变异概率的染色体。在被选中的染色体中随机生成个变异点,将其划分为个基因片段。将第、个基因片段交换位置,即视为完成变异操作。对于种群则可对所有染色体生成的随机数,选取小于旋转变异概率 的染色体,在染色体上随机选取基因进行与间的变异。选择操作用改进的缺陷约束最低水平线算法对子代种群的个个体进行排样求解,并分别对其适应度进行计算。若该子代的最高适应度值大于父代,则选择子代种群,替换其父代种群作为下一代的父代;否则,证明当前父代演化不完全,继续将其作为
15、下一代的父代种群进行演化。当达到设定的迭代次数后,停止计算,输出本次计算适应度最优的解。算法流程如图所示。图 算法流程算例测试分析为验证本文算法对于矩形件在含缺陷板材上进行优化排样的可行性及有效性,本文选取了组自定义待排矩形件,针对无缺陷及含种缺陷、种缺陷、李志华等:基于双种群遗传算法的含缺陷矩形件排样优化研究研究与设计种缺陷的种不同板材进行了算例测试分析。算例中各项参数均为无量纲参数:设定板材宽度为 ,算法最大迭代次数为 ,算法初始种群规模大小,交叉概率.,排样顺序变异概率.,摆放角度变异概率 ,算法均使用 编程实现。算例中,矩形件尺寸与数量信息如表所示,板材缺陷位置与尺寸信息如表所示。图运
16、算算例在种不同板材上的排样结果表矩形件排样求解算例序号宽高个数 表板材表面缺陷集缺陷序号缺陷起始点横坐标缺陷起始点纵坐标缺陷宽缺陷高 采用缺陷约束最低水平线算法,并分别结合 及对算例进行 次独立运算,算例运算测试结果如表所示。表中,表示种算法对排样顺序优化后,矩形件在种板材上 次独立运算中最佳板材利用率的差值;表示种算法对排样顺序优化后,矩形件在种板材上 次独立运算板材利用率的平均值差值。表算例运算测试结果板材缺陷数量最优利用率 最优利用率 利用率的平均值 利用率的平均值 无 种 种 种 由表可知,本文算法对种板材的最优利用率 可 分 别 达 到 、和 。矩形件在种板材上的最优排样结果如图所示,图中黑色阴影部分为板材中存在的缺陷部分。用 与分别结合缺陷约束最低水平线算法对矩形件排样优化分析,种板材的板材利用率最优排样结果如图所示。结合表的实验数据与图的曲线对比可以看出,可有效避免算法早熟,并能在搜索停滞后跳出局部最优解,全局寻优能力和搜索效率更强。多次运算求解得到的最优 板材 利 用 率 及 平均板材利 用 率 全 面 优 于,最优利用率及利用率平均值的最大差值分别达到 与 ,对矩形件