基于遗传算法的不规则钢构件排料问题

沈祎萍

摘 要：本文采用遗传算法结合临界多边形算法与凸包算法，设计了自助排料的流程，客观有效地提高了排样速度。

关键词：遗传算法；材料利用率

1 遗传算法求解不规则排料问题

1.1 染色體编码算法

假设k个零件的编号分别为P1，P2……Pi，k个零件要装入板材当中，需要说明的是，第一块板材不一定能容下所有的零件，很有可能只是排下其中的一部分，剩下的零件就放入下一块板材，各个零件Pi（i=1，2，……m）所放入板材中的编号顺序就构成了该问题的染色体编码。即我们使用的是等长的字符代码编码方法，而不采用通常的二进制编码方法，因为二进制编码方法不能较好的适用于该类组合优化问题。

1.2 目标函数和适应度函数

目标函数是指在排样过程中用于判定优化结果的计算式。排料的目标是用尽量少的板材排下尽量多的零件，并使板材的利用率最高。假设一共排放了m块板材，其中m块尚未排满，其余已经排满，每张板材的面积为S，第m块板材上零件的凸包面积为Sm，本文将目标函数设为

可见所用板材面积越小，则λ值越大，适应度越高。

2 对于不规则钢构件的排料问题

2.1 模型假设

（1）假设不考虑板材厚度影响；

（2）假设零件与零件之间靠接无损耗，不考虑人为因素使板料破损；

（3）假设不考虑零件不同部位切割工艺的不同。

2.2 模型建立与求解

已知：（单位：mm）L表示的是直线，L后边的4个数字分别表示直线两端点的坐标，板材：2380×1630（一张）

零件一（14个）【五边形板材】

零件二（14个）【六边形板材】

自动排料关键问题是在排料的过程中，如何找到排放零件的最佳位置（不重叠且利用率最高）。假设板材上已经排放了n个零件，如何找到排放第n+1个零件的最优位置，通常采用的是移动碰触检测法，不规则的零件视为多边形，具有有限个顶点（如表1）依据已知所得的不规则零件，根据第 n+1个零件的参考点，把第n+1零件排放在临界多边形的边上或顶点上就可以保证零件之间彼此相互接触，但是彼此之间不重叠。同时，大量研究表明，把零件的参考点排放在临界多边形的顶点上，可以达到利用率最高。

所以，临界多边形的求解具有重要意义，临界多边形构成了排料算法的核心算法。当求解得到两个多边形的临界多边形后，由于临界多边形具有多个顶点，仍然无法确定第n+1个零件放在哪个位置更优，所以通过求解两个多边形的凸包，然后计算一下每个顶点的利用率。利用率是已经摆放在板材上的零件和零件凸包面积之间的比值，选取比值大的保留。

临界多边形的计算只是针对两个多边形的计算，所以当在板材上摆放了一个新零件后，必须把板材上的多边形零件合成为一个多边形，为排放下一个零件做准备即合成多边形算法。同时，每个零件都可以旋转任意的角度，零件的排放角度直接影响板材的利用率，但是，我们无法也不可能对零件的每个角度都进行一次计算，通常我们取几个特殊的角度来计算，然后去一个最优的角度，在本文中，允许零件旋转90，180和270度。

自动排料算法如图2所示：

板材的利用率就是所有零件面积之和与在一刀切工艺后继续切割的那部分板材面积的比值。通过计算我们得到板材的利用率为：

2.3 结果分析

因此，在对多边形零件直接排样的研究讨论中，我们采用遗传算法结合临界多边形算法与凸包算法，设计了自助排料的流程，依据算法，最终得到板料的利用率最高为85.293%。

参考文献

[1]黄艳群，徐燕申.基于遗传算法的不規则零件近优板材排料[J].机械设计，2002，19（5）：33-35.

（作者单位：南京师范大学泰州学院）