遗传算法在风管制造排样中的应用

陈洁琼，樊留群，杨 剑

（同济大学 中德学院，上海 201804）

遗传算法在风管制造排样中的应用

陈洁琼，樊留群，杨 剑

（同济大学 中德学院，上海 201804）

针对风管制造下料的排样问题，结合包络矩形算法、空余面积扫描算法和遗传算法应用，对零件进行旋转拼接、碰靠处理，提高原材料的利用率。改进了遗传算法的设计编码和适应度值，保证整条风管生产线的生产效率和连续性。设计了排样程序并进行仿真，结果表明了所提出的算法具有可行性与有效性。

风管；包络矩形；空余面积扫描；遗传算法

0 引言

风管生产工序包括：1.卷料自动送料；2.校平、压筋；3.冲角；4.切断；5.传输；6.咬口；7.共板法兰成型；8.折弯成型。材料的利用率是下料工艺中要考虑的一个重要问题。排样方法直接影响材料利用率、零件的精度和加工效率。因此，高效、优良的排样技术是风管零件制造中的关键技术之一。利用BIM技术，在风管成型软件中，将三维立体风管模型进行数字化处理[1]，拆解成二维平面的零件图纸，形成与排样系统可通讯的CAM信息，并完成自动化排样、生成数控加工代码的过程，将大大减少因人工干预而形成的效率降低和误差增多现象，并将对降低人工成本、提高产品质量起到根本性作用。

排样问题可以描述为在一定的板材上，对给定形状和数量的风管零件进行排布，保证这些零件互不干涉、重叠，且都不超出排样区域外。同时要确保材料利用率尽可能高。由于风管在拆分后，大量的零件属于二维不规则件，所以不同零件之间的靠接、判交等运算比较复杂，计算量大，加上排样次序组合的变化、旋转角度的改变都会生成不同的排样方案。从计算复杂度上看，这个属于NP完全问题。因此长期以来，国内外众多学者都有通过各种方法对这个问题进行了大量的研究，提出了一些解决方法。从当前的研究求解方法归总起来，针对规模较大的问题，采用启发式算法求解是比较常用的方法，比较经典的启发式算法有BL算法及其改进的BLF算法；孙波、李粉利、刘璐[2]等设计了利用剩余矩形排样算法对二维矩形件排样问题进行了优化，并利用遗传算法进行排样求解；谢友宝[3]等人设计了结合遗传算法和模拟退火算法的混合算法求解了在飞机钣金零件排样中的问题。由上述可知，性能稳定的遗传算法被应用的最为广泛成熟，并且在许多复杂优化问题中，都可以得到较为满意的解。

本文旨在对拆分后的风管零件进行排样，对现有风管成型软件中存在排样方案过于简单的问题进行优化，对二维不规则零件采用包络法的预处理，利用空余面积扫描法，并结合遗传算法，提出一个有效且具有实际应用价值的求解二维不规则零件排样优化的方法，以提高风管制造材料的利用率。

1 改进的优化排样算法

针对矩形件排样算法，目前提出的排样数学模型[4]已经非常成熟，因此本文就不再赘述。本文提出的算法优化主要是：1）对二维不规则零件的矩形包络处理；2）多块且长宽有限的板材排样问题；3）考虑到排样下料切割板材后要对零件进行风管成型加工，同一编号风管的零部件放在邻近的板材上进行排样，优化了评价指标。包络矩形算法，在处理二维不规则零件排样上运用广泛且实用性较高，空余面积扫描算法与传统的BL排样算法、下台阶排样算法、最低水平线排样算法相比有着较强的局部优化性能，而遗传算法在全局寻优搜索方面的性能较好，将三者结合使用，能更加有效的解决风管零件的排样优化问题，据此来寻找最优的排样方案。图1是整个排样算法流程图。

1.1 零件预处理

目前风管零件类型有很多，图2中列举出了几种常见的风管类型和拆分后的零部件。

图1 排样流程图

图2 常见的风管类型及拆分零部件详图

