基于K均值聚類和改進(jìn)遺傳算法的制絲工藝研究

方利梅 王柳婧 徐元根

摘要 制絲工藝是卷煙生產(chǎn)的重要工藝步驟，由于原料煙葉缺乏統(tǒng)一的性能指標(biāo)數(shù)據(jù)，傳統(tǒng)煙絲摻配主要采用人工經(jīng)驗?zāi)Ｊ絹磉M(jìn)行，因此傳統(tǒng)制絲工藝存在原料成本高、摻配速度慢、煙絲質(zhì)量不穩(wěn)定等缺點(diǎn)。為改進(jìn)制絲工藝，提出一種結(jié)合K均值聚類算法和改進(jìn)遺傳算法的自動煙絲摻配工藝。首先，基于原料煙葉生產(chǎn)卷煙產(chǎn)品質(zhì)量的不同，對原料煙葉數(shù)據(jù)進(jìn)行K均值聚類分析，從而實(shí)現(xiàn)原料煙葉的自動分級;然后，通過改進(jìn)遺傳算法的種群初始化策略、遺傳算子以及進(jìn)化終止條件，將煙絲摻配的各項約束條件融合到種群進(jìn)化過程中，在保證煙絲摻配的各項約束條件的前提下，兼顧算法求解的有效性和效率，從而實(shí)現(xiàn)制絲工藝的改進(jìn)。通過在給定數(shù)據(jù)上的仿真試驗，驗證該算法的有效性，在保證煙絲摻配質(zhì)量的情況下，有效降低了原料成本。

關(guān)鍵詞 聚類分析;遺傳算法;制絲工藝;卷煙生產(chǎn)

中圖分類號 TS 452 ?文獻(xiàn)標(biāo)識碼 A

文章編號 0517-6611（2019）12-0191-03

doi：10.3969/j.issn.0517-6611.2019.12.052

開放科學(xué)（資源服務(wù)）標(biāo)識碼（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

煙草行業(yè)是國家財政收入中占據(jù)重要地位的產(chǎn)業(yè)。隨著世界經(jīng)濟(jì)貿(mào)易的相互交融，我國煙草企業(yè)面臨著國際煙草企業(yè)越來越多的挑戰(zhàn)[1]。國內(nèi)的煙草企業(yè)在不同的卷煙產(chǎn)品上也存在激烈的競爭。因此，如何提升核心競爭力成為各企業(yè)亟待解決的問題。隨著信息技術(shù)的發(fā)展，將數(shù)據(jù)挖掘、智能分析等技術(shù)引入生產(chǎn)制造工藝中是大多數(shù)企業(yè)提升競爭力的常用手段。

殷君偉[2]提出了改進(jìn)的聚類分析方法，并將其用于服裝生產(chǎn)，根據(jù)工人操作熟練程度的不同，對工人進(jìn)行聚類，依此來配置合理的生產(chǎn)線;同時，通過對大量生產(chǎn)工時進(jìn)行聚類來獲得服裝生產(chǎn)的標(biāo)準(zhǔn)工時。宋楚平等[3]提出一個改進(jìn)的遺傳算法，并將其應(yīng)用到自動配棉模型的優(yōu)化求解中，在保證配棉模型約束條件的前提下，兼顧算法的效率和有效性，從而實(shí)現(xiàn)對自動配棉進(jìn)行優(yōu)化的目的。徐立云等[4]提出一種改進(jìn)的免疫遺傳算法，對原有加工工藝轉(zhuǎn)移重構(gòu)，從而形成新構(gòu)型下的工藝平衡與優(yōu)化。沈云波[5]提出一種改進(jìn)的粒子群算法，并將其用于卷接包生產(chǎn)排程的優(yōu)化。孫藝[6]提出一種混合粒子群算法，并將其用于置換流水車間調(diào)度方法的優(yōu)化。

制絲工藝是卷煙生產(chǎn)的重要工藝步驟[7]，制絲流程是將原料煙梗和煙葉分別加工成符合要求的梗絲和煙絲，然后按照某種工藝要求將其按照一定的比例進(jìn)行摻配，形成成品煙絲的過程。由于原料煙葉缺乏統(tǒng)一的性能指標(biāo)數(shù)據(jù)，傳統(tǒng)煙絲摻配主要采用人工經(jīng)驗?zāi)Ｊ絹磉M(jìn)行，因此傳統(tǒng)制絲工藝存在原料成本高、摻配速度慢、煙絲質(zhì)量不穩(wěn)定等缺點(diǎn)。因此，基于智能算法的自動煙絲摻配工藝的研究對于卷煙制絲工藝的改進(jìn)具有非常重要的意義。

