蜂群遺傳算法在一維下料問題中的應(yīng)用*

王曉偉，劉 林，周 謐

(合肥工業(yè)大學(xué) 管理學(xué)院，安徽 合肥230009)

下料問題是將庫存的原材料切割成形狀不同、大小不一或是長(zhǎng)短各異的多種零件以滿足顧客的需求，在鋼鐵企業(yè)、造紙業(yè)、紡織業(yè)和木材加工業(yè)中都有著廣泛的應(yīng) 用 ，Dyckhoff[1]和 Wa¨scher[2]就 下 料 問 題 給 予 了 全 面 的分類。根據(jù)原材料和零件維數(shù)的數(shù)目，可以把下料問題劃分為一維下料問題、二維下料問題和多維下料問題。

一維下料問題是其中一個(gè)重要的組成部分，討論該問題是研究二維、三維等多維下料問題的基礎(chǔ)。不同學(xué)者在對(duì)待這個(gè)問題時(shí)也有著不同的研究重點(diǎn)，例如考慮最大限度地節(jié)約原材料，提高原材料利用率；如何減少排樣方案數(shù)；或是優(yōu)先使用較短原材料、增加最后一根余料長(zhǎng)度；在規(guī)定的交貨期前完成生產(chǎn)任務(wù)等不同目標(biāo)。經(jīng)過調(diào)查發(fā)現(xiàn)，大部分研究一維下料問題的文獻(xiàn)很少考慮企業(yè)面臨生產(chǎn)力不足的情況，這時(shí)企業(yè)會(huì)面臨一定的損失或者盈利下降的問題，參考文獻(xiàn)[3]考慮了有交貨期限制的一維下料問題，通過合理安排生產(chǎn)進(jìn)度來減少延遲所造成的損失；而參考文獻(xiàn)[4]、參考文獻(xiàn)[5]雖然針對(duì)不完全下料這種情況提出了解決方案，但也僅僅在如何提高原材料的利用率上加以研究，其他與此相關(guān)的文章也鮮見發(fā)表。任何時(shí)候企業(yè)的生產(chǎn)能力都是有限制的,包括加工能力和原材料儲(chǔ)備，而生產(chǎn)出來的各種零件也因?yàn)槠涫袌?chǎng)價(jià)值或后期加工需求的緊迫程度不同所帶來的收益也不盡相同，當(dāng)企業(yè)不得不面對(duì)這些突發(fā)情況時(shí)，合理安排價(jià)值高、需求緊迫的零件優(yōu)先生產(chǎn)、同時(shí)盡可能多地減少?gòu)U料、使企業(yè)的損失最小成為決策者必須考慮的問題之一，本文在這種情況下針對(duì)單一規(guī)格原材料的一維下料問題給出了一個(gè)以價(jià)值導(dǎo)向?yàn)榛A(chǔ)的、將問題實(shí)際量化的新模型。

1 模型結(jié)構(gòu)

模型的建立需要考慮將兩個(gè)問題同時(shí)融入其中：一是企業(yè)自身能力可以滿足生產(chǎn)需求，包括生產(chǎn)能力滿足和原材料庫存充足，在這種情況下，下料方案所產(chǎn)生的廢料最小，原材料的利用率最高是決策者所關(guān)心的主要方面，這時(shí)模型所要解決的就只是充分利用原材料的問題；另一個(gè)方面是因?yàn)榭陀^原因?qū)е碌纳a(chǎn)力受限或因?yàn)樯嫌纹髽I(yè)原材料供應(yīng)不上而導(dǎo)致無法按時(shí)完成全部的生產(chǎn)任務(wù)，此時(shí)，將需求緊迫和延遲交貨所造成的損失價(jià)值高的零件優(yōu)先安排生產(chǎn)，保證企業(yè)總的損失最小是主要目標(biāo)。

具體參數(shù)設(shè)定如下：假設(shè)企業(yè)共需要生產(chǎn)m種零件，i為待生產(chǎn)零件的編號(hào)，li為第i種零件的長(zhǎng)度，vi為第i種零件對(duì)應(yīng)的市場(chǎng)價(jià)值，di為第i種零件的需求數(shù)量，L則為原材料的長(zhǎng)度，v為其單位價(jià)值，n為生產(chǎn)中使用的原材料總數(shù)量，aij為j號(hào)原材料所生產(chǎn)的第i種零件的數(shù)量，cj為j號(hào)原材料切割完畢后剩下的余料的長(zhǎng)度，E為企業(yè)的生產(chǎn)能力或是原料總量限制。具體模型如下：

