基于知识进化与自然进化的优化排样算法研究

包梦华，唐 平，朱章松，卢齐飞

（广东工业大学 自动化学院，广东 广州510006）

0 引 言

优化排样算法是指根据零件的特征设计一种算法，将规则或是不规则的零件按照算法的要求尽可能紧密的排放在一起，知识进化和自然进化是算法设计的依据。同时要求排样过程中零件必须排放在板材内，各个零件互不叠加，并满足一定的工艺要求，使板材的利用率最高。

20世纪末期，随着遗传算法的成熟，许多学者开始将它应用于零件排样中，取得了一些显著成果。遗传算法是模拟自然进化的一种全局搜索算法，具有简单实用、鲁棒性强的优点，但是具体运用中还存在一些不足。例如文献［1］、文献 ［2］都是运用常见的 “轮盘赌”选择，随机性太强。文献 ［3］利用遗传算法和碰撞算法混合求解冲裁件自动优化排样，碰撞算法可以大大提高板材的利用率，同时也大幅提高时间复杂度。文献 ［4］针对大规模零件和不规则石材下料优化排样问题，提出了改进的遗传算法优化排样方法，提出了基于材料利用率、排样图的高度和排布最高点中最左边顶点的x坐标3个因素结合的适应度函数，将适应度函数的考虑因素大大扩展，有效地提高了算法的搜索效率，本文在此基础上又添加了一个考虑因素——零件排样后的图形重心，使排样结果更尽如人意。上述工作都是为了提高板材利用率而忽视了时间复杂度，过分的强调板材利用率的提高并不能弥补时间复杂度带来的损失，所以本文换了一种思维方式，在保证板材利用率不降低的情况下，大幅降低时间复杂度，借助时间的急剧缩短，提高整体排样的效率。

本文基于提高不规则零件排样效率的考虑，提出了基于知识进化与自然进化的优化排样算法。该算法的重点是大大提高选择速度，利用知识规则和适应度函数相结合的选择方法，同时采用重心最低的排样策略。实验数据分析得出：该算法不仅提高了板材利用率，还大大降低了算法的时间复杂度。

一是零件数量较大时；二是零件的形状比较复杂，不能完全归类时，都会延长计算时间，排样的利用率也会随之降低。从这两个方面着手，以期达到提高排样效率的目的。

1 知识进化中规则建立原则

知识规则的建立是降低时间复杂度的一个重要方法，将所有的零件先按照知识规则进行筛选，可以有效地避免对不符合要求的零件进行多余的操作，浪费时间。

知识进化的规则包括：零件边界判定、板材利用率判定和零件重叠判定。每次首先用知识规则对零件进行初步选择，同时符合知识进化3个规则的零件接受适应度函数的第二次选择。

（1）判断零件的边界是否都处于板材内部，选择边界不超过板材边界或是与板材边界重合的零件。

图1可知，零件在板材内部的分布情况有：

1）在板材内部且不与板材相交；

2）在板材内部，与板材边界有交点。

图1 零件是否在板材内部的判断

通过比较线条：A、B、C、D 和E，可得出结论：通过任意横坐标画一条垂直线与板材有两个任意交点M、N 与零件有两个任意交点P 、K，P、K 到原点的距离大小总是大于板材上的纵坐标最大的点M 到原点的距离并且小于板材上纵坐标最小点N 到原点的距离。板材上4个点的关系符合式（1），可以判断零件边界没有超过在板材边界

其中，m、n为处于板材左右边界之间的任意自然数，p≤y2≤k，xi为任意横坐标，ym为垂直线与板材相交时纵坐标最大的交点的纵坐标，yn为垂直线与板材相交时纵坐标最小的交点的纵坐标，y2为垂直线与零件相交时的交点的纵坐标。

（2）判断零件是否重叠

利用像素格式的位图进行零件之间的重叠检测，首先将零件用像素格式的位图表现出来，如图2所示， “1”代表此处有零件覆盖， “0”代表此处没有零件覆盖。图2中的 “1”像素表达了一个不规则四边形的零件。

图2 像素格式表达的零件

假如两个或是多个零件都覆盖了相同的像素格，就是两个或是多个零件在相同的像素格上都表现出 “1”，就说明零件发生了重叠。运用像素格式来检测零件还是很比较节省时间的，首要条件是将矢量图转换成像素格式的位图。

在用像素格式的位图进行重叠检测时，像素格过大，检测结果不准备；像素格过小，势必增加算法的事件复杂度和空间复杂度。在实际划分像素格时，会出现一些意想不到的情况：两个多边形并不相交，但是由于另个多边形占据了同一个像素格，根据像素格格判断法的定义，两个多边形就是被判为相交。假如网格划分的足够精细，则可以判断两个多边形并不重叠。

