双种群混合遗传算法的裁剪分床应用研究

杜守信，毋 涛

西安工程大学 计算机科学学院，西安710048

裁剪分床计划（Cut Order Planning，COP）的制定是服装企业生产过程中难以避免的问题。该问题旨在寻找多尺码、不规则数量的生产订单在多个裁床上排布的最佳搭配，来满足服装企业低成本、高效率的生产需求。当下的服装企业订单大多以短交期、多款式多尺码、中小批量为主，在客户的生产订单到达后，迅速制定裁剪方案并投入生产，能提高企业的生产效率，带来利润的显著提升。COP 的制定是整个生产过程中重要的一环，对生产效率和生产成本都有着关键的影响。COP制定过程又受到企业生产环境中众多因素的影响，在实际生产中可以使用层次分析法[1]来对影响裁剪分床的因素进行分类，并确定影响重大的因素作为裁剪分床数学模型的约束条件。COP 制定时综合考虑企业的生产环境，将生产需求订单分到多个裁床，确定裁床铺布层数，并对每个裁床中的尺码进行合理搭配，在较短的时间内寻找最优方案并完成裁剪，达到原材料的最大利用和生产成本的最小化，对当下服装生产企业的竞争与生存有着重要意义。

传统的裁剪分床方法要求生产订单不同尺码之间的数量配比具有一定的规律性，或者人为地增减需求数量而产生一定的规律，这种以经验为主的分床方法需要进行大量的计算，并且结果有着较大的误差，造成了很多不必要的浪费。随着市场需求不断改变，生产订单的尺寸、风格、面料和颜色等越来越多样化，导致COP 问题愈加复杂[2]。为了有效地解决该问题，国内外学者进行了众多理论研究，其中Ünal等为获取最佳解决方案，使用了混合整数非线性规划的方法来建立模型，并使用计算机求解[3]。在智能算法的使用方面，Nascimento 和Casali等提出了一种基于状态空间的启发式搜索算法来解决裁剪分床问题[4]。M’Hallah 和Bouziri 对裁剪分床中的COP 和TDL（Two-Dimensional Layout）问题进行了整体考虑，使用构造启发式和元启发式方法实现最小化织物长度的目的[5]。国内学者王学骥等[6]、江丽林等[7]分别在不同的方向上改进了粒子群优化算法，并用来解决裁剪分床实际问题。实际应用过程中，单一的启发式算法往往会存在一定的问题，使得结果不总是优秀的，为此一些学者开始考虑结合多种算法来弥补单一算法的缺陷。刘艳梅等提出一种针对大批量定制服装裁剪分床计划的两阶段优化算法，分阶段寻优得到符合要求的最优解[8]。Xu 和Thomassey 等在遗传算法寻优的基础上提出一种基于整数编程的裁剪订单模型来完成订单的裁剪计划[9]。Abeysooriya 和Fernando 则将传统的启发式算法与遗传算法相结合来优化裁剪分床计划，并提升算法的执行效率[10]。而Tsao 和Liao 等在混合算法的基础上，结合基于退火的遗传算法和基于禁忌搜索的遗传算法，并以降低总成本为目的来进一步解决COP问题[11]。

综合上述情况，在现有理论中一些单一算法改进的方式已经被混合算法所替代，而在混合算法研究中部分算法没有从实际生产环境的整体情况来考虑，只在相应的具体情境下进行算法的改进来提升效率，并不能适用于大多数生产过程，还有部分在改进算法的同时增加了算法复杂度，增大了时间成本。

本文对实际服装生产过程进行综合、全面的考虑，由于不同类型的生产订单需求迥异，提出了围绕多个目标建立的优化数学模型，企业可以通过调整权重参数选择最符合生产的模型。模型求解利用遗传算法和粒子群算法两者的优势，将算法优化过程分为两个种群进行，遗传算法带来群体多样性的同时，将优秀的个体组成精英群体再使用粒子群算法优化求解，以较快的速度筛选出最优方案。混合算法在提升搜索效率的同时又减小了陷入局部最优的可能。

1 裁剪分床问题模型

1.1 问题描述

假设某服装生产企业现接收到一批订单需要生产，已知该订单共有n个尺码，且每个尺码的需求数量为A={a1,a2,…,an}，考虑企业生产情况，需要制定一个裁剪分床计划方案，使得生产时间较小，面料利用率较高，裁剪时不可少裁，超出数量也要在一定范围内，设置各尺码最大超裁数量为G={g1,g2,…,gn} 。为了更好地进行套排分布，裁床上各尺码最大铺设数量设置为S={s1,s2,…,sn} 。

1.2 多维度数学模型的建立

裁剪分床计划的数学模型，要以生产订单的尺码和需求数量为基准，裁床的长度、裁刀的长度、订单织物的幅宽和厚度、订单的需求款式等为约束条件，企业实际需求为目标来建立。为了充分利用原材料，减少生产成本和裁剪时间，裁剪分床计划制定时会尽可能选择大小尺码套排的方式。