目標(biāo)函數(shù)為：

約束條件是：

目標(biāo)函數(shù)（1）保證了企業(yè)的總體損失最小，當(dāng)滿足生產(chǎn)時(shí)，目標(biāo)變?yōu)槭股a(chǎn)結(jié)束后產(chǎn)生的廢料損失最??；式（2）確保企業(yè)的生產(chǎn)總量不會(huì)超出需求的數(shù)量，使得產(chǎn)需平衡，這里認(rèn)為超額生產(chǎn)的零件會(huì)帶來庫存、管理、耗損等一系列費(fèi)用，同樣視為損失；式（3）則確保在一根原材料上生產(chǎn)出的零件長(zhǎng)度之和不會(huì)超過原材料自身的長(zhǎng)度，否則生產(chǎn)是無法進(jìn)行的；式（4）限制企業(yè)實(shí)際能夠生產(chǎn)的零件數(shù)量。

2 蜂群遺傳算法

根據(jù)上述已經(jīng)建立的模型，采用應(yīng)用較多的遺傳算法求解問題。遺傳算法最早是在20世紀(jì)60年代末～70年代初由美國(guó)密歇根大學(xué)的Holland教授及其學(xué)生提出的。本文采用一種基于蜂群繁殖原理的改進(jìn)型遺傳算法[6，7]，這種算法既能保證最優(yōu)個(gè)體的存活和交配的權(quán)利，又能保持種群中個(gè)體的多樣性。

在自然界中，整個(gè)蜂群是由蜂后、雄蜂和雌蜂三部分組成的，每個(gè)蜂群中有且僅有一只蜂后，蜂后也是整個(gè)蜂群中唯一一個(gè)具有生殖能力的蜜蜂。蜂后如果死亡或者失去繁殖能力，若干潛在可能成為新蜂后的雌蜂會(huì)互相競(jìng)爭(zhēng)，直到一只勝出成為新一代的蜂后。蜂后會(huì)產(chǎn)生兩種類型的后代，一種發(fā)育成雌蜂，數(shù)量較多，沒有生育能力；而另一種則發(fā)育成雄蜂，數(shù)量較少，只負(fù)責(zé)和蜂后進(jìn)行交配。

根據(jù)蜂群的生育原理，文中的蜂群遺傳算法的種群是由蜂后、雄蜂群和雌蜂群三者組成，其中蜂后的數(shù)量為1，雄蜂群個(gè)體的數(shù)量為N，雌蜂群個(gè)體的數(shù)量為M。

2.1 適應(yīng)度函數(shù)

文中所述一維下料問題的優(yōu)化目標(biāo)是使得下料方案的總損失最小，用適應(yīng)度函數(shù)來評(píng)價(jià)算法時(shí)，一般規(guī)定適應(yīng)度越大解的質(zhì)量越好。根據(jù)上述原因，本文將適應(yīng)度函數(shù)取為：

其中，分子是已生產(chǎn)零件的價(jià)值總和減去廢料的價(jià)值之和，分母為總需求零件的價(jià)值和，只有當(dāng)需求滿足且沒有余料時(shí)，適應(yīng)度函數(shù)值可以達(dá)到最大，取值為1，即原材料利用率達(dá)到了100%。

2.2 染色體編碼

編碼方式也稱為基因表達(dá)方式，種群中的每個(gè)個(gè)體即每個(gè)染色體由基因構(gòu)成。本文中染色體的編碼采用零件全排列組合方式，即個(gè)體中的每個(gè)基因代表一個(gè)零件，例如由要切的 1個(gè)3號(hào)零件、2個(gè) 2號(hào)零件、1個(gè)8號(hào)零件、3個(gè) 5號(hào)零件隨機(jī)產(chǎn)生的編號(hào)序列(2，5，3，8，2，5，5)就是一個(gè)個(gè)體。 譯碼時(shí)，取一根原料，按順序從編號(hào)序列中取一個(gè)零件配切，直到所取的零件不能在此原料上配切為止，然后從序列中刪去已配切的零件編號(hào)，再取一根原料，對(duì)剩下的零件編號(hào)序列重復(fù)以上步驟直到生產(chǎn)滿足或是原材料用盡。

2.3 遺傳算子的選擇

2.3.1 交叉算子

