應用改進遺傳算法的自動配棉模型優(yōu)化與應用

宋楚平, 李少芹

(江蘇工程職業(yè)技術學院 機電工程學院, 江蘇 南通 226007)

應用改進遺傳算法的自動配棉模型優(yōu)化與應用

宋楚平, 李少芹

(江蘇工程職業(yè)技術學院 機電工程學院, 江蘇 南通 226007)

針對配棉工藝具有多約束條件的特點和現(xiàn)有自動配棉的不足，提出將改進的遺傳算法應用到線性規(guī)劃優(yōu)化求解問題中，通過改進遺傳算法的初始種群生成策略、遺傳算子和進化收斂條件，將配棉約束條件動態(tài)融合到種群進化過程中，在保證配棉約束條件的前提下，兼顧了求解的效率和有效性，以達到對自動配棉進行優(yōu)化的目的。應用結果顯示：用改進遺傳算法對配棉模型的求解優(yōu)于基本遺傳算法，且配棉的各項指標值符合生產(chǎn)技術要求，在滿足混棉質量的前提下，該方法能指導技術人員對候選棉和庫存棉做出更合理的選擇，有效降低了配棉成本。

自動配棉； 配棉模型； 改進遺傳算法； 多約束條件

配棉是紡織企業(yè)的一項常規(guī)性技術工作，在自動配棉之前，由于原棉缺乏統(tǒng)一的性能指標數(shù)據(jù)，配棉工作主要采用傳統(tǒng)的人工經(jīng)驗模式，配棉速度慢，成本較高，紗線質量不穩(wěn)定。隨著計算機、人工智能等技術的發(fā)展，以及HVI(high volume instrument，大容量棉花纖維測試儀)公檢體制在我國的實施和推廣，為自動配棉提供了數(shù)據(jù)基礎和技術支撐。自動配棉一直是一個復雜的工作過程，由于原棉性能多樣性和差異性的特點，另受每組棉花的配比、配棉品質指標、生產(chǎn)成本和紗線質量的多條件約束，目前紡織企業(yè)還沒有完善的技術手段對配棉質量進行控制和預測，導致配棉成本和質量波動性較大，影響了企業(yè)的經(jīng)濟效益和生產(chǎn)競爭力。針對該問題，國內(nèi)外學者和行業(yè)專家進行了大量的研究，如按棉臺容量和混棉指標建立配棉模型[1]，用PSO(particle swarm optimization)算法對配棉目標函數(shù)進行優(yōu)化[2]，用組合方案法構建配棉模型[3]等?，F(xiàn)有的自動配棉系統(tǒng)主要采用線性規(guī)劃法和組合方案法，當原棉種類數(shù)大于4時，組合的方案數(shù)顯著增加，計算量十分龐大、耗時過長，難以對眾多方案的成紗質量進行客觀評價，可能會使該方法失去實用價值。線性規(guī)劃實際是一種最優(yōu)化問題，其決策變量、約束條件和資源參數(shù)的關系能較好地反映配棉的實際情況，通用性和適用性較強，計算精度高，但求解過程易陷入局部優(yōu)先，可能無法尋到全局最優(yōu)解[4]。

為解決線性規(guī)劃法下自動配棉全局尋優(yōu)能力不強的缺陷，本文利用遺傳算法具有較強的魯棒性和全局搜索能力[5]，在此基礎上提出一種改進的遺傳算法對自動配棉線性模型進行求解，以提高配棉的最優(yōu)化和有效性。

1 應用HVI的配棉模型建立

1.1 HVI數(shù)據(jù)

