摘  要： 針對一維下料優化問題，根據企業的實際生產情況，考慮能夠滿足和不滿足生產兩種情況，建立一個新的優化模型，并使用蜂群遺傳算法求解方案。用各零件長度的一個排列作為一個染色體，每個零件的長度作為染色體的一個基因，根據蜂群原理設置兩個不同的種群，種群1用于全局搜索，種群2用于局部搜索。實驗結果表明，該模型具有一定的實用價值。
關鍵詞： 一維下料問題；優化下料；蜂群遺傳算法；染色體；種群；抑制算子

    下料問題是將庫存的原材料切割成形狀不同、大小不一或是長短各異的多種零件以滿足顧客的需求，在鋼鐵企業、造紙業、紡織業和木材加工業中都有著廣泛的應用，Dyckhoff[1]和Wascher[2]就下料問題給予了全面的分類。根據原材料和零件維數的數目，可以把下料問題劃分為一維下料問題、二維下料問題和多維下料問題。
    一維下料問題是其中一個重要的組成部分，討論該問題是研究二維、三維等多維下料問題的基礎。不同學者在對待這個問題時也有著不同的研究重點，例如考慮最大限度地節約原材料，提高原材料利用率；如何減少排樣方案數；或是優先使用較短原材料、增加最后一根余料長度；在規定的交貨期前完成生產任務等不同目標。經過調查發現，大部分研究一維下料問題的文獻很少考慮企業面臨生產力不足的情況，這時企業會面臨一定的損失或者盈利下降的問題，參考文獻[3]考慮了有交貨期限制的一維下料問題，通過合理安排生產進度來減少延遲所造成的損失；而參考文獻[4]、參考文獻[5]雖然針對不完全下料這種情況提出了解決方案，但也僅僅在如何提高原材料的利用率上加以研究，其他與此相關的文章也鮮見發表。任何時候企業的生產能力都是有限制的,包括加工能力和原材料儲備，而生產出來的各種零件也因為其市場價值或后期加工需求的緊迫程度不同所帶來的收益也不盡相同，當企業不得不面對這些突發情況時，合理安排價值高、需求緊迫的零件優先生產、同時盡可能多地減少廢料、使企業的損失最小成為決策者必須考慮的問題之一，本文在這種情況下針對單一規格原材料的一維下料問題給出了一個以價值導向為基礎的、將問題實際量化的新模型。
1 模型結構
    模型的建立需要考慮將兩個問題同時融入其中：一是企業自身能力可以滿足生產需求，包括生產能力滿足和原材料庫存充足，在這種情況下，下料方案所產生的廢料最小，原材料的利用率最高是決策者所關心的主要方面，這時模型所要解決的就只是充分利用原材料的問題；另一個方面是因為客觀原因導致的生產力受限或因為上游企業原材料供應不上而導致無法按時完成全部的生產任務，此時，將需求緊迫和延遲交貨所造成的損失價值高的零件優先安排生產，保證企業總的損失最小是主要目標。
    具體參數設定如下：假設企業共需要生產m種零件，i為待生產零件的編號，li為第i種零件的長度，vi為第i種零件對應的市場價值，di為第i種零件的需求數量，L則為原材料的長度，v為其單位價值，n為生產中使用的原材料總數量，aij為j號原材料所生產的第i種零件的數量，cj為j號原材料切割完畢后剩下的余料的長度，E為企業的生產能力或是原料總量限制。具體模型如下：
  
    目標函數（1）保證了企業的總體損失最小，當滿足生產時，目標變為使生產結束后產生的廢料損失最小；式（2）確保企業的生產總量不會超出需求的數量，使得產需平衡，這里認為超額生產的零件會帶來庫存、管理、耗損等一系列費用，同樣視為損失；式（3）則確保在一根原材料上生產出的零件長度之和不會超過原材料自身的長度，否則生產是無法進行的；式（4）限制企業實際能夠生產的零件數量。