判断像素格内两个多边形是否重叠，可以利用查漏补缺法对重叠情况进行检测。这样就不用对所有的像素格都进行更细的划分，只需要对无法判断的像素格进行细分即可，从而减少时间复杂度。像素格细分精度不够的情况下，如图3所示。

图3 像素格细分精度不够的情况下

（3）计算排样零件的面积和占板材总面积的比例 （板材利用率），比例超过50%的排样群体作为子代。

计算零件和板材的面积：给出各个多边形的顶点坐标，利用顶点来求多边形的面积，进而通过多边形的面积计算板材的利用率。任何多边形的面积可以分割成几个三角形面积之和来求得，通过多边形各顶点坐标可以求得各边长，再采用海伦公式，计算分割后的小三角形的面积。

海伦公式如下：

假设有一个三角形，边长分别为a，b，c，三角形的面积S 可有以下公式求得

对于复杂的多边形由于顶点很多，划分成小的三角形不是很方便，所以可直接采用多边形顶点计算多边形的面积。假设多边形的顶点按顺时针排序，利用下面公式计算复杂多边形的面积

在式 （3）中，Xn＋1＝X1，Yn＋1＝Y1。在 式 （4）中，X0＝Xn，Y0＝Yn。从式 （3）和式 （4）可以看出，多边形的面积等于相邻两个顶点纵横坐标交叉乘积。

综上所述：同时满足知识进化 （1）（2）（3）这3个规则的零件，相当于通过了第一次选择，然后利用适应度函数进行第二次选择，经过两次选择后达标的零件进入自然进化过程。

2 知识进化和自然进化相结合的排样优化算法

遗传算法是模拟生物在自然环境中的遗传和进化过程形成的一种全局优化概率搜索算法。针对传统的遗传算法更擅长全局搜索而局部搜索能力却不足的问题提出了基于知识进化的改进遗传算法，在遗传算法进行子代选择的过程中加入知识规则，大大提高选择的效率。

基于知识进化和自然进化的算法首先通过知识规则和适应度函数相结合的选择方法对零件进行选择，然后将交叉、变异等操作算子作用于整个进化群体，在设定的循环代数中得到问题的最优解或近似最优解。图4为改进遗传算法的基本流程图。

2.1 图形重心适应度函数设计

适应度函数 （fitness function）是遗传算法进行选择过程中决定每个染色体能不能进入下代循环的重要依据。染色体的适应度值越大，在遗传操作中就更有可能被选中。

一般按下面一些要求设计：单值性、非负性、连续性、单调性；适用性强，可处理性好；充分显示每个个体优势。

在零件排样过程中，板材的利用率、零件排样的高度、整体布局的重心都是我们在设计适应度函数时应该注意的，综上所述，设计出同时包含3个主要优化条件的适应度函数f（x）

图4 基于知识进化和自然进化算法的流程

其中s（x）为板材利用率，g（x）为零件排样后的图形重心，h（x）为排样图的高度，w（x）为排布最高点中最左边顶点x 坐标，k，l，m，n 为权重，k＋l＋m＋n＝1取k＝0.5，l＝0.2，m＝0.2，n＝0.1。

2.2 混合编码方法

遗传算法在解决排样问题时，编码问题也是至关重要的一个环节。编码和遗传算法的排样效率有息息相关的联系，可靠的编码方法为后面的交叉、变异提供了高效运行的基础；不适合的编码方法对整个遗传算法的时间复杂度、运算效率、还有最后的解码工作都会带来很多不便之处。

一个适宜的编码方案往往是遗传算法的重要追求目标，但是不可能一个编码方案适合于任何情况，每个编码方案的设计都是与每个项目的背景有密切联系的，但是每个编码方案都符合这样的规则：将所有的排样结果表现为染色体的形式，所有的染色体就组成所谓的 “可行域”，每条染色体对应可行域中的一个解。考虑到零件的多样性和数量巨大，本文采用二进制与实数相结合的混合编码方法，不仅扩大了搜索范围而且提高了搜索的效率。

零件的形状可谓多种多样，如果只是像撒网一样将所有零件一拥而上进行排样，这些零件就会一个一个的进行归位，时间复杂度也会更高。为了便于零件能更快找到适合自己的最佳排样位置，减少匹配的过程，本文特将所有的零件按顶点的多少和位置大概分为4类：

（1）没有顶点的零件：圆，圆环。

（2）3个顶点的零件：三角形和扇形。

（3）4个及4个顶点以上的凸型零件。

（4）4个及4个顶点以上的凹型零件。

给每个零件分配一个编号，只是为了便于排样时区分不同的零件。零件在排样的过程中需要通过旋转确定适合的位置，我们将旋转的角度范围设为：0度到360度之间。但是为了减小零件之间的空隙，可以采用实数编码。何类图形用2位二进制数来表示，如圆为第 （1）类图形00，第（2）类图形01，第 （3）类图形10，第 （4）类图形为11。

