解決矩形件帶排樣問題的一種遺傳算法.pdf

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

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

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

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

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

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

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