HVI數(shù)據(jù)是采用HVI檢測設備對原棉纖維成熟度、細度、棉結、單纖維強力、色澤、等級的指標數(shù)據(jù)，該數(shù)據(jù)表征了原棉的重要性能。隨著我國棉花新標準的實施和HVI公檢制度的推進，原棉的收購、加工、銷售和使用各環(huán)節(jié)己經(jīng)轉向利用HVI檢測，使得每個棉包都有1組HVI數(shù)據(jù)，利用公檢HVI數(shù)據(jù)進行計算機配棉從根本上保證了HVI數(shù)據(jù)的權威性和一致性，為實現(xiàn)自動配棉奠定了數(shù)據(jù)基礎。

自動配棉是根據(jù)紡紗質量要求對庫存原棉進行混合，既要盡可能控制生產(chǎn)成本，又要滿足混棉的質量指標要求的過程。無論是購棉還是配棉，都可以在HVI數(shù)據(jù)的支持下做到合理采購原料，科學設計配棉方案，并能有效預測紗線質量。

1.2 配棉模型

原料成本約占到棉紡企業(yè)整個成本的70%，因此，配棉的好壞將直接影響企業(yè)的生產(chǎn)效益和紗線質量，是一項經(jīng)濟性和技術性很強的工作。在配棉過程中，要考慮原棉的種類、原棉性能指標、紡紗的品質和工藝條件、經(jīng)濟指標等，研究彼此之間的關系，統(tǒng)籌規(guī)劃，建立配棉目標模型。

目前配棉模型主要有2種函數(shù)表達方式：一種是成本最小化，另一種是混棉質量指標誤差最小化。2種方式都要考慮成本與質量的統(tǒng)一，二者本質是一致的，因為原棉的技術品質與價格是密切相關的，界定了原棉品質，也就確定了其價格，反之亦然。本文采用配棉成本達到最小為目標函數(shù)[6]。

(1)

式中：Pi為第i種原料的價格；Xi為第i種原料在配棉中所占的比重；n為不同批次原棉的種類數(shù)。

顯然，根據(jù)配棉原理，配棉后混棉的各項品質(如平均馬克隆值、纖維平均長度、纖維平均強度、平均黃度、疵點總數(shù)等)必須在規(guī)定的范圍內(nèi)，以滿足成紗質量約束，即有以下約束。

1)批棉權重約束。

(2)

式中：各批棉所占比重之和為1，maxi和mini分別為第i批棉所占比重的上限值和下限值。

通常根據(jù)已紡紗線的線密度，從實驗室數(shù)據(jù)中選取第i批棉的占比參數(shù)作為Xi的上下限參考值。

2)主體成分約束。

(3)

式中：ki為主體成分因子，若i原料被選中，ki取值為1，否則為0；C為原棉主體成分要求值。

3)原棉品質指標約束。

(4)

式中：Pij為第j種棉的第i項品質指標值；Ai、Bi分別指混棉的第i項平均品質指標值的下限和上限。

2 改進遺傳算法對模型的求解

盡管基本遺傳算法(簡稱BGA)具有魯棒性和全局搜索能力強的特點，但在求解配棉問題時，由于基本遺傳算法使用隨機生成的個體種群進行遺傳操作，從而可能出現(xiàn)大量無效個體參與運算，導致尋優(yōu)過程失效[7]。另外，基本遺傳算法直接采用適應度的大小或迭代次數(shù)作為進化終止條件，在種群進化過程中缺乏對約束條件的監(jiān)控，這意味著單純以成本為適應度計算的進化過程會過早收斂，但又不符合求解要求。在基本遺傳進化的后期，數(shù)量稀少的適應度高的個體由于概率低沒被選中，而它們可能部分或全部是最優(yōu)解，從而出現(xiàn)算法效率低或在一定時間內(nèi)得不到最優(yōu)解。

針對上述問題，本文利用一種改進的遺傳算法(簡稱IGA)求解多條件約束的自動配棉問題。改進的遺傳算法流程描述如下。

