基于遗传算法的被动式木窗材下料优化

Optimization of Passive Wooden Window Material Cutting Based on Genetic Algorithm

摘要

在定制化被动式木窗加工过程中，减少边框材下料过程中的原料浪费是降低成本的关键。为此，将该问题建模为一维下料问题，针对传统遗传算法中个体编码方式在迭代过程中容易导致切割模式被破坏和探索效率低下的问题，提出一种新的个体编码方式，以保护进化过程中切割模式的完整性。同时，设计启发式策略和修正策略，用于个体修正和种群进化。仿真试验表明，在不同算例下，除末根外的原料平均利用率均可达到99%，且末根余料长度相较其他算法也有所提高。在2组企业的实际生产数据中，与企业现有软件相比，该算法不仅达到了理论下界，还在除末根外的平均利用率上分别达到99.49%和99.66%，优于企业软件的计算结果。该算法有助于降低成本，能为工程实践提供可靠的解决方案。

关键词

一维下料问题 / 遗传算法 / 启发式算法 / 种群编码 / 可用剩余物

Key words

One-dimensional cutting stock problem / genetic algorithm / heuristic algorithm / population encoding / usable leftovers

0 引言

随着人们对家具定制需求的增加，定制化家具市场正在不断扩大。其中，被动式木窗因其美观、保温、隔音以及低碳等优势，逐渐受到市场的关注和喜爱^[1]。然而，高昂的原料成本制约了定制化被动式木窗市场的进一步扩展。在生产过程中，被动式木窗的边框材通常通过截断标准长度的集成材获得，这一过程中会产生各种废料。因此，为了降低成本，可以通过减少截断过程中原材料的浪费来实现优化，这就涉及一维下料问题。

一维下料问题（one-dimensional cutting stock problem，1D-CSP）旨在通过切割给定规格的原料生成满足生产需求的零件或产品，并尽可能减少材料浪费或使用量。这一问题在制造业中备受关注^[2]，由于1D-CSP具有非确定性多项式困难（non-deterministic polynomial-time hard，NP-hard）属性，随着问题规模的增大，求解愈发困难。为解决1D-CSP，大量文献进行了相关研究。目前主要的解决方式有2种。一是精确算法，包括列生成^[3-4]、分支-切割-定价^[5]等方法，常用于求解最优解，但需要消耗大量的计算资源。二是启发式算法，可分为传统启发式和元启发式，用于获得可接受时间内的可行解^[6]。传统启发式算法，如降序首次适应算法（first fit decreasing，FFD）^[7]、降序最佳适应算法（best fit decreasing，BFD）^[8]、残差重组启发式算法 （residual recombination heuristic，RRH）等^[9]，通过设计的策略快速获取下料方案，但对于较大规模的问题，此类方法仅能得到局部解，为此许多文献中使用元启发算法进行求解，比如沈显君等^[10]结合粒子群算法、遗传算法以及模拟退火算法提出的自适应广义粒子群优化算法（adaptive general particle swarm optimization，AGPSO），魏凉良等^[11]结合BFD算法提出了自适应混合遗传算法（modified adaptive genetic algorithm hybridized with BFD algorithm，MAHGA），侯改等^[12]借助金字塔演化策略并结合差分进化算法提出了基于差分进化的金字塔演化策略算法（pyramid evolution strategy with differential evolution，DEPES），丁为^[13]将多种传统启发式算法的解作为初始解，受交叉遗传启发，实现算法的快速收敛。

元启发式算法在求解问题之前，需要对个体进行编码。对于1D-CSP，在传统遗传算法中，个体编码是直接对所有需要生成的零件进行排序，个体长度等于零件个数。这种编码方式的进化过程实质上是对排列顺序进行优化。然而，当问题规模较大时，该编码方式显现出明显的局限性：一方面，在优化过程中，交叉和变异操作需要频繁打乱当前排列顺序，从而实现对解空间进行探索，但这种以零件为基因单位的扰动，会破坏基因片段，进而破坏已有切割模式的完整性，最终降低探索效率；另一方面，随着问题规模增大，交叉和变异操作对个体影响逐渐减弱，探索驱动力降低，使算法更容易陷入局部解。

