分步求解切割路徑的優(yōu)化算法研究

徐晟逸，蘇 平，鄧暉飛

（廣東工業(yè)大學(xué)機(jī)電工程學(xué)院，廣東廣州 510006）

分步求解切割路徑的優(yōu)化算法研究

徐晟逸，蘇 平，鄧暉飛

（廣東工業(yè)大學(xué)機(jī)電工程學(xué)院，廣東廣州 510006）

為實(shí)現(xiàn)切割路徑優(yōu)化，提升加工效率，提出了分步求解切割路徑的思想。第一步：引用坐標(biāo)中心點(diǎn)概念，確定所有圖案切割點(diǎn)，實(shí)現(xiàn)切割路徑優(yōu)化問題向旅行商問題的轉(zhuǎn)化。第二步：設(shè)計(jì)遺傳算子，在MATLAB下實(shí)現(xiàn)遺傳算法對(duì)旅行商問題的仿真求解。與采用最鄰近算法確定切割點(diǎn)方法的結(jié)果對(duì)比，前者最優(yōu)路徑（8 845.2 mm）為后者最優(yōu)路徑（9 652.0 mm）的91.6%，證明了提出算法的可行性。

切割路徑優(yōu)化；旅行商問題；遺傳算法；最鄰近算法

0 引言

切割是加工行業(yè)中一項(xiàng)重要的技術(shù)，隨著科學(xué)技術(shù)的發(fā)展，企業(yè)對(duì)切割加工效率的要求越來越高，切割加工的效率和質(zhì)量將直接影響到生產(chǎn)的效率和質(zhì)量。針對(duì)大理石材的大批量切割生產(chǎn)，提高加工效率就顯得尤為重要。為提升效率，本文立足于優(yōu)化切割路徑這一點(diǎn)來實(shí)現(xiàn)。在切割過程中，刀具的空走行程完全是無效行程，通過減少這些無效行程達(dá)到縮短單個(gè)產(chǎn)品的生產(chǎn)時(shí)間，更是實(shí)現(xiàn)批量生產(chǎn)加工效率的跳躍。在切割路徑優(yōu)化這一問題上，大量學(xué)者都做出了研究。C Oysu等作者在解決刀具優(yōu)化問題時(shí)，提出了一種把遺傳算法與模擬退火算法混合的方法[1]。這種智能算法相結(jié)合的混合算法，雖然取得了不錯(cuò)的效果，但是計(jì)算起來復(fù)雜度高，效率低，不適應(yīng)快速生產(chǎn)加工的需求。李妮妮等作者提出了一種基于局部搜索和遺傳算法結(jié)合的切割路徑優(yōu)化算法[2]。該算法從加工輪廓中提取節(jié)點(diǎn)，通過局部搜索法對(duì)節(jié)點(diǎn)進(jìn)行局部路徑優(yōu)化，再運(yùn)用遺傳算法求得切割最優(yōu)路徑。孫慧平等作者采用增加節(jié)點(diǎn)的方法把切割路徑優(yōu)化問題變換為經(jīng)典旅行商問題，再用遺傳算法實(shí)現(xiàn)求解[3]。羅辭勇等作者通過建立加工中空走路徑優(yōu)化的數(shù)學(xué)模型，將問題轉(zhuǎn)化為旅行商問題后，采用自適應(yīng)鄰域遺傳算法來求解[4]。這些研究者在求解切割問題時(shí)，均采用簡(jiǎn)化問題的思想，實(shí)現(xiàn)問題的分步求解。在計(jì)算效率上都有了提升，但是在把問題轉(zhuǎn)為旅行商問題來求解時(shí)，局部搜索法和鄰近算法都有自身的局部?jī)?yōu)化的弊端，并在很大程度上經(jīng)簡(jiǎn)化后，丟失了最優(yōu)解空間。為了解決這些問題，本文提出基于坐標(biāo)中心點(diǎn)實(shí)現(xiàn)切割問題向旅行商問題轉(zhuǎn)化的方法，使得簡(jiǎn)化后的解空間集中在一個(gè)包絡(luò)面積較小的范圍內(nèi)，極大概率的保留了最優(yōu)解空間，在此基礎(chǔ)上用遺傳算法實(shí)現(xiàn)最優(yōu)路徑的求解，提高了問題求解的準(zhǔn)確度與效率。

