药品纸质包装盒智能排样算法研究

杨志军 赵一临 郑哲 李方娟

摘  要：遗传算法通过模拟自然进化流程寻找最优解，全局搜索力量较强。将其运用于对药品纸质包装盒的排样环节，能够取得非常好的效果。文章在多边形扫描定位算法的基础之上，采用遗传算法进一步优化排样，降低了计算复杂度，减少了算法运行时间。实例分析表明，此算法在保证计算质量的同时，计算复杂度明显降低，适用于大规模药品纸质包装盒的排样。

关键词：遗传算法;扫描定位算法;纸盒;排样;智能

中图分类号：TP301.6       文献标识码：A文章编号：2096-4706（2021）22-0165-04

Abstract： Genetic algorithm seeks the optimal solution by simulating the natural evolution process， and has strong global search capabilities. It can achieve very good effect when it is applied to the layout of drug paper packaging boxes. Based on the polygon scanning and positioning algorithm， genetic algorithm is used to further optimize the layout， reduce the computational complexity and reduce the running time of the algorithm. The example analysis shows that this algorithm not only ensures the calculation quality， but also significantly reduces the calculation complexity. It is suitable for the layout of large-scale drug paper packaging boxes.

Keywords： genetic algorithm; scanning and positioning algorithm; paper packaging box; layout; intelligence

0  引  言

藥品纸质包装盒是药品生产中一项重要的成本，需求量越来越大。近年来，中国现代包装产业正逐步地向“绿色包装”这一条节资环保的道路上前行，而增加纸板使用率也是现代包装公司降低生产成本，增强产业竞争力的主要手段。药品纸质包装盒的平面展开图形都属于不规则多边形，纸盒的排样问题则属于典型的NP问题。随着计算机科学技术的不断发展，国内外许多学者对纸质包装盒排样问题进行了大量的研究。孙厚芳等人对各种型号冲裁件的预处理与智能排样等过程展开了深入研究，通过多边形与顶点射线方法的运用大大提高了加工材料的生产效率，同时也通过遗传模拟与退火计算的融合解决了顶点算法计算量大、费时多的问题，为不规则零件的排样优化提出了可靠易行的方法。然而，由于纸盒平面展开图的几何形状十分复杂且数量很多，增加了计算的复杂性，造成算法收敛速度慢，排样效率降低。如何改进算法以降低计算复杂度，提高纸盒排样效率（即提高材料利用率）是本文重点讨论的问题。

现代排样算法在追求排样最优解的同时，往往忽略了时间因素。排样计算过程中零件的判交和定位是比较耗时的工作，几何图形的复杂度是影响零件判交和定位的主要因素，本文在扫描定位算法的基础上采用遗传算法优化计算，使得几何复杂度并不会影响计算的繁简，从而简化运算过程，提高纸盒排样的效率。

1  纸盒排样数学模型建立

不规则多边形的优化排样系指把多个不规则的平面几何图形[1，2，…，n]放置于一个固定的长为a，宽为b的板材中（a≥b），通过寻找不同的摆放顺序实现板材利用率最大化，即通过寻找一个近似最优的排样顺序，使排样后的板料浪费量最少，从而达到节省材料的目的。本文针对多个二维不规则待排样件在同一样板中的排样建立数学模型。

约束条件为：

（1）e和f不能有重叠的部分，e∩f=ø;

（2）e、f∈R;

（3）使用贪心旋转算法在各个角度进行试探性摆放，取最优适应角度后，在摆放过程中应用BL思想。

e、f∈[1，n]为所有待排样件中的某一个样件;R为板材;条件（1）保证待排样件两两之间不会重叠;条件（2）保证排样完成后待排样件位于板材内。

板材的利用率可以用函数F（X）表示，每种排样顺序x，最高轮廓为f（x），如图1所示。

f（x）下方面积表示排样完成后所使用板材的面积，板材利用率可以表示为：