筆者提出一種結(jié)合K均值聚類算法和改進(jìn)遺傳算法的自動煙絲摻配工藝。首先，基于原料煙葉生產(chǎn)卷煙產(chǎn)品質(zhì)量的不同，對原料煙葉數(shù)據(jù)進(jìn)行K均值聚類分析，從而確定最佳的原料煙葉;然后，通過改進(jìn)遺傳算法的種群初始化策略、遺傳算子以及進(jìn)化終止條件，將煙絲摻配的各項約束條件融合到種群進(jìn)化過程中，在保證煙絲摻配的各項約束條件的前提下，兼顧算法求解的有效性和效率，從而實(shí)現(xiàn)制絲工藝的改進(jìn)。

1 制絲工藝流程

制絲生產(chǎn)是卷煙生產(chǎn)流程中的重要工藝之一[8-9]，主要包括梗絲段、葉絲段和加香處理段3個部分。圖1為煙絲生產(chǎn)的主要流程圖。首先，將原料煙葉和煙梗分別加工成相應(yīng)的煙絲和梗絲。對煙梗原料先進(jìn)行清洗，然后利用潤梗機(jī)進(jìn)行潤梗，接著對潤梗處理后的煙梗進(jìn)行回潮、壓梗、切梗處理，再將其送入膨前梗絲柜，對柜中梗絲依次使用超級回潮機(jī)、烘梗絲機(jī)和梗絲加香機(jī)進(jìn)行處理后送入梗絲柜，在這些處理中都需要同時保證溫度和濕度的工藝要求。對原料葉片需要先進(jìn)行潤葉加香，然后進(jìn)行切絲、烘絲和回潮處理，最后送入葉絲予配柜。在梗絲和葉絲加工的各個環(huán)節(jié)中只有嚴(yán)格地控制溫度、濕度和香料的添加比例，才能生產(chǎn)出滿足工藝要求的梗絲和葉絲。對梗絲和葉絲按照一定比例進(jìn)行摻配，同時按照生產(chǎn)工藝的嚴(yán)格要求加入一定比例的殘煙絲、薄片絲和香料，最終得到符合要求的成品煙絲。最后，將成品煙絲送入貯絲柜作為后續(xù)卷包的原料。

2 基于K均值聚類算法的煙葉分級

2.1 K均值聚類算法

K均值聚類算法是一種經(jīng)典的數(shù)據(jù)分析方法，在輸入?yún)?shù)K的引導(dǎo)下，將d維空間中的數(shù)據(jù)自動的劃分為K個類，使得類內(nèi)對象相似，類間對象相異。K均值聚類算法的基本思想是從原始數(shù)據(jù)集中隨機(jī)的選取K個數(shù)作為初始中心，然后計算其他數(shù)據(jù)到各聚類中心的距離，再根據(jù)最相近原則，將每個數(shù)據(jù)分配到與其距離最近的聚類中心所代表的類中，接著利用各個類所包含的數(shù)據(jù)對象的均值來更新聚類中心，根據(jù)收斂函數(shù)判斷新的聚類中心與上次聚類中心的差異。如果滿足收斂條件，則算法結(jié)束，輸出聚類結(jié)果，否則繼續(xù)迭代分配，直到滿足收斂條件為止。傳統(tǒng)K均值聚類算法流程如下：

輸入樣本集：

D={x1，x2，…，xn}，包含n個對象的數(shù)據(jù)集，K個聚類

輸出的是K個聚類的集合C={C1，C2，…，CK}。

具體方法如下：

①從原始數(shù)據(jù)集D中任意選取K個對象作為初始聚類中心;

②根據(jù)最近鄰原則將其他對象分配到K個類;

③計算K個類別的均值，更新聚類中心;

④判斷聚類中心與上次的差異，滿足收斂條件則停止計算，否則從步驟②開始重復(fù)迭代。

2.2 基于K均值聚類分析的自動煙葉分級

傳統(tǒng)的煙葉篩選主要依靠人為經(jīng)驗判斷，以煙葉的外觀質(zhì)量、內(nèi)在質(zhì)量、物理特性、化學(xué)成分等為考察指標(biāo)，評判原料煙葉的等級。這種方法會嚴(yán)重受到環(huán)境人為因素的影響，篩選效率低，誤差大。這些問題都會嚴(yán)重影響卷煙制絲生產(chǎn)的進(jìn)度，從而制約著卷煙企業(yè)的發(fā)展。隨著制造業(yè)信息化技術(shù)的不斷發(fā)展，采用智能算法實(shí)現(xiàn)煙葉質(zhì)量自動分級的方案是提高煙絲制造工藝的一個有效手段。