1 切割路徑數(shù)學(xué)模型

在切割過程中，要求依次加工所有圖案且加工路徑最短。切割路徑總行程由圖案輪廓切割行程和刀頭空走行程構(gòu)成。其中，圖案輪廓切割行程相對(duì)不變且位置固定，刀頭空走行程與每個(gè)圖案切割起始點(diǎn)的選取以及各個(gè)圖案的切割順序相關(guān)。

已知經(jīng)排樣優(yōu)化的樣板包含N個(gè)圖案。Vi表示為第i個(gè)圖案，其中1≤i≤N。ni代表第i個(gè)圖案包含頂點(diǎn)的個(gè)數(shù)。Vi,j表示為第i個(gè)圖案的第j個(gè)頂點(diǎn)，其中j∈ ni。

圖1 樣板示意圖

切割路徑總行程由圖案輪廓切割行程和刀具空走行程組成，即：

其中，LP：刀具切割空走行程；

LM：輪廓切割行程；

ls：切割原點(diǎn)到第一個(gè)圖案切割起始點(diǎn)的距離；

le：第N個(gè)圖案切割起始點(diǎn)到原點(diǎn)的距離；第i個(gè)圖案與第i+1個(gè)圖案之間的切割空走行程。

分析模型，LM屬于切割總行程中固定不變部分，無優(yōu)化空間。因此模型可簡(jiǎn)化為：

2 問題的求解

為避免大量復(fù)雜計(jì)算，針對(duì)上述模型，本文對(duì)問題進(jìn)行分步求解，降低求解難度，增加求解效率。具體思路：（1）確定每個(gè)圖案的切割起始點(diǎn)，將路徑優(yōu)化問題轉(zhuǎn)化為旅行商問題，引入坐標(biāo)中心點(diǎn)這一概念，利用圖案輪廓頂點(diǎn)與坐標(biāo)中心點(diǎn)的幾何關(guān)系，找出每個(gè)圖案的切割起始點(diǎn)，產(chǎn)生一個(gè)相對(duì)密集、包絡(luò)面積較小的點(diǎn)群，將問題轉(zhuǎn)化為TSP來求解；（2）確定圖案之間的切割順序，得出最優(yōu)切割路徑。采用遺傳算法，在MATLAB下實(shí)現(xiàn)求解，得出最優(yōu)切割路徑。

定義第i個(gè)圖案的第j個(gè)頂點(diǎn)的坐標(biāo)為Pi,j（xi,j，yi,j）。其中1≤i≤N ，1≤j≤ni。坐標(biāo)中心點(diǎn)M（x，y）的x、y定義如下：

其中， Pi,j：第i個(gè)圖案的第j個(gè)頂點(diǎn)的坐標(biāo)；

xi,j：第i個(gè)圖案的第j個(gè)頂點(diǎn)的x坐標(biāo)；

yi,j：第i個(gè)圖案的第j個(gè)頂點(diǎn)的y坐標(biāo)。

以坐標(biāo)中心點(diǎn)M（x，y）為基點(diǎn)，定義第i個(gè)圖案的第j個(gè)頂點(diǎn)到坐標(biāo)中心點(diǎn)的距離為di,j。

其中，i=1，2，3…N，1≤j≤ni。min(di,j)

表示第i個(gè)圖案中頂點(diǎn)到坐標(biāo)中心點(diǎn)的最短距離。把min(di,j)中對(duì)應(yīng)的頂點(diǎn)坐標(biāo)Pi,j確定為圖案的切割起始點(diǎn)。至此，得到N個(gè)圖案的切割起始點(diǎn)集合{Pi,j}，完成了向旅行商問題的轉(zhuǎn)化。

