基于K均值聚类和改进遗传算法的制丝工艺研究

方利梅 王柳婧 徐元根

摘要 制丝工艺是卷烟生产的重要工艺步骤，由于原料烟叶缺乏统一的性能指标数据，传统烟丝掺配主要采用人工经验模式来进行，因此传统制丝工艺存在原料成本高、掺配速度慢、烟丝质量不稳定等缺点。为改进制丝工艺，提出一种结合K均值聚类算法和改进遗传算法的自动烟丝掺配工艺。首先，基于原料烟叶生产卷烟产品质量的不同，对原料烟叶数据进行K均值聚类分析，从而实现原料烟叶的自动分级;然后，通过改进遗传算法的种群初始化策略、遗传算子以及进化终止条件，将烟丝掺配的各项约束条件融合到种群进化过程中，在保证烟丝掺配的各项约束条件的前提下，兼顾算法求解的有效性和效率，从而实现制丝工艺的改进。通过在给定数据上的仿真试验，验证该算法的有效性，在保证烟丝掺配质量的情况下，有效降低了原料成本。

关键词 聚类分析;遗传算法;制丝工艺;卷烟生产

中图分类号 TS 452  文献标识码 A

文章编号 0517-6611（2019）12-0191-03

doi：10.3969/j.issn.0517-6611.2019.12.052

开放科学（资源服务）标识码（OSID）：

Abstract Tobacco process is an important procedure in cigarette production.Due to the lack of uniform performance index of raw material tobacco，traditional cut tobacco blending mainly uses artificial experience model.Therefore，the traditional cut tobacco process has the disadvantages of high raw material cost，slow blending speed and unstable cut tobacco quality.In order to improve the cut tobacco process，this paper proposed an automatic cut tobacco blending process based on Kmeans clustering algorithm and improved genetic algorithm.Firstly，due to different quality of tobacco products produced by raw material tobacco，a Kmeans clustering analysis was carried out to automatic classification of the tobacco leaf  of raw material.Then，according to the improved genetic algorithm and corresponding initialization strategy，genetic operators and evolution termination conditions，we can fuse all the constraint conditions of tobacco blending into the population evolution process.In the guarantee of various constraint conditions of tobacco blending，we can obtain the improvement tobacco process and achieve the effectiveness and efficiency of the algorithm.The validity of this algorithm was verified by the simulation experiment on the given data，which effectively reduced the cost of raw materials in the case of ensuring the quality of tobacco blending.

Key words Clustering analysis;Genetic algorithm;Cut tobacco process;Cigarette production

煙草行业是国家财政收入中占据重要地位的产业。随着世界经济贸易的相互交融，我国烟草企业面临着国际烟草企业越来越多的挑战[1]。国内的烟草企业在不同的卷烟产品上也存在激烈的竞争。因此，如何提升核心竞争力成为各企业亟待解决的问题。随着信息技术的发展，将数据挖掘、智能分析等技术引入生产制造工艺中是大多数企业提升竞争力的常用手段。

殷君伟[2]提出了改进的聚类分析方法，并将其用于服装生产，根据工人操作熟练程度的不同，对工人进行聚类，依此来配置合理的生产线;同时，通过对大量生产工时进行聚类来获得服装生产的标准工时。宋楚平等[3]提出一个改进的遗传算法，并将其应用到自动配棉模型的优化求解中，在保证配棉模型约束条件的前提下，兼顾算法的效率和有效性，从而实现对自动配棉进行优化的目的。徐立云等[4]提出一种改进的免疫遗传算法，对原有加工工艺转移重构，从而形成新构型下的工艺平衡与优化。沈云波[5]提出一种改进的粒子群算法，并将其用于卷接包生产排程的优化。孙艺[6]提出一种混合粒子群算法，并将其用于置换流水车间调度方法的优化。

制丝工艺是卷烟生产的重要工艺步骤[7]，制丝流程是将原料烟梗和烟叶分别加工成符合要求的梗丝和烟丝，然后按照某种工艺要求将其按照一定的比例进行掺配，形成成品烟丝的过程。由于原料烟叶缺乏统一的性能指标数据，传统烟丝掺配主要采用人工经验模式来进行，因此传统制丝工艺存在原料成本高、掺配速度慢、烟丝质量不稳定等缺点。因此，基于智能算法的自动烟丝掺配工艺的研究对于卷烟制丝工艺的改进具有非常重要的意义。

