基于改进自适应遗传算法的异形标签排样

Irregular Label Packing Based on Improved Adaptive Genetic Algorithm

摘要: 针对二维异形标签人工排版费时费力费料的问题，提出了一种高效便捷的解决方案。首先，建立二维矩形带排样问题的数学模型，使用最低水平线算法作为排样定位算法。其次，通过自适应调整遗传算法中交换和变异的概率，平衡算法的收敛速度与种群多样性之间关系。实例验证表明该方案具有较强的可操作性，对异形标签的排样具有较大的应用价值。社会的发展推动技术更迭，异形标签的自动排样技术对于推动传统印刷产业升维，促进印刷产业在智能时代持续发展具有重要意义。

Abstract: In order to solve the problem of time-consuming and labor-intensive manual layout of two-dimensional irregular labels, an efficient and convenient solution is proposed. Firstly, the mathematical model of two-dimensional rectangular strip packing problem is established, and the lowest horizontal line algorithm is used as the packing location algorithm. Secondly, by adaptively adjusting the probability of exchange and mutation in the genetic algorithm, the relationship between the convergence speed of the algorithm and the population diversity was balanced. The example shows that the scheme has strong maneuverability and great application value for the layout of irregular labels. The development of society promotes the change of technology. The automatic packing technology of irregular labels is of great significance to promote the traditional printing industry and promote the sustainable development of the printing industry in the intelligent age.

1. 引言

产业的飞速发展也带动了相关技术的变革，当下数字印刷技术已经成为标签印刷的主流，数字或混合印刷方式已占总产值的1/3以上 [1] 。相比于传统的印刷技术，数字印刷过程简单、操作方便，对于中小型订单来说成本更低，可以满足现代人对于产品的实时性和个性化的需求。数字印刷技术的发展也使得标签印刷产业规模进一步扩大，仅固融印刷(上海)有限公司旺季一月的印刷量就超过了10万平方米 [2] 。由此可见，标签排版的优劣会对标签印刷产业原材料的节省起到至关重要的作用，此外，针对异形标签的智能排版也是传统印刷工业转向智能化发展过程中不过或缺的一环。

当下针对异形样品的排样问题最常见的方法就是NFP算法与群智能优化算法的结合。近年来不断有学者提出改进方法，其中Guo等 [3] [4] 针对二维不规则包装问题做了大量研究，综述了相关领域的最近进展，总结了典型二维不规则形状堆积问题的发展趋势和研究热点，为该领域的研究者提供了指导；此外，还提出了一种基于几何相似性特征搜索和模糊匹配的贪婪算法，来解决二维自由形状布局问题。Huang等 [5] 提出了一种基于自适应模糊并行遗传算法的弹药库布局优化算法，通过改进并联机构调整遗传操作并平衡种群的收敛速度和多样性，最终获得多种最优部署方案。

文中提出的一种基于改进自适应遗传算法的异形标签排样方案。通过自适应调节交叉概率和变异概率在保留优秀个体的前提下尽量避免了种群陷入局部最优，同时，将最低水平线算法作为排样定位算法，实现对异形标签的排样。

2. 算法设计

2.1. 问题分析

该方案针对异形标签排版问题采用最小包络矩形，将其转化为规则图形。规则图形排样问题要保证样品之间不重叠、不超出边界，文中所研究的异形标签打印问题属于二维矩形带排样问题，即在无限长的矩形带上以某种方法排列样品，在满足约束条件的情况下使其所使用的面积最小。其约束条件如下：

