宋楚平, 李少芹

(江蘇工程職業(yè)技術(shù)學(xué)院 機(jī)電工程學(xué)院, 江蘇 南通 226007)

應(yīng)用改進(jìn)遺傳算法的自動(dòng)配棉模型優(yōu)化與應(yīng)用

宋楚平, 李少芹

(江蘇工程職業(yè)技術(shù)學(xué)院 機(jī)電工程學(xué)院, 江蘇 南通 226007)

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

自動(dòng)配棉； 配棉模型； 改進(jìn)遺傳算法； 多約束條件

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

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

1 應(yīng)用HVI的配棉模型建立

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

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

自動(dòng)配棉是根據(jù)紡紗質(zhì)量要求對(duì)庫(kù)存原棉進(jìn)行混合，既要盡可能控制生產(chǎn)成本，又要滿足混棉的質(zhì)量指標(biāo)要求的過(guò)程。無(wú)論是購(gòu)棉還是配棉，都可以在HVI數(shù)據(jù)的支持下做到合理采購(gòu)原料，科學(xué)設(shè)計(jì)配棉方案，并能有效預(yù)測(cè)紗線質(zhì)量。

1.2 配棉模型

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

目前配棉模型主要有2種函數(shù)表達(dá)方式：一種是成本最小化，另一種是混棉質(zhì)量指標(biāo)誤差最小化。2種方式都要考慮成本與質(zhì)量的統(tǒng)一，二者本質(zhì)是一致的，因?yàn)樵薜募夹g(shù)品質(zhì)與價(jià)格是密切相關(guān)的，界定了原棉品質(zhì)，也就確定了其價(jià)格，反之亦然。本文采用配棉成本達(dá)到最小為目標(biāo)函數(shù)[6]。

(1)

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

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

1)批棉權(quán)重約束。

(2)

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

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

2)主體成分約束。

(3)

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

3)原棉品質(zhì)指標(biāo)約束。

(4)

式中：Pij為第j種棉的第i項(xiàng)品質(zhì)指標(biāo)值；Ai、Bi分別指混棉的第i項(xiàng)平均品質(zhì)指標(biāo)值的下限和上限。

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

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

針對(duì)上述問(wèn)題，本文利用一種改進(jìn)的遺傳算法(簡(jiǎn)稱IGA)求解多條件約束的自動(dòng)配棉問(wèn)題。改進(jìn)的遺傳算法流程描述如下。

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

2)初始種群生成策略。如果沒(méi)有任何條件約束，采用隨機(jī)在[0,n-1]生成的k個(gè)基因構(gòu)成的個(gè)體絕大部分是無(wú)效個(gè)體，這是因?yàn)樗鼈兌疾荒軡M足式(2)、(3)的約束。為此，本文采取以下策略生成初始種群。

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

(5)

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

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

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

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

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

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

(6)

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

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

3 應(yīng)用實(shí)例

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

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

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

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

表2 配棉技術(shù)要求

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

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

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

表4 2種算法計(jì)算結(jié)果

表5 配棉方案對(duì)應(yīng)的技術(shù)指標(biāo)

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

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

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

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

4 結(jié) 語(yǔ)

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

FZXB

[1] 邱兆寶．配棉混包排列優(yōu)化模型與效果評(píng)價(jià)[J]．棉紡織技術(shù)，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] 陳懷忠，何仁初，史桂麗．基于改進(jìn)PSO算法的自動(dòng)配棉工藝參數(shù)優(yōu)化設(shè)計(jì)[J]．紡織學(xué)報(bào)，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ìn)的方案組合配棉方法研究[J]．紡織學(xué)報(bào)，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] 杜兆芳，劉小平，韓江洪．基于改進(jìn)微分進(jìn)化算法的優(yōu)化配棉[J]．紡織學(xué)報(bào)，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ù)的配棉技術(shù)和案例分析[J]．棉紡織技術(shù)，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] 李成國(guó)，范秀娟．改進(jìn)混合遺傳算法在自動(dòng)配棉上的應(yīng)用[J]．紡織學(xué)報(bào)，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棉花標(biāo)準(zhǔn)中各質(zhì)量指標(biāo)在配棉中的應(yīng)用[J]．棉紡織技術(shù)，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è)院校國(guó)內(nèi)高級(jí)訪問(wèn)學(xué)者計(jì)劃資助項(xiàng)目(2014FX)；江蘇工程職業(yè)技術(shù)學(xué)院科研計(jì)劃項(xiàng)目(FYKY/2014/3)

宋楚平(1972—)，男，副教授，碩士。研究方向?yàn)橛?jì)算機(jī)應(yīng)用、教育信息化。E-mail：ntscp@sina.com。

TP 399

A