基于遗传算法的二维滑窗排样算法_二维排样_遗传算法

基于遗传算法的二维滑窗排样算法

2014/4/29 13:42:02

摘要：根据板材的整体情况，将板材抽象为框架，用点云形式表示，模拟板材之间、板材与边界的碰撞与约束，以滑窗的形式插入新的板材。并以遗传算法求解最佳插入方案。

关键词：二维排样遗传算法滑窗算法概述

二维不规则零件的排样问题就是将一系列形状各异的零件排放在给定的板材上，按最优方式找出零件的最优排布。要求零件排放在板材内，各个零件互不重叠，并满足一定的工艺要求，使得给定板材的利用率最高，以达到节约材料，提高效益的目的。二维排样技术广泛应用于钣金加工、轻工、服装和印刷业排版等行业中。对于材料利用率的提高可带来显著的经济效益，因此，研究零件在板材上的最优布局具有重要的现实意义。

传统二维排样算法通过不停排除最小包围矩形来计算剩余空间的多少，常要求被分割的原材料为矩形。对于不规则形状的原材料难以下手。

本文提出了一种通过点云来模拟空间的排布，来对不规则板材下的不同尺寸的矩形毛料进行排布，并通过遗传算法进行优化的算法，获得了较好的效果。

1. 算法流程

遗传算法的基因定位毛料的型号与摆放的方向。适应度函数为收益最大。其中，收益的计算来自于不同尺寸的每块毛料可以获得的收益之和。算法思路为：

Step 1:随机生成初始种群基因。该基因记载了按照顺序码放的毛料型号及横放或纵放

Step 2：载入墙体图片，其中黑色（0）代表无法安放毛料的位置，白色（255）代表可以安放毛料的位置。

Step 3：遍历全部基因，按照基因记载的码放方式依次码放毛料。码放时，以毛料为为模板进行匹配（搜索窗），从左至右，从上至下滑动窗口，直至搜索窗内的像素全部为白色（255），将对应毛料码放至此（将搜索窗内像素填充为黑色）。

Step 4：计算全部基因码放毛料后，所产生的总利润，作为该基因的适应度。若某基因适应度为当前最优，则记录。

Step 5：依据各基因适应度大小占全部基因适应度和的比例，计算对应基因被复制的概率，并依该概率进行复制。

Step 6：根据交配概率选出交配的基因组，进行交配，并依据突变概率进行突变。

Step 7：转至Step 3，循环流程。直至达到规定次数，结束循环并输出当前最优方案。

并且，实际编程中，由于上述流程计算量过大，运行时间过长，因此将原比例按照10毫米=1像素进行缩放，并且毛料以仅有外框和少量横竖轴线的骨架图代替实心色块进行匹配。优化后，程序的运行速度得到了大幅的提高，使得遗传算法的运行时间达到许可范围。编程实现

2. 实验结果

在core i5 cpu，2.53GHz，内存2GB的计算机上，程序运行时间约为300秒。

验证数据使用了太阳能小屋设计中光伏电池的最优铺设问题[9]的数据。该问题是一对墙体的太阳能电池板铺设问题，其中的墙体多为不规则图形，是本算法的一种较好的应用场景。

毛料的尺寸数据：

表 1 毛料数据表

毛料编号\数据宽高利润

C2 1321 711 265

C7 615 180 157

C10 818 355 178

图 1 板材1

图 2板材2

2.1. 验证结果

图 3板材1拍样

图 4 板材2拍样

由图 3、图 4可见，基于遗传算法的二维滑窗拍样对于特异板材的分割有良好的适应性，可以获得一个较好的拍样方案。

2.2. 比较

为了便于比较，使用了如图 5所示的板材和毛料。该板材大小为10100×8570 cm2，毛料大小为1482×992 cm2。根据人工计算，若横放可以码放6×8=48块，纵放可以码放10×5=50块。根据直观感受，这一板材难有更佳分割方式。然而本文的利用基于遗传算法的二维滑窗拍样却可以在该板材上码放51块毛料。（图 5所示）。这一结果充分证明了该拍样方法是有效的具有实际意义的拍样算法。

图 5算法拍样

3. 结论

基于遗传算法的二维滑窗排样结合了传统矩形优化排样算法和图像匹配算法的优点，可以有效的应对各种不规则情况下的排样问题，对空间利用率较高。且由于遗传算法的特性，该模型有希望得到全局最优解。模型采用了骨架化模板匹配对算法效率进行了优化，大幅提升了算法的运行效率。对比人工比较，可以达到更优的结果。

但是，由于滑窗匹配算法时间复杂度高的基本特性和遗传算法大运算量的特征，程序运行效率依然较低，限制了遗传算法的迭代次数和种群容量。且由于点云的性质本身，数据的精度和运算的速度无法同时保证。这是本算法还待改进的地方。

参考文献

1.韩喜君, 丁根宏. 矩形件优化排样问题的混合遗传算法求解[J]. 计算机技术与发展, 2006, 16(6): 219-221.

2.王晓庆. 基于层排样方式的矩形毛坯下料算法[D]. 广西师范大学, 2011.

3.郭俐, 崔耀东. 有约束单一尺寸矩形毛坯最优排样的拼合算法[J]. 农业机械学报, 2007, 38(10): 140-144.

4.曹炬, 周济. 矩形件排样优化的背包算法[J]. 中国机械工程, 1994, 5(2): 11-12.

5.黄红兵, 蒋望东. 二维不规则零件排样问题的研究[J]. 广西科学院学报, 2004, 20(4): 225-227.

6.李明, 宋成芳, 周泽魁. 一种二维不规则零件优化排样算法[J]. 四川大学学报 (工程科学版), 2005.

7.史俊友, 冯美贵. 二维不规则件优化排样的小生境遗传算法[J]. 工程设计学报, 2007, 14(2).