基于非支配排序与遗传算法的毛边锯材优化下锯算法研究

姜新波，李 珂，杨春梅

（东北林业大学 林业机械与木工工程技术中心，黑龙江 哈尔滨 150040）

木材作为四大原材料中唯一绿色可再生的资源而被广泛应用，随着我国造纸、人造板、实木地板和家具等行业的蓬勃发展，木材作为生产原材料其消耗量逐年递增，然而我国林木资源相对匮乏，因此每年需进口大量原木和锯材[1]。木材资源巨大的供需矛盾给我国木材加工企业带来了挑战，推动木材加工向着自动化与智能化发展[2]。

伴随着人工智能技术的不断发展，为高效利用木材资源，各国学者逐渐将智能算法及理论融入到木材加工中：Urbonas等[3]将基于区域的快速卷积神经网络应用于锯材表面缺陷识别，采用机器视觉代替人工目视检测，快速准确地识别木材表面的节子、孔洞等缺陷。李海芸等[4]为提高毛边锯材清边效率，设计了基于视觉检测的锯材加工系统，可实现毛边锯材的智能化清边。张国梁等[5]采用分组降维的方法将大规模人造板锯切问题转化为每组不超过3种板材的组间排序问题，并采用惩罚函数与遗传算法求解，减少了计算时间并提高了木材出材率；刘诚等[6]采用局部枚举与贪心算法，通过改变局部枚举规模并采用贪心策略，在较小空间内得到高质量人造板锯切方案，降低了锯切原料成本；Ying等[7]提出一种启发式算法确定含单个缺陷木材锯切方案，提高了木材加工效率；孙理越[8]对最低水平线算法进行改进，对含2个缺陷的矩形木材进行锯切方案求解，算例测试表明出材率有8%以上提升。

从上述研究可以看出，将智能算法与木材加工相融合可更合理地使用木材。但以往研究对木材锯切方案的求解主要针对人造板与含少量缺陷的木材，对含缺陷较多的毛边锯材锯切方案求解研究较少。虽然国外先进木材加工企业如威力木工、豪迈等已研制出锯材智能锯切系统，但大多已形成技术垄断，国内大型木工企业主要通过进口国外先进技术进行锯材加工[9]。就目前而言，适合我国中小企业的锯材智能锯切系统相对较少，中小企业进行锯材加工主要采用“人海战术”，锯材加工全部依赖工人主观进行，无法针对缺陷众多的锯材快速准确地计算合理加工方案，造成木材原料大量浪费[10]。为解决此问题，对锯材自动化锯切进行研究和优化以提高锯材出材率是十分必要的。因此本研究通过分析毛边锯材下锯方式构建了优化下锯模型，采用非支配排序与遗传算法实现模型求解，最后通过算法仿真锯切测试，验证了本算法的可行性，为我国毛边锯材智能化锯切提供一种新的解决方案。

1 模型建立

1.1 毛边锯材下锯方式

由于锯材中含有节子、腐朽和孔洞等缺陷，需去除后制成木制品坯料使用。加工锯材时，通常根据锯材的种类和尺寸选择锯切方法，对于毛边锯材，常用的有先截断后纵解、先纵解后截断2种加工方式[11]，如图1a—b所示。

图1 毛边锯材下锯方式Fig.1 The cutting methods of burr sawn timber

当采用先截断后纵解的方式加工时，首先根据缺陷位置将锯材横向截断，再通过多锯片纵解圆锯机将产生的短板纵解。此方法由于将长锯材截断成短板，便于车间运输加工且能够利用部分锯材弯曲部分，但在横向去除缺陷时会造成较多优质木材浪费。

当采用先纵解后截断方式加工时，初步将锯材按坯料宽度纵向锯解，然后根据坯料长度将锯材横向截断，同时去除缺陷部分。与先截断后纵解加工相比，此方法去除缺陷时切除的优质木材较少且能获得较长的坯料，但会因锯材边缘的纵向弯曲而降低出材率。

通过上述分析可知，以上2种加工方式在进行锯材加工时均存在部分木材浪费。为更充分利用木材，本研究在以上2种加工方式的基础上提出一种新的加工方法，即先截断后纵解再截断的加工方式，如图1c所示。首先根据横向截断长度将锯材锯切成2～3段，再根据坯料宽度纵解锯材，最后横向去除缺陷。此方法与单一的先纵解后截断加工方式相比，锯材沿边缘纵向弯曲的影响将减小，可充分利用木材，并且最终坯料长度也大于采用先截断后纵解的加工方式。