本研究提出一种基于切割模式的编码方式来求解1D-CSP。通过该编码方式可以更加激烈地探索，有助于跳出局部解。此外，还设计一种启发式策略和修正策略，用于个体修正和种群优化。

1 问题背景

某被动式木窗企业的定制化加工车间中，负责截断生成被动式木窗边框材（简称边框材）的生产线工艺如图1所示。该生产线的工艺流程为：首先，吸盘机械手将标准长度的集成材抓取并放置到传送带上；然后，集成材经优选锯切割成符合订单需求的各类边框材；最后，工人将切割完成的边框材码垛并转运至后续加工区域。边框材的种类和数量由制造执行系统（manufacturing execution system，MES）根据总生产需求分配，以满足订单要求。

为能够提升木窗的生产效率并降低人工成本，企业希望可以使用码垛机械臂代替工人，为此需要能够提前获取到边框材的出料顺序以辅助机械臂实现高效码垛。然而，由于生产线上的优选锯是外购设备，无法提前获知出料顺序，企业急需开发一个有效的下料优化方案，以便将其嵌入到现有工艺流程中。下料优化方案应当考虑到多个因素，包括边框材的尺寸、数量和排料方式，旨在实现最优的原料利用率。

2 问题模型

所提木窗企业实际生产过程中，由于标准集成材的长度仅有一种，故假设所有原料长度均为L且数量不受限制。现需要从这些原料上切割出N种零件，零件的长度为 l_i \left(i=\mathrm{1},\cdots ,N\right)，相应的数量为 d_i \left(i=\mathrm{1},\cdots ,N\right)，目标是寻找最优的下料方案，使得所需要的原料数量最少。考虑到最后一根原料生成的余料可直接在下一批订单中使用或被存放到库存中，在将来的加工中再次使用，均有利于降低生产成本^[14]。本研究模型为

\begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}{\displaystyle \sum _{k=\mathrm{1}}^K}{x}_{k}L-{\displaystyle \sum _{i=\mathrm{1}}^N}{l}_i{d}_i-l\\ \mathrm{s}.\mathrm{t}.\left\{\begin{array}{l}\begin{array}{cc}{\displaystyle \sum _{k=\mathrm{1}}^K}{a}_{ik}{x}_k=d_i& i=\mathrm{1},\cdots ,n\end{array}\\ \begin{array}{cc}{\displaystyle \sum _{i=\mathrm{1}}^N}{a}_{ik}{l}_i\le L& k=\mathrm{1},\cdots ,K\end{array}\\ x_k\in Z^{+}\\ \begin{array}{cc}{a}_{ik}\ge \mathrm{0}& a_{ik}\in Z\end{array}\end{array}\right.\end{array}。（1）

式中：K为下料方案中不同切割模式的数量； x_k为第k种切割模式所使用的次数； a_{ik}为第k种切割模式下产生的第i种边框材的数量；l为最后一根料的余料；Z ⁺和Z分别为正整数集和整数集。第1个约束条件为需求约束，表示按照下料方案切割后，产生的边框材需要满足生产的种类和数量需要；第2个约束条件表示尺寸约束，即对于任意一根原料，切割后产生的边框材总长度不大于原料长度；最后2个约束条件确定了决策空间，即每种切割模式的使用次数以及产生的边框材个数都为整数。

3 算法设计

3.1 个体编码和种群初始化

在遗传算法的种群中，对于1D-CSP，每个个体代表一种下料方案，一个下料方案可由多种切割模式及相应的使用次数组成。本研究算法中使用矩阵表示个体，矩阵大小为 \left(N+\mathrm{1}\right) \times K^{\mathit{\text{'}}}，其中 K^{\mathit{\text{'}}} \le K表示仅在下料方案中使用到的切割模式数量，可以减小个体存储和计算成本。

以6 m原料生成3个2 m和2个3 m的边框材为例，个体编码和种群初始化的方式如图2所示。首先，以随机序列方式生成所有边框材，如｛2-2-2-3-3｝和｛2-3-3-2-2｝；然后，依据尺寸约束对生成的序列进行分割，分割出的每一个子序列都是一种切割模式，如｛2-2-2-3-3｝分割为｛2-2-2｝和｛3-3｝，｛2-3-3-2-2｝分割为｛2-3｝、｛3-2｝和｛2｝。由于子序列中边框材的产生顺序并不影响废料产生结果，即｛2-3｝与｛3-2｝产生的废料长度均为1 m，因此对每个子序列都进行 降序排序，并将排序结果进行分类统计，实现个体的 矩阵编码，见图2中的生成的个体1（Ind.1）和个体2（Ind.2）。

在矩阵中，第1行表示每种切割模式的使用次数，第2行起每列代表一种切割模式，其中的数值表示该模式下各类边框材的数量。相比以单个零件作为基因的编码方式，本研究提出的编码方式将切割模式作为基因单位，使个体的变化表现为对不同切割模式的组合。这种方式不仅避免了随意破坏现有切割模式，还保证了切割模式的完整性，有助于将高效的切割模式遗传给下一代，从而提高算法的求解效率和质量。

3.2 启发式策略

尽管所设计的编码方式中，种群中的个体已满足模型的约束条件，但部分切割模式可能不合适，影响下料方案的优化效果。仍以6 m原料产生3根2 m以及2根3 m的边框材为例。假设初始顺序为｛2-2-3-2-3｝，分割产生3个子序列，即｛2-2｝、｛3-2｝和｛3｝，此时需要使用3根原料。可以发现该序列下，第1根原料产生的2 m余料被丢弃，但其可被保留用于生成一个2 m的边框材。而对于｛2-2-2-3-3｝的初始顺序，余料长度为0，消耗2根原料。可见切割模式满足最大切割模式^[8]条件，即 ，是实现最优下料的前提。考虑到当问题规模变大时，满足最大切割模式的模式数量增加，而不同切割模式组合都有可能实现最优解，因此以随机顺序进行初始化是必要的。

为了尽可能保证用到的切割模式都满足最大切割条件，设计一种启发式策略，流程如图3所示。对于任意个体，从第1列（ k = \mathrm{0}）开始判断当前切割模式是否满足最大切割模式条件，若满足则向后逐步判断。若不满足，则从最后一列（ k \text{'} = K \text{'}）开始往前，将基因所包含的内容统计到 A^{\mathrm{\text{'}}} = \{ A_{\mathrm{1}}^{\mathrm{\text{'}}} , \cdots , A_N^{\text{'}} \}中，并根据 A \text{'}对不满足最大切割条件的模式进行补充。具体而言，按照长度的降序顺序选择可用于补充的边框材，直到满足最大切割模式条件。当前后搜索到同一列时，即 k = k \mathrm{\text{'}}，停止 k \mathrm{\text{'}}的移动。继续向后逐步搜索时，将对应模式所涉及的边框材按照种类和数量归还，并按边框材长度降序顺序补充，可保持种群多样性。

值得注意的是，每个个体不仅包含切割模式，还包含相应的使用次数，每次调整补充时需要考虑数量因素。仅向后逐步搜索时，若 A \mathrm{\text{'}}中符合条件的边框材数量不能够完全补充当前模式，那么需要在满足最大切割条件的基础上最大化使用次数，并从 A \mathrm{\text{'}}中去除相应内容。当 K \mathrm{\text{'}}个切割模式补充完整后，将 A \mathrm{\text{'}}中的剩余内容按照FFD算法进行组合并添加到个体中。

3.3 遗传算子

3.3.1 选择算子

使用随机竞争选择算子^[2]。首先采用轮盘赌的方式选择2个个体，然后根据适应度大小选择更好的个体，不断选择直到满足种群数量需求。该算子能够有效减缓早熟收敛现象。

3.3.2 交叉算子

为将个体中的优秀基因遗传下去，在选择2个个体后，采用类似顺序交叉策略的方式^[15-16]。首先随机选择个体上的2个点，然后将2点之间的基因片段中不存在另一个个体中的基因放到前面，并将相同基因（切割模式）的使用次数进行替换。通过该方式既可以将优秀基因遗传下去，又可以尝试新的基因组合。

3.3.3 变异算子

对各切割模式的使用次数进行随机变异，变异范围从 \left[\mathrm{0},\mathrm{m}\mathrm{i}\mathrm{n}(⌊d/a_k⌋)\right]，其中 ⌊⌋表示下界，d为各种边框材需求的数量， a_k为第k种切割模式下各边框材的生产数量。该算子主要是为了尝试不同比例的切割模式组合。

3.4 修正策略

在经过交叉和变异操作后，生成的个体无法保证满足需求约束。为此设计了一种修正策略，使得个体可以满足需求约束。

流程如图4所示，每次仅修正一种边框材。从第1列（ k = \mathrm{0}）开始，计算能够生成的边框材数量 p = {\sum }_{k=\mathrm{1}}^K a_{ik}{x}_k，并与需求数量 d_i进行比较，当满足需求约束的时候存在2种情况。一是在统计当前切割模式后，刚好满足数量需求 p = d_i，此时令后续所有模式相应的 a_{ik} = \mathrm{0} , k = k + \mathrm{1} , \cdots , K^{\text{'}}。二是统计切割模式后 p > d_i，为满足需求约束时不破坏其他种类边框材数量关系，首先对当前切割模式进行复制，然后最大化当前模式的使用次数，更新 x_k。并对复制后的内容 a_k^{\text{'}}进行调整，最后令后续 a_{ik} = \mathrm{0} , k = k + \mathrm{1} , \cdots , K^{\text{'}}，并且将 a_k^{\text{'}}添加到个体中。在修正过程中，需要及时删除不能产生边框材的切割模式，以减少计算和存储成本。

上述步骤后，可能某类边框材数量少于需求个数。为此采用FFD算法对缺少的边框材进行规划并补充到个体中。在完成修正后，部分模式可能不满足最大切割条件，可通过启发式策略进行调整。

4 仿真试验对比与分析

本研究通过Python实现算法，计算机的配置为Intel（R） Core（TM） i7-7700HQ CPU@2.8 GHz，内存为16 G。遗传算法相关参数设置见表1。

4.1 试验数据

为验证本研究设计算法的性能，搜索相关文献的算例。具体算例数据见表2。此外，采集了2组被动式木窗边框材下料的实际数据，该数据规模更大，算例数据见表3。表2和表3括号中的数字表示相应长度需要的数量，括号缺省表示数量为1。

4.2 算法对比

使用算例F1和F2对不同算法进行比较。本算法独立运行20次，单独运行时间不超过35 s。试验结果见表4（粗体数字表示相应评价指标下不同算法对比的最优结果），所提算法在消耗的原料根数上可以达到23和24的理论下界。在算例F1中，相比Exon-AF算法的9 138末根余料长度，所提算法将末根余料长度提升至9 176。同样地，在算例F2中，所提算法将末根余料长度从AGPSO算法的6 704提升至6 888。试验结果表明，所提算法在计算效率和余料保留方面均表现出较高的能力。

4.3 实际应用

将基于CPLEX求解器^[17]实现的列生成算法的结果作为基准，并与企业提供的下料软件优化结果进行对比。独立运行20次，单独运行时间不超过50 s。结果见表5（粗体数字表示相应评价指标下不同算法对比的最优结果），在算例S1中，所提算法能够达到139根原料的理论下界，而企业软件未能达到该值。同时，末根余料长度相比CPLEX求解器的718，提升至1 461.1。在算例S2中，所提算法的末根余料长度相较于CPLEX求解器和企业软件，提升至4 350，除末根外的平均利用率达到99.66%。试验结果表明，本研究所提算法相比企业现有软件具备更好的求解能力，有助于进一步减少实际生产中的浪费，降低原料成本。

5 结论

针对被动式边框材下料问题，基于遗传算法，通过矩阵表示改进个体编码方式。同时，提出一种启发式策略和修正策略，以实现个体修正和种群进化。在 2个文献算例上的运行结果表明，所提算法能够达到理论下界，除末根外的平均利用率均在99%，末根余料长度也优于文中提及的其他算法。与企业现有软件的优化结果进行比较，所提算法在2个实际算例中均达到了理论下界，并且在除末根外的平均利用率上分别达到99.49%和99.66%，显著优于企业现有软件的计算结果。结果表明，本研究所提算法具备较高的求解和余料保留能力，优于企业现有软件，能够在工程实践中提供更有效的解决方案。本研究所提算法通过Python实现，未来可以基于C/C++和并行计算技术提高计算效率，并且可以考虑将该算法用于多尺寸下料以及多维下料问题。

参考文献

[1] ZHENG L， MUELLER M， LUO C，et al.Variations in whole-life carbon emissions of similar buildings in proximity：An analysis of 145 residential properties in Cornwall，UK[J].Energy and Buildings，2023，296：113387.

[2] RAVELO S V， MENESES C N， SANTOS M O.Meta-heuristics for the one-dimensional cutting stock problem with usable leftover[J].Journal of Heuristics，2020，26（4）：585-618.

[3] GILMORE P C， GOMORY R E.A linear programming approach to the cutting-stock problem[J].Operations Research，1961，9（6）：849-859.

[4] GILMORE P C， GOMORY R E.A linear programming approach to the cutting stock problem—Part Ⅱ[J].Operations Research，1963，11（6）：863-1025.

[5] BELOV G， SCHEITHAUER G.A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting[J].European Journal of Operational Research，2006，171（1）：85-106.

[6] CHEN Y H， HUANG H C， CAI H Y，et al.A genetic algorithm approach for the multiple length cutting stock problem[C]//2019 IEEE 1st Global Conference on Life Sciences and Technologies （LifeTech）.IEEE，2019：162-165.

[7] JOHNSON D S， DEMERS A， ULLMAN J D，et al.Worst-case performance bounds for simple one-dimensional packing algorithms[J].SIAM Journal on Computing，1974，3（4）：299-325.

[8] BAKER B S， COFFMAN E G.A tight asymptotic bound for next-fit-decreasing bin-packing[J].SIAM Journal on Algebraic Discrete Methods，1981，2（2）：147-152.

[9] CAMPELLO B S C， GHIDINI C T L S， AYRES A O C，et al.A residual recombination heuristic for one-dimensional cutting stock problems[J].Top，2022，30（1）：194-220.

[10] 沈显君，杨进才，应伟勤，一维下料问题的自适应广义粒子群优化求解[J].华南理工大学学报（自然科学版），2007，35（9）：113-117.

[11] SHEN X J， YANG J C， YING W Q，et al.Adaptive general particle swarm optimization for one-dimension cutting stock problem[J].Journal of South China University of Technology （Natural Science Edition），2007，35（9）：113-117.

[12] 魏凉良，叶家玮.一维下料问题的改进自适应遗传算法[J].华南理工大学学报（自然科学版），2003，31（6）：26-30.

[13] WEI L L， YE J W.Modified adaptive genetic algorithm for one-dimensional cutting problem[J].Journal of South China University of Technology （Natural Science Edition），2003，31（6）：26-30.

[14] 侯改，何朗，黄樟灿，基于差分进化的金字塔演化策略求解一维下料问题[J].计算机科学，2020，47（7）：166-170.

[15] HOU G， HE L， HUANG Z C，et al.Pyramid evolution strategy based on differential evolution for solving one-dimensional cutting stock problem[J].Computer Science，2020，47（7）：166-170.

[16] 丁为.线材下料优化问题建模与混合求解算法研究[D].武汉：华中科技大学，2022.

[17] DING W.Research on modeling and hybrid solving algorithms for wire cutting stock optimization problem[D].Wuhan：Huazhong University of Science and Technology，2022.

[18] ALAM T， QAMAR S， DIXIT A，et al.Genetic algorithm：Reviews，implementations，and applications[J].arXiv preprint arXiv：2020.

[19] 李培勇，王全华，裘泳铭.型材优化下料的混合遗传算法[J].上海交通大学学报，2001，35（10）：1557-1560.

[20] LI P Y， WANG Q H， QIU Y M.Optimization for one-dimensional cutting using hybrid genetic algorithm[J].Journal of Shanghai Jiao Tong University，2001，35（10）：1557-1560.

[21] 李斌，贺飞.求解一维下料问题的改进混合遗传算法[J].内蒙古大学学报（自然科学版），2014，45（3）：245-250.

[22] LI B， HE F.Improved hybrid genetic algorithm for one-dimensional cutting stock problem[J].Journal of Inner Mongolia University （Natural Science Edition），2014，45（3）：245-250.

[23] LU Y， VASKO F J.A Comprehensive empirical demonstration of the impact of choice constraints on solving generalizations of the 0-1 knapsack problem using the integer programming option of CPLEX^® [J].Engineering Optimization，2020，52（9）：1632-1644.

基金资助

黑龙江省重大成果转化项目(CG23013)