周佳立，郭 奇，吳 超，武 敏

?

面軌道特征的矩形排樣與加工路徑優(yōu)化方法研究

周佳立1，郭 奇1，吳 超1，武 敏2

(1. 浙江工業(yè)大學理學院，浙江 杭州 310023；2. 浙江科技學院理學院，浙江 杭州 310023)

為了解決實際生產中遇到的一種帶有面軌道特征的矩形排樣問題，重點研究了自適應遺傳算法和圖論相結合的優(yōu)化方法，極大提高了切削加工效率。該方法將路徑優(yōu)化問題轉化為一個考察無向圖連通性問題，并利用遺傳算法在解空間中進行全局搜索，以尋找加工路徑最優(yōu)解，并按照BL定位策略完成對矩形的排樣。通過對遺傳算法的改進：①對初始個體基因位的合法性判斷，并利用深度優(yōu)先遍歷結果評估個體性能的優(yōu)劣；②交叉、變異算子均采用自適應機制，并且執(zhí)行變異操作的對象限定為一條染色體上的斷點集，極大提高了算法的性能。最后，通過實驗驗證了該算法在絕大多數情況下完全可以找到滿足需求目標的結果，是一種非?？煽康姆椒?。

等邊矩形排樣；特征加工；路徑優(yōu)化；自適應遺傳算法

在工程應用領域中，矩形排樣技術一般是指需要開料的矩形工件在給定的矩形板料上的布置和開切方式，從而達到板料利用率的最大化。上個世紀60年代，GILMORE和GOMORY[1]提出二維排樣優(yōu)化問題，其屬于NP完全問題[2]，求解難度極高，存在“組合爆炸”。對這類復雜問題，遺傳算法是尋求這種滿意解的最佳工具之一。遺傳算法從解的串集開始搜索，覆蓋面大，利于全局擇優(yōu)，對于組合優(yōu)化中的NP問題非常有效[3]。HOPPER和TURTON[4]將改進的BL算法和遺傳算法相結合，用于解決矩形的排樣問題，以算例論證了算法的有效性。文獻[5]提出一種將最低水平線方法與改進GA算法相結合的混合優(yōu)化方法。吳忻生等[6]利用遺傳算法獲得矩形的排放順序，在遺傳算子操作過程中，為避免優(yōu)良基因的缺失，采用了不同階段引入不同遺傳算子的方法，之后采用最低水平線法對其進行自動排樣。

在數控加工中研究的問題是數控的切削加工問題。合理的切削加工路徑可以避免刀具空行程，從而減少加工時間和加工成本，因此優(yōu)化加工路徑是提高加工效率的重要環(huán)節(jié)。

遺傳算法的靈活性，使其在解決路徑優(yōu)化問題上同樣適用，但在實際應用中，不同特征的加工零件，優(yōu)化方法截然不同。文獻[7]針對孔群加工路徑優(yōu)化模型，提出一種整數染色體的遺傳算法，這種采用孔號為染色體的編碼方案省去了繁雜的編解碼過程，簡化了遺傳算法的編程。文獻[8]將多輪廓加工路徑優(yōu)化問題轉化為廣義旅行商問題(generalized traveling salesman problem，GTSP)，并提出了廣義染色體遺傳算法，該算法對多輪廓加工路徑優(yōu)化問題做出合理有效的解決。文獻[9]根據門窗類五金配件加工中孔、槽的特殊精度要求，提出了一種基于遺傳算法的熱誤差建模方法，在遺傳算法中引入熱變形補償，進而提高了機床加工精度。

本文研究的排樣與路徑優(yōu)化問題和上述情況截然不同，研究對象為帶有面軌道特征的矩形，此類特殊的矩形排樣問題，研究成果較少，排樣結果不單是尋求板材的最大利用率，而且更主要考慮矩形表面軌道的整體連通性，以實現加工路徑的最優(yōu)化。此外，相比于傳統的矩形排樣問題，排樣結果中單個零件的改動(旋轉、替換)會對全局產生較大的擾動，一定程度上加大了研究難度。可使用圖論方法中的深度優(yōu)先搜索算法來解決排樣圖連通性。所以，本文用改進的遺傳算法與圖論方法求解此類特殊排樣問題，最后給出了具體實例，驗證該算法的可行性。

1 面軌道及其矩形排樣

本文研究課題源于改進某類軌道積木的加工工藝，以提高生產效率。加工的軌道積木種類如圖1所示。

圖1 軌道積木種類圖

由圖1可知，積木的軌道種類分為內部軌道(體軌道)和表面軌道(面軌道)，本文研究對象為面軌道。圖2展示了所有面軌道集合的俯視圖，其中基礎面軌道可分為直線型基礎面軌道和圓弧型基礎面軌道兩類，通過這兩種軌道的自身組合形成直線型復合面軌道和圓弧型復合面軌道，軌道種類共5種，分別為直線軌道、十字軌道、單圓弧軌道、雙圓弧軌道以及特殊的無軌平面。