雄蜂群按照交叉率和蜂后進(jìn)行交叉操作，有利于產(chǎn)生新的高適應(yīng)度的個(gè)體。交叉后產(chǎn)生一雄一雌的后代。用雄性后代取代父代，雌性后代臨時(shí)存放，以便作下一步處理。雄蜂群主要是為了保持較高的選擇壓力，以提高收斂速度。交叉是最重要的遺傳算子，本文中交叉算子的設(shè)計(jì)采用順序交叉方案，首先隨機(jī)確定兩個(gè)交叉位置，在交換交叉點(diǎn)之間的片段后，從第2個(gè)交叉位置起在原先父代個(gè)體中，刪除從另一個(gè)父代個(gè)體中交換過來的基因，然后從第2個(gè)交叉位置后填入剩余基因，從而生成兩個(gè)新的染色體。

2.3.2 變異算子

變異可以提供初始種群中所沒有的染色體，為種群提供新的內(nèi)容。變異算子的設(shè)計(jì)多采用多點(diǎn)交換變異的方案，本文采用的變異算子皆為兩點(diǎn)變異，即在每個(gè)染色體中以概率P隨機(jī)選取染色體上的兩點(diǎn)進(jìn)行交換。變異概率控制著新基因?qū)敕N群的比例，若太低，一些有用的基因就難以進(jìn)入選擇；若太高，則會(huì)造成后代失去雙親繼承下來的好特性。

2.3.3 選擇算子

雌性蜂群按照錦標(biāo)賽選擇的方法，將交叉后產(chǎn)生的雌性后代和原雌性蜂群中的個(gè)體進(jìn)行選擇，重新組成M個(gè)個(gè)體的新雌蜂群。選擇方法為：兩個(gè)群體各隨機(jī)抽取x個(gè)個(gè)體進(jìn)行比較，適應(yīng)度高者保留，直到滿足新群體規(guī)模。這個(gè)新的雌性蜂群和原來的雌蜂群在個(gè)體上存在了一定數(shù)量的差異，所以需要重新選擇蜂后，方法是從新群體中選出適應(yīng)度最大的個(gè)體與蜂后比較，若適應(yīng)度高于原蜂后，那么就取代原蜂后；否則，原蜂后不做改變。錦標(biāo)賽規(guī)模一般取為2。

2.3.4 抑制算子

蜂后為了維持自身的地位，需要對(duì)編碼相似程度較高的染色體進(jìn)行抑制，抑制的閾值為T。具體的抑制方法是：若雌蜂群中的某些個(gè)體與蜂后之間的歐式距離D≤T，則進(jìn)行抑制，刪除這些個(gè)體并以隨機(jī)個(gè)體取代。其他沒有被抑制的個(gè)體按照變異率進(jìn)行變異。雌蜂群的目的主要是為了保持種群的多樣性，避免種群早熟收斂，隨時(shí)可以跳出局部峰值。歐式距離D表示如下：

其中參數(shù)d為染色體的長(zhǎng)度，Abi為 A染色體的第 i個(gè)基因位，Bbi為B染色體的第i個(gè)基因位。

2.3.5 算法描述

蜂群遺傳算法BSGA(Bee-Swarm Genetic Algorithm)的過程描述為：

(1)隨機(jī)產(chǎn)生兩個(gè)群體，雄蜂群和雌蜂群，每個(gè)種群各有N和M個(gè)個(gè)體，在雌蜂群中選出適應(yīng)度最大的個(gè)體做為蜂后；

(2)雄性個(gè)體經(jīng)過輪盤選擇操作，按固定的交叉率與蜂后進(jìn)行交叉，產(chǎn)生一個(gè)雄性和一個(gè)雌性后代，然后再進(jìn)行變異操作；

(3)雌性蜂群按照錦標(biāo)賽選擇的方法，將新產(chǎn)生的雌性后代和原雌性蜂群進(jìn)行選擇操作，重組為新的M個(gè)個(gè)體的雌蜂群；

(4)對(duì)新產(chǎn)生的雌性群體實(shí)行蜂后排擠機(jī)制，對(duì)群體中與蜂后的歐式距離D在一定閾值之內(nèi)的個(gè)體予以消滅，再隨機(jī)生成新的雌性個(gè)體，補(bǔ)齊該種群所消滅的個(gè)體的數(shù)量；

(5)若算法條件不滿足，回到過程(3)；否則，輸出蜂后作為全局最優(yōu)解；

(6)算法結(jié)束。

3 仿真案例分析

仿真程序采用PB編程，設(shè)置雄性種群數(shù)目為50，雌性種群數(shù)目為 50，染色體的交叉概率為0.8，變異概率為0.005，迭代最大次數(shù)為100次。