笔者提出一种结合K均值聚类算法和改进遗传算法的自动烟丝掺配工艺。首先，基于原料烟叶生产卷烟产品质量的不同，对原料烟叶数据进行K均值聚类分析，从而确定最佳的原料烟叶;然后，通过改进遗传算法的种群初始化策略、遗传算子以及进化终止条件，将烟丝掺配的各项约束条件融合到种群进化过程中，在保证烟丝掺配的各项约束条件的前提下，兼顾算法求解的有效性和效率，从而实现制丝工艺的改进。

1 制丝工艺流程

制丝生产是卷烟生产流程中的重要工艺之一[8-9]，主要包括梗丝段、叶丝段和加香处理段3个部分。图1为烟丝生产的主要流程图。首先，将原料烟叶和烟梗分别加工成相应的烟丝和梗丝。对烟梗原料先进行清洗，然后利用润梗机进行润梗，接着对润梗处理后的烟梗进行回潮、压梗、切梗处理，再将其送入膨前梗丝柜，对柜中梗丝依次使用超级回潮机、烘梗丝机和梗丝加香机进行处理后送入梗丝柜，在这些处理中都需要同时保证温度和湿度的工艺要求。对原料叶片需要先进行润叶加香，然后进行切丝、烘丝和回潮处理，最后送入叶丝予配柜。在梗丝和叶丝加工的各个环节中只有严格地控制温度、湿度和香料的添加比例，才能生产出满足工艺要求的梗丝和叶丝。对梗丝和叶丝按照一定比例进行掺配，同时按照生产工艺的严格要求加入一定比例的残烟丝、薄片丝和香料，最终得到符合要求的成品烟丝。最后，将成品烟丝送入贮丝柜作为后续卷包的原料。

2 基于K均值聚类算法的烟叶分级

2.1 K均值聚类算法

K均值聚类算法是一种经典的数据分析方法，在输入参数K的引导下，将d维空间中的数据自动的划分为K个类，使得类内对象相似，类间对象相异。K均值聚类算法的基本思想是从原始数据集中随机的选取K个数作为初始中心，然后计算其他数据到各聚类中心的距离，再根据最相近原则，将每个数据分配到与其距离最近的聚类中心所代表的类中，接着利用各个类所包含的数据对象的均值来更新聚类中心，根据收敛函数判断新的聚类中心与上次聚类中心的差异。如果满足收敛条件，则算法结束，输出聚类结果，否则继续迭代分配，直到满足收敛条件为止。传统K均值聚类算法流程如下：

输入样本集：

D={x1，x2，…，xn}，包含n个对象的数据集，K个聚类

输出的是K个聚类的集合C={C1，C2，…，CK}。

具体方法如下：

①从原始数据集D中任意选取K个对象作为初始聚类中心;

②根据最近邻原则将其他对象分配到K个类;

③计算K个类别的均值，更新聚类中心;

④判断聚类中心与上次的差异，满足收敛条件则停止计算，否则从步骤②开始重复迭代。

2.2 基于K均值聚类分析的自动烟叶分级

传统的烟叶筛选主要依靠人为经验判断，以烟叶的外观质量、内在质量、物理特性、化学成分等为考察指标，评判原料烟叶的等级。这种方法会严重受到环境人为因素的影响，筛选效率低，误差大。这些问题都会严重影响卷烟制丝生产的进度，从而制约着卷烟企业的发展。随着制造业信息化技术的不断发展，采用智能算法实现烟叶质量自动分级的方案是提高烟丝制造工艺的一个有效手段。

基于大量的原料烟叶品质特性数据，提出基于聚类分析的烟叶质量自动分类方法，由于不同品质的烟叶等级区分十分明显，也就能实现烟叶的自动分级。

对于原料烟叶品质的评判，主要从外观质量、内在质量、物理特性、化学成分和安全性等方面來考虑。原始烟叶数据往往存在错误性、不一致性和缺失性等问题。如果直接对这些数据进行分析，可能会降低数据处理的速度，甚至会导致错误的分析结果。因此，在对数据进行分析前，需要先对原始数据进行预处理，使之满足聚类算法的标准和规范。对于烟叶数据的品质主要考虑以下特征指标，具体见表1。

由此可以获得一个具有5维特征的数据集D（外观质量、内在质量、物理特性、化学成分和安全性），为了区分这些数据对象，应对其加上对象编号。利用来自某烟草公司提供的烟草原料数据作为样本数据集，共包含来自不同批次的120 份原料烟叶数据。每个数据的各个维度特征都有独特的分值评价标准，因此不同维度的特征在聚类分析前需要进行标准化处理。这里统一采用零-均值标准化处理，即按照均值标准差进行处理：新特征数据=（原始特征数据-均值）/标准差。在烟叶原料的分类上，按照非常差、差、一般、好、非常好5个等级来区分，因此聚类分析的类别参数K=5。然后，随机选取5个样本作为初始的聚类中心。最后，迭代地进行聚类优化，直到收敛输出聚类结果。120例原料烟叶的聚类分析结果如图2所示。