基于大量的原料煙葉品質(zhì)特性數(shù)據(jù)，提出基于聚類分析的煙葉質(zhì)量自動分類方法，由于不同品質(zhì)的煙葉等級區(qū)分十分明顯，也就能實(shí)現(xiàn)煙葉的自動分級。

對于原料煙葉品質(zhì)的評判，主要從外觀質(zhì)量、內(nèi)在質(zhì)量、物理特性、化學(xué)成分和安全性等方面來考慮。原始煙葉數(shù)據(jù)往往存在錯誤性、不一致性和缺失性等問題。如果直接對這些數(shù)據(jù)進(jìn)行分析，可能會降低數(shù)據(jù)處理的速度，甚至?xí)?dǎo)致錯誤的分析結(jié)果。因此，在對數(shù)據(jù)進(jìn)行分析前，需要先對原始數(shù)據(jù)進(jìn)行預(yù)處理，使之滿足聚類算法的標(biāo)準(zhǔn)和規(guī)范。對于煙葉數(shù)據(jù)的品質(zhì)主要考慮以下特征指標(biāo)，具體見表1。

由此可以獲得一個具有5維特征的數(shù)據(jù)集D（外觀質(zhì)量、內(nèi)在質(zhì)量、物理特性、化學(xué)成分和安全性），為了區(qū)分這些數(shù)據(jù)對象，應(yīng)對其加上對象編號。利用來自某煙草公司提供的煙草原料數(shù)據(jù)作為樣本數(shù)據(jù)集，共包含來自不同批次的120 份原料煙葉數(shù)據(jù)。每個數(shù)據(jù)的各個維度特征都有獨(dú)特的分值評價標(biāo)準(zhǔn)，因此不同維度的特征在聚類分析前需要進(jìn)行標(biāo)準(zhǔn)化處理。這里統(tǒng)一采用零-均值標(biāo)準(zhǔn)化處理，即按照均值標(biāo)準(zhǔn)差進(jìn)行處理：新特征數(shù)據(jù)=（原始特征數(shù)據(jù)-均值）/標(biāo)準(zhǔn)差。在煙葉原料的分類上，按照非常差、差、一般、好、非常好5個等級來區(qū)分，因此聚類分析的類別參數(shù)K=5。然后，隨機(jī)選取5個樣本作為初始的聚類中心。最后，迭代地進(jìn)行聚類優(yōu)化，直到收斂輸出聚類結(jié)果。120例原料煙葉的聚類分析結(jié)果如圖2所示。

3 結(jié)合改進(jìn)遺傳算法的煙絲摻配方法

從煙絲加工流程可看出，在完成煙絲和梗絲的加工后，需要通過一定的摻配工藝將原料煙絲、梗絲、薄片絲和香料等制成成品煙絲。傳統(tǒng)的摻配工藝依賴于人工經(jīng)驗，摻配速度慢，成本高，摻配質(zhì)量不穩(wěn)定。隨著人工智能技術(shù)的發(fā)展，為自動煙絲摻配提供了技術(shù)支持。由于原料煙絲存在多樣性和差異性等特點(diǎn)以及各種原料摻配比例、煙絲品質(zhì)指標(biāo)等約束，使得自動煙絲摻配成為一個有挑戰(zhàn)的任務(wù)。由于煙絲摻配通常采用線性規(guī)劃的方法，而線性規(guī)劃實(shí)際上是一種最優(yōu)化方法，其決策變量、約束條件和資源參數(shù)的關(guān)系能很好地反映煙絲參配的實(shí)際情況，通用性很好，但求解過程容易陷入局部最優(yōu)。為解決線性規(guī)劃下全局尋優(yōu)的缺陷，這里提出一種改進(jìn)的遺傳算法，對煙絲自動摻配模型進(jìn)行求解，從而實(shí)現(xiàn)煙絲摻配的最優(yōu)化。

3.1 煙絲自動摻配模型的建立

原料成本占整個煙葉成本的很大部分，因此煙絲摻配質(zhì)量將直接影響企業(yè)的生產(chǎn)效益和卷煙質(zhì)量。在煙絲摻配過程中，需要考慮原料煙葉的種類、煙絲的性能指標(biāo)、卷絲的品質(zhì)和工藝條件、經(jīng)濟(jì)指標(biāo)等，研究這些指標(biāo)之間的關(guān)系，統(tǒng)籌規(guī)劃，建立煙絲摻配的目標(biāo)模型。

