基于遺傳算法的兩階段切割問(wèn)題的研究

劉志宏 喻曉旭

摘要

切割問(wèn)題因切割模式數(shù)量非常龐大，存在較多局部最優(yōu)解，被看作一個(gè)NP-hard問(wèn)題。本文所研究的兩階段切割問(wèn)題是基于無(wú)縫鋼管制造過(guò)程，將無(wú)縫鋼管的熱軋和冷軋過(guò)程抽象成一個(gè)兩階段切割問(wèn)題，以對(duì)其進(jìn)行數(shù)學(xué)建模。同時(shí)利用遺傳算法求解非線性規(guī)劃問(wèn)題的優(yōu)勢(shì)，并使用MATLAB工具對(duì)遺傳算法進(jìn)行實(shí)驗(yàn)?zāi)M仿真，從而得出實(shí)驗(yàn)結(jié)果數(shù)據(jù)，經(jīng)研究顯示遺傳算法是一種很理想的求解兩階段切割問(wèn)題的算法。

【關(guān)鍵詞】遺傳算法 兩階段 切割問(wèn)題MATLAB

切割問(wèn)題常見于我國(guó)制造業(yè)中，包括布料、造紙、玻璃、皮革機(jī)、鋼鐵等行業(yè)。根據(jù)Dyckhoff的分類方法，切割問(wèn)題按維度數(shù)可劃分為一維、二維和三維切割問(wèn)題。國(guó)內(nèi)就一維切割問(wèn)題的研究進(jìn)展較大，目前使用較為廣泛的有啟發(fā)式算法、單純型算法等，都能取得較好的實(shí)驗(yàn)結(jié)果，但現(xiàn)有研究對(duì)余料控制問(wèn)題尚有不足。

1兩階段切割問(wèn)題數(shù)學(xué)模型

無(wú)縫鋼管的制造包括兩個(gè)加工流程：熱軋和冷軋。鋼管的熱軋和冷軋過(guò)程非常復(fù)雜。在傳統(tǒng)一維切割問(wèn)題中，通常把原材料直接進(jìn)行一次加工切割，這種方式會(huì)產(chǎn)生大量的余料。而兩階段切割是從訂單合同交貨長(zhǎng)度出發(fā)，形成一定量的鋸切長(zhǎng)度管坯，再進(jìn)行二次切割，從而減少余料的方法。為了便于研究，可把問(wèn)題簡(jiǎn)單描述如下：在生產(chǎn)過(guò)程中，將原料管坯通過(guò)第一階段熱軋，切割成鋸切長(zhǎng)度;之后將第一階段的鋸切長(zhǎng)度鋼管進(jìn)行第二階段冷軋，從而變成訂單合同交貨長(zhǎng)度鋼管，如圖1所示。訂單合同可根據(jù)交貨合同長(zhǎng)度不同劃分為兩種，即定尺合同和非定尺合同。定尺合同對(duì)鋼管的單根交貨長(zhǎng)度和總交貨量進(jìn)行了明確規(guī)定;非定尺只給出了單根管子的交貨長(zhǎng)度區(qū)間和總交貨長(zhǎng)度。

本文不考慮鋸切損失的問(wèn)題，同時(shí)，由于非定尺合同存在較大的不確定性，很難直接進(jìn)行最優(yōu)化求解，對(duì)此，本文提出一種將非定尺合同轉(zhuǎn)為定尺合同的簡(jiǎn)單方法，從而將兩階段切割問(wèn)題轉(zhuǎn)化為直接針對(duì)定尺合同問(wèn)題進(jìn)行研究。非定尺合同轉(zhuǎn)化為定尺合同的步驟如下.

（1）取出第一個(gè)合同，計(jì)算出符合交貨區(qū)間長(zhǎng)度的最小根數(shù)flmin和最大根數(shù)flmax。

（2）根據(jù)[flmin，flmax]區(qū)間，從小到大順序依次計(jì)算出根數(shù)所對(duì)應(yīng)的交貨長(zhǎng)度，如有符合的交貨長(zhǎng)度，則結(jié)束，若無(wú)，則取交貨長(zhǎng)度十分位最大者，將它作為新的定尺合同長(zhǎng)度。

以下給出模型建立的變量定義：

Id，（d∈l…n）：定尺合同集合。If，（f∈1…n）：非定尺合同集合。

Id，（d∈1…n）：定尺合同集合。Li，（i∈Id）：定尺合同交貨長(zhǎng)度。

DNi，（i∈Id）：定尺合同交貨數(shù)量。Y∈[Ymin，Ymax]：原料管坯長(zhǎng)度。

SL∈[SLmin，SLmax]：鋸切長(zhǎng)度。

從而可得出兩階段切割問(wèn)題數(shù)學(xué)模型：