以距離坐標(biāo)中心點(diǎn)距離最近為原則，產(chǎn)生相對(duì)集密的、包絡(luò)面積較小的點(diǎn)群，區(qū)別于最鄰近算法的局部?jī)?yōu)良性，該點(diǎn)群在更大可能保留最優(yōu)切割路徑解空間的前提下，實(shí)現(xiàn)在較小包絡(luò)面積中尋找最優(yōu)切割路徑的可能。

結(jié)合生產(chǎn)實(shí)際，將已確定N個(gè)圖案的切割起始點(diǎn)和切割原點(diǎn)看成旅行商問題[5]中N+1個(gè)城市的坐標(biāo)，求解旅行商問題，得到最優(yōu)切割路徑。旅行商問題是一個(gè)經(jīng)典的組合優(yōu)化問題。由于該問題的可行解數(shù)與城市個(gè)數(shù)是成指數(shù)型增長(zhǎng)的，故旅行商問題是一個(gè)NP難問題，宜采用近似求解。目前，這一問題已研究的比較成熟，大量學(xué)者采用智能優(yōu)化算法來解決。包括模擬退火算法，人工神經(jīng)網(wǎng)絡(luò)，蟻群算法，遺傳算法，禁忌搜索，粒子群優(yōu)化算法等。本文采用遺傳算法來求解。遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法，對(duì)于組合優(yōu)化中的NP完全問題非常有效的。以適者生存為原則，在群體搜索技術(shù)下逐代進(jìn)化，最終得到最優(yōu)解或次優(yōu)解。具體步驟如下：（1）確定解空間的編碼方式；（2）初始種群的產(chǎn)生及適應(yīng)度函數(shù)的選擇；（3）選擇、交叉、變異算子的設(shè)計(jì)。

2.1 編碼

遺傳算法不能直接處理問題空間的解。為了將問題空間的解轉(zhuǎn)化為由基因按一定結(jié)構(gòu)組成的染色體或個(gè)體，本文采用十進(jìn)制編碼[6]。產(chǎn)生隨機(jī)數(shù)列S1S2…SN作為一個(gè)個(gè)體，其中0＜Si＜1，i= 2，3，…，N-1，S1=0，SN=1。每個(gè)隨機(jī)序列對(duì)應(yīng)種群中一個(gè)個(gè)體，例如8個(gè)圖案的切割順序問題的染色體表示為：[0.15 0.67 0.38 0.64 0.43 0.59 0.89 0.73]，其中編碼i位置代表圖案i，i位置上的隨機(jī)數(shù)表示圖案i在切割路徑中的排序，將隨機(jī)數(shù)升序排列得到切割順序?yàn)椋?/p>

1-3-5 -6-4-2-8-7

2.2 初始種群及適應(yīng)度函數(shù)

為節(jié)省進(jìn)化代數(shù)，從一開始就能夠獲得一個(gè)較好的初始群體，本文采用改良圈[7]算法確定初始種群。對(duì)于初始圈C：

其 中 2≤u＜v≤N+1，2≤Lu＜Lv≤N+1。逆反u與v之間的順序，得到新群體：

適應(yīng)度函數(shù)用于評(píng)價(jià)個(gè)體的優(yōu)劣程度。適度越高，個(gè)體越好。每個(gè)個(gè)體代表一條切割空走路徑，為保留較優(yōu)個(gè)體，本文采用切割路徑空走行程大小的倒數(shù)作為適應(yīng)度函數(shù)，即：

其中，D：切割路徑空走行程；

d0d1：切割原點(diǎn)與第一個(gè)圖案間的空走行程；

dNd0：第N個(gè)圖案與切割原點(diǎn)間的空走行程；

didi+1：相鄰兩圖案的空走行程。

2.3 選擇、交叉、變異算子設(shè)計(jì)