算例1：計(jì)算參考文獻(xiàn)[7]中的例子?，F(xiàn)需總長(zhǎng)度2 104 m，長(zhǎng)度分別為 4 m、6 m、10 m、13 m、14 m、19 m、20 m、21 m、22 m、28 m、32 m、33 m、36 m、38 m、38 m、40 m、41 m、42 m、48 m、48 m、50 m、55 m、57 m、60 m、64 m、66 m、67 m、72 m、76 m、77 m、83 m、84 m、85 m、86 m、91 m、91 m、94 m、94 m、99 m、100 m的網(wǎng)線40段，求所需每箱長(zhǎng)度為305 m的網(wǎng)線箱數(shù)及分割方案。因?yàn)楸疚闹械哪繕?biāo)函數(shù)和適應(yīng)度函數(shù)中有價(jià)值系數(shù)的存在，所以賦予零件和原料每米相同的單位價(jià)值1，具體價(jià)值和長(zhǎng)度不同的例子將在算例2中討論。

表1給出了利用本文給出的算法計(jì)算得到的結(jié)果，網(wǎng)線需要7箱，合計(jì)余料31 m，其中除了最長(zhǎng)的那箱余料31 m，材料利用率為89.84%，其余的都加以充分利用。

表1 算例演算過程及結(jié)果

模型主要考慮解決的問題是不能完成全部生產(chǎn)任務(wù)時(shí)的情況，如何盡可能地在有限的資源內(nèi)創(chuàng)造較高的價(jià)值是本文所關(guān)心的問題，在此給出算例2：假設(shè)需求10種零件，長(zhǎng)度分別為 135 cm、31 cm、23 cm、92 cm、28 cm、257 cm、14 cm、110 cm、55 cm、147 cm， 需求量分別為 75、250、250、45、200、50、920、67、100、15 個(gè)，零件價(jià)值分別為 217、44、30、113、33、450、18、169、63、277 元， 原料長(zhǎng)度為600 cm，單位價(jià)值為0.5元。仿真結(jié)果如表2所示。

表2 算例演算過程及結(jié)果

從仿真結(jié)果中可以看到，在原材料不足（這里僅考慮原料不足的狀況，生產(chǎn)力不足的情況和此類似）時(shí)，需要考慮的是盡可能多地生產(chǎn)產(chǎn)品，創(chuàng)造價(jià)值。(v)表示考慮價(jià)值因素影響的切割方式，通過仿真結(jié)果中的數(shù)據(jù)對(duì)比可以看到，原料不滿足生產(chǎn)時(shí)，如果以價(jià)值為導(dǎo)向進(jìn)行切割，將比不考慮價(jià)值因素的切割方式得到更多的利潤(rùn)，這樣可以保證在突發(fā)情況下盡可能多地創(chuàng)造出價(jià)值。這時(shí)，企業(yè)可以把帶來價(jià)值高的自己進(jìn)行生產(chǎn)，而將其余產(chǎn)品的加工進(jìn)行外包等其他形式進(jìn)行。實(shí)驗(yàn)數(shù)據(jù)也證明了本文中提出的模型具有一定的實(shí)際使用意義。

本文針對(duì)企業(yè)實(shí)際的一維下料問題，運(yùn)用蜂群遺傳算法求解。從實(shí)例結(jié)果來看，在保證最高生產(chǎn)價(jià)值的同時(shí)，原材料的利用率也令人滿意，對(duì)于在實(shí)際生產(chǎn)中應(yīng)對(duì)突發(fā)狀況是很有意義的。

[1]DYCKHOFF H.A typology of cutting and packing problems[J].European Journal of Operational Research，1990，44(2)：145-159.

[2]WA¨SCHER G，HAUSSNER H，SCHUMANN H.An improved typology of cutting and packing problems[J].European Journal of Operational Research，2007，183(3)：1109-1130.

[3]HARALD R，VOSSEN W M.The one-dimensional cutting stock problem with due dates[J].European Journal of Operational Research，2010，201(3)：701-711.

[4]李培勇.多規(guī)格一維型材優(yōu)化下料[J].機(jī)械科學(xué)與技術(shù)，2003，22(Z1)：80-83.

[5]POLDI K C，ARENALES M N.Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths[J].Computers and Operations Research，2009，36(6)：2074-2081.

[6]吳迪，崔榮一.蜂群遺傳算法[C].中國(guó)人工智能學(xué)會(huì)第 11屆全國(guó)學(xué)術(shù)年會(huì)論文集，2005：733-736.

[7]吳迪，李長(zhǎng)榮，宋廣軍.基于蜂群遺傳算法的一維優(yōu)化下料問題[J].計(jì)算機(jī)技術(shù)與發(fā)展，2010，20(10)：82-85.