参照如图1所示的实际生产裁剪分床流程，从企业的需求出发，分别在超裁数量、裁剪时间、面料利用率三个维度上建立数学模型。

图1 裁剪分床流程图Fig.1 Flow chart of cut order planning

在裁剪分床计划制定时，同一个裁床上不同的套排配比会产生不同的面料使用长度，铺设尺码时要在面料的长宽方向进行取整，则第i个裁床面料使用长度的计算公式为：

式中，Cij是裁床i上尺码j的铺设数量；w1是待裁剪面料的幅宽；w2是产生裁片的标准宽度；L是最大铺布长度。

1.2.1 超裁目标函数

超裁数量是制定裁剪分床计划时的一个必要参数，也是大多数企业生产中主要参考的目标。超裁数量过大会使生产成本上升，整体效率下降，还有可能导致库存堆积引起大量浪费。但是由于尺码数量不一致，难免会造成裁剪误差，在实际裁剪中要使得各尺码裁片裁剪的误差尽量小。设进行裁剪时需要的裁床数量为m，为减少整体误差使用了方差作为目标值，则订单的裁剪数量误差目标函数可表示为：

式（3）作为尺码j裁剪误差的一个条件函数，生产中裁剪数量不可小于需求数量，因此添加约束来避免少裁。其中，Hi是裁床i的铺布层数，其数值在裁床铺布层数最大值Hmax和最小值Hmin之间。

1.2.2 裁剪时间

裁剪时间目标函数主要分为裁剪时间和拉布时间。裁剪时间与裁床台数、铺布长度有关，拉布时间受拉布机速度和用布总长度影响。目标函数公式为：

式中，v1是裁床上裁刀的行进速度；v2是拉布机拉布速度。

1.2.3 面料利用率

面料利用率考虑的是在每个裁床上尽可能地实现多尺码套排分布，并最大地占用铺设面料长度。目标函数公式为：

2 混合的多种群粒子群-遗传算法

2.1 算法选择

根据所建模型的非线性特点，引入了现代智能算法进行模型求解。现代智能算法种类丰富，不同算法又有着不同的适应能力，从模型与算法的相关特性考虑，选择了粒子群优化算法混合遗传算法的方式来求解问题模型。

遗传算法是一种模拟自然进化中的自然选择和遗传学机理来搜索最优解的方法[12]，具有较强的全局搜索优化能力，但常规的遗传算法在求解复杂模型时存在收敛速度慢、优化精度低的缺点。粒子群算法（Particle Swarm Optimization，PSO）是1995 年由Eberhart 博士和Kennedy 博士共同提出的一种模拟鸟类捕食行为的群智能算法，与其他算法相比有着参数少、易实现、收敛速度快的特点[13]。

为了能够提高算法的全局搜索能力，降低陷入局部最优的可能，并适当提升算法的收敛速度，提出使用多种群的粒子群-遗传混合算法，将粒子群算法快速收敛能力与遗传算法的全局多样性优势结合起来，并对内部进化机制做出一定的改进。

2.2 多目标数学模型的处理

对于多个目标函数的处理，一般是使用线性组合将多个不同的目标函数按照一定的权重叠加，得到一个最终的函数进行求解。

由于多目标函数尺度不同，要先进行归一化处理，其中超裁数量目标函数使用订单尺码设定的最大超裁数量平方和进行归一化处理，时间目标中使用了当前情况下的最大裁剪时间进行归一化处理。

对处理后的目标函数进行线性组合为：

式中α,β,γ≥0 且α ＋β ＋γ=1,是不同目标函数在实际生产中的权重参数。

在模型求解时，算法需要解决的关键问题是寻找最优的铺布层数配比Hi和各尺码铺布数量配比Cij，目标函数的寻找过程中使用以下公式：

2.3 混合的双种群算法设计

采用混合的双种群粒子群-遗传算法来解决裁剪分床问题的主要步骤可描述为：第一步，企业根据生产订单、设备等信息初始化参数，结合生产现状设定需求模型；第二步，根据已有条件计算合适的分床数量区间并确定算法目标函数；第三步，取可用分床数量M进行算法种群初始化，设定算法最大进化世代数；第四步，使用遗传算法进化普通群体，进化过程每一代取两个最优个体加入到精英种群，对种群进行交叉和变异；第五步，等到精英种群数量满足时，暂停遗传算法，使用粒子群算法对精英种群进行进化；第六步，记录粒子群算法进化过程中的局部和全局最优并更新粒子；第七步，粒子群算法进化结束，记录最优个体，排序并选择优秀个体替换到普通种群，开始新一轮的混合算法迭代；第八步，算法达到最大迭代次数后比较算法进化结果，取最优个体作为当前分床数M下的最优方案；第九步，当前分床数M=M ＋1，如果仍在可用区间内，转到第三步继续使用算法求解，否则比较不同分床数下的最优方案，选择最符合目标需求的即为最终方案。具体的混合双种群算法设计流程如图2。

