基于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.