2.3 具有知识规则的选择方法

适应度比例方法也被称为赌轮或蒙特卡罗选择是现阶段使用比较频繁的选择方法。本文选择方法的原理：利用知识规则选出的个体被选中的概率和其在群体中所表现的适应度值的大小成比例。

假设群体大小为n，知识规则选择出个体i （i≤n）的适应度为f＊i，则个体i被选取的概率表示为

分析式 （6）可知，如果适应度函数值越大，则个体被选中的机率越大；反之，如果适应度越小，则个体被选中的的机率也越小。确定出优秀排样个体或是排样个体的序列，作为精英基因保存。同时在后代中还要保存劣等基因，主要是指适应度低于设定值的基因个体。劣等零件的排样个体在后续的优化中一旦发现，及时将其否决。

2.4 两点交叉与变异

通过交叉和变异来增加个体的多样性是遗传算法的一个特点，交叉和变异可以避免算法因为个体的单调性而陷入局部最优。

采用三角形两点交叉的方法，图5所示首先将父代基因围城三角形的形状，然后选择任意两点作为交叉点，互相交换父代基因长度相同的部分，得到新的完整基因作为作为子代基因。

图5 三角形两点交叉

染色体的基因位 （x、y、β、h）中既包含有排样件序号的属性，X 轴平移距离x、Y 轴平移距离y、旋转角度β及幅度变换量h，因此这里将变异运算分成X 轴平移距离变异、Y 轴平移距离y 变异、旋转角度α变异、幅度变换量s变异4个子运算来进行。

遗传算法中交叉概率Pc和变异概率Pm是影响遗传算法行为和性能的关键因素，直接影响着遗传算法的收敛性和搜索效率，在本文中所采用的自适应遗传算法中Pc和Pm是能够随种群中个体的适应度自动改变的

其中fmax是每代种群中的个体的最大适应度；favg是每代种群适应度的平均值：f1每次进行交叉的个体中较大的适应度值；f 是即将要变异的个体的适应度；PcA＝0.8，PCb＝0.5，PmA＝0.09，PmB＝0.001。

2.5 最低重心排样策略

利用临界多边形找到零件重心的最低位置。具体步骤：将零件置于板材内部，利用几何图形的性质找到零件的重心，以重心为参考点，找出零件每旋转一个角度对应的临界多边形 （零件必须在板材内部旋转）在这些临界多边形上找到重心的最低位置，零件按最低位置对应的坐标和旋转角度进行排样，就是最佳排样位置。零件旋转变化范围：0－360°，可以较准确找出零件的最低重心位置。利用临界多边形找到零件最低重心，如图6所示。

图6 利用临界多边形找到零件最低重心

3 仿真与结果分析

（1）零件输入方法

在对零件进行排样前，必须考虑先将零件以图形的形式输入计算机中，利用零件的轮廓图对零件进行排样。顶点序列法、等距扫描法、网格拟合法是几种比较常用多边形零件表达方法。根据零件的复杂度可以选择适合的零件表达方法。

顶点序列法的具体步骤是，首先把图形各个顶点的坐标表示出来，然后将各个顶点坐标按一定的顺序排成一个队列，这个队列中的每个顶点都有自己对应的编码。如一个按顺时针方向编码的n 边形的各个顶点 （以横坐标最小的顶点作为起始顶点）依次为A、B、C……，这些顶点队列构成的图形，如图7所示。

图7 顶点序列法

顶点序列法主要是以一定的顺序将顶点搜集起来组成队列，不仅需要记录多边形的每个顶点还需要将这些顶点进行排序、编号。对于简单的多边形比较适合，顶点较多的多边形工作量就会大大提高。网格拟合法只能进行水平和垂直两个方向的移动，同时每个零件能移动的最小距离是一个网格的距离，存在误差。

等距扫描法采用间隔相等的水平线或是垂直线扫描零件，零件的轮廓与这些线条的交点集合就构成一个完整的零件图。这种方法比顶点序列法的工作量减少，比网格拟合法的移动距离更精确。所以本文采用等距扫描法来进行多边形的输入，如图8所示。

图8 等距扫描法

（2）试验中设种群数N 为10，进化代数Gm＝100，交叉概率Pc＝0.8，变异概率Pm＝0.1，总共进行2次实验。30个零件的基本信息见表1。两种算法进行排样的结果如图9，图10所示。

通过表2可知，基于知识进化的遗传算法和传统的遗传算法相比，虽然时间复杂度明显降低，但是板材利用率并不算高，而且与传统遗传算法相比提高不明显。

4 结束语