最小包络矩形算法是一种常用的处理二维不规则零件排样优化的方法。这种算法的思想就是：利用图形识别、图形处理技术，在排样的初始阶段，根据二维不规则零件的形状进行相应处理，将零件处理成近似矩形的排样单元，并以此为基础对近似成矩形的二维不规则零件在原材料板材上进行合理的排放，从而获得全局的近似最优排样方案[5]。

对不规则风管零件各边进行矩形包络，并将形成包络矩形后的风管零件面积通过比较风管零件面积与包络后的矩形面积比值，选择面积最小的包络矩形作为排样方案中的待选零件集。设置一个最小包络率，筛选出待选零件集中小于该包络率的不规则风管零件，对其进行图形拼接与碰靠组合。

对不规则零件首先进行图形旋转拼接与碰靠进行组合后，再进行矩形包络。以R接头的两个零部件举例说明，如图3所示。

图3 R接头零部件拼接组合包络

R接头完成拼接与碰靠组合后进行的矩形包络，明显比单个零件进行包络所占用的面积要小。当所需排样的所有风管零件都生成最小包络矩形后，不规则风管零件的排样问题就转化为标准的矩形件排样问题。

1.2 个体编码设计

对于采用空余面积扫描法的排样算法，决定最终排样方案的是各个零件排到板材上的顺序以及零件放置的角度。而由于零件采用最小包络矩形进行了预处理，因此零件的放入角度只有横放和竖放两种情况。最终决定采用三层染色体编码作为遗传算法的编码方案。

图4 编码方式

在该编码方案中，第一层染色体的数字代表着零件的顺序，第二层染色体的数字代表所属风管编号，第三层染色体的数字代表组成第二层中风管的零件编号，而正负号代表零件的放入方向，正号代表横放，负号代表竖放。例如，当一个染色体的编码为{-41，32，21，-12，43}时，代表着编号4风管序号为1的零部件，编号3风管的序号为2的零部件，编号2风管的序号为1的零部件，编号1风管的序号为2的零部件，编号4风管的序号为3的零部件按照12345的顺序放入板材。其中41和12零件为竖放，23、34、43号零件为横放。

图5 样片染色体三层编码方法

这样，染色体就与排样结果之间就形成了一一对应的关系。通过对染色体组成的种群进行择优、交叉、变异的操作，最终得到最优个体，也就得到了最优的排样方案。

1.3 排样定位方法

空余面积扫描算法是基于剩余矩形排样算法提出的一种排样算法。剩余矩形排样算法在计算时，是统计板材上所有未被利用的剩余空白矩形区域，将待排矩形件插入到剩余的空白矩形面积，能有效的提高板材的利用率。而本文所使用的空余面积扫描算法是将板材中的剩余空白区域算为一个数据集。每一个待排入的矩形件都要根据这个剩余空白区域数据集记录的位置来选择一个合理的位置排放。设一组经过最小包络法预处理的风管零件的排样序列Pi（i=1，2，3，…，n）

空余面积扫描算法的具体步骤为：

1）设置初始剩余空白区域数据集为整个板材。

2）成功排入矩形件Pi-1后更新剩余空白区域数据集，为矩形件Pi的排入做准备。

3）矩形件Pi在排入时，先选择空白区域数据集中最左下的点进行尝试，将矩形件Pi的左下角顶点与空白区域最左下的点（x，y）重合，在此点坐标（x，y）上加个矩形件Pi的wi和hi值，得到坐标（x+wi，y+hi），通过与空白区域数据集的长宽坐标点对比，若均不超出空白数据集的长宽坐标点，则将该矩形件排入。如果不能排入，则将空白区域最左下的坐标点（x，y）在X轴、Y轴方向上各加一个步进值，重新尝试排入。

4）当矩形件Pi在排入板材Ri时，在该块板材中的所有空白区域数据集中都无法将该矩形件排入，则将该矩形件排入板材Ri+1中。

5）重复上述步骤，直到将所有矩形件全部排入板材中为止。

1.4 评价指标

