基于遺傳算法的二維下料的仿真與實(shí)現(xiàn)

摘 要：利用遺傳算法抽象了它們的通用編碼，對簡單的管材和板材下料問題進(jìn)行了模擬實(shí)驗(yàn)，進(jìn)行了一維和二維下料問題的軟件設(shè)計(jì)和仿真。本文的研究為求解簡單的一維管材下料和二維板材下料問題提供了一種有效的思路，也為相關(guān)下料行業(yè)，如機(jī)械、建筑、船舶、服裝、皮革、車輛等行業(yè)提供了解決方案。

關(guān)鍵詞：遺傳算法；二維下料；仿真

中圖分類號：TP391.9

目前，我國正處在并將長期處在資源緊缺的狀況下，造成此狀況的原因是經(jīng)濟(jì)的粗放式發(fā)展和人口的不斷增多。所以，我國提出了可持續(xù)性發(fā)展戰(zhàn)略，伴隨著此發(fā)展戰(zhàn)略的實(shí)施，各類資源的消耗問題在我國也被日益重視起來。我國在資源方面是一個(gè)矛盾體，雖然資源總量多、種類多，但是資源的人均占有量較少。二十世紀(jì)二、三十年代，是我國經(jīng)濟(jì)發(fā)展最快的年代，當(dāng)時(shí)的經(jīng)濟(jì)發(fā)展主要走的是粗放式經(jīng)營和高消耗的道路，所以造成人力、資源浪費(fèi)嚴(yán)重以及高投入低產(chǎn)出的現(xiàn)象?，F(xiàn)在我國要建立和諧社會，所以優(yōu)化和高效的利用各類資源成為我國經(jīng)濟(jì)發(fā)展戰(zhàn)略的重要內(nèi)容和研究課題之一。另一方面，由于我國成為了世貿(mào)組織中的一員，世界范圍的大市場向我國制造業(yè)提出了更加激烈的市場競爭問題。制造業(yè)想方設(shè)法通過提高原料的利用率來達(dá)到降低成本的目的，從而來提高企業(yè)的經(jīng)濟(jì)效益，使自己的企業(yè)在競爭中長期立于不敗之地。因此下料問題的解決可以使能源得到充分的利用，也越來越受到人們的重視。

1 遺傳算法的研究

遺傳算法非常簡單，任何人只需通過高中時(shí)學(xué)過的生物術(shù)語就可以理解。以一群個(gè)體為例，它們都有自己的DNA。然后衡量每一個(gè)個(gè)體的適應(yīng)性（把它看作是適用于個(gè)體的DNA的官能來衡量），并且使那些更適應(yīng)的個(gè)體更有可能繁衍。而最不適應(yīng)的個(gè)體將會被滅絕。每個(gè)幸存者都會有機(jī)會繁衍（重要的是任何幸存者都可能會繁衍，如果不太適應(yīng)的話，僅僅是降低了可能性）。合并雙親的DNA，對合并后的DNA應(yīng)用隨機(jī)變異以模擬繁衍。理論上說來，新的個(gè)體是和雙親一樣適應(yīng)的，由于變異或增或減會有些微小的變化。然后循環(huán)會周而復(fù)始。

遺傳算法Genetic algorithms縮寫為GA，模擬自然界大量生物體的生長，能為傳統(tǒng)方法難以解的問題較快地求出好的近似解，用于工程化問題的設(shè)計(jì)，可能獲得全局最優(yōu)解。舉世聞名的遺傳算法在1975年由美國密執(zhí)根（Michigan）大學(xué)的Holland教授受達(dá)爾文進(jìn)化論的啟發(fā)而被提了出來，并在《自然和人工系統(tǒng)的適配》的文中提出了這種算法的理論基礎(chǔ)。同年，該校Deong在博士論文中，將AGS成功地用于解決優(yōu)化題，從而進(jìn)入實(shí)踐開發(fā)階段。經(jīng)典的遺傳算法采用達(dá)爾文學(xué)說中的“適者生存”及“自然選擇”等法則進(jìn)行組合來達(dá)到求得最優(yōu)解的目的，經(jīng)典的遺傳算法是采用簡單的二進(jìn)制或?qū)崝?shù)編碼技術(shù)來表示各種復(fù)雜的結(jié)構(gòu)，將染色體的不斷適應(yīng)環(huán)境和生存進(jìn)化過程表達(dá)成問題的求解方式，通過采用各種算子。目前，遺傳算法被廣泛應(yīng)用于許工程和研究領(lǐng)域，如控制參數(shù)、運(yùn)輸調(diào)度、管道線選擇以及電磁器件優(yōu)化設(shè)計(jì)等問題。

