基于遺傳算法的板式定制家具異形件排樣優(yōu)化研究

■胡玉婷，陳星艷，陶 濤，戴向東，黃艷麗，歐陽周洲，呂 宙，詹秀麗，張玲玲

(1.中南林業(yè)科技大學(xué)，湖南長沙 410004；2.農(nóng)林生物質(zhì)綠色加工技術(shù)國家地方聯(lián)合工程研究中心，湖南長沙 410004；3.木竹資源高效利用省部共建協(xié)同創(chuàng)新中心，湖南長沙 410004；4.麓山實驗室智能家居設(shè)計中心，湖南長沙 410004）

在當(dāng)前日益激烈的市場競爭環(huán)境下，板式定制家具以其大批量生產(chǎn)的低成本、高質(zhì)量和高效率優(yōu)勢逐漸成為家具制造業(yè)發(fā)展的主流方向[1-3]。由于產(chǎn)品結(jié)構(gòu)和造型的多樣性，板式定制家具的組合板件種類繁多且復(fù)雜，可根據(jù)外部輪廓形狀是否為矩形將其分為矩形件和異形件[4]。隨著智能算法在排樣方面的研究不斷深入[5-8]，越來越多的板式定制家具企業(yè)對矩形件的排樣方案進行智能優(yōu)化，以提升原材料利用率和生產(chǎn)效率[9-10]。但由于異形件的外部輪廓無確定長寬參數(shù)，為多條線段或曲線構(gòu)成，排樣難度大，在家具行業(yè)中相應(yīng)研究較少。目前，不少企業(yè)在生產(chǎn)中多依賴人工經(jīng)驗排樣或是將異形件包含在滿足其最大長寬的矩形中進行優(yōu)化開料，導(dǎo)致原材料浪費大、生產(chǎn)效率低。

遺傳算法是一種在全局范圍內(nèi)進行隨機搜索的優(yōu)化算法，其優(yōu)點在于對全局的解空間具有良好的搜索性能以及自適應(yīng)優(yōu)化等特點[11-13]，被廣泛應(yīng)用于金屬切割、船舶制造和服裝裁剪等領(lǐng)域中多目標(biāo)且求解規(guī)模巨大的異形件排樣問題中[14-16]。在板式定制家具中，遺傳算法多用于矩形件排樣問題研究，在異形件排樣問題中較少涉及。因此，本文基于生產(chǎn)實際情況，將遺傳算法應(yīng)用于板式定制家具異形件排樣問題中，以原材料利用率最大化為優(yōu)化目標(biāo)，構(gòu)建板式定制家具異形件排樣的數(shù)學(xué)模型，為企業(yè)提供合理的異形件排樣方案，實現(xiàn)板式定制家具異形件排樣問題優(yōu)化，以期提升企業(yè)原材料利用率，降低人工生產(chǎn)成本，增強綜合競爭力[17]。

1 板式定制家具異形件排樣問題

1.1 問題描述

異形件排樣問題屬于二維平面上的排樣問題，指將大量不規(guī)則異形零件放在指定的板材中以最優(yōu)的方法進行排布，使排放異形零件區(qū)域在板材上的占有率最大，各個異形零件不能重疊，也不能超出板材范圍。這是一個組合優(yōu)化問題，也是一個具有高計算復(fù)雜性的NP完全問題[18-19]。板式定制家具的異形件排樣是將輪廓和尺寸幾乎不相同的多個異形件，在滿足實際生產(chǎn)條件的情況下，按照一定的旋轉(zhuǎn)角度和放置順序在相同規(guī)格的原材料大板上進行合理排布，以提高原材料利用率。

1.2 問題建模

1.2.1 數(shù)學(xué)模型

板式定制家具異形件排樣問題具體描述如下：有n個不同的異形件P=(P1,P2,..,Pn)，在滿足實際生產(chǎn)條件的情況下可進行任意角度旋轉(zhuǎn)，按照一定順序放置在N張寬度為W，長度為L的原材料大板上，使原材料大板的利用率最高，約束條件如下所示：

（1）滿足工廠實際生產(chǎn)中因鋸路寬度產(chǎn)生的工藝間隙要求、異形件輪廓的加工余量要求和質(zhì)量精度要求以及原材料大板的修邊要求等；

（2）異形件在排布時不能發(fā)生相互重疊的情況；

（3）所有異形件在最后輸出結(jié)果中的位置始終包含在原材料大板內(nèi)部，不得跨越原材料大板邊界。

建立板式定制家具異形件排樣問題的數(shù)學(xué)模型如下：

式(1.1)中F(x,θ)為異形件排樣問題的目標(biāo)函數(shù)，x和θ表示異形件序號和放置前的旋轉(zhuǎn)角度，i=(1,2,..N)為原材料大板的編號，piarea為第i塊原材料大板的面積，Miarea為第i塊原材料大板上異形件最小放置矩形的面積，使用的原材料大板越少，目標(biāo)函數(shù)F(x,θ)的值越小。

式(1.2)為上述(2)(3)原則的數(shù)學(xué)表述，pi(idi,?xi,?yi,?θ)中id為異形件的序號，?xi，?yi為異形件進行平移、旋轉(zhuǎn)后坐標(biāo)的變化量，△θ為異形件旋轉(zhuǎn)的角度，交集為空集代表任意兩個異形件之間沒有相互重疊。Pi(x)為異形件在原材料大板上排布的最大橫坐標(biāo)，處于0到W之間，Pj(y)為異形件在原材料大板上排布的最大縱坐標(biāo)，處于0到L之間，以確保排樣的異形件全都包含在原材料大板中。

1.2.2 重疊判斷

在異形件放置過程中，通過點與線段、點與異形件和線段與線段的相互位置來判斷異形件與異形件的位置關(guān)系。異形件和異形件的位置關(guān)系主要有以下5種：相離、外接、相交、內(nèi)接、內(nèi)含，如圖1所示。

■圖1 異形件相互位置關(guān)系

在異形件的位置關(guān)系為相交、內(nèi)含和內(nèi)接時，判定為重疊，需將異形件重新放置或調(diào)整角度。

1.2.3 幾何運算

在減少異形件彼此之間空隙時，為避免其相互重疊或超出原材料大板，需不斷對異形件進行平移和旋轉(zhuǎn)，運算法則如下所示：

式(1.3)中(x，y)為異形件的坐標(biāo)位置，?x，?y為平移距離，(x',y')為平移后坐標(biāo)；式(1.4)中，(rx,ry)為異形件旋轉(zhuǎn)中心，θ為旋轉(zhuǎn)角度。

2 異形件排樣的遺傳算法設(shè)計

2.1 算法原理

遺傳算法是模擬生物在自然界進化過程中自然選擇和遺傳機理的計算模型和全局搜索最優(yōu)解的概率搜索算法[20]。在面對異形排樣這類目標(biāo)種類多，且求解規(guī)模巨大的問題上提供了一個通用的計算框架和有效解決路徑，求解路徑如圖2所示。

■圖2 遺傳算法求解路徑

2.2 算法設(shè)計

2.2.1 染色體編碼

進行排樣的一組異形件有n件，將每件異形件視為一個個體進行旋轉(zhuǎn)，然后根據(jù)順序依次放入原材料大板中。異形件序號根據(jù)1～n進行編號，旋轉(zhuǎn)角度為（0°，360°）中任意角度，采用多參數(shù)級聯(lián)編碼方法，最終的編碼公式如（2.1）所示：

式（2.1）中xi為排放的每個異形件的序號，θi表示相對應(yīng)的異形件在放置前旋轉(zhuǎn)的角度。例如，假設(shè)有5塊異形件進行排布，若染色體編碼為β={[4,5,3,1,2],[90°,60°,30°,180°,45°]}，表示第一個放置的是序號為4的異形件，且在放置前進行90°旋轉(zhuǎn)，以此類推，最后一塊放置是序號為2的異形件，且放置前進行45°旋轉(zhuǎn)。當(dāng)有n個異形件時，按照染色體編碼中位置順序和該位置序號的異形件相應(yīng)旋轉(zhuǎn)角度放置，直至所有的異形件放置完畢。

2.2.2 種群初始化和適應(yīng)度函數(shù)確定

初始化種群選擇隨機生成，按照種群的數(shù)量M對個體進行初始化。設(shè)有n個異形件，則序號x的初始化為隨機排序的1到n的序列，對應(yīng)的旋轉(zhuǎn)角度θ初始化為（0°，360°）中的任一角度值。

適應(yīng)度函數(shù)表明個體的優(yōu)劣性，在板式定制家具異形件排樣模型中，目標(biāo)是尋找最大化利用率的異形件排樣方案[21]，因此本文以目標(biāo)函數(shù)的倒數(shù)為適應(yīng)度函數(shù)。

2.2.3 選擇算子的設(shè)計

選擇操作是從舊種群中以一定的方法選擇優(yōu)良個體組成新的種群，以繁殖得到下一代個體。本文采取四元錦標(biāo)賽選擇策略，即從種群中隨機挑選四個個體，通過比較適應(yīng)值大小，選取值最大的個體進入下一代種群，重復(fù)進行上述挑選比較，直至新種群達到原來種群規(guī)模時停止。

2.2.4 交叉算子的設(shè)計

交叉操作是從種群中隨機選擇兩個個體作為父代，通過兩個染色體的交換組合，從而產(chǎn)生新的個體。本文采用分段式交叉，即對兩個個體中基因x和θ分別進行多點交叉和單點交叉。交叉完后，為保證x為1～n之間不重復(fù)，需對交叉結(jié)果做重排序處理，例如：

設(shè)有6塊異形板件，隨機選取兩個父代染色體為：

在x上的任意兩個不同基因位置和θ中一個基因位置進行交叉操作：

得到子代染色體為：

因x基因中1～n中序號不可重復(fù)，對x基因中交換位點外重復(fù)的基因進行重排序處理后，得到的子代染色體為：

2.2.5 變異算子設(shè)計

為防止遺傳算法在優(yōu)化過程中陷入局部最優(yōu)解，在搜索過程中，需對個體進行變異操作。本文采用分段式變異，即對個體基因x和θ分別進行變異。x的變異需要選擇兩個位置做交互突變，θ直接選中一個位置做突變即可，例如：

設(shè)有6塊異形板件，隨機選取變異的父代染色體為：

選取x中兩個隨機的位置做順序交互的突變，θ中一個位置做突變：

突變后的個體染色體為：

3 實例仿真

3.1 異形件生產(chǎn)信息

本文選取某天內(nèi)某板式定制家產(chǎn)企業(yè)異形件生產(chǎn)線的三組異形件生產(chǎn)數(shù)據(jù)作為研究對象，根據(jù)每組異形件的板件名稱和尺寸輪廓等生產(chǎn)信息進行編號。其中，第一組異形件的生產(chǎn)信息如表1所示。

表1 第一組異形件生產(chǎn)信息

3.2 算法參數(shù)確定

遺傳算法中的各個參數(shù)選取大多依靠經(jīng)驗值。為保障解的多樣性、運行時間和種群優(yōu)化速度，通常種群規(guī)模M取值范圍為20～100，迭代次數(shù)N取值范圍為100～500，在交叉操作中，通常交叉概率Pc取值范圍為0.4～0.99，在變異操作中，通常變異概率Pm取值范圍為0.0001～0.1。

本文中，采用MATLAB編寫上述遺傳算法程序，通過多次實驗分析確定種群規(guī)模M取值為40，迭代次數(shù)N取值為120，交叉概率Pc取值為0.8，變異概率Pm取值為0.1。

3.3 運行實例分析

本研究選取三組異形件在企業(yè)常用規(guī)格的原材料大板上進行排樣方案示例，第一組異形件總面積為17.53 m2，共53塊異形件，第二組異形件總面積為14.69 m2，共50塊異形件，第三組異形件總面積為16.41 m2，共52塊異形件，將三組異形件加工信息導(dǎo)入MATLAB軟件中進行圖形數(shù)據(jù)化處理，再通過遺傳算法多次迭代求解后，最終完成三組異形件排樣優(yōu)化方案，選取第一組的部分排樣方案實例如圖3所示。

■圖3 部分排樣方案示例

通過遺傳算法多次迭代后，可得出三組異形件最終優(yōu)化排樣方案的原材料利用率，并與目前生產(chǎn)模式下將異形件包含在滿足其最大長寬的矩形中進行優(yōu)化開料的原材料利用率進行對比，如表2所示。

表2 不同算例的排樣結(jié)果

由表2可得，對板式定制家具異形件的三組算例進行排樣時，對比了某企業(yè)異形件在目前生產(chǎn)模式下作為矩形優(yōu)化排樣和采用遺傳算法方案優(yōu)化后進行排樣對原材料利用率的影響，結(jié)果表明，本文采用遺傳算法進行優(yōu)化排樣較目前生產(chǎn)模式下的原材料利用率分別提高2.36%，8.80%，4.43%。通過遺傳算法多次迭代搜索異形件排樣方案，能夠有效減少原材料大板上的空隙部分，提高原材料利用率，為企業(yè)提高經(jīng)濟效益和提升競爭力[22]。

4 結(jié)語

本文以原材料利用率最大化為目標(biāo)對板式定制家具異形件排樣問題進行描述并構(gòu)建了數(shù)學(xué)模型，將遺傳算法應(yīng)用于異形件旋轉(zhuǎn)角度和放置順序的求解，提出了更優(yōu)的板式定制家具異形件排樣方案。經(jīng)多次實驗分析確定遺傳算法中各項參數(shù)值，通過三組實際數(shù)據(jù)進行仿真實驗，對比算法優(yōu)化方案與目前企業(yè)生產(chǎn)方式下的原材料利用率，實驗結(jié)果表明，采用遺傳算法優(yōu)化后的異形件排樣方案的原材料利用率分別提高了2.36%，8.80%，4.43%，表明本文提出的基于遺傳算法的優(yōu)化排樣方案在求解板式定制家具異形件排樣問題中的可行性和有效性。