階段一：熱軋切割模型。模型建立的過(guò)程如下：首先，從數(shù)據(jù)庫(kù)中取出{Li，DN.}，兩個(gè)參數(shù)以確定第一階段的切割長(zhǎng)度;其次，對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，這個(gè)過(guò)程對(duì)切割數(shù)量非常少的合同十分重要;第三，按照定尺合同的長(zhǎng)度進(jìn)行字典排序;第四，根據(jù)參數(shù)建立切割數(shù)學(xué)模型，求出SL長(zhǎng)度，即第一次熱軋的鋸切長(zhǎng)度。具體模型如下：

SL=∑ni=1aiβiLi，

（1）

具體參數(shù)說(shuō)明如下，DN.表示第個(gè)合同的定尺長(zhǎng)度，ai是調(diào)整系數(shù)的權(quán)重，ai∈（O，10），表示所占比重，計(jì)算公式如下ai=m*Pi，這里m取10，Pi表示第2個(gè)長(zhǎng)度切割在所有合同占的比重，公式如下：

βi表示是否選擇這個(gè)做為有效的長(zhǎng)度，定義如下：

這個(gè)系數(shù)通過(guò)對(duì)于DN，的排序進(jìn)行選擇。

階段二：冷軋切割模型。模型建立過(guò)程如下：從數(shù)據(jù)庫(kù)中取出{Li，DNi）兩個(gè)參數(shù)，根據(jù)上述計(jì)算出的鋸切長(zhǎng)度SL，以求解余料最少為最終問(wèn)題。

min f（1，x），其中1表示SL，x是一組向量，表示定尺長(zhǎng)度L.，表達(dá)式如下：

f（l，x）=∑i（l-∑，xi Li），

（3）

S.T. l-∑ixiLi>o，

（4）

實(shí)際上就是切割1分成定尺長(zhǎng)度Li，屬于帶約束的線性規(guī)劃問(wèn)題，xi的確定方法同上。

2遺傳算法

遺傳算法通過(guò)模擬人類進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程所建立的計(jì)算模型，并通過(guò)不斷的自然進(jìn)化搜索最優(yōu)解的方法。遺傳算法常用于求解線性規(guī)劃方面的問(wèn)題，其主要步驟如下：

（1）編碼。

（2）初始化種群。

（3）評(píng)估個(gè)體適應(yīng)度。評(píng)估種群中所對(duì)應(yīng)個(gè)體的適應(yīng)度。

（4）選擇。參照適應(yīng)度函數(shù)，遵照適應(yīng)度越高，選擇概率越大的原則，從種群中選擇兩個(gè)個(gè)體作為父方和母方。

（5）交叉。將父方和母方染色體進(jìn)行交叉，產(chǎn)生新的子代。

（6）變異。對(duì)子代染色體進(jìn)行變異。

（7）演化。重復(fù)3/4/5/6步驟，直至產(chǎn)生新的種群。

（8）結(jié)束。3實(shí)驗(yàn)仿真

由于兩階段問(wèn)題可行性解數(shù)量較大，當(dāng)合同數(shù)量達(dá)到50個(gè)時(shí)，切割模式數(shù)量可達(dá)到700多種，迭代次數(shù)3275次。原料管坯長(zhǎng)度lOOOmm，本次仿真取3個(gè)合同集，具體參數(shù)如表l所示。

在實(shí)驗(yàn)仿真時(shí)，使用MATLAB進(jìn)行實(shí)驗(yàn)仿真，該軟件自帶遺傳工具箱，通過(guò)迭代不斷逼近最優(yōu)解。

上述最優(yōu)解為：原料管坯共使用47根，鋸切長(zhǎng)度為500mm，一共需鋸切94根鋸切長(zhǎng)度，余料為1650mm，余料比率為3.5106%。

4結(jié)論

兩階段切割問(wèn)題是公認(rèn)的NP-hard問(wèn)題，存在大量的局部最優(yōu)解，在第三部分的實(shí)驗(yàn)仿真階段可以看出，遺傳算法可以很好地解決兩階段切割問(wèn)題中最優(yōu)解問(wèn)題，同時(shí)計(jì)算效率較高，余料控制比較理想。由于合同問(wèn)題中的非定尺合同長(zhǎng)度具有較大的不確定性，本文通過(guò)把非定尺合同定尺化的方法，將難點(diǎn)進(jìn)行轉(zhuǎn)移。這一做法在尋找最優(yōu)解的過(guò)程中是非常關(guān)鍵的一步。

參考文獻(xiàn)

[1] Dyckhoff， H.A typology of cuttinga packing problem[J]. EuropeanJournal of Operational Research，1939 （44）：145 -159.

[2]劉桂林，鋼管生產(chǎn)短尺寸合同與非定尺合同組批優(yōu)化算法[J].寶鋼技術(shù)，2007 （02）： 42-44.

[3]王紫萍，線材下料問(wèn)題

目標(biāo)函數(shù)的一個(gè)注記[J]，中國(guó)科技信息，2008 （21）.