1.2 优化下锯模型

本研究拟采用先截断后纵解再截断的加工方式，因其具有木材利用率高、便于车间运输加工等优点。但由于传统锯材加工在进行纵向锯解时会采用固定宽度等宽锯切，并由工人自主确定下锯位置，锯切过程中存在木材浪费、智能化加工能力不足和短坯料数量过多等问题，无法实现锯材最大化利用，导致锯材出材率降低。针对此问题，本研究提出一种优化锯切模式，纵向锯解时采用不等宽锯切，将出材率作为优化目标，根据坯料宽度与锯材缺陷调整锯路位置，最大程度避开锯材缺陷锯切，提高出材率的同时合理考虑经济因素，具体如下：

对于被横向截断后产生的多段含缺陷短毛边锯材，首先将其视作无缺陷锯材进行下锯方案求解。在确定每段无缺陷锯材下锯方案时，同时考虑出材率与经济价值2个目标。对于出材率目标，视作在一块去除毛边后可用宽度为W的待纵向锯切的整边锯材中，使用宽度为W1，W2，…，Wn的坯料进行宽度组合，坯料合计宽度Z1越高，则出材率越大，但宽度总和不可超出可用宽度。对于经济价值目标，则通过宽度组合中对应坯料价值与数量计算，坯料合计价值S越高，则整体经济价值越好。对以上2个目标和约束进行整合即：

求解目标：

约束条件：

式中：Wk表示第k种方案的坯料合计宽度，mm；Sk表示第k种方案的坯料合计价值；Sk表示第k种坯料对应价值；Qnk表示第k种方案的第n种坯料对应数量。

图2 无缺陷锯材下锯方案的确定Fig.2 The sawing plan for clear sawn timber

图3 确定最终下锯方案Fig.3 The final sawing plan

通过求解上述双目标问题，可得到多组优秀下锯方案（Q1，Q2，…，Qn），取出所有下锯方案对原含缺陷锯材模拟锯切以获取对应出材率（f1，f2，…，fn），选取其中最大出材率方案作为最终下锯方案，即可得到高出材率与经济价值较优的锯切方案。

最终求解目标：

2 算法求解

2.1 无缺陷锯材下锯方案求解

支配等级排序和拥挤距离排序是求解多目标问题的有效方法，通过对种群内个体的支配关系和相应拥挤距离对种群内个体逐级、逐个进行区分，确定每个解集的优劣，并以此为基础通过后续策略实现种群寻优[12]。

2.1.1 编码与初始种群生成

编码方式采用基于坯料宽度的实数编码，采用随机长度的二维数组表示基因个体，基因上序号与对应的坯料宽度相映射，每一基因个体代表一种下锯方案（图4）。下锯时，根据基因上坯料宽度从左到右依次锯切。

图4 基因编码示意Fig.4 The schematic diagram of encoding

采用随机生成的方式产生初始种群。每次在坯料宽度W1，W2，…，Wn中随机选取一个放入，并统计总宽度，以此往复，直至总宽度将要大于锯材可用宽度W即生成一组基因个体。重复上述过程，直至产生个体数量达到设置种群规模即生成初始种群。解码时，通过统计宽度相同的基因序号个数即可求得对应坯料数量。

2.1.2 种群支配等级排序与个体拥挤距离排序

多目标问题中由于每个个体具有多种属性，比较个体之间解的优劣不采用简单的大小关系而采用支配关系进行比较。支配关系按如下方式定义，设a、b是种群中的任意不同个体，若同时满足：

1）对任意求解目标，有Zk(a)≥Zk(b)（k=1,2, ......,r）。

2）至少存在一个求解目标， ∃m∈（1 ,2,......,r） ，使Zm(a)＞Zm(b)。

那么则称个体b被个体a支配，若a不被种群其余任何个体支配，则称a为非支配个体，式中：r为求解目标数量。

种群的支配等级排序是一个循环分级的过程，本研究采用变量NP表示种群支配等级为P的个体集合，SP表示个体的支配个体集合，FP表示个体的被支配计数。首先找出整个种群中所有FP=0的个体，将其支配等级P设置为1，计入N1并统计每个个体对应的SP。然后遍历每个支配个体集合SP，找出其中FP的个体，将其支配等级P设置为2，计入N2同时统计SP。循环往复，直至完成对整个种群的支配等级排序。

