灰狼算法在定制化家具矩形件排樣中的應用

吳正佳 李金雄 單飛祥 李子奇

（三峽大學機械與動力學院，湖北宜昌 443002）

0 引言

當前，定制化家具企業面臨著訂單種類和數量逐漸增加的問題，而排樣是企業生產加工的首要工序，其好壞程度直接影響生產成本。定制化家具排樣可理解為企業利用機械設備從一定規格的原板材中切割出組裝成整套家具的矩形零件，從生產成本的角度來說，板材利用率越高，所需板材越少，成本越低。

基于此種情況，部分學者采用不同方法對矩形件排樣問題展開了研究。Sanchez等人[1]將模擬退火算法和遺傳算法相結合，一定程度上提高了板材利用率；羅強等人[2]提出了一種改進的十進制灰狼算法，根據排樣圖形狀設計定位算法，求解矩形件排樣問題；王莉[3]結合模擬退火算法和基于匹配度的最低水平線排樣算法，求解以利用率最大化為目標的問題模型；郭文文等人[4]考慮工藝約束和機器刀縫限制，設計不同切割規則求解，以提高利用率?；依撬惴ㄊ且环N群智能算法，由于其較為良好的全局搜索和局部搜索能力，受到廣泛關注，目前，在聚類分析[5]、路徑規劃[6]、車間調度[7]等諸多領域得到應用。

本文擬基于定制化家具矩形件排樣問題中零件差異性較大的特點，以板材利用率最大化為求解目標，應用改進的灰狼算法進行求解，提高板材利用率，減少板材數量消耗，降低生產成本，提高企業的經濟效益。

1 數學模型

1.1 問題描述

本文以定制化家具矩形件排樣問題為研究對象，排樣問題是定制化家具生成的首道工序，直接影響整個訂單的后續生產加工。該排樣問題可描述為：將長度和寬度分別為hi和wi的待切割矩形件排布在長寬固定且為H和W的原板材上，零件的排放位置不能超出板材的邊界，零件在排放的過程中不能互相重疊。針對定制化家具，采用木材作為原板材，其尺寸固定，而訂單中待排零件尺寸不一，所以每張板材上排放的零件數b亦不相同，如何合理安排零件的排布順序和位置，盡可能實現每張原板材的利用率最大化，減少廢料和余料的生成，從而實現整體利用率最大化，是本文要考慮的關鍵問題。

1.2 模型建立

模型主要基于以下假設：

（1）排樣過程中，考慮零件紋理，矩形件不能旋轉90°；

（3）排樣過程中，原板材的尺寸固定，數量充足。

其中，約束條件（1）表示原板材利用率最大化，Ha表示最后一張板材所使用的高度，以板材的左下角為坐標原點，（xi，yi）表示零件排入板材后零件左下角的坐標。約束條件（2）和（3）表示零件不超出原板材的邊界，約束條件（4）和（5）不同時成立，表示原板材上的零件互相不重疊。

2 改進的灰狼算法

排樣問題在實際求解過程中，可以分為零件的定序和定位問題。定序問題為第一步，決定零件的排布順序，考慮運用改進的灰狼算法，并調整游走和奔襲策略，實現從全局優化到局部優化的過程；定位問題為第二步，確定待排零件序列在原板材上的排布位置，該過程考慮使用改進的最低水平線算法，適當調整零件在板材上的排布位置和順序，實現排樣利用率最大化。

2.1 改進的最低水平線定位算法

改進的最低水平線算法是一種更有效的排樣定位算法，其主要思想是：找到板材上的最低水平線，判斷其寬度w和當前待排零件的寬度l的大小，若w＜l，則判斷下一個零件的寬度與水平線寬度的大小，找到可排零件排入，否則更新水平線序列，尋找最低水平線，繼續排放零件，直到零件全部排完。

改進的最低水平線定位算法流程如下：

（1）初始化參數；

Requirement Analysis of Intelligent Editing of Academic Journal……………HU Yi(1·83)

（2）選取第i張板材，初始化水平線序列；

（3）從待排零件中選取第一個可排入零件；

（4）若step3中存在可排入零件，則排入零件，返回step3，否則進入下一步；

（5）判斷此時的水平線序列是否為一條，若是，則i=i+1，返回step2，否則進入下一步；

（6）提升水平線序列，更新最低水平線，若零件未排完，則返回step3，否則結束；

（7）排樣完成，輸出排樣結果。

2.2 灰狼定序算法

灰狼優化算法也稱“狼群算法”，是基于狼群群體智能，模擬狼群捕食行為及其獵物分配方式，抽象出游走、召喚、圍攻三種智能行為以及“勝者為王”的頭狼產生規則和“強者生存”的狼群更新機制而提出的一種新的群體智能算法。