本文通过对不规则零件排样的研究，提出了一种基于知识进化的遗传算法来达到优化排样的目的。利用遗传算法排样时，板材利用率低，时间复杂度高，并且传统的选择方法随机性太强，针对这些难题我们采取知识进化规则和适应度函数相结合的选择方法。知识进化规则包括边界判定、板材占有率判定、零件重叠判定等，大大提高选择的速度。提出了重心最低的排样策略和等距扫描零件输入法，降低零件的排样和输入时间。通过实验，本文算法在处理大量不规则零件排样的问题上的时间复杂度明显降低，并且板材利用率和时间复杂度都超越了传统的遗传算法，但是本文的板材利用率并不理想，还有待进一步提高，知识规则的设计可能不是很全面，希望大家能够提供宝贵意见。

表1 30个零件的基本信息

表2 两种算法排样结果比较

［1］LI Chen，NING Hongyun.The improved genetic algorithm selection ［J］.Journal of Tianjin Polytechnic University，2008（12）：1－4 （in Chinese）.［李晨，宁红云.改进的遗传算法选择算子 ［J］.天津理工大学学报，2008 （12）：1－4.］

［2］MA Xuan，ZHANG Yalong.Based on the genetic algorithm of optimal layout of rectangular pieces of a mass ［J］.Journal of Intelligent Systems，2007，2 （5）：49－52 （in Chinese）.［马炫，张亚龙.基于遗传算法的大规模矩形件优化排样 ［J］.智能系统学报，2007，2 （5）：49－52.］

［3］ZHAO Zhiguo，LU Jun，JIA Lili.Genetic algorithm and collision algorithm automatic blanking pieces layout problem solving ［J］.Journal of Engineering Drawing，2008，9 （1）：38－42 （in Chinese）.［赵治国，卢军，贾俐俐.遗传算法和碰撞算法自动排样问题求解冲裁件［J］.工程图学报，2008，9 （1）：38－42.］

［4］LU Qifei，TANG Ping，ZHANG Guangfu，et al.The improved genetic algorithm to optimize two－dimensional irregular graphics layout［J］.Computer Engineering and Design，2013，34 （4）：1410－1414 （in Chinese）.［卢齐飞，唐平，张光富，等.改进的遗传算法优化二维不规则图形排样 ［J］.计算机工程与设计，2013，34 （4）：1410－1414.］

［5］LIU Huyao，HE Yuanjun.2D irregular nesting algorithm based on gravity center NFP ［J］.Chinese Mechanical Engineering，2007，18 （6）：723－731（in Chinese）.［刘胡瑶，何援军. 基于重心NFP 的不规则形状排样算法 ［J］.中国机械工程，2007，18 （6）：723－731.］

［6］TANG Jiangang，LIU Cong，ZHANG Lihong.Irregular shapes layout based on improved genetic algorithm ［J］.Computer Engineering，2010，36 （21）：185－187 （in Chinese）.［唐坚刚，刘从，张丽红.基于改进遗传算法的不规则图形排样［J］.计算机工程，2010，36 （21）：185－187.］

［7］LIANG Lidong，YE Jiawei.Research of irregular parts packing with genetic algorithm ［J］.Computer Engineering and Applications，2009，24 （2）：223－228 （in Chinese）.［梁利东，叶家伟.基于遗传算法的不规则件优化排样研究 ［J］.计算机工程与应用，2009，24 （2）：223－228.］

［8］MEI Ying.Hull construction plank out sample nesting system optimization algorithm and touch by technology research ［D］.Guangzhou：South China University of Technology，2010 （in Chinese）.［美颖.船体建造板材套料系统中排样优化算法与碰靠技术研究 ［D］.广州：华南理工大学，2010.］

［9］GU Zhenhua.Two－dimensional irregular layout CAD system design ［D］.Shanghai：Shanghai Jiao Tong University，2007（in Chinese）.［顾振 华.二维不规 则 排样CAD 系统的 设 计［D］.上海：上海交通大学，2007.］

［10］LIU Huyao.Based on the critical poly 2dlayout algorithm research ［D］.Shanghai：Shanghai Jiao Tong University，2007（in Chinese）.［刘胡瑶.基于临界多边形的二维排样算法研究［D］.上海：上海交通大学，2007.］

［11］HUANG Feng，QI Ji，TAN Ying，et al.A kind of genetic a discrete particle swarm optimization algorithmolving rectangular layout problem ［J］.Journal of Electronics，2012，40 （6）：1104－1106 （in Chinese）.［黄岚，齐季，谭颖，等.一种求解矩形排样问题的遗传一离散粒子群优化算法 ［J］.电子学报，2012，40 （6）：1104－1106.］

［12］WU Jun，ZHANG Jingjuan.Using genetic algorithm of multimachine free flight conflict free policy ［J］.Journal of Intelligent Systems，2013，8 （1）：1－5 （in Chinese）.［吴君，张京娟.采用遗传算法的多机自由飞行冲突解脱策略 ［J］.智能系统学报，2013，8 （1）：1－5.］