完成种群支配等级排序后，由于同支配等级中可能含有多个个体，此时需对处于同一支配等级的个体再次进行排序。采用传统拥挤距离排序方法，个体间按照拥挤距离从大到小进行排序。该方法无须重新定义参数即可使整个解集在目标空间内均匀分布，可有效维持种群的多样性[13-14]。计算公式如下：

式中：di为第i个体拥挤距离；Zk(i+1)与Zk(i-1)分别表示了第i+1与i-1个体的第k目标函数值；Zkmax与Zkmin则代表种群中所有个体在第k目标函数上的最值。

2.1.3 多种群寻优策略

初始种群产生后，需进行迭代搜索优秀下锯方案，本研究提出一种多种群寻优策略（图5）。初始时产生多个种群a1，a2，…，an，随机选择其中一个作为父代种群A1，对其余初始种群进行支配等级排序并取出其中精英解集N1放入子代种群B1直至填满。将A1与B2并入中间种群C1，对C1进行支配等级排序和个体拥挤度排序，按支配等级和拥挤度距离区分C1以构造新父代种群A2。子代种群B2则同样通过随机产生初始种群选取其中的精英序列构造，同样通过合并A2与B2产生C2，对C2排序即可产生A3，重复上述步骤直至产生最终种群An。迭代过程中，子代种群的产生均由相应种群的优质个体组成，可保证每代种群Ak中均为优秀下锯方案。

图5 多种群寻优Fig.5 Screening the excellent solution sets through multiple populations

在多种群寻优过程中会不可避免地产生重复解集，而重复解集在进行支配等级排序时会被赋予同样的支配等级，在迭代过程中可能被重复选入新种群，影响后续锯切方案求解。因此，本研究在每次合并产生新种群时会对中间种群C进行一次重复检测，统计C中完全重复的多个解集，对于每个重复解集只选取其中第一个重复个体进入父代种群，有效消除重复个体，保证后续求解质量。

2.2 最终下锯方案求解

通过多种群寻优策略，最终可得到多组下锯方案，此时需在原含缺陷锯材中进行模拟锯切以选出最终下锯方案。但与无缺陷锯材锯切不同，锯切含缺陷锯材时，由于缺陷存在，下锯顺序会对出材率产生影响，因此，需对每一下锯方案寻找最佳下锯顺序。

遗传算法起源于进化算法，是一种模仿生物进化机制的全局搜索算法，常被用于求解排序、旅行商等问题，该算法通过对问题可能的解编码产生个体，每个个体即对应一种问题解决方案，采用选择、交叉、变异等遗传操作进行种群迭代，并采用适应度函数对种群进行评估以淘汰劣质解，使得种群不断进化，最终收敛至最优解[15]。因此，本研究选择遗传算法进行每一下锯方案的最优下锯顺序搜索，以最终种群An中第k种下锯方案Qk为例进行说明，假设。

2.2.1 初始种群生成与适应度计算

延续2.1.1小节中的编码方法，对Qk进行随机调序一次即生成一种新的下锯方案，重复n次即生成初始种群R1。采用毛边锯材出材率作为适应度函数，计算方法如下：

首先建立坐标系，以右下角为原点，为方便不同宽度毛边锯材计算，以距离锯材中心线下方250 mm处向左为X轴正方向，沿锯材最底端向上为Y轴正方向，通过四元数组（xn，yn，bn，hn）表示缺陷位置。对于种群中任意一个个体Pk，按以下步骤计算适应度（在整个计算过程中不计锯路损耗）。

图6 适应度计算Fig.6 The calculation of fitness

步骤1：首先去除锯材毛边，同时记录锯路初始纵坐标yl1，并依据Pk中宽度产生下一锯路纵坐标yl2=yl1+W1；

步骤2：依次读取缺陷，根据以下公式判断是否有缺陷位于yl1与yl2之间。

步骤3：若无缺陷位于两锯路之间，则产生完整坯料，记录坯料宽度与体积并通过Pk中下一个宽度更新锯路纵坐标，转回步骤2。若锯路之间存在缺陷，则进行步骤4，直至所有宽度读取完毕结束。

步骤4：统计位于锯路之间缺陷个数与位置，从左至右依次锯切，统计所产生短坯料宽度、体积和个数（小于150 mm的短坯料不记录），更新锯路纵坐标，转回步骤2。

步骤5：通过完整坯料总体积与短坯料总体积计算适应度。