選擇是模擬自然界生命繁殖和優(yōu)勝劣汰的主要載體，即是一個(gè)從當(dāng)前群體中選擇適應(yīng)值高的個(gè)體以生成交配池的過程。依據(jù)適應(yīng)度函數(shù)值的大小對(duì)個(gè)體進(jìn)行選擇，適應(yīng)度值大的個(gè)體被選中的概率高，適應(yīng)度值小的個(gè)體可能被淘汰。本文采用李晨等作者提出的基于排序的多輪輪盤賭選擇算子與最佳算子保存法相結(jié)合的法[8]。提高算子選優(yōu)能力同時(shí)也減少了隨機(jī)性所產(chǎn)生的誤差，并達(dá)到了既能夠選出最好個(gè)體又能夠保證種群多樣性的效果。

交叉是把兩個(gè)父代個(gè)體的部分基因加以替換重組而生成新個(gè)體的操作，從而使更優(yōu)個(gè)體的出現(xiàn)成為可能。為保持算法的全局優(yōu)化能力，本文采用單點(diǎn)交叉法[9]來實(shí)現(xiàn)兩個(gè)配對(duì)個(gè)體部分基因的交換。隨機(jī)選取配對(duì)個(gè)體W1、W2的基因i位置處為交叉點(diǎn)，則W1的前i個(gè)基因加上W2的后N+2-i個(gè)基因構(gòu)成新的個(gè)體Z1，W2的前i個(gè)基因加上W1的后N+2-i個(gè)基因構(gòu)成新的個(gè)體Z2(1 ＜i＜102)。

變異是通過隨機(jī)改變個(gè)體中的某些基因，產(chǎn)生出新的個(gè)體。它可以防止求解過程中過早收斂產(chǎn)生局部最優(yōu)解而非總體最優(yōu)解，決定遺傳算法的局部搜索能力。在本文，對(duì)于選定的個(gè)體，采取 產(chǎn) 生 兩 個(gè) 隨 機(jī) 整 數(shù) α、β ，1≤α＜β≤N+1，交換α、β基因位上對(duì)應(yīng)基因的策略實(shí)現(xiàn)變異。

3 實(shí)例應(yīng)用

圖2 待切割樣板圖

對(duì)樣板圖中的圖案依次進(jìn)行編號(hào)，列出每個(gè)圖案中的各個(gè)節(jié)點(diǎn)坐標(biāo)：

由坐標(biāo)中心點(diǎn) M（x，y）的計(jì)算公式得到中心坐標(biāo)點(diǎn)：M（750.000，750.000）。

由min(di,j)確定切割點(diǎn)集合：

在MATLAB中實(shí)現(xiàn)遺傳算法的程序設(shè)計(jì)[10]。取種群大小M=50，交叉概率Pc=0.95，變異概率Pm=0.05，進(jìn)化代數(shù)1 000。仿真求解結(jié)果如圖3，得到優(yōu)化路徑的大小為8 845.2 mm。對(duì)應(yīng)的最短切割路徑中，原點(diǎn)的編號(hào)為0，具體如下：

0-16-36 -17-18-19-20-38-37-45

46-47-48 -43-44-35-15-14-34-33

13-32-12 -31-11-10-30-42-41-29

28-9-27 -8-26-25-40-39-24-7-6

23-5-22 -4-21-3-2-1-0

同樣的包含48個(gè)圖案的待切割樣板，采用鄰近算法實(shí)現(xiàn)切割路徑優(yōu)化問題對(duì)TSP問題的轉(zhuǎn)化，得到切割點(diǎn)集合：

圖3 基于中心坐標(biāo)點(diǎn)的最優(yōu)切割路徑圖

取相同的種群大小、交叉概率、變異概率以及進(jìn)化代數(shù)，在MATLAB下實(shí)現(xiàn)遺傳算法仿真求解，結(jié)果如圖4。得到最短路徑大小為：9 652.0 mm。對(duì)應(yīng)的最優(yōu)切割路徑為：

0-16-15 -14-34-35-43-33-13-12

32-31-11 -30-29-28-10-27-9-8

26-40-25 -24-6-5-4-21-22-23

24-39-41 -42-48-47-45-46-38-20

3-2-19 -18-37-44-36-17-1-0