因此纸盒排样问题可以归纳为求minF（X）。函数F（X）的值越小，排列次序越优，板材利用率越高。

2  排样问题的求解

2.1  多边形扫描定位法

在纸盒排样的计算中，零件的判交和定位是算法收敛速度的主要影响因素，而零件的判交和定位由于受几何图形不规则性的影响而增加了算法的复杂性。因此，有必要寻求一种简便的判交和定位方法来降低计算的复杂度。本文对文献[2]中提出的多边形扫描定位方法进行改进延伸，可有效地解决上述问题。

2.1.1  零件与样板的几何表示

对于零件H，将其旋转α角度后，得到零件H（α），其在样板平面坐标系中横纵坐标的最大和最小值分别为Xmax、Xmin、Ymax、Ymin。系统使用0.5 mm的等间距水平直线扫描零件H（α）并计算扫描线与图形的交点所得到的线段。对某一水平直线的计算步骤为：

Step1：计算水平直线与零件各边的交点;

Step2：对得到的交点进行判断，决定取舍，若与零件的交点为局部极值点，算作两个交点;其余算作一个交点;

Step3：将得到的交点按递增顺序排序;

Step4：对于得到的交点，从第一个和第二个开始两两进行配对。

扫描最终图形如图2所示。

离散后得到的扫描线段实际上是由一对x坐标（x1，x2）构成的，只要判断不同x值的大小，便可知是否重叠。

2.1.2  算法过程

在零件的排样次序和旋转角度确定后，采用以下算法定位：

Step1：初始i=1，得到初始定位位置str（x，y）;

Step2：取H（α）上第i条扫描线，取样板上第（y+i）条扫描线;

Step3：对于Step2中H（α）所得到的扫描区间[sx1，sx2]不断更新，增加位移增量[sx1+x，sx2+x]。取Step2样板扫描区间[px1，px2]，若其与[sx1+x，sx2+x]有重叠，则H（α）向右移动△x=px2-（sx1+x）。将△x加入一个数组int[];

Step4：若P（α）在x方向上超过了矩形包围盒范围，则y=x+1，x=0，重新进行Step1;

Step5：检查int[]中元素的个数，若元素个数为0，则返回TRUE，表示H（α）可放在此区域，否则返回Step3中的最大值作为零件的offset值，同时返回FALSE，表示H（α）无法放到此区域，算法结束。

2.1.3  多边形扫描定位算法流程

在扫描算法开始前，应用贪心旋转算法寻求最优适应角度，之后进行零件的判交和定位，此算法设计流程图如图3所示。

此算法使用等距扫描线进行排样对象的表示，使其计算工作不受零件几何复杂度的影响。同时基于BL思想，计算过程简洁，能有效利用样板，获得较高的排样利用率。

2.2  改进的遗传算法优化排样策略

遗传算法优化的排样问题也是一个多参数的优化问题。通过不断变化的排列顺序使排列计算实现近似最优的估计求解，相较于其他计算，前者的全局搜索能力较强，从而减少陷入局部最优估计求解的可能性。遗传算法运用达尔文的“优胜劣汰，适者求生”原则，种群经过交叉和变异之后，一部分个体被挑选出来繁衍下一代群体，此过程称为选择过程。选择过程是基于适应度大小来完成优胜劣汰的，适应度高的个体更容易进入下一代，适应度低的个体则容易被淘汰，这样更有利于优良基因的扩展。在排样中通过人工方法对图像进行优化排序，排列过程中需要关注以下三点：

（1）确定编码方案。对于包含n个待排放零件的排样问题，可行解是由n个对象组成的序列，序列中的每个零件对象都包含排放顺序和旋转角度两个变量。将待排放的n个零件按照排放顺序编号，构成一个整数序列{X1，X2，…，Xn}，Xi为第i个排入板材的多边形零件编号，Oi为第i个零件排放时的旋转角度，1≤Xi≤n。每个可行解序列可以表示为：{（X1，O1），（X2，O2），…，（Xn，On）}，其中（Xi，Oi）表示编号为Xi的零件旋转Oi度后的排放。