2 蜂群遺傳算法
    根據上述已經建立的模型，采用應用較多的遺傳算法求解問題。遺傳算法最早是在20世紀60年代末～70年代初由美國密歇根大學的Holland教授及其學生提出的。本文采用一種基于蜂群繁殖原理的改進型遺傳算法[6，7]，這種算法既能保證最優個體的存活和交配的權利，又能保持種群中個體的多樣性。
    在自然界中，整個蜂群是由蜂后、雄蜂和雌蜂三部分組成的，每個蜂群中有且僅有一只蜂后，蜂后也是整個蜂群中唯一一個具有生殖能力的蜜蜂。蜂后如果死亡或者失去繁殖能力，若干潛在可能成為新蜂后的雌蜂會互相競爭，直到一只勝出成為新一代的蜂后。蜂后會產生兩種類型的后代，一種發育成雌蜂，數量較多，沒有生育能力；而另一種則發育成雄蜂，數量較少，只負責和蜂后進行交配。
    根據蜂群的生育原理，文中的蜂群遺傳算法的種群是由蜂后、雄蜂群和雌蜂群三者組成，其中蜂后的數量為1，雄蜂群個體的數量為N，雌蜂群個體的數量為M。
2.1 適應度函數
    文中所述一維下料問題的優化目標是使得下料方案的總損失最小，用適應度函數來評價算法時，一般規定適應度越大解的質量越好。根據上述原因，本文將適應度函數取為：
  
其中，分子是已生產零件的價值總和減去廢料的價值之和，分母為總需求零件的價值和，只有當需求滿足且沒有余料時，適應度函數值可以達到最大，取值為1，即原材料利用率達到了100%。
2.2 染色體編碼
    編碼方式也稱為基因表達方式，種群中的每個個體即每個染色體由基因構成。本文中染色體的編碼采用零件全排列組合方式，即個體中的每個基因代表一個零件，例如由要切的1個3號零件、2個2號零件、1個8號零件、3個5號零件隨機產生的編號序列(2，5，3，8，2，5，5)就是一個個體。譯碼時，取一根原料，按順序從編號序列中取一個零件配切，直到所取的零件不能在此原料上配切為止，然后從序列中刪去已配切的零件編號，再取一根原料，對剩下的零件編號序列重復以上步驟直到生產滿足或是原材料用盡。
2.3 遺傳算子的選擇
2.3.1 交叉算子
    雄蜂群按照交叉率和蜂后進行交叉操作，有利于產生新的高適應度的個體。交叉后產生一雄一雌的后代。用雄性后代取代父代，雌性后代臨時存放，以便作下一步處理。雄蜂群主要是為了保持較高的選擇壓力，以提高收斂速度。交叉是最重要的遺傳算子，本文中交叉算子的設計采用順序交叉方案，首先隨機確定兩個交叉位置，在交換交叉點之間的片段后，從第2個交叉位置起在原先父代個體中，刪除從另一個父代個體中交換過來的基因，然后從第2個交叉位置后填入剩余基因，從而生成兩個新的染色體。
2.3.2 變異算子
    變異可以提供初始種群中所沒有的染色體，為種群提供新的內容。變異算子的設計多采用多點交換變異的方案，本文采用的變異算子皆為兩點變異，即在每個染色體中以概率P隨機選取染色體上的兩點進行交換。變異概率控制著新基因導入種群的比例，若太低，一些有用的基因就難以進入選擇；若太高，則會造成后代失去雙親繼承下來的好特性。
2.3.3 選擇算子
    雌性蜂群按照錦標賽選擇的方法，將交叉后產生的雌性后代和原雌性蜂群中的個體進行選擇，重新組成M個個體的新雌蜂群。選擇方法為：兩個群體各隨機抽取x個個體進行比較，適應度高者保留，直到滿足新群體規模。這個新的雌性蜂群和原來的雌蜂群在個體上存在了一定數量的差異，所以需要重新選擇蜂后，方法是從新群體中選出適應度最大的個體與蜂后比較，若適應度高于原蜂后，那么就取代原蜂后；否則，原蜂后不做改變。錦標賽規模一般取為2。