圖2 面軌道示意圖

如若單獨加工每塊積木的上表面軌道，則60塊裝的一套積木，其上表面加工操作要進行多達60次的裝夾，多次裝夾操作不但效率低下，且無法保證較高的加工精度。

本文采用組合切削加工工藝，將邊長為一個單位的矩形上表面軌道在6×7的板材上進行排樣，積木的上表面加工軌道可抽象為6種，如圖3所示。再進行簡化后，如圖4所示。

圖3 軌道種類

圖4 簡化后軌道種類

圖5 排樣圖示例

2 面軌道加工路徑優(yōu)化數學模型及其求解算法

2.1 數學模型

2.2 個體編碼策略

表1 矩形編碼表

2.3 構造初始種群

實際加工環(huán)境如圖6所示，待加工零件整齊排放在工作臺，上端和右端緊貼靠山，下端及左端用工裝夾鉗固定在一個矩形框內，由于靠山高度高于矩形，所以在排樣過程中要盡可能避免在排樣圖的四邊出現軌道出口，如圖7所示，否則會出現撞刀情況。在構造初始種群過程中，應考慮以上問題，盡量避免非法個體的產生。

圖6 實際加工環(huán)境

圖7 排樣軌道出口

產生的初始值執(zhí)行如下兩個操作：①以50％的概率乘以–1，這樣可以產生負數序列；②按照初始值所對應排樣圖的位置對其進行篩選，剔除不符合加工工藝要求的非法基因，從而保證初始種群中個體的合法性，提高初始種群的質量。

2.4 個體適應度評價函數與選擇算子

圖8 排樣圖

圖9 排樣圖示例

綜上所述，適應度函數取

如果越大，表明個體排樣布局越優(yōu)。

將選擇算子作用于種群，可將優(yōu)良的個體直接遺傳到下一代而拋棄劣質個體，體現了“適者生存”的原理，這也是遺傳算法收斂性的一個重要保證條件。本文使用輪盤賭選擇法和最優(yōu)保存策略相結合的聯合選擇算子，由于輪盤賭選擇法是基于概率選擇的，存在統計誤差，從而導致”退化”現象的發(fā)生，即優(yōu)良個體失去選擇機會，因此結合最優(yōu)保存策略以保證當前適應度最優(yōu)的個體能夠進化到下一代而不被遺傳操作的隨機性破壞，保證算法的收斂性。具體執(zhí)行過程為：

(1) 對群體中的所有個體按其適應度大小進行排序，適應度最高的10%的個體，直接遺傳到下一代；

(2) 計算出每個個體被選擇的概率

2.5 交叉和變異算子

交叉算子和變異算子是產生新個體的主要方法，前者決定了遺傳算法的全局搜索能力，后者決定了遺傳算法的局部搜索能力，兩者相互配合，可以完成對解空間的搜索。

每條染色體由兩層編碼表示，分別為基因位和基因檢索位，由于相同矩形以同一實數編碼，所以在染色體執(zhí)行交叉運算時，由基因檢索位唯一區(qū)分同一編碼號的不同基因位。

圖10 個體交叉運算示意圖

2.6 算法流程圖

圖11 算法流程圖

算法實現及算例分析。

算例 1.為了驗證本文中提出的特殊矩形排樣算法的有效性，首先選取一組待加工矩形，待加工零件種類及個數見表2。

表2 待加工零件數目表

實驗平臺：普通PC機一臺，處理器Inter Core i3 CPU 1.5 GHz，內存(RAM)4 GB，32位Windows 7操作系統，算法使用C++編程語言, 編譯器Visual Studio 2010。

表3 試驗數據表

由于遺傳算法的概率性，對于同一組數據，每次運行的結果都不盡相同，所以本文采用多次運行的方法對算法的性能進行評估。由于加工零件種類的變動性，完全連通的排樣圖可能并不存在，所以，子段個數為3的排樣圖即在接受范圍之內，表4為10次運行結果。

表4 試驗數據表

其中所求最優(yōu)排樣結果的編碼{3,–4,3,2,–4,–2, –3,1,5,–4,–2,–2,3,1,–5,1,5,4,–3,5,1,5,1,–4,3,–5,5,1,1,4,–3,–5,1,1,–5,–4,–3,4,–3,4,–3,4}，算法在30代以后穩(wěn)定，其收斂過程如圖12所示。分別為第2代、第11代、第20代和第30代的排樣情況。

圖12 排樣情況

算例 2. 選取3組不同代加工矩形，應用該算法求解最優(yōu)排樣圖，以說明該算法針對此類問題具有普遍的適用性。試驗平臺、運行參數均不改變，采用每組代加工矩形運行十次取平均值的方法考察排樣結果。表5為每組矩形的組合情況及運行結果，其中，運行結果主要由平均子段最大長度、平均子段個數和平均斷點個數來評估。

表5 排樣結果評估