图2 混合的双种群算法设计流程图Fig.2 Flow chart of double population hybrid genetic algorithm

2.4 算法的实现

2.4.1 编码方案

算法中个体方案包括各裁床铺布层数与各裁床各尺码的数量配比，由于裁床铺布层数是比较大的实数，使用二进制编码会导致编码过长过大，不利于计算，而实数编码意义明确，且减少了编码和解码的步骤，提高了算法效率[14]，为此混合算法编码时使用了实际数值作为编码。而算法的求解过程是对裁床铺布层数矩阵和裁床各尺码数量配比矩阵同时寻优，会导致嵌套过深而丢失性能，混合算法中考虑两矩阵的相同维度，寻优过程中将两者编码在同一矩阵中，计算时再将结果解码成两个独立矩阵，有效降低了算法的时间复杂度。编码形式为：

2.4.2 适应度函数

适应度函数通常是根据目标函数进行设计的，混合算法进化时使用目标函数作为个体适应度进行计算，满足约束条件时，适应度越小代表当前方案越优秀。模型的适应度函数为：

2.4.3 选择机制

算法进化过程涉及三处选择，即普通种群进化时选取精英个体更新精英种群，遗传算法进化中进行交叉个体的选择，精英群体进化完成后选择个体替换普通种群。从普通种群中选择更新精英群体时，在普通种群按照适应度排序，选择最优的两个加入到精英种群；遗传算法进化时和精英种群反向优化普通种群时，均使用轮盘赌的机制选择个体；保证优秀个体有更大概率选中的同时又保存了个体多样性。轮盘赌选择时被选中的概率使用其适应度占比：

式中，fiti为个体适应度，pop代表混合算法的种群大小。

2.4.4 交叉

算法的交叉操作是选择两个染色体进行配对，配对染色体的基因片段相互交换形成新的个体，增加种群多样性。为了在进化时有更好的全局搜索能力，算法中的交叉机制采用随机交叉的方式进行，在个体矩阵的全索引区间内随机生成一个整数r，针对选择的配对个体，交换r后的基因片段。对于选择机制产生的新种群，令其奇数位置个体与偶数位置个体进行配对交叉，最终获得一个新的基因种群。具体交叉流程如图3。

图3 混合算法交叉机制流程图Fig.3 Flow chart of hybrid algorithm crossover mechanism

当交叉位置r=n时，如下所示为选择个体s1、s2进行配对交叉，产生两个新的子代s3、s4的过程：

2.4.5 变异

变异操作是对种群中一些个体产生随机的变化来使个体能够更加适应进化的需求。算法进化的前期过程主要靠交叉操作来产生多样性，后期则依赖于变异操作，因此算法中采用一种随进化次数增多而逐渐增加的自适应变异概率，并对选择的个体生成一个（0，1）内分布的概率矩阵P，所有概率元素与p相比较，如果该基因片段对应的概率大于变异概率不发生变异，小于则发生变异。自适应的变异概率公式为：

式中，p0是初始设定的变异概率；μ是自适应概率的最大尺度；maxIter是算法最大进化代数。

变异算子选取时，在文献[15]中的变异算子基础上，结合粒子群算法进化机制，提出了一种基因片段近优趋势的变异方式。对于个体xk的变异过程公式如下：

式中，ρ是惯性系数；P是变异概率矩阵；σ和θ是两个学习率。

图4为算法具体变异流程。

图4 混合算法变异机制流程图Fig.4 Flow chart of hybrid algorithm mutation mechanism

2.4.6 粒子群优化算法

精英种群进化时使用一种改进的惯性权重自适应的粒子群优化算法来快速收敛找到最优解，对于精英种群的个体粒子，初始位置已经确定，初始化粒子的速度，并根据速度和位置公式不断更新粒子状态，直至达到最大迭代次数或者最优解不再发生变化。进化时更新公式为：

式中，c1、c2是学习因子；r1、r2是随机数值。

参数对算法的优化性能影响很大，因此在使用中要选择合适的参数值[16]。惯性权重ω较大时有利于算法跳出局部最优，较小时有利于局部寻优，结合文献[17]中惯性权重的改进思想，设置一个在进化过程中自适应的惯性权重因子：

式中，ω0是初始设定的惯性因子；ω1是进化过程减小的最大尺度。

2.4.7 混合算法的交叉影响机制