2 遺傳算法下料問題的研究與仿真

2.1 編碼和譯碼。用遺傳算法求解問題，必須首先確定編碼的方法，不同的編碼方法，遺傳算子的實(shí)現(xiàn)方法也不同。編碼是設(shè)計(jì)遺傳算法的關(guān)鍵步驟。編碼的策略和方法對遺傳操作，尤其是對交叉操作的性能會造成很大的影響。在設(shè)計(jì)遺傳算法時(shí)，需要在考慮編碼技術(shù)的基礎(chǔ)上，選擇適當(dāng)?shù)倪z傳操作策略和其它設(shè)計(jì)細(xì)節(jié)。當(dāng)想應(yīng)用遺傳算法來求解問題時(shí)，我們必須將染色體位串結(jié)構(gòu)與目標(biāo)問題實(shí)際表述之間建立聯(lián)系，就是要確定編碼和解碼的運(yùn)算。不同的適應(yīng)度函數(shù)的計(jì)算和遺傳操作方法會受到不同編碼的影響。傳統(tǒng)的編碼方法有實(shí)數(shù)編碼和二進(jìn)制編碼。二進(jìn)制編碼Holland所采用，經(jīng)過多年的發(fā)展演變，人們相繼提出了各種不同的編碼方法來解決具體問題。不同的編碼方法，遺傳算子的實(shí)現(xiàn)方法也不同。根據(jù)本文所研究的問題的模型，我們選擇以實(shí)數(shù)表示的個(gè)零件長度的排列作為一個(gè)可行解，對問題的解集進(jìn)行編碼，構(gòu)造一個(gè)染色體，其中每個(gè)零件長度為個(gè)體基因；同時(shí)，為了方便遺傳算子的設(shè)計(jì)，要對染色體基因進(jìn)行分段，并且每一段上的基因表示它們截自同一原材料。

2.2 基于單親遺傳算法的一維下料的研究與仿真。一維下料問題，指怎樣根據(jù)相同形狀的原料切割出不同規(guī)格但相同大小的零件，并且使原料消耗最小。該問題在網(wǎng)線、鋼管、網(wǎng)絡(luò)等行業(yè)對角鋼、建筑、制造等消耗型材巨大的生產(chǎn)實(shí)踐中很是常見。

以下典型的下料問題在很多行業(yè)的實(shí)際生產(chǎn)中較為常見：原材料L是給定長度的原材料，對其進(jìn)行下料，生產(chǎn)總長度為m，數(shù)量為d的零件（i=1，2，…，n），應(yīng)該怎樣下料才能達(dá)到資源利用率最大。

2.2.1 適應(yīng)度函數(shù)的設(shè)計(jì)。遺傳算法在進(jìn)化計(jì)算中基本上不用外部信息，僅使用適應(yīng)度函數(shù)做為判斷依據(jù)。遺傳算法的目標(biāo)函數(shù)不受各種約束且其定義域可以為任意集合，對目標(biāo)函數(shù)的唯一要求是輸入可計(jì)算出能進(jìn)行互相比較的結(jié)果。

2.2.2 輪盤改進(jìn)方法。每輪選擇都是從種群的第一個(gè)個(gè)體開始每次產(chǎn)生隨機(jī)數(shù)進(jìn)行判斷是否進(jìn)入下一代的種群。當(dāng)下一代種群滿為止。

2.2.3 單體交叉操作。交叉的方法有許多種方法這個(gè)操作是為了產(chǎn)生下一代與當(dāng)前種群的區(qū)別，在隨機(jī)當(dāng)中選擇出最優(yōu)化的個(gè)體來；傳統(tǒng)的遺傳算法的交叉方式是選擇兩個(gè)父代的染色體進(jìn)行交叉，從而產(chǎn)生下一代染色體，這樣會實(shí)現(xiàn)染色體的交叉后產(chǎn)生較多的進(jìn)化。