3 结合改进遗传算法的烟丝掺配方法

从烟丝加工流程可看出，在完成烟丝和梗丝的加工后，需要通过一定的掺配工艺将原料烟丝、梗丝、薄片丝和香料等制成成品烟丝。传统的掺配工艺依赖于人工经验，掺配速度慢，成本高，掺配质量不稳定。随着人工智能技术的发展，为自动烟丝掺配提供了技术支持。由于原料烟丝存在多样性和差异性等特点以及各种原料掺配比例、烟丝品质指标等约束，使得自动烟丝掺配成为一个有挑战的任务。由于烟丝掺配通常采用线性规划的方法，而线性规划实际上是一种最优化方法，其决策变量、约束条件和资源参数的关系能很好地反映烟丝参配的实际情况，通用性很好，但求解过程容易陷入局部最优。为解决线性规划下全局寻优的缺陷，这里提出一种改进的遗传算法，对烟丝自动掺配模型进行求解，从而实现烟丝掺配的最优化。

3.1 烟丝自动掺配模型的建立

原料成本占整个烟叶成本的很大部分，因此烟丝掺配质量将直接影响企业的生产效益和卷烟质量。在烟丝掺配过程中，需要考虑原料烟叶的种类、烟丝的性能指标、卷丝的品质和工艺条件、经济指标等，研究这些指标之间的关系，统筹规划，建立烟丝掺配的目标模型。

对于烟丝掺配模型可从以下2种函数表达方式来考虑：一是成本最小化;二是掺配质量指标误差最小化。这2种方式都需要考虑成本与质量的统一，二者的本质是一致的，因为原料的技术品质与价格是密切相关的，确定了原料品质也就确定了价格，反之亦然。这里采用最小烟丝掺配成本作为目标函数。

minF（x）=ni=1（pi×xi）（1）

式中，pi为第i种原料的价格;xi为第i种原料在掺配中所占的比例;n为不同批次原料烟丝的种类数。根据烟丝掺配要求，经过掺配工艺后的各项品质（如外在颜色光泽、内在气味、物理性质、化学成分和安全性）必须在规定的要求内，因此有以下约束：

①原丝比例约束。

ni=1xi=1，min（i）≤xi≤max（i）（2）

式中，各原料的比例之和为1，max（i）和min（i）分别为第i种原丝的比例上限和比例下限，这个参数通常来自先验数据。

②主成分限制。

ni=1（ki×xi）≤C（3）

式中，ki为主体成分因子，如果第i类原料被选中，ki取值为1，否则为0;C为原丝主体成分要求值。

③原丝品质指标约束。

Ai≤mi=1nj=1（Pij×xi）≤Bi（4）

式中，Pij为第j种烟丝的第i项品质指标值;Ai、Bi分别为掺配烟丝的第i项指标值的下限和上限。

3.2 改进遗传算法对模型的求解

由于传统遗传算法（简称BGA）具有很好的鲁棒性和全局寻优能力，但在求解烟丝掺配问题时，由于随机生成的个体种群会导致大量无效个体参与运算。另外，基本遗传算法直接使用适应度的大小或者迭代次数作为进化终止条件，在种群优化过程中缺乏对约束条件的监控，这意味着简单以成本为适应度计算的进化过程会过早收敛。这里提出一种改进的遗传算法（简称IGA）来求解自动烟丝掺配问题。改进算法流程如下：

（1）采用整数编码，首先根据库存和生产情况确定烟丝批次种类数和限定掺丝总包数以及各批烟丝使用包数的上限ki（i=1，2，…，m）。在实际掺配方案中，各批次烟丝的包数均为整数，所以基因编码采用整数编码，1组参数（x1，x2，…，xi）为1个染色体，xi表示每种原料的包数，在[0，n-1]取值。采用上述编码不仅能有效满足实际整包取丝的要求，而且能缩小xi的搜索空间，提高求解效率。

（2）初始种群生成策略。这里抛弃随机种群初始化的做法，采用以下做法来初始化种群：

①染色体（x1，x2，…，xi）中的xi随机从[0，n-1]中选取，当xi>ki时舍弃，继续取值，最后对其进行缩放。