1)采用整數(shù)編碼。企業(yè)在配棉時會根據(jù)庫存原棉和生產(chǎn)情況，設定棉批種類數(shù)m和限定混棉總包數(shù)n、以及各批棉使用包數(shù)的上限ki(i=1,2,…,m)。雖然待求解的Xi為(0,1)間的實數(shù)，但由于實際配棉方案中各批棉的包數(shù)皆為整數(shù)，故基因編碼采用整數(shù)編碼，1組參數(shù)(x1、x2、…、xi)為1個染色體，xi代表每種配棉的包數(shù)，在[0,n-1]取值。采用上述編碼不僅能有效滿足實際整包抓棉的要求，而且能明顯縮小xi的搜素空間，提高求解效率。

2)初始種群生成策略。如果沒有任何條件約束，采用隨機在[0,n-1]生成的k個基因構成的個體絕大部分是無效個體，這是因為它們都不能滿足式(2)、(3)的約束。為此，本文采取以下策略生成初始種群。

步驟1：染色體(x1、x2、…、xi)中的xi隨機在[0,n-1]取值，如果xi>ki，則舍棄，繼續(xù)取，最后按式(5)對xi進行縮放。

(5)

步驟2：每生成1個個體，就放在集合X中，且計數(shù)器count+1(count初值=0)，然后回到步驟1，直至集合X的長度等于種群大小S。這樣，不僅保證了個體都滿足式(2)、(3)，而且在較短時間生成初始種群。

3)適應度函數(shù)。適應度是衡量個體優(yōu)劣程度的值，該函數(shù)的好壞對遺傳操作有重要的影響，也直接影響求解的效率。采用式(1)計算個體的適應度函數(shù)fit(y)=1/F。為消除不同量綱數(shù)據(jù)因變化幅度帶來的影響，式(1)中Pi的單位采用元/kg，保留2位小數(shù)。

4)選擇操作。為避免最優(yōu)個體在雜交操作中被破壞，此處引入精英保留策略[8]，用上一輪的最優(yōu)個體替代本輪中的最差個體，對其余個體利用賭輪選擇法隨機選擇組成新的種群，從而在保留最優(yōu)個體的同時也保證了新種群中的個體有較大的適應度和個體優(yōu)勢。

5)交叉操作。為擴大搜素范圍，增大種群離散度，提高跳出局部優(yōu)先的能力，此處采用隨機單點頭-頭、頭-尾交叉法生成新的個體。頭-頭、頭-尾交叉的概率分別為Pc和(1-Pc)，Pc為交叉系數(shù)。

6)變異操作。顯然近鄰變異操作更符合各批棉在配棉中的變化情況，且每段基因的變化受式(2)的限制，參考文獻[9]，按概率Pm對隨機選定的某位基因gj進行如下操作。

7)收斂條件。適應度大小的變化反映了混棉價格相對標準棉價格的變化幅度，為監(jiān)控種群進化收斂程度，并提高算法的效率，必須設置合適的收斂終止條件。在種群進化過程中,當部分最優(yōu)個體適應度的變化小于某一確定的臨界值e時，即通過式(6)來決定收斂是否終止。

(6)

式中：s為精英策略中前10%最優(yōu)個體的大??；Y為最優(yōu)個體的適應度；e為這些最優(yōu)個體收斂的臨界值，e的經(jīng)驗取值為[5×10-6，5×10-5]。

若最優(yōu)個體群的收斂值變化很小，并符合式(4)的約束條件，停止進化，輸出最優(yōu)解；否則，繼續(xù)迭代，直至達到最大迭代次數(shù)。

3 應用實例

根據(jù)上述配棉方法和算法思想，利用Java和MySQL在Win7平臺上開發(fā)出自動配棉應用程序。實驗數(shù)據(jù)來自南通某大型國營紡織企業(yè)，原棉價格、HVI主要數(shù)據(jù)如表1所示。

在配棉工藝中，根據(jù)實際生產(chǎn)情況和專家經(jīng)驗，主要考慮短絨率、斷裂比強度、馬克隆值、黃度和雜質等主要技術指標[10]。本次配棉的混用上限和新的品質指標要求如表2所示。