在该问题中所要优化的目标函数为F=H，即要使排样后所有零件占用板材的总体高度H最小，另一个就是同编号的风管零件要求排放在邻近的板材上，以每三块板材进行筛选，统计种群中个体里能完整组成同编号风管的染色体数量，数值越高的个体，适应度函数越高。而在遗传算法中，适应度函数代表着个体适应选择的能力，适应度函数越高，则个体越容易在选择中留存下来。故选取适应度函数Ffitness=1/H。这样个体对应的排样方案中零件所占的高度H越小，个体的适应度函数就越高。

在按评价指标择优后，上一代种群中的个体需要通过选择、交叉、变异三个过程来产生下一代种群。

2 实例应用

本文的算法主要将应用于风管制造数控下料切割软件系统中，系统运用C#语言在Visual Studio中编程设计系统，结合上述三种算法排样，以三种规格风管BIM模型为例，进行排样应用，最终生成可视化PDF格式的风管零件排样图纸，以及其对应NC代码的CNC格式文件，并且将每次排样的运算时间，零件编号、左下角坐标值以及最佳适应度值输出在txt格式文本文件。为了测试本文中使用的算法的有效性，对此进行了实例排样验证，最终用以解决风管制造数控下料的排样问题。

算例：测试排样数据如下：板材的尺寸为2000mm×1500mm，利用Visual Studio设计的系统UI界面总共包括了三个部分：

1）算法排样区：该区域设有“读取数据”按钮，在后台代码中添加了读取零件坐标值和尺寸，并且对拆分的风管零件进行最小包络法预处理的功能。“开始排序”按钮则是对获取的零件，通过空余面积扫描法和遗传算法的混合算法，进行排样处理，最终获取各零件在板材中的坐标值，并在后台导出各点坐标值的文本文件，为后续生成切割所用NC代码做准备。排样进度条的作用可以使用户对排样算法时间有个直观的了解，在后台的文本中，对每次排样的运算时间也有相应的记录，该算法经多次运算测试，在代数为50代的情况下，运算时间稳定在5s～10s之间。

2）展示区：在该区域中显示出最终排样结果的图纸，用于检验排样算法的有效性，令整个排样结果可视化，并且保存成PDF的文件格式，供用户打印阅览。

3）工艺区：调用后台产生的坐标值文本文件，根据项目风管制造商所使用设备的ACL控制器代码标准，显示数控下料切割系统可直接读取运行的NC代码。并保存成CNC文件格式，直接可以利用U盘等数据传输工具，导入数控下料切割系统中运行。

【】【】

图6展示了测试排样零件最终的排样结果和切割用NC代码。

图6 排样实例展示图

3 结束语

本文的排样方法是使用包络矩形处理，将不规则风管零件包络成矩形进行排样，并且结合空余面积扫描算法的局部优化特点和遗传算法全局搜索的优点，进行排样处理，取得了理想的结果。并最终将该算法成功应用到风管零件排样中。与现有的风管排样方式比较，提高了风管板材的原材料利用率，也提高了风管生产的效率，降低了成本，对风管制造生产有着一定的实际应用价值。

[1] 贺明玄,沈峰.基于BIM的钢结构数字化制造[A].2014年中国钢结构行业大会论文集[C].2014,10：121-136.

[2] 孙波.钣金件剩余矩形排样遗传优化方法研究[J].西安工业大学学报,2015,35(4)：287-292.

[3] 谢友宝,罗婷婷,李凌辉,吕永海.混合遗传算法在飞机钣金零件排样中的应用[J].机械与电子,2009,(12)：18-21.

[4] 杨卫波.基于遗传模拟退火算法的矩形件优化排样[J].计算机工程与应用,2016,52(7)：259-263.

[5] 卢齐飞,唐平,张光富,包梦华.改进的遗传算法优化二维不规则图形排样[J].计算机工程与设计,2013,34(4)：1409-1414.

Genetic algorithm application in air duct sheet metal parts layout

CHEN Jie-qiong, FAN Liu-qun, YANG Jian

TP391

：A

：1009-0134(2017)05-0113-04

2017-02-09

陈洁琼（1991 -），女，浙江杭州人，硕士研究生，研究方向为自动化生产线。