②每生成1个个体，就将其放在集合X中，计数加1，然后重复步骤①，直到集合X的长度满足种群的大小S。

③适应度函数。它是衡量每个个体优劣程度的参数，其好坏对遗传操作有着重要的影响，也直接影响着求解的效率。利用公式（1）来计算适应度函数。

④选择操作。为避免最优个体在杂交操作中被破坏，这里采用的策略是用上一轮的最优个体来代替此轮的最差个体，其余个体则采用轮盘赌发选择生成新的种群。

⑤交叉操作。为了扩大搜索范围，增大种群的离散程度，提高全局寻优能力，这里采用随机单点交叉法来生成新的个体。

⑥变异操作。这里采用近邻变异操作来实现烟丝掺配中的基因变化。

⑦收敛条件。适应度反映了掺配烟丝价格相对标准烟丝价格的变化情况。为了监控种群进化的收敛程度，提高算法的效率，这里采用下式的临界值e作为终止条件。

1SSi=1（Yi-ii）2

Ai≤mi=1nj=1（Pij×xi）≤Bi（5）

式中，S是步骤④精英策略中前10%的最优个体;Y是最优个体的适应度;e为这些最优个体收敛的临界值，经验取值范围为[0.000 004，0.000 04]。当最优个体群的收敛值变化很小且满足公式（4）的约束条件时，停止优化，输出最优解;否则继续迭代优化，直到达到最大迭代次数。

3.3 烟丝自动掺配实例

在实际烟丝掺配中，根据实际情况和专家经验，主要考虑烟丝的颜色光泽、内在气味、物理性质、化学成分和安全性等主要指标，各项指标在具体量化时都以专家在百分制下的打分作为依据。烟丝掺配的原料情况如表2所示。

烟丝掺配技术要求如下：颜色光泽≥60，内在气味≥65，物理性质≤70，化学成分为45～65，安全性≥85。使用遗传算法进行求解的参数设置如下：种群大小S=40，最大遗传代数n=250，交叉系数α=0.75，变异系数β=0.03，收敛临界值e=0.000 04。

最后，采用基础遗传算法（BGA）和改进遗传算法来对烟丝掺配过程进行求解。结果表明，改进遗传算法能够在保证较低原料价格的同时，使得掺配烟丝的各项指标满足配烟技术的要求。

4 结论

笔者针对卷烟生产中的制丝工艺问题开展研究，由于传统制丝工艺存在原料成本高、掺配速度慢、烟丝质量不稳定等缺点，因此提出一种结合K均值聚类算法和改进遗传算法的自动烟丝掺配工艺。首先，基于原料烟叶生产卷烟产品质量的不同，对原料烟叶数据进行K均值聚类分析，从而自动确定原料烟叶等级;然后，通过改进遗传算法的种群初始化策略、遗传算子以及进化终止条件，将烟丝掺配的各项约束条件融合到种群进化过程中，在保证烟丝掺配的各项约束条件的前提下，兼顾算法求解的有效性和效率，从而实现制丝

工艺的改进。该研究提出的K均值聚类算法和改进遗传算法有望为卷烟生产中的烟丝自动掺配工艺提供参考。

参考文献

[1] 杨启成.卷烟生产物流系统的优化设计及管理研究：以红塔生产物流为例[D].昆明：昆明理工大学，2013.

[2] 殷君伟.K-均值聚类算法改进及在服装生产的应用研究[D].苏州：苏州大学，2013.

[3] 宋楚平，李少芹.应用改进遗传算法的自动配棉模型优化与应用[J].纺织学报，2016，37（9）：151-155.

[4] 徐立云，刘伟，楼科文，等.基于改进免疫遗传算法的加工工艺重构[J].同济大学学报，2016，44（6）：907-914，921.

[5] 沈云波.基于改进粒子群-禁忌搜索的卷接包生产排程优化[D].长沙：湖南大学，20014.

[6] 孙艺.基于混合粒子群优化的置换流水车间调度方法研究[D].武汉：华中科技大学，2011.

[7] 王旭鋒，刘蒙蒙，李向阳，等.制丝工艺参数对烟丝结构和卷烟感官质量的影响[J].安徽农业科学，2016，44（13）：61-62，71.

[8] 夏秀芳，彭威，吕希胜.卷烟厂制丝线生产过程建模与计划仿真[J].机械设计与制造，2009（5）：231-233.

[9] 陈恩，谷德良.制造执行系统（MES）在卷烟制丝生产管理中的应用[J].当代经济，2010（2）：24-25.