在上述約束條件下，求解目標是混棉的最低價格。利用配棉應用程序求解最低成本前，先設定本次計算的各個參數(shù)，如表3所示。

表1 原棉基本數(shù)據(jù)

表2 配棉技術要求

注：混用上限分別為1#、2#、…、6#候選棉的混合上限值。

表3 算法基本參數(shù)

為測試改進遺傳算法求解的有效性，在應用程序中分別選用本文算法和標準遺傳算法對目標函數(shù)F(x)進行10次最優(yōu)求解后取平均值，實驗結果如表4所示。表5示出最低成本配棉方案對應的混棉技術指標值。

表4 2種算法計算結果

表5 配棉方案對應的技術指標

由表4、5可以看出，采用基本遺傳算法配棉的價格雖然比標準棉的價格要低，但混棉的斷裂比強度、黃度達不到品質指標要求，雖短絨率要優(yōu)于標準棉，但高于該項的配棉技術指標，不能滿足實際配棉的需要，故有必要對其進行改進。采用本文改進的遺傳算法進行配棉，不僅配棉價格比標準棉低，且短絨率、強度和雜質要優(yōu)于標準棉，馬克隆值和黃度的指標值與標準棉相當，各項指標值均在配棉技術要求的范圍內(nèi)，所以改進遺傳算法給出的配棉方案合理有效，符合棉紡廠實際生產(chǎn)要求。根據(jù)應用結果，可得出如下結論：

1)基本遺傳算法由于本身的缺陷導致配棉尋優(yōu)能力差，所求解往往不符合配棉的約束條件，甚至找不到最優(yōu)解；而改進算法通過算子的巧妙設計和多約束條件的處理，保證了求解的最優(yōu)化和實用性。

2)只要在配棉應用程序中改變?nèi)旧w的長度參數(shù)，就能自動適應不同批次種類棉的求解要求，這樣有利于技術人員在配棉時對候選棉做出更多的選擇。

3)想要提高改進算法的效率，可在合理范圍內(nèi)適當增大收斂臨界值e，這時的相對最優(yōu)解也能滿足配棉要求，雖然可能價格不是最低，但對于企業(yè)來說，可以根據(jù)實際情況對庫存批棉做出靈活的選用，來降低整個庫存成本。

4 結 語

針對傳統(tǒng)配棉手段的缺點和其他配棉模型在求解方面的不足，本文將線性規(guī)劃與遺傳算法相結合，通過改進種群生成策略、遺傳操作和收斂條件，解決了配棉多約束條件下的尋優(yōu)問題。實際應用結果顯示，基于本模型開發(fā)的應用程序能為企業(yè)的紗線生產(chǎn)提供配棉控制和決策。本文在建模過程中只考慮了混棉的平均品質指標，沒有考慮混棉與后續(xù)產(chǎn)品紗線的質量關系，后續(xù)的研究將把混棉質量與紗線質量一并進行綜合考慮，在應用系統(tǒng)中能根據(jù)求解結果預測紗線的質量，來進一步提高自動配棉的適應性和精度，為實際生產(chǎn)提供更多的技術手段和參考價值。

FZXB

[1] 邱兆寶．配棉混包排列優(yōu)化模型與效果評價[J]．棉紡織技術，2013，41(4)：218-219. QIU Zhaobao. Cotton assorting blended bale arrangement optimized model and its effect evalua-tion[J]. Cotton Textile Technology, 2013, 41(4): 218-219.

[2] 陳懷忠，何仁初，史桂麗．基于改進PSO算法的自動配棉工藝參數(shù)優(yōu)化設計[J]．紡織學報，2014，35(6)：142-143． CHEN Huaizhong, HE Renchu, SHI Guili. Parameter optimization design for automatic cotton assorting based on improved PSO algorithm [J]. Journal of Textile Research, 2014, 35(6): 142-143.

