徐晟逸，蘇 平，鄧暉飛

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

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

徐晟逸，蘇 平，鄧暉飛

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

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

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

0 引言

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

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

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

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

圖1 樣板示意圖

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

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

LM：輪廓切割行程；

ls：切割原點到第一個圖案切割起始點的距離；

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

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

2 問題的求解

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

定義第i個圖案的第j個頂點的坐標為Pi,j（xi,j，yi,j）。其中1≤i≤N ，1≤j≤ni。坐標中心點M（x，y）的x、y定義如下：

其中， Pi,j：第i個圖案的第j個頂點的坐標；

xi,j：第i個圖案的第j個頂點的x坐標；

yi,j：第i個圖案的第j個頂點的y坐標。

以坐標中心點M（x，y）為基點，定義第i個圖案的第j個頂點到坐標中心點的距離為di,j。

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

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

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

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

2.1 編碼

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

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

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

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

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

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

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

d0d1：切割原點與第一個圖案間的空走行程；

dNd0：第N個圖案與切割原點間的空走行程；

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

2.3 選擇、交叉、變異算子設計

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

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

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

3 實例應用

圖2 待切割樣板圖

對樣板圖中的圖案依次進行編號，列出每個圖案中的各個節(jié)點坐標：

由坐標中心點 M（x，y）的計算公式得到中心坐標點：M（750.000，750.000）。

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

在MATLAB中實現(xiàn)遺傳算法的程序設計[10]。取種群大小M=50，交叉概率Pc=0.95，變異概率Pm=0.05，進化代數(shù)1 000。仿真求解結(jié)果如圖3，得到優(yōu)化路徑的大小為8 845.2 mm。對應的最短切割路徑中，原點的編號為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個圖案的待切割樣板，采用鄰近算法實現(xiàn)切割路徑優(yōu)化問題對TSP問題的轉(zhuǎn)化，得到切割點集合：

圖3 基于中心坐標點的最優(yōu)切割路徑圖

取相同的種群大小、交叉概率、變異概率以及進化代數(shù)，在MATLAB下實現(xiàn)遺傳算法仿真求解，結(jié)果如圖4。得到最短路徑大小為：9 652.0 mm。對應的最優(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)仿真對比可知，采用本文提出的中心點坐標對切割問題實現(xiàn)轉(zhuǎn)化的方法比由最鄰近算法實現(xiàn)切割問題轉(zhuǎn)化的方法效果更佳，得到的最優(yōu)切割路徑空走行程大小為后者的91.6%。進一步縮短了切割路徑的空走行程，達到了切割效率的提升。

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

4 結(jié)束語

針對切割路徑優(yōu)化這一問題，本文遵循將復雜問題簡單化的思想，通過引入坐標中心點這一概念，實現(xiàn)切割路徑優(yōu)化問題向TSP問題的轉(zhuǎ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］.計算機工程與應用，2010（2）：234-236.

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

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

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

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

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

［8］李晨，寧紅云.改進的遺傳算法選擇算子［J］.天津理工大學學報，2009，24（6）：1-4.

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

［10］儲理才.基于MATLAB的遺傳算法程序設計及TSP問題求解［J］.集美大學學報：自然科學版，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