1、矩形件排樣問題廣泛存在于機械、家具、服裝等國民經(jīng)濟行業(yè)，解決好該問題可以節(jié)省原材料，簡化生產(chǎn)工藝，降低生產(chǎn)成本，增加企業(yè)效益。對于許多不規(guī)則零件的排樣問題，也可通過計算機的圖形處理技術(shù)將其轉(zhuǎn)化為矩形件排樣問題。矩形件帶排樣問題(RSPP)是指將給定的一定數(shù)量的矩形件 排放在定寬無限高的板材中，使所占據(jù)板材的高度最小。它是計算機輔助排樣的一個重要分支。但RSPP在理論上是屬于高計算復(fù)雜性的NP完全問題，在問題規(guī)模較大時，很難用精確算法求得

2、最優(yōu)解。因此，研究RSPP具有重要的實用和理論價值。 遺傳算法是基于生物進化和隨機選擇的全局搜索優(yōu)化計算技術(shù)，它模擬生物進化的基本過程，用數(shù)碼基因串來類比生物中的染色體，通過選擇、交叉、變異等遺傳算子來仿真生物的基本進化過程，進化若干代以后，使最優(yōu)異染色體所代表的問題解逼近問題的全局最優(yōu)解或近優(yōu)解。多種群遺傳算法采用多個種群代替單一種群，其中每個子種群按各自不同的進化策略和遺傳操作并行獨立進化。進化過程中可以選取和保留每個子種群

3、的優(yōu)秀染色體，就可以在保持優(yōu)秀染色體進化的穩(wěn)定性的同時加快進化速度，避免單一種群進化過程中出現(xiàn)的過早收斂現(xiàn)象。 基于上述考慮，本文以多種群遺傳算法為基礎(chǔ)，提出了一種基于遺傳算法求解RSPP的新算法。通過大量的實例測試，驗證了該算法的有效性。本文的主要工作和創(chuàng)新點如下： 首先，改進了一種矩形件近似排樣算法。對中外學(xué)者提出的四種近似排樣算法進行比較和分析，在總結(jié)其優(yōu)缺點的基礎(chǔ)上，針對遞減排序的矩形序列，對基于最低水平線的搜索

4、算法進行了改進，稱為基于最低水平線的擇優(yōu)插入算法。改進算法在零件排放過程中，將最低水平線的長度先與當(dāng)前待排放矩形件的長度（本文定義矩形件平行X軸的方向稱為長度，另一邊稱為寬度）比較，若最低水平線的長度大于矩形件的長度，將矩形件排放在此位置；否則將最低水平線的長度與當(dāng)前矩形的寬度比較，若最低水平線的長度大于矩形件的寬度，將矩形件旋轉(zhuǎn)90度排放在此位置。若最低水平線的長度均小于當(dāng)前矩形件的長度和寬度，即說明當(dāng)前矩形件不能放到最低水平線上，則

5、在排樣序列的當(dāng)前位置向后搜索，選擇一個滿足排放條件并且長度或者寬度與最低水平線的長度最接近的矩形件（稱為最優(yōu)零件）進行合理排放；否則，更新最低水平線。將搜索到的最優(yōu)零件直接插入到當(dāng)前排放位置，不更改后續(xù)矩形的序列。算法可以使得零件之間排放緊湊，降低排樣高度，在一定程度上提高材料利用率。 其次，將基于最低水平線的擇優(yōu)插入算法和簡化的多種群遺傳算法結(jié)合，設(shè)計了一種采用兩個種群并行進化的遺傳算法求解RSPP的新算法。矩形件排樣問題中如

6、何產(chǎn)生排樣序列是一個關(guān)鍵的問題，許多學(xué)者應(yīng)用遺傳算法，模擬退火算法等算法產(chǎn)生排樣序列，再將產(chǎn)生的排樣序列與某種矩形件近似排樣算法結(jié)合求解矩形件排樣問題，取得了較好的排樣效果。多種群遺傳算法是在基本遺傳算法基礎(chǔ)上改進的一種算法。本文分析了多種群遺傳算法，應(yīng)用兩個規(guī)模相當(dāng)?shù)淖臃N群進行并行進化，其中兩個子種群采用不同的初始策略。產(chǎn)生兩種不同性質(zhì)的矩形零件遞減序列，并設(shè)計了求解RSPP的相關(guān)操作，定義了求解RSPP的適應(yīng)度函數(shù)。將遺傳算法產(chǎn)生矩

7、形件的遞減序列，按照本文的基于最低水平線的擇優(yōu)插入算法和本文的適應(yīng)度函數(shù)得到序列的適應(yīng)度值，并生成排樣圖。通過矩形零件序列的適應(yīng)度值的比較，從而得到一個較優(yōu)的排樣方案。 然后，規(guī)劃和設(shè)計了排樣系統(tǒng)的基本功能模塊，開發(fā)了一個基于遺傳算法的矩形件優(yōu)化排樣系統(tǒng)。通過大量實驗測試，并將實驗結(jié)果與應(yīng)用遺傳算法、模擬退火算法、隨機算法求解矩形件排樣問題的實驗結(jié)果進行了比較和分析，驗證了該系統(tǒng)的算法的有效性。 最后，論文對己完成的工作