[3] 丁志榮．改進的方案組合配棉方法研究[J]．紡織學報，2005，26(3)：38-39． DING Zhirong. Method research on improved schemes combination for cotton assorting[J]. Journal of Textile Research, 2005, 26(3): 38-39.

[4] 杜兆芳，劉小平，韓江洪．基于改進微分進化算法的優(yōu)化配棉[J]．紡織學報，2011，32(7)：35-36． DU Zhaofang, LIU Xiaoping, HAN Jianghong. Cotton blending optimization based on improved differential evolution algorithm[J]. Journal of Textile Research, 2011, 32(7): 35-36.

[5] 宋楚平，蔡彬彬，李少芹．基于SVM的紗線生產(chǎn)工藝智能優(yōu)化研究[J]．毛紡科技，2015，43(7)：14-15． SONG Chuping, CAI Binbin, LI Shaoqin. Intelligent optimization study of yarn production processes based on SVM[J]. Wool Textile Journal, 2015, 43(7): 14-15.

[6] 郭光振．基于HVI公檢數(shù)據(jù)的配棉技術和案例分析[J]．棉紡織技術，2014，42(4)：11． GUO Guangzhen. Cotton assorting technology and case analysis based on HVI notary inspection data[J]. Cotton Textile Technology, 2014, 42(4): 11.

[7] 李成國，范秀娟．改進混合遺傳算法在自動配棉上的應用[J]．紡織學報，2009，30(3)：29． LI Chengguo, FAN Xiujuan. Application of improved hybrid genetic algorithm on automatic cotton-blending[J]. Journal of Textile Research, 2009, 30(3):29.

[8] RUDOLPH G. Convergence analysis of canonical genetic algorithms[J]. IEEE Transactions on Neural Networks, 1994, 5(1): 97-98.

[9] LEITNER P, HUMMER W, DUSTAR S. Cost-based optimization of service compositions[J]. IEEE Transactions on Services Computing, 2013,6(2): 240-245.

[10] 何銀官．2012棉花標準中各質量指標在配棉中的應用[J]．棉紡織技術，2014，42(11)：1-3． He Yinguan. Application of 2012 cotton standard quality index in cotton assorting [J]. Cotton Textile Technology, 2014, 42(11): 1-3.

Optimum and application of automatic cotton blending by improved genetic algorithm

SONG Chuping, LI Shaoqin

(CollegeofMechanicalandElectricalEngineering,JiangsuCollegeofEngineeringandTechnology,Nantong,Jiangsu226007,China)

Aiming at the characteristics of multi-constraints condition and the deficiency of the existing automatic cotton blending, the improved genetic algorithm is applied to linear programming optimization problem. By improving generation strategy of the initial population, genetic operators and evolutionary convergence condition, constraint conditions of cotton blending will be fused dynamically with the evolution process. The efficiency and effectiveness of the solution are considered in the premise of ensuring the constraint conditions of cotton blending so as to optimize automatic cotton blending. The experimental results show that the solution of the improved genetic algorithm is superior to that of the basic genetic algorithm and all index values of cotton blending are in line with the requirements of production technology. Under the premise of meeting the quality of mixed cotton, the method can guide technicians to make a more reasonable choice for the candidate cotton and stock cotton and the cost of cotton blending can be reduced effectively.

automatic cotton blending; cotton blending model; improved genetic algorithm; multi-constraints condition

10.13475/j.fzxb.20150801205

2015-08-07

2016-01-31

江蘇省高等職業(yè)院校國內(nèi)高級訪問學者計劃資助項目(2014FX)；江蘇工程職業(yè)技術學院科研計劃項目(FYKY/2014/3)

宋楚平(1972—)，男，副教授，碩士。研究方向為計算機應用、教育信息化。E-mail：ntscp@sina.com。

TP 399

A