2.2.4 初始群體的產(chǎn)生。目前對初始群體的選取存在兩種觀點(diǎn)：第一種觀點(diǎn)是認(rèn)為應(yīng)隨機(jī)選取，才能遍歷所有狀態(tài)；而另一種觀點(diǎn)則認(rèn)為應(yīng)采用啟發(fā)式算法或自主經(jīng)驗(yàn)選擇較好的染色體，可以加快找到最優(yōu)解的速度。鑒于二者都有一定的道理，本文采用了經(jīng)驗(yàn)選擇與隨機(jī)生成相結(jié)合的初始群體產(chǎn)生方法。

2.2.5 編碼?；谝痪S下料問題所具有的特點(diǎn)，本篇論文選擇以實(shí)數(shù)編碼的表現(xiàn)形式來構(gòu)成了一個(gè)染色體，而把每個(gè)零件長度作為遺傳基因。

3 遺傳算法下料問題的仿真與實(shí)現(xiàn)

3.1 數(shù)學(xué)描述板材優(yōu)化下料。設(shè)現(xiàn)有N塊板材，需要對n個(gè)零件進(jìn)行下料，最終得出的各個(gè)單板組合、且平均材料利用率最大的優(yōu)化下料方案，其中Li×Wi是第i塊板材的尺寸，設(shè)i=1，…，N。而Lj×Wj是第j個(gè)零件的尺寸，設(shè)j=1，…，n。Rj是零件所在的矩形名。

3.2 軟件的功能模塊。本程序算法的實(shí)現(xiàn)基本上都在主界面實(shí)現(xiàn)的，運(yùn)用java語言實(shí)現(xiàn)遺傳算法的編寫。（本程序主要是利用遺傳算法實(shí)現(xiàn)板材下料系統(tǒng)）。怎樣運(yùn)行本程序算法，首先設(shè)置配置文件路徑，擴(kuò)展名為任意。第二步單擊菜單“參數(shù)配置”，出現(xiàn)一個(gè)下彈出對話框，依次配置遺傳算法形管參數(shù)，該操作是初始化種群實(shí)現(xiàn)。最后，點(diǎn)擊“開始”按鈕，即可運(yùn)行該程序算法。

3.3 程序的實(shí)現(xiàn)。利用J2SE的swing編程實(shí)現(xiàn)了軟件的圖形界面，使其更加直觀化的表現(xiàn)出來實(shí)驗(yàn)數(shù)據(jù)的結(jié)果。從而使用戶群體更加擴(kuò)大化。

3.4 軟件模塊。遺傳算法解決二維下料問題的實(shí)驗(yàn)演示軟件主要包括三部分的功能，分別是配置文件路徑設(shè)置，控制參數(shù)輸入以及下料需求錄入模塊。配置文件路徑設(shè)置模塊可以讓軟件找到相關(guān)的配置文件，以便于正確運(yùn)行。

總之，材料下料問題廣泛存在于社會經(jīng)濟(jì)的許多行業(yè)當(dāng)中，該問題的研究具有很強(qiáng)的實(shí)用價(jià)值。一維優(yōu)化下料問題屬于具有最高計(jì)算復(fù)雜性的NP完全問題，一般無法被傳統(tǒng)的優(yōu)化方法較好地解決。目前國內(nèi)外不少學(xué)者從各種不同的領(lǐng)域用不同的方法對其展開研究，主要包括矩形件優(yōu)化下料和不規(guī)則形狀件優(yōu)化下料，理論上取得了不少成績，但真正投入企業(yè)介入生產(chǎn)的不多。

參考文獻(xiàn)：

[1]孫杰.遺傳算法在板材優(yōu)化下料中的應(yīng)用和研究[D].東北林業(yè)大學(xué)，2012.

[2]王彩紅.二維不規(guī)則多邊形自動布局系統(tǒng)的研究與開發(fā)[D].河北工業(yè)大學(xué)，2002.

[3]劉嘉敏，張勝男，黃有群.二維不規(guī)則形狀自動排料算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2011（07）.

作者簡介：朱思華（1980.09-），講師，碩士，研究方向：軟件開發(fā)。

作者單位：仙桃職業(yè)學(xué)院，湖北仙桃 433000