對于煙絲摻配模型可從以下2種函數(shù)表達(dá)方式來考慮：一是成本最小化;二是摻配質(zhì)量指標(biāo)誤差最小化。這2種方式都需要考慮成本與質(zhì)量的統(tǒng)一，二者的本質(zhì)是一致的，因為原料的技術(shù)品質(zhì)與價格是密切相關(guān)的，確定了原料品質(zhì)也就確定了價格，反之亦然。這里采用最小煙絲摻配成本作為目標(biāo)函數(shù)。

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

式中，pi為第i種原料的價格;xi為第i種原料在摻配中所占的比例;n為不同批次原料煙絲的種類數(shù)。根據(jù)煙絲摻配要求，經(jīng)過摻配工藝后的各項品質(zhì)（如外在顏色光澤、內(nèi)在氣味、物理性質(zhì)、化學(xué)成分和安全性）必須在規(guī)定的要求內(nèi)，因此有以下約束：

①原絲比例約束。

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

式中，各原料的比例之和為1，max（i）和min（i）分別為第i種原絲的比例上限和比例下限，這個參數(shù)通常來自先驗數(shù)據(jù)。

②主成分限制。

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

式中，ki為主體成分因子，如果第i類原料被選中，ki取值為1，否則為0;C為原絲主體成分要求值。

③原絲品質(zhì)指標(biāo)約束。

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

式中，Pij為第j種煙絲的第i項品質(zhì)指標(biāo)值;Ai、Bi分別為摻配煙絲的第i項指標(biāo)值的下限和上限。

3.2 改進(jìn)遺傳算法對模型的求解

由于傳統(tǒng)遺傳算法（簡稱BGA）具有很好的魯棒性和全局尋優(yōu)能力，但在求解煙絲摻配問題時，由于隨機(jī)生成的個體種群會導(dǎo)致大量無效個體參與運(yùn)算。另外，基本遺傳算法直接使用適應(yīng)度的大小或者迭代次數(shù)作為進(jìn)化終止條件，在種群優(yōu)化過程中缺乏對約束條件的監(jiān)控，這意味著簡單以成本為適應(yīng)度計算的進(jìn)化過程會過早收斂。這里提出一種改進(jìn)的遺傳算法（簡稱IGA）來求解自動煙絲摻配問題。改進(jìn)算法流程如下：

（1）采用整數(shù)編碼，首先根據(jù)庫存和生產(chǎn)情況確定煙絲批次種類數(shù)和限定摻絲總包數(shù)以及各批煙絲使用包數(shù)的上限ki（i=1，2，…，m）。在實(shí)際摻配方案中，各批次煙絲的包數(shù)均為整數(shù)，所以基因編碼采用整數(shù)編碼，1組參數(shù)（x1，x2，…，xi）為1個染色體，xi表示每種原料的包數(shù)，在[0，n-1]取值。采用上述編碼不僅能有效滿足實(shí)際整包取絲的要求，而且能縮小xi的搜索空間，提高求解效率。

（2）初始種群生成策略。這里拋棄隨機(jī)種群初始化的做法，采用以下做法來初始化種群：

①染色體（x1，x2，…，xi）中的xi隨機(jī)從[0，n-1]中選取，當(dāng)xi>ki時舍棄，繼續(xù)取值，最后對其進(jìn)行縮放。

②每生成1個個體，就將其放在集合X中，計數(shù)加1，然后重復(fù)步驟①，直到集合X的長度滿足種群的大小S。

③適應(yīng)度函數(shù)。它是衡量每個個體優(yōu)劣程度的參數(shù)，其好壞對遺傳操作有著重要的影響，也直接影響著求解的效率。利用公式（1）來計算適應(yīng)度函數(shù)。

④選擇操作。為避免最優(yōu)個體在雜交操作中被破壞，這里采用的策略是用上一輪的最優(yōu)個體來代替此輪的最差個體，其余個體則采用輪盤賭發(fā)選擇生成新的種群。

⑤交叉操作。為了擴(kuò)大搜索范圍，增大種群的離散程度，提高全局尋優(yōu)能力，這里采用隨機(jī)單點(diǎn)交叉法來生成新的個體。

⑥變異操作。這里采用近鄰變異操作來實(shí)現(xiàn)煙絲摻配中的基因變化。

⑦收斂條件。適應(yīng)度反映了摻配煙絲價格相對標(biāo)準(zhǔn)煙絲價格的變化情況。為了監(jiān)控種群進(jìn)化的收斂程度，提高算法的效率，這里采用下式的臨界值e作為終止條件。

1SSi=1（Yi-ii）2

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

