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

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

?

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

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

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

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

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

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

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

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

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

1 面軌道及其矩形排樣

本文研究課題源于改進(jìn)某類(lèi)軌道積木的加工工藝，以提高生產(chǎn)效率。加工的軌道積木種類(lèi)如圖1所示。

圖1 軌道積木種類(lèi)圖

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

圖2 面軌道示意圖

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

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

圖3 軌道種類(lèi)

圖4 簡(jiǎn)化后軌道種類(lèi)

圖5 排樣圖示例

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

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

2.2 個(gè)體編碼策略

表1 矩形編碼表

2.3 構(gòu)造初始種群

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

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

圖7 排樣軌道出口

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

2.4 個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)與選擇算子

圖8 排樣圖

圖9 排樣圖示例

綜上所述，適應(yīng)度函數(shù)取

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

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

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

(2) 計(jì)算出每個(gè)個(gè)體被選擇的概率

2.5 交叉和變異算子

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

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

圖10 個(gè)體交叉運(yùn)算示意圖

2.6 算法流程圖

圖11 算法流程圖

算法實(shí)現(xiàn)及算例分析。

算例 1.為了驗(yàn)證本文中提出的特殊矩形排樣算法的有效性，首先選取一組待加工矩形，待加工零件種類(lèi)及個(gè)數(shù)見(jiàn)表2。

表2 待加工零件數(shù)目表

實(shí)驗(yàn)平臺(tái)：普通PC機(jī)一臺(tái)，處理器Inter Core i3 CPU 1.5 GHz，內(nèi)存(RAM)4 GB，32位Windows 7操作系統(tǒng)，算法使用C++編程語(yǔ)言, 編譯器Visual Studio 2010。

表3 試驗(yàn)數(shù)據(jù)表

由于遺傳算法的概率性，對(duì)于同一組數(shù)據(jù)，每次運(yùn)行的結(jié)果都不盡相同，所以本文采用多次運(yùn)行的方法對(duì)算法的性能進(jìn)行評(píng)估。由于加工零件種類(lèi)的變動(dòng)性，完全連通的排樣圖可能并不存在，所以，子段個(gè)數(shù)為3的排樣圖即在接受范圍之內(nèi)，表4為10次運(yùn)行結(jié)果。

表4 試驗(yàn)數(shù)據(jù)表

其中所求最優(yōu)排樣結(jié)果的編碼{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)定，其收斂過(guò)程如圖12所示。分別為第2代、第11代、第20代和第30代的排樣情況。

圖12 排樣情況

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

表5 排樣結(jié)果評(píng)估

由表5可知，組2中0號(hào)積木數(shù)量較多，平均子段長(zhǎng)度明顯下降，這是因?yàn)闊o(wú)軌積木占用了母版多數(shù)空間，軌道長(zhǎng)度自然縮減，這也是符合常理的。平均子段個(gè)數(shù)在3個(gè)左右，也在本文的接受范圍之內(nèi)。所以，該算法可以有效解決此類(lèi)特殊矩形排樣問(wèn)題。

3 結(jié)束語(yǔ)

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

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

圖13 實(shí)際生產(chǎn)應(yīng)用實(shí)例

[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] 賈志欣. 排樣問(wèn)題的研究現(xiàn)狀與趨勢(shì)[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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] 吳忻生, 吳超成, 劉海明. 基于改進(jìn)遺傳算法的矩形排樣優(yōu)化算法[J]. 制造業(yè)自動(dòng)化, 2013, 35(10): 55-58.

[7] 肖軍民. 一種改進(jìn)遺傳算法在孔群加工路徑中的優(yōu)化[J]. 組合機(jī)床與自動(dòng)化加工技術(shù), 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)波, 王萬(wàn)良, 張景玲, 等. 基于模擬退火算法的矩形優(yōu)化排樣[J]. 計(jì)算機(jī)工程與應(yīng)用, 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

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

周佳立(1981-)，男，浙江諸暨人，副教授，博士，碩士生導(dǎo)師。主要研究方向?yàn)橛?jì)算機(jī)視覺(jué)、模式識(shí)別、機(jī)器人切削。 E-mail：zhoulue@zjut.edu.cn