由表5可知，組2中0號積木數量較多，平均子段長度明顯下降，這是因為無軌積木占用了母版多數空間，軌道長度自然縮減，這也是符合常理的。平均子段個數在3個左右，也在本文的接受范圍之內。所以，該算法可以有效解決此類特殊矩形排樣問題。

3 結束語

本文將一種改進的遺傳算法和圖論方法相結合，主要研究方向為一種帶有面軌道特征的矩形排樣問題，并以路徑最優(yōu)為目標，最終將路徑優(yōu)化問題轉化為圖論連通性問題，實現了矩形在母板上的合理排樣。在遺傳算法中，通過對初始個體基因位的合法性判斷，有效提高了初始種群的質量，交叉、變異算子均采用自適應機制，并且執(zhí)行變異操作的對象限定為一條染色體上的斷點集，增強了算法的局部搜索能力，最后將排樣結果轉化為無向圖，通過計算無向圖的連通程度來衡量個體的優(yōu)良性。

對于矩形排樣問題，任何算法也難以保證得到最優(yōu)解，所以在具體應用問題上，需多次試驗以尋得最優(yōu)排樣效果。圖13為實際生產中的應用實例，極大提高了生產效率。

圖13 實際生產應用實例

[1] GILMORE P C, GOMORY R E. Multistage cutting stock problems of two and more dimensions [J]. Operations Research, 1965, 13(1): 94-120.

[2] JINDAL P, KUMAR A. Towers the solution of NP complete problems [J]. Jouranl of Applied Computer Science & Mathematics, 2010, 4(9): 63-65.

[3] 賈志欣. 排樣問題的研究現狀與趨勢[J]. 計算機輔助設計與圖形學學報, 2004, 17(7): 890-893.

[4] HOPPER E, TURTON B C. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem [J]. European Journal of Operational Research, 2001, 128(1): 34-57.

[5] LIU H M, ZHOU J, WU X S, et al. Optimization algorithm for rectangle packing problem based on varied-factor genetic algorithm and lowest front-line strategy [C]//2014 IEEE Congress on Evolutionary Computation (CEC). New York: IEEE Press, 2014: 352-357.

[6] 吳忻生, 吳超成, 劉海明. 基于改進遺傳算法的矩形排樣優(yōu)化算法[J]. 制造業(yè)自動化, 2013, 35(10): 55-58.

[7] 肖軍民. 一種改進遺傳算法在孔群加工路徑中的優(yōu)化[J]. 組合機床與自動化加工技術, 2015(2): 151-153.

[8] HUANG H, YANG X, HAO Z, et al. Hybrid chromosome genetic algorithm for generalized traveling salesman problems [C]//International Conference on Advances in Natural Computation. Berlin: Springer Press, 2005: 137-140.

[9] XIAO J, YAN M. Heat error modeling methods of NC machine tool machining holes or slots of door hardware based on genetic algorithms [C]//Proceedings of 2011 International Conference on Electronic & Machanical Engineering and Information Technology. New York: IEEE Press, 2011: 3326-3329.

[10] 楊衛(wèi)波, 王萬良, 張景玲, 等. 基于模擬退火算法的矩形優(yōu)化排樣[J]. 計算機工程與應用, 2016, 52(7): 259-263.

Research on Packing Problem and Cutting Path Optimization of Rectangle with Surface Orbit Characteristics

ZHOU Jiali1, GUO Qi1, WU Chao1, WU Min2

(1. College of Science, Zhejiang University of Technology, Hangzhou Zhejing 310023, China;2. College of Scienc, Zhejiang University of Science and Technology, Hangzhou Zhejing 310023, China)

The purpose of this paper is to solve the equilateral rectangular packing problem characterized by surface orbit arised in practical production. We focus on the optimization system based on adaptive genetic algorithm and graph theory, and greatly improve the cutting efficiency. Our method target the optimization of the machining path, in this method, the path optimization problem is turned into an undirected graph connectivity problem, and using genetic algorithm to find the optimized machining path. The optimal solution of the final search is used to arrange the rectangular parts according to BL positioning strategy. Through the improvement of genetic algorithm, such as: ① the judgment of the legitimacy of the initial individual genes, and using the depth first traversal results evaluation of individual performance. ② The crossover and mutation operators use adaptive mechanism, and the object that performs the mutation operation is limited to a broken point set on a chromosome, which greatly improves the performance of the algorithm. Finally, the experiments show that the algorithm can provide the available solution in most cases, and it is also a very reliable method.

equilateral rectangle packing; feature machining; path optimization; adaptive genetic algorithm

TP 391

10.11996/JG.j.2095-302X.2018020256

A

2095-302X(2018)02-0256-07

2017-07-04；

2017-08-05

青年科學基金項目(11301482)；科技型中小企業(yè)技術創(chuàng)新基金項目(13C26213302261)；浙江省重大科技專項項目(2013C01077)；浙江省科技廳面上項目(2015F50021)

周佳立(1981-)，男，浙江諸暨人，副教授，博士，碩士生導師。主要研究方向為計算機視覺、模式識別、機器人切削。 E-mail：zhoulue@zjut.edu.cn