2.3.4 抑制算子
    蜂后為了維持自身的地位，需要對編碼相似程度較高的染色體進行抑制，抑制的閾值為T。具體的抑制方法是：若雌蜂群中的某些個體與蜂后之間的歐式距離D≤T，則進行抑制，刪除這些個體并以隨機個體取代。其他沒有被抑制的個體按照變異率進行變異。雌蜂群的目的主要是為了保持種群的多樣性，避免種群早熟收斂，隨時可以跳出局部峰值。歐式距離D表示如下：
    
其中參數d為染色體的長度，Abi為A染色體的第i個基因位，Bbi為B染色體的第i個基因位。
2.3.5 算法描述
    蜂群遺傳算法BSGA(Bee-Swarm Genetic Algorithm)的過程描述為：
    (1)隨機產生兩個群體，雄蜂群和雌蜂群，每個種群各有N和M個個體，在雌蜂群中選出適應度最大的個體做為蜂后；
    (2)雄性個體經過輪盤選擇操作，按固定的交叉率與蜂后進行交叉，產生一個雄性和一個雌性后代，然后再進行變異操作；
    (3)雌性蜂群按照錦標賽選擇的方法，將新產生的雌性后代和原雌性蜂群進行選擇操作，重組為新的M個個體的雌蜂群；
    (4)對新產生的雌性群體實行蜂后排擠機制，對群體中與蜂后的歐式距離D在一定閾值之內的個體予以消滅，再隨機生成新的雌性個體，補齊該種群所消滅的個體的數量；
    (5)若算法條件不滿足，回到過程(3)；否則，輸出蜂后作為全局最優解；
    (6)算法結束。
3 仿真案例分析
    仿真程序采用PB編程，設置雄性種群數目為50，雌性種群數目為50，染色體的交叉概率為0.8，變異概率為0.005，迭代最大次數為100次。
    算例1：計算參考文獻[7]中的例子。現需總長度2 104 m，長度分別為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的網線40段，求所需每箱長度為305 m的網線箱數及分割方案。因為本文中的目標函數和適應度函數中有價值系數的存在，所以賦予零件和原料每米相同的單位價值1，具體價值和長度不同的例子將在算例2中討論。
    表1給出了利用本文給出的算法計算得到的結果，網線需要7箱，合計余料31 m，其中除了最長的那箱余料31 m，材料利用率為89.84％，其余的都加以充分利用。

    模型主要考慮解決的問題是不能完成全部生產任務時的情況，如何盡可能地在有限的資源內創造較高的價值是本文所關心的問題，在此給出算例2：假設需求10種零件，長度分別為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個，零件價值分別為217、44、30、113、33、450、18、169、63、277元，原料長度為600 cm，單位價值為0.5元。仿真結果如表2所示。

    從仿真結果中可以看到，在原材料不足（這里僅考慮原料不足的狀況，生產力不足的情況和此類似）時，需要考慮的是盡可能多地生產產品，創造價值。(v)表示考
慮價值因素影響的切割方式，通過仿真結果中的數據對比可以看到，原料不滿足生產時，如果以價值為導向進行切割，將比不考慮價值因素的切割方式得到更多的利潤，這樣可以保證在突發情況下盡可能多地創造出價值。這時，企業可以把帶來價值高的自己進行生產，而將其余產品的加工進行外包等其他形式進行。實驗數據也證明了本文中提出的模型具有一定的實際使用意義。
    本文針對企業實際的一維下料問題，運用蜂群遺傳算法求解。從實例結果來看，在保證最高生產價值的同時，原材料的利用率也令人滿意，對于在實際生產中應對突發狀況是很有意義的。
參考文獻
[1] DYCKHOFF H.A typology of cutting and packing problems [J].European Journal of Operational Research，1990，44(2)：145-159.
[2] WASCHER 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 Oper ational Research，2010，201(3)：701-711.
[4] 李培勇.多規格一維型材優化下料[J].機械科學與技術，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].中國人工智能學會第11屆全國學術年會論文集，2005：733-736.
[7] 吳迪，李長榮，宋廣軍.基于蜂群遺傳算法的一維優化下料問題[J].計算機技術與發展，2010，20(10)：82-85.