本文將改進的灰狼定序算法與最低水平線定位算法相結合，一個在解空間中不斷地搜索更優解，另一個解碼計算當前利用率，每次迭代都保存最佳排樣方案，不斷更新迭代，直到達到最大利用率或者最大迭代次數。對算法中根據狼群行為抽象出來的游走和奔襲策略進行簡單更改，盡量使游走過程中種群的差異性增大，提升全局搜索范圍。在奔襲過程中，重新定義種群和頭狼之間的距離，并不斷讓種群向頭狼靠近，實現局部搜索。

（1）編碼。結合矩形件排樣問題，采用十進制的編碼方式對零件序列進行編碼，例如（1，3，5，2，4）表示在原板材上依次排入零件1、零件3、零件5、零件2和零件4。

（2）初始種群。采用十進制的編碼方式對所有的待排零件進行編碼，形成一個從數字1開始的連續不重復十進制整數零件序列，從而得到一個灰狼個體。按照該方式，隨機生成不同的零件序列，形成初始種群。

（3）游走。即將一個灰狼中的某一個編碼位向左或向右移動一個較大的距離，例如將灰狼Zi=（1，3，5，2，4）中的第一個編碼位的zi1向右移動4個單位長度變為Zi′=（3，5，2，4，1）?；谄髽I加工情況調研，大部分零件在實際切割時有紋理要求，本文不進行旋轉。定義游走策略為T（Zi，Q，s，d），表示從第i個灰狼Zi=（zi1，zi2，zi3，…，zin）的可編碼位Q=（1，2，3，…，n）中選擇連續的s個編碼位進行位移為d的操作。在文本中，若連續的s個編碼位的起始位置小于（1+n）/2，則向右位移，否則向左位移，盡可能增大游走范圍，實現游走過程中的全局搜索。

（4）奔襲。即灰狼向頭狼靠近的過程，用灰狼與頭狼對應編碼位的值不同的個數體現其距離，例如灰狼Zi=（1，3，5，2，4），頭狼Z=（1，2，3，4，5），灰狼和頭狼的編碼位2、編碼位3、編碼位4和編碼位5對應的數都不相同，則定義兩者的距離為4。奔襲策略R（Zi，L1，L2，d）表示選擇第i個灰狼Zi=（zi1，zi2，zi3，…，zin）中與頭狼編碼位不同的前d個編碼位，用頭狼中對應位置替代，例如若L1=（2，3，4，5），L2=（2，3，4，5），則R（Zi，L1，L2，1）表示用頭狼Z中第2個編碼位中的數將灰狼Zi中數進行替代，得到奔襲后的灰狼Zi′=（1，2，5，3，4）。

（5）解碼。解碼是運用改進的最低水平線算法將一串有序、不重復、代表矩形件的十進制整數序列轉化為零件排布圖。整個解碼過程中，會對序列進行簡單調整，為保證編碼的有效性，該十進制整數序列不存在兩個相等的數且不遺漏任何一個整數。

3 算例分析

3.1 某批次訂單零件尺寸

根據某制定化企業的生產情況，選取了5個不同批次的生產訂單，為滿足零件排樣要求，將所有訂單數據按照零件尺寸、材料進行整理，表1為其中一個批次的部分訂單數據信息。

表1 零件數據信息

基于訂單數據信息可知，由于單個訂單中零件數量一般較少，對訂單零件進行排樣前，會將訂單按照其交貨期合并到一個批次，從而減少生產過程中的切換頻率，在一定程度上提高利用率，本文中每一個批次零件的材質、顏色和厚度相同，所有零件均可排布在尺寸為2 440 mm×1 220 mm 的原板材上。

3.2 實例計算

根據矩形件排樣問題的數學模型，結合各批次的零件尺寸，以原板材的利用率最大化為目標進行求解。對比訂單分批后的經驗算法，將算法運行50次，得到不同批次的利用率及其所需板材數量，如表2所示。

表2 不同批次排樣結果

在不同的排樣批次中，為了較充分地比較算法的有效性，分別選取了不同零件規模的算例，零件個數從42個到196個不等，將本文中的改進灰狼算法和企業訂單分批后所使用的經驗算法進行比較，板材利用率均有不同程度的提升，分別提升了8.58%、5.23%、7.13%、9.36% 和7.31%，對應批次所需板材的數量分別減少2、3、1、4和4塊。改進的灰狼算法較經驗算法利用率有較大的提升，減少了企業生產成本，提高了企業的生產效益。

部分零件的排布情況如圖1所示。

圖1 部分零件排樣圖

4 總結與展望

本文應用改進的灰狼算法求解定制化家具矩形件排樣問題，針對排樣優化中的零件定序和定位問題，改進灰狼定序算法中游走、奔襲策略和最低水平線定位策略，實現從全局求解到局部求解的優化過程，并與實際的經驗排樣算法對比，利用率有較大程度的提升。但文中都是單個批次分別排樣，未考慮整個排樣過程中廢料與余料再利用的情況，且文中待排零件都是已分類完成的，未考慮零件本身的尺寸情況對排樣利用率的影響，以上兩個方面還有待進一步研究。