式中，S是步驟④精英策略中前10%的最優(yōu)個體;Y是最優(yōu)個體的適應(yīng)度;e為這些最優(yōu)個體收斂的臨界值，經(jīng)驗取值范圍為[0.000 004，0.000 04]。當(dāng)最優(yōu)個體群的收斂值變化很小且滿足公式（4）的約束條件時，停止優(yōu)化，輸出最優(yōu)解;否則繼續(xù)迭代優(yōu)化，直到達(dá)到最大迭代次數(shù)。

3.3 煙絲自動摻配實(shí)例

在實(shí)際煙絲摻配中，根據(jù)實(shí)際情況和專家經(jīng)驗，主要考慮煙絲的顏色光澤、內(nèi)在氣味、物理性質(zhì)、化學(xué)成分和安全性等主要指標(biāo)，各項指標(biāo)在具體量化時都以專家在百分制下的打分作為依據(jù)。煙絲摻配的原料情況如表2所示。

煙絲摻配技術(shù)要求如下：顏色光澤≥60，內(nèi)在氣味≥65，物理性質(zhì)≤70，化學(xué)成分為45～65，安全性≥85。使用遺傳算法進(jìn)行求解的參數(shù)設(shè)置如下：種群大小S=40，最大遺傳代數(shù)n=250，交叉系數(shù)α=0.75，變異系數(shù)β=0.03，收斂臨界值e=0.000 04。

最后，采用基礎(chǔ)遺傳算法（BGA）和改進(jìn)遺傳算法來對煙絲摻配過程進(jìn)行求解。結(jié)果表明，改進(jìn)遺傳算法能夠在保證較低原料價格的同時，使得摻配煙絲的各項指標(biāo)滿足配煙技術(shù)的要求。

4 結(jié)論

筆者針對卷煙生產(chǎn)中的制絲工藝問題開展研究，由于傳統(tǒng)制絲工藝存在原料成本高、摻配速度慢、煙絲質(zhì)量不穩(wěn)定等缺點(diǎn)，因此提出一種結(jié)合K均值聚類算法和改進(jìn)遺傳算法的自動煙絲摻配工藝。首先，基于原料煙葉生產(chǎn)卷煙產(chǎn)品質(zhì)量的不同，對原料煙葉數(shù)據(jù)進(jìn)行K均值聚類分析，從而自動確定原料煙葉等級;然后，通過改進(jìn)遺傳算法的種群初始化策略、遺傳算子以及進(jìn)化終止條件，將煙絲摻配的各項約束條件融合到種群進(jìn)化過程中，在保證煙絲摻配的各項約束條件的前提下，兼顧算法求解的有效性和效率，從而實(shí)現(xiàn)制絲

工藝的改進(jìn)。該研究提出的K均值聚類算法和改進(jìn)遺傳算法有望為卷煙生產(chǎn)中的煙絲自動摻配工藝提供參考。

參考文獻(xiàn)

[1] 楊啟成.卷煙生產(chǎn)物流系統(tǒng)的優(yōu)化設(shè)計及管理研究：以紅塔生產(chǎn)物流為例[D].昆明：昆明理工大學(xué)，2013.

[2] 殷君偉.K-均值聚類算法改進(jìn)及在服裝生產(chǎn)的應(yīng)用研究[D].蘇州：蘇州大學(xué)，2013.

[3] 宋楚平，李少芹.應(yīng)用改進(jìn)遺傳算法的自動配棉模型優(yōu)化與應(yīng)用[J].紡織學(xué)報，2016，37（9）：151-155.

[4] 徐立云，劉偉，樓科文，等.基于改進(jìn)免疫遺傳算法的加工工藝重構(gòu)[J].同濟(jì)大學(xué)學(xué)報，2016，44（6）：907-914，921.

[5] 沈云波.基于改進(jìn)粒子群-禁忌搜索的卷接包生產(chǎn)排程優(yōu)化[D].長沙：湖南大學(xué)，20014.

[6] 孫藝.基于混合粒子群優(yōu)化的置換流水車間調(diào)度方法研究[D].武漢：華中科技大學(xué)，2011.

[7] 王旭鋒，劉蒙蒙，李向陽，等.制絲工藝參數(shù)對煙絲結(jié)構(gòu)和卷煙感官質(zhì)量的影響[J].安徽農(nóng)業(yè)科學(xué)，2016，44（13）：61-62，71.

[8] 夏秀芳，彭威，呂希勝.卷煙廠制絲線生產(chǎn)過程建模與計劃仿真[J].機(jī)械設(shè)計與制造，2009（5）：231-233.

[9] 陳恩，谷德良.制造執(zhí)行系統(tǒng)（MES）在卷煙制絲生產(chǎn)管理中的應(yīng)用[J].當(dāng)代經(jīng)濟(jì)，2010（2）：24-25.