式中：Vjk为采用第k种锯切方案锯切后完整坯料总体积；Vdk为采用第k种锯切方案切除缺陷后短坯料总体积；V为毛边锯材总体积。

2.2.2 遗传操作

1）选择操作：初始种群产生后，通过适应度对整个种群进行优劣区分，此时需选择优秀个体进行后续遗传操作。由于无精英策略的遗传算法不收敛[16]，因此每次选择前首先保存最大适应度个体，防止后续遗传操作对其进行破坏。对其余个体采用锦标赛选择，每次进行选择操作时随机选取2个种群个体，取适应度大者进入后续交叉、变异操作。

2）交叉操作：交叉是遗传算法核心操作，通过对选择操作产生优质个体进行基因互换，使整个种群不断进化。本研究采用片段匹配交叉，对于需交叉的2个父代，随机产生2个实数m、n，将父代中各自位于m和n之间的基因片段交换产生新子代个体。

图7 片段匹配交叉Fig.7 Partial-mapped crossover

图8 矛盾检测Fig.8 Conflict detection

与其他智能算法相同，遗传算法在求解过程中可能会陷入局部优解，其原因在于通过大量交叉后种群内部个体趋于相似，此时再进行交叉操作难以获得新解。为加强算法搜索新解的能力，本算法采用自适应交叉概率，在算法迭代前中期设置较大交叉概率，使得种群内部快速、大量交叉，加快算法寻优速度。随着迭代进行，种群内部相似度开始增大，则将交叉概率不断减小，主要通过后续变异操作搜索新优质解。交叉概率计算公式如下：

式中：k1为设置初始交叉概率；m为当前迭代次数；n为算法总迭代次数。

3）变异操作：采用基本位变异方式，变异时，随机选取基因上2个位置交换序列，若选取序列对应宽度相同，则重新选取，直至选取非重复宽度。同样设置自适应变异概率，随着迭代进行，变异概率逐渐增大，增强算法后期搜索新解能力。

式中：k2为设置初始变异概率。

算法求解总流程图如图9所示。

图9 算法总流程Fig.9 The overall flowchart of algorithm

3 算法仿真分析

3.1 算法参数设置

采用C++编程实现算法功能，并通过OpenCV C++编程显示仿真结果，编译器采用Visual Studio 2019，在CORE i7 2.00 GHz CPU，8 GB 内存的PC机上进行下文仿真测试，算法相关参数设置为：无缺陷情形下种群规模为150，迭代次数为100；含缺陷情形下种群规模为20，迭代次数为100，初始交叉概率为0.9，初始变异概率设置为0.2。横向截断长度设置3种，分别为1、2、3 m；坯料宽度为自输入，本研究设置了11种宽度，坯料价值系数由相应宽度计算得出，坯料越宽其价值越大。为保证求解质量，每次计算算法运行10次，取最优结果。

式中：Sn为宽度为Wn的坯料价值系数。

3.2 算法仿真测试

为验证算法的有效性，从辽宁某木材加工企业实测毛边锯材数据，使用不同横向截断长度、不同输入坯料宽度与不同毛边锯材进行算法仿真测试。

首先采用锯材a进行仿真测试，锯材实测模型如图10所示。其中锯材长度为6 050 mm，宽度从锯材底端（图中右端）至锯材顶端（图中左端）每隔1 m分别为350、340、340、330、320、330、330 mm，含14个缺陷。

图10 锯材a实测模型图Fig.10 Measured model diagram of sawn timber a

输入坯料宽度设置为50～150 mm（每10 mm一种宽度），采用不同的横向截断长度（1、2、3 m），分别使用传统等宽锯切方法（60、80 mm）与本算法对锯材a进行仿真锯切，数据统计结果见表1。图11中为不同横向截断长度下传统等宽锯切方法（80 mm）与本算法的仿真锯切结果。

图11 仿真锯切结果对比图Fig.11 The comparison diagram of simulation sawing results

由表1可知，与传统等宽锯切方法相比：横向截断长度设置为1 m时，本算法仿真锯切结果中完整坯料出材率平均提升了24.30%，总出材率平均提升了8.59%；横向截断长度设置为2 m时，本算法仿真锯切结果中完整坯料出材率平均提升了24.80%，总出材率平均提升了7.06%；横向截断长度设置为3 m时，本算法仿真锯切结果中完整坯料出材率平均提升了11.91%，总出材率平均提升了6.42%；说明在不同横向截断长度下，与传统等宽锯切方法相比，本算法均能够根据所输入坯料宽度，依据锯材缺陷位置提供合理下锯方案，高效使用锯材。

