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

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

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

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

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

1.1 問題描述

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

1.2 問題建模

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

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

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

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

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

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

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

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

1.2.2 重疊判斷

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

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

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

1.2.3 幾何運(yùn)算

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

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

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

2.1 算法原理

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

■圖2 遺傳算法求解路徑

2.2 算法設(shè)計(jì)

2.2.1 染色體編碼

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

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

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

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

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

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

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

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

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

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

在x上的任意兩個(gè)不同基因位置和θ中一個(gè)基因位置進(jìn)行交叉操作：

得到子代染色體為：

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

2.2.5 變異算子設(shè)計(jì)

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

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

選取x中兩個(gè)隨機(jī)的位置做順序交互的突變，θ中一個(gè)位置做突變：

突變后的個(gè)體染色體為：

3 實(shí)例仿真

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

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

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

3.2 算法參數(shù)確定

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

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

3.3 運(yùn)行實(shí)例分析

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

■圖3 部分排樣方案示例

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

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

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

4 結(jié)語

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