$\{\begin{array}{l}\min \left(Wi,Li\right)\le W0\le i\le n-1\\ {\theta }_i\in \left[0^{\circ },{90}^{\circ }\right]0\le i\le n-1\\ P_i\left({\theta }_i\right)\cap P_j\left({\theta }_j\right)=\varnothing 0\le i<j\le n-1\\ P_i\left({\theta }_i\right)\in C\left(W,L\right)0\le i\le n-1\end{array}$ (1)

其中W代表矩形带宽，Wi、Li分别代表第i个样品的宽高，θ_i代表第i个样的旋转角度，P_i(θ_i)代表第i个样品以角度θ_i旋转以后得到禁忌区域，P_j(θ_j)代表第j个样品以角度θ_j旋转以后得到禁忌区域，C(W,L)代表版型坐标区域。约束条件： $P_i\left({\theta }_i\right)\cap P_j\left({\theta }_j\right)=\varnothing$ 保证样品之间不重叠， $P_i\left({\theta }_i\right)\in C\left(W,L\right)$ 保证样品不会超出边界。

该方案的数学优化模型如下：

$\min S={\displaystyle \underset{0\le i\le n-1}{\sum }{P}_i\left(O_i\right)}$ (2)

其中minS代表最终所使用矩形带的面积，该方案的目标就是在保证异形标签排样效率的前提下，尽可能获取较小的minS。

2.2. 优化最低水平线算法

自贾志欣 [6] 提出最低水平线理论以后，在排样问题方面众多学者对其加以改进应用。如李志华等 [7] 提出基于缺陷约束的最低水平线算法通过更新缺陷矩形轮廓信息与引入缺陷位置约束判断，使矩形件在根据优化顺序排样时可避开缺陷部位；王巍等 [8] 在选择下一个待排样样品过程中使用边缘匹配算法进行寻找；张鹏程等 [9] 通过在排样过程中限制样品摆放的顺序和位置满足了单侧“一刀切”的需求。实践结果也证明，最低水平线算法在解决各类排样问题方面具有非常强大的实用价值，因此，文中选择使用最低水平线算法来解决异形标签的排版问题，并在原始算法的基础上进行了的优化。

原始的最低水平线算法虽然解决了BL等其他排样策略中容易出现的偏高问题，但是对于样品的排样顺序有较高的要求，否则会造成不必要的浪费。文中在原始最低水平线的基础上加入了旋转和向后搜索策略，使得排样结果摆脱了对样品顺序的依赖，减少了最低水平线提升的次数。

修改后的步骤如下：

Step1. 初始化禁忌区域E，获取E中最低水平线信息，记作Lowest_Line。如果有多段，选择最左侧的线段；

Step2. 更新Lowest_Line；根据最低水平线信息，从待排样样品集合中，按顺序从前往后选择出可以排入当前最低水平线的样品Sample_Iter。如果都不可排入，则提升当前最低水平线，然后再次执行Step2；

Step3. 根据当前样品信息和最低水平线信息更新禁忌区域E。如果当前样品的宽大于最低水平线的长度，则将其顺时针旋转90°再排放，否则直接排放；

Step4. 去除E中因对齐所产生的长度为0的线段，跳转Step2，直到排完所有样品。

2.3. 改进自适应遗传算法

遗传算法可以自动寻找较优解空间，但是当个体之间差距非常小的时候，算法容易陷入局部最优解。为了避免遗传算法过早收敛陷入局部最优，文中采用自适应遗传算法，根据每代种群中最优个体适应度与整体平均适应度来调节交叉概率和变异概率，具体过程如下。

2.3.1. 个体编码

该方案采用包络矩形处理所有样品，并且只考虑0˚和90˚旋转。其中正数代表0˚，负数代表90˚。例如(−3, 5, 7, −1, 4, −6, 2)代表3、1、6号样品在排样过程中需要顺时针旋转90˚。

2.3.2. 改进自适应交叉概率

根据生物学中的杂交理论，两个优秀的个体结合所产生的后代更具有优势，据此提出了改进的自适应交叉概率。将两个待交叉个体的适应度之差比上种群最优个体和最差个体之差，结果记为Kc，代表当前待交叉个体之间的差距。

遗传算法在进化过程中其种群个体适应度差异较小，进化后期多数个体集中在0.75~0.95之间。以往学者提出的自适应交叉概率变化较小，不能很好地帮助种群跳出局部最优解，文中通过Sigmoid激活函数扩大个体之间的差距，增大符合条件的个体之间的交叉概率，可以有效地避免种群“早熟”。

令Kc =(f' − f)/(f_max − f_min)，得到自适应调节交叉概率公式如下：

$Pc=\{\begin{array}{l}1-\frac{1}{1+{\text{e}}^{10-20Kc}}{f}^{\prime }>f_{avg}\\ Pc1f^{\prime }\le f_{avg}\end{array}$ (3)

其中，Pc代表交叉概率，Pc1代表交叉概率预设值，f'代表交叉的两个个体中适应度较大者，f_avg代表种群平均适应度，f_max代表种群中最优个体的适应度，f_min代表种群中最差个体的适应度。

通过上述方法使得Pc随着种群迭代在不断变化，当较优个体适应度高于平均适应度时若两个个体间的差距越小说明两个个体都是优秀的个体，则使其以较大的概率进行交叉变换；若两个个体间的差距越大说明两个个体中有一个相对较差，则使其以较小的概率进行交叉变换。当较优个体适应度低于平均适应度时，则表明两个个体均较差，以预设概率进行交叉变换即可。通过改进后的自适应交叉概率，不仅可以保留种群中优质个体的基因，还可以有效增加种群的多样性。

2.3.3. 改进自适应变异概率

根据生物学知识可知变异多数都有害变异，但是变异也是提高种群多样性不可或缺的一部分。将个体适应度与平均适应度之差比上最优个体适应度与最差个体适应度之差记为Km，代表该个体在种群中的“地位”。

令Km =(f − f_avg)/(f_max − f_min)，得到自适应调节变异概率公式如下：

$Pm=\{\begin{array}{l}Pm1f>f_{avg}\\ 0.1-\frac{0.1}{1+e^{-10Km}}f\le f_{avg}\end{array}$ (4)

其中，Pm代表变异概率，Pm1代表变异概率预设值，f代表当前待变异个体适应度，其余符号同式(3)。

通过上述方法使得Pm随着种群迭代在不断变化，当个体适应度高于平均适应度时，表明个体较为优秀取预设变异概率即可，避免优秀个体遭到破坏。当个体适应度低于平均适应度时，表明个体较差，根据其“地位”利用上述公式自适应调节变异概率，增加种群的多样性，保证种群不会过早成熟。

2.3.4. 适应度

使用2.2小节中优化后的最低水平线算法按照个体编码顺序对样品进行排样，得到的面积利用率作为该个体的适应度。

3. 实验结果与分析

为了检验算法对异形标签排样问题的实用性以及算法本身的性能，设计了两组实验，一组是基于实际问题中的异形标签排样问题验证，另一组是与其他文献中的算法对比优劣。

3.1. 实例验证

该实验选取最常用的超市促销标签排版作为实例验证。超市促销标签具有内容形状多样化、订单交付周期短、订单量少次数多等特点，在打印过程中使用人工排版非常耗费时间，同时排版效果难以保证，造成材料的浪费。因此该实验选取几种常见的超市促销标签进行实例验证，详细数据见表1。

Table 1. Supermarkets commonly use promotional label classification data

表1. 超市常用促销标签分类数据

实验分为六组，使用文中算法进行排样，每组重复排样30次，每次迭代更新2000次得到的实际排版结果见表2。

Table 2. Six kinds of promotional label layout results

表2. 六种促销标签排样结果

从表2中可以看出，本算法对于超市促销标签排版具有非常好的效果，六种标签的面积利用率都在90%以上，最高的达到了97.97%。此外，结合表1中的样品个数可知，样品越多所需要的运行时间越长，不同的样品集合其达到最优值的时间不同，在实际使用过程中可以根据自身需求调整种群大小和进化次数来控制运行时间。实际排版效果见图1。

(a) (b) (c)

(d) (e) (f)

图1. 排样结果图

图1中(a)~(f)分别是艺术字、爆炸贴纸、KT板、异形商标、拟物商标、促销标签六种常见的超市促销标签通过文中算法得到的排样结果。从图中可知，文中所提出的算法对于异形标签的排样效果非常好，同时也证明了本算法适用于多种异形标签的自动排样问题。

3.2. 算例对比

为进一步验证文中所提出算法的效果，分别采用文献 [10] 的C算例和文献 [11] 中的N算例，进行测试，相关参数见表3、表4。

使用文中算法计算上述算例，与GA-BLF算法、SA-BLF算法进行对比，其中GA-BLF算法和SA-BLF算法的结果直接来源于文献 [11] 。对比结果如下表所示，其中H、R、T分别代表最终排样高度、面积利用率和运行时间。

由表5得，文中算法相比于GA + BLF算法与SA + BLF算法在C算例上的运算时间和排样效果都得到了较明显的提升，排样面积利用率的提升在1.52%~6.25%，并且有部分情况下达到了理论最佳状态，但在个体差异较大的N算例上排样面积利用率有所下降。在运算时间上该算法具有明显优势，随着样品数量的增多优势也更加突出。实验结果表明该算法对不同规模的排样问题都具有较好的实用性。

Table 3. C example sample data

表3. C算例样品数据

Table 4. N example sample data

表4. N算例样品数据

Table 5. Results of different algorithms

表5. 不同算法计算结果

4. 结束语

文中针对异形标签的排版打印问题提出了可行性的解决方案，实验证明自适应遗传算法对于异形标签的排版具有非常好的效果，但对个体差异较大的样品集效果一般。异形标签的自动排样可以应用的领域非常广泛，除文中提到的超市促销标签外，还可以用于食品标签、医药标签、图案Logo、贴画等二维异形样品的生产，为其提供了一种省时省力省料的排版方案。

致谢

首先感谢在对我细心指导的曹老师，没有曹老师高标准严要求的指导就不会有我的现在进步，每当我科研遇到问题时，曹老师总是能驾轻就熟的给予指导，帮助我顺利度过难关。在完成论文的这段时间里，不仅提升自己的写作能力，同时对科研也有了更深层次的认识，也更加清楚的认识到了自己的不足之处。研究生三年，曹老师严谨的治学态度时刻影响着我的思想，同时也为我今后的学习和工作树立了榜样，在未来的生活和工作我一定会一直铭记师恩，把指导老师学术上和品行上的教诲应用在实际的工作中去，不负老师和校方的栽培。

基金项目

国家自然科学基金面上项目(61972042)；北京印刷学院校级项目(21090123009)。