表1 3类横向截断长度下仿真锯切结果对比表Table 1 The comparison table of simulation sawing results in 3 types of transverse truncation lengths

更换锯材，采用锯材b进行仿真测试，锯材b实测模型图如图12所示。其中锯材长度为6 100 mm，宽度从锯材底端至锯材顶端每间隔1 m分别为360、360、360、350、340、340、350 mm，含11个缺陷。

图12 锯材b实测模型Fig.12 Measured model diagram of sawn timber b

采用2 m的横向截断长度，输入坯料宽度分别设置为50～100 mm(每5 mm一种宽度)、50～150 mm(每10 mm一种宽度)、50～200 mm(每15 mm一种宽度)，使用传统等宽锯切方法与本算法对锯材b进行模拟锯切，数据统计结果见表2。图13中举例说明了输入坯料宽度设置为50～100 mm时，采用传统等宽锯切方法（85 mm）与本算法的模拟锯切结果。

图13 仿真锯切结果对比Fig.13 The comparison diagram of simulation sawing results

表2 3类输入坯料宽度下仿真锯切结果对比表Table 2 The comparison table of simulation sawing results in three types of input widths

由表2可以看出，与传统等宽锯切方法相比，输入坯料宽度设置为50～100 mm时，本算法仿真锯切结果中完整坯料出材率平均提升了34.36%，总出材率平均提升了6.72%；输入坯料宽度设置为50～150 mm时，本算法仿真锯切结果中完整坯料出材率平均提升了36.45%，总出材率平均提升了12.73%；输入坯料宽度设置为50～200 mm时，本算法仿真锯切结果中完整坯料出材率平均提升了33.89%，总出材率平均提升了15.57%；说明在不同输入坯料宽度下，本算法同样能够提供合理的下锯方案。

为进一步验证本算法的有效性，随机选取实测锯材中5块不同的毛边锯材，选用2 m的横向截断长度，输入坯料宽度设置为50～150 mm(每10 mm一种宽度)，分别使用传统等宽锯切方法与本算法对锯材进行仿真锯切，数据统计结果见表3。

由表3可知，本算法的仿真锯切结果均优于传统等宽锯切方法，完整坯料出材率和总出材率明显提升，其中完整坯料出材率平均提升了12.62%、23.58%、21.01%、25.93%和24.25%，总出材率平均提升了5.16%、7.97%、6.62%、9.20%和4.88%，说明本算法能够针对不同锯材合理计算下锯方案。

表3 不同锯材的仿真锯切结果对比Table 3 Comparison of simulation sawing results in different sawn timbers

4 结论与讨论

4.1 结 论

为解决我国木材加工企业智能化加工能力不足和出材率低的问题，本研究提出了基于非支配排序与遗传算法的毛边锯材优化下锯算法，主要结论如下：

1）通过分析毛边锯材下锯方法，确定了先截断后纵解再截断的加工方法，并以此为依据将锯材出材率作为优化目标同时合理考虑坯料价值完成了优化下锯模型的构建。

2）求解无缺陷锯材下锯方案时，通过非支配排序与拥挤度排序确定个体之间的优劣，并提出了一种多种群寻优策略，快速寻找优秀下锯方案。使用遗传算法搜寻每一方案的最佳下锯顺序时，采用片段匹配完成基因交叉，并通过对照关系去除了基因矛盾，同时设置了自适应交叉变异概率来加强算法的搜索新解能力。

3）算法仿真测试结果表明，本研究提出的算法能够针对不同横向截断长度、不同输入坯料宽度与不同毛边锯材分别确定合理的下锯方案，为我国毛边锯材智能化锯切提供一种新的解决方案。

4.2 讨 论

本研究还存在一些不足之处：

1）由于确定最终下锯方案时是以锯材出材率作为求解目标，若毛边锯材上缺陷过多，那么通过无缺陷锯材下锯方案求解得到的部分高价值下锯方案因为坯料较宽，在出材率计算时将处于劣势，在后续的研究中，应当寻找出材率与坯料价值之间的平衡方法。

2）本研究中输入坯料宽度设置为11种，最终求解得到的下锯方案仅为给定输入宽度下的合理方案。在未来的研究中，应该扩大可输入坯料宽度种类，并合理调整无缺陷情形下种群大小，针对每一块毛边锯材求解更优秀的下锯方案。