經(jīng)仿真對(duì)比可知，采用本文提出的中心點(diǎn)坐標(biāo)對(duì)切割問題實(shí)現(xiàn)轉(zhuǎn)化的方法比由最鄰近算法實(shí)現(xiàn)切割問題轉(zhuǎn)化的方法效果更佳，得到的最優(yōu)切割路徑空走行程大小為后者的91.6%。進(jìn)一步縮短了切割路徑的空走行程，達(dá)到了切割效率的提升。

圖4 基于最鄰近算法的最優(yōu)切割路徑圖

4 結(jié)束語

針對(duì)切割路徑優(yōu)化這一問題，本文遵循將復(fù)雜問題簡(jiǎn)單化的思想，通過引入坐標(biāo)中心點(diǎn)這一概念，實(shí)現(xiàn)切割路徑優(yōu)化問題向TSP問題的轉(zhuǎn)化。最終通過實(shí)例對(duì)比分析，驗(yàn)證算法的可行性。

［1］ Oysu C，Bingul Z.Application of heuristic and hy?brid-GASA algorithms to tool-path optimization problem for minimizing airtime during machining［J］.Engineer?ing Applications of Artificial Intelligence，2009，22（3）：389-396.

［2］李妮妮，陳章位，陳世澤.基于局部搜索和遺傳算法的激光切割路徑優(yōu)化［J］.計(jì)算機(jī)工程與應(yīng)用，2010（2）：234-236.

［3］孫慧平，李健，郭偉剛.遺傳算法在束流切割路徑優(yōu)化中的應(yīng)用［J］.農(nóng)業(yè)機(jī)械學(xué)報(bào)，2008，39（39）：158-160.

［4］羅辭勇，盧斌，韓力.求解空走優(yōu)化路徑的自適應(yīng)鄰域遺傳算法［J］.重慶大學(xué)學(xué)報(bào)，2009，32（12）：1477-1481.

［5］劉荷花，崔超，陳晶.一種改進(jìn)的遺傳算法求解旅行商問題［J］.北京理工大學(xué)學(xué)報(bào)，2013，33（004）：390-393.

［6］張曉繢，方浩，戴冠中.遺傳算法的編碼機(jī)制研究［J］.信息與控制，1997，26（2）：134-139.

［7］曹旭.旅游線路優(yōu)化設(shè)計(jì)研究［D］.西安：西北工業(yè)大學(xué)，2012.

［8］李晨，寧紅云.改進(jìn)的遺傳算法選擇算子［J］.天津理工大學(xué)學(xué)報(bào)，2009，24（6）：1-4.

［9］運(yùn)籌學(xué)，樹棟，遺傳學(xué).遺傳算法原理及應(yīng)用［M］.北京：國防工業(yè)出版社，1999.

［10］儲(chǔ)理才.基于MATLAB的遺傳算法程序設(shè)計(jì)及TSP問題求解［J］.集美大學(xué)學(xué)報(bào)：自然科學(xué)版，2001，6（1）：14-19.

Research on Optimization Algorithm for Solving the Cutting Path Step by Step

XU Sheng-yi，SU Ping，DENG Hui-fei
（School of Mechatronic Engineering，Guangdong University of Technology，Guangzhou510006，China）

To achieve the cutting path optimization and improve processing efficiency，this paper proposes a thought of solve the cutting path step by step.The first step is to cite the conception of center point of coordinates,determine all pattern’s cutting point to achieve the transformation of the cutting path optimization problem to the TSP.The second step is to design the genetic operators and realize the simulation of solving the TSP by GA in the MATLAB.Compared the method using the nearest neighbor algorithm to determine all the cutting points,the best path(8845.2mm)of use the center point of coordinates is 91.6%of the latter’s best path(9655.8mm).Demonstrated the feasibility of the proposed algorithm.

cutting path optimization；TSP；GA；nearest neighbor algorithm

TP312

A

1009－9492(2014)09－0081－04

10.3969/j.issn.1009-9492.2014.09.022

徐晟逸，男，1987年生，湖南株洲人，碩士研究生，研究領(lǐng)域：生產(chǎn)加工優(yōu)化，組合優(yōu)化問題。

(編輯：向 飛)

2014－03－15