（2）确定计算中的基本参数，如种群规模、计算执行最大代数、交叉概率、变异概率、最优秀个体的判定区间。

求解二维不规则排样问题时，所追求的目标是实现原材料利用率的最大化。由（1）可知，函数F（x）值越小，板材利用率越高，为使计算更加简便，本文定义适应度函数为：

故纸盒二维排样问题可归纳为求maxG（X），适应度函数越大，排样次序越优。

通过初始父代种群的生成、选择操作、交叉操作、变异操作、形成子代种群、演化迭代来寻求算法的最优解。

（3）计算停止执行的条件通常是，算法到达最大代数或者已经取得所期望的最优解。

本文应用遗传算法对多边形扫描算法进行优化计算，使得算法计算的繁简与零件的几何复杂度无关，从而缩短了判交和定位零件所消耗的时间，在一定程度上降低了计算复杂度。该算法流程如图4所示。

3  实例验证

对遗传算法优化的多边形扫描定位算法使用Java语言进行程序实现。以30个不同类型的药品纸质包装盒的排样为例进行验证，排样纸盒的数量和相应尺寸如表1所示。

本文实例设置种群数量为30，最大迭代次数为50次，交叉概率Pc=0.95，变异概率Pm=0.45，采用市场上较为常见的三种药品包装盒——对插嵌套式、旋转嵌套式、平铺式——进行排样研究，排样结果输出图如图5所示。

第一代种群的最优排样利用率为54.93%，第一百代种群的最优排样利用率为80.71%，算法执行时间为55 s。结果表明，本文算法与传统遗传算法相比，材料利用率提高了5%左右，算法执行时间明显降低，排样达到了预期效果。

4  结  论

通过多边形扫描定位算法与遗传算法的结合来解决不规则零件的排样问题满足了实际生产的需要，具有求解稳定、排样速度快、自动化程度高等优点。由于排样问题是复杂的组合优化问题，任何单一的算法都无法取得最优解，而通过多边形扫描定位算法与遗传算法相结合进行排样，取得了更加显著的排样效果。实例验证结果表明，它不仅大大提高了材料利用率，而且缩短了运算时间，将多边形扫描定位法与遗传算法相结合进行排样计算具有很好的应用前景，是目前药品中纸质包装盒排样问题研究的一个主要方向。

参考文献：

[1] 雷贺功，孙厚芳，刘汉雄.遗传模拟退火算法在冲裁件优化排样中的应用 [J].现代制造工程，2004（6）：55-57.

[2] 李文学.多约束二维排样算法研究与应用 [D].武汉：华中科技大学，2016.

[3] 宋亚男.邓飞其，叶家玮.基于改进免疫遗传算法的不规则图形排样 [J].计算机工程，2005（9）：170-172.

[4] 唐坚刚，刘丛，张丽红.基于改进遗传算法的不规则图形排样 [J].计算机工程，2010，36（21）：185-187.

[5] 王静静，瞿少成，李科林.一种基于并行交叉遗传算法的二维不规则排样问题求解[J].计算机应用与软件，2020，37（7）：188-193.

[6] 张立驰，李健.优化排样问题研究及其发展 [J].制造业自动化，2010，32（5）：95-96+196.

作者简介：杨志军（2000—），男，汉族，山西朔州人，本科在读，研究方向：制药工程与人工智能;郑哲（2000—），男，汉族，浙江绍兴人，本科在讀，研究方向：制药工程与人工智能;赵一临（2000—），女，满族，云南红河州人，本科在读，研究方向：制药工程与人工智能;通讯作者：李方娟（1978—），女，汉族，黑龙江绥化人，副教授，硕士，研究方向：制造技术与人工智能。