在文献[18]算法的基础上，调整种群结构，将改进的遗传算法和粒子群优化算法结合，提出了交叉影响双种群的混合算法。将个体分为普通种群和精英种群，普通种群使用遗传算法进化保留种群的多样性，精英群体使用粒子群优化算法进化提高收敛速度，在进化过程中双种群之间交叉影响，相互促进。双种群影响关系如图5。

图5 混合算法进化两种群交叉影响关系图Fig.5 Relationship graph of hybrid algorithm evolution of two groups

算法交叉进化时具体流程如图6。

图6 混合算法种群交叉进化流程图Fig.6 Flow chart of hybrid algorithm population cross evolution

3 实验结果

根据某服装生产企业的实际需求订单以及企业生产条件，进行了算法的实用性测试。实验环境为英特尔Core i5-9300H，2.4 GHz 主频，16 GB 内存，GTX 1660 Ti 6 GB 显卡；算法运行环境为PyCharm2017.1。实验过程选择了手工计算方法、遗传算法、粒子群算法与本文算法进行对比。

根据订单信息表1可知，该订单所有尺码总的需求数量为5 016 件，由企业生产条件及生产设备参数可以得到裁床适宜铺布层数范围为[50，250]，每层面料最大可以裁剪各尺码总数量为15，计算出裁床数量的适用区间是[4，8]，设定尺码套排时每种尺码数量不超过3 件，尺码最大允许超裁比例为2%，结合生产需求建立模型并使用混合算法求解。

表1 生产订单详情Table 1 Production order details

由图7 中三种算法的进化曲线可以看出：（1）粒子群算法在进化过程中种群收敛速度较快，却容易陷入局部最优而停止搜索。（2）遗传算法更为稳定，在进化过程中能保证种群多样性，但是算法进化缓慢，需要进行较多的进化世代才能寻找到最优解。（3）混合算法进化速度有显著提升，图中混合算法在200代以内便已经寻得最优解并停止了搜索，且最优解也与遗传算法最优解相当。

图7 多种算法的适应度和迭代次数的关系曲线图Fig.7 Relationship graph between fitness and number of iterations of multiple algorithms

使用双种群粒子群-遗传混合算法最终获取最优裁剪分床方案为：

使用人工经验计算的方式得到一组裁剪分床方案为：

对比算法和人工计算裁剪方案可以得到：智能算法遍历寻找最优解，满足裁剪要求的同时会尽可能地套排尺码来减少裁床的使用数量并降低目标函数值。而人工计算由于不能进行所有可能的枚举，只能根据经验及需求数量的规律性来进行分床和排布，套排情况较差且增加1个裁床的成本。

表2 是使用四种不同算法求解同一订单模型时的结果比较。人工计算的方法多使用1个裁床，超裁数量为59 件，且个别尺码超裁数量超过了2%，由于裁床数量多，裁剪时间也最长。智能算法结果比人工计算要提高很多，PSO 算法收敛速度快，遗传算法进化比较稳定。混合算法在各方面数据均优于其他算法，且裁剪超出数量比人工计算减少50%以上，时间缩短了5 min；与单个改进遗传算法相比，裁剪超出数量少了6 件，裁剪时间提升了0.24 min，算法执行时间加快了16.2%，面料的利用率也保持在较高水平。

表2 多种算法的裁剪分床方案最优结果Table 2 Results of cut order planning schemes based on multiple algorithms

从表3中比较结果可以看出，在使用不同维度的目标函数模型时，算法优化的方向是不同的。与考虑三种目标的结果相比，不考虑裁剪时间和面料利用率得到了超出数量为18 的结果，而裁剪时间增加了7.96 min，面料利用率则下降了3 个百分点；考虑其中两个目标时，则剩余目标会造成较大的浪费。

表3 不同维度目标函数情况下的结果Table 3 Results under different dimensional objective functions

4 结束语

本文针对服装生产企业的裁剪分床问题，充分考虑生产条件，提供了一个动态的多维目标函数模型，使企业可以根据自身生产需求调整裁剪方案，提出了使用一种基于双种群的混合粒子群-遗传算法来求解多目标模型的流程方法。使用混合算法对企业生产的一个具体订单信息进行了裁剪分床计划的制定，并与当下的人工计算方法、粒子群优化算法、遗传算法进行了对比。

结果表明，双种群粒子群混合遗传算法进化过程结合了粒子群和遗传算法的优势，提升了算法执行效率的同时能稳定寻优。与手工计算结果相比，裁床数量减少1个，超出裁剪数量降低了60%左右，实际裁剪时间减少5 min。同时分析了实际生产中需求目标不同对裁剪方案的影响，针对不同的目标模型寻求最适宜的裁剪分床方案。证明了本文混合算法有着优秀的寻优能力，且表现稳定，能够适应不同的生产环境，满足多种生产需求。

后续研究可以将进化种群进行更系统的分类，突出层次结构，深度结合两种优化算法，进一步提升裁剪分床过程中的效率和生产利润。