摘要：將數(shù)控車床作為研究對(duì)象，重點(diǎn)分析和探討了數(shù)控系統(tǒng)加工路徑的優(yōu)化方法。利用K元交換試探算法以及最近鄰算法進(jìn)行對(duì)比，試驗(yàn)結(jié)果顯示，對(duì)數(shù)控系統(tǒng)加工路徑進(jìn)行優(yōu)化之后，數(shù)控車床的加工系統(tǒng)顯著提高了加工效率。在企業(yè)化和規(guī)模化的加工領(lǐng)域，優(yōu)化數(shù)控系統(tǒng)加工路徑能夠?yàn)槠髽I(yè)創(chuàng)造出更加豐厚的經(jīng)濟(jì)回報(bào)。
　　關(guān)鍵詞：K元交換試探算法；最近鄰算法；數(shù)控系統(tǒng)；加工路徑優(yōu)化
　　中圖分類號(hào)：TG659文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-3791(2012)03(A)-0000-00
　　0. 引言
　　對(duì)數(shù)控系統(tǒng)加工路徑進(jìn)行必要的、合理的優(yōu)化還是具有重要的現(xiàn)實(shí)意義的：首先，優(yōu)化數(shù)控系統(tǒng)加工路徑能夠比較明顯地減少數(shù)控機(jī)床的輔助運(yùn)動(dòng)路徑，進(jìn)而實(shí)現(xiàn)加工效率的大幅度提升；其次，對(duì)于某些具有批量化加工生產(chǎn)需求或者零件加工路徑十分復(fù)雜的加工任務(wù)而言，其加工時(shí)間能夠顯著縮短，不僅降低了企業(yè)的生產(chǎn)成本，更是讓企業(yè)能夠獲得了非?？捎^的經(jīng)濟(jì)利潤。在生產(chǎn)實(shí)踐當(dāng)中，如果需要對(duì)微量射出標(biāo)簽機(jī)、點(diǎn)膠機(jī)、繪圖儀、PCB 鉆孔機(jī)以及雕刻機(jī)等設(shè)備工具進(jìn)行加工時(shí)，通常都會(huì)選擇優(yōu)化數(shù)控系統(tǒng)加工路徑，以便獲得更高的加工效率。
　　1. 優(yōu)化數(shù)控系統(tǒng)加工路徑的理論基礎(chǔ)
　　在加工生產(chǎn)領(lǐng)域，利用數(shù)控車床系統(tǒng)對(duì)零件進(jìn)行加工時(shí)，需要將原材料依照預(yù)定的圖樣將其加工成為成形狀各異、大小不同的成品。需要進(jìn)行加工的過程中，數(shù)控系統(tǒng)需要依照預(yù)定的加工先后順序?qū)υ牧线M(jìn)行加工，加工設(shè)備（刀具、鉆頭等）從開始加工一直到加工完成所形成的線路圖便是該數(shù)控系統(tǒng)的加工路徑。數(shù)控車床類型不同、加工任務(wù)不同，相應(yīng)的其加工任務(wù)也存在差異。通常我們可以把數(shù)控加工路徑進(jìn)行詳細(xì)地劃分，使之成為“點(diǎn)”、“線段”、“曲線”以及“閉合曲線”等加工要素。通過優(yōu)化數(shù)控系統(tǒng)加工路徑，能夠讓數(shù)控機(jī)床在加工過程中行走的加工路程最短。加工路程的最短在實(shí)質(zhì)上也就等于加工時(shí)間的最短和加工效率的提高，所以說，優(yōu)化數(shù)控系統(tǒng)加工路徑能夠以更低的成本完成相同數(shù)量的任務(wù)。
　　通過以上分析我們知道，優(yōu)化數(shù)控系統(tǒng)加工路徑在本質(zhì)上與數(shù)學(xué)領(lǐng)域著名的“Traveling Salesman Problem”，即“旅行商人問題”，簡稱“TSP”?！癟SP”描述的內(nèi)容是：現(xiàn)在有一個(gè)旅行商人（Traveling Salesman），他需要對(duì)若干個(gè)的城市進(jìn)行拜訪，并且要提前確定自己的行走路徑。但是對(duì)行走路徑的限制是，每一個(gè)城市只能夠行走一次，并且最后必須要回到原來的城市，簡而言之，旅行商人（Traveling Salesman）規(guī)劃行走路程的最短行走路程應(yīng)該是所有行走路程方案當(dāng)中距離最短（時(shí)間最少）的一種。在這里，我們可以將數(shù)控機(jī)床的刀具或者鉆頭理解為旅行商人（Traveling Salesman），將數(shù)控加工當(dāng)中的任務(wù)點(diǎn)看作“城市”。
　　“TSP”的數(shù)學(xué)描述是：存在一個(gè)距離矩陣：M=（Mab）（其中，a，b=1，2，3，……，n；a，b均為整數(shù)），Mab代表的含義是點(diǎn)a到點(diǎn)b之間的距離。主要目的就是找到一個(gè)從1開始至n結(jié)束的整數(shù)序列（a1，a2，a3，……，an）能夠保證（Ma1a2+Ma2a3+Ma3a4+……+Mana1）所得到的數(shù)值最小。即，求“TSP”的最優(yōu)解。在本文中，主要利用K元交換試探算法以及最近鄰算法來求解。
　　2. K元交換試探算法以及最近鄰算法的優(yōu)化對(duì)比
　　2.1 K元交換試探算法
　　我們知道，一條完整的路徑可以按點(diǎn)劃分為各種段。對(duì)于任意給定的一條已知路徑，交換其中的K段，如果交換后生成的新路徑比交換之前的路徑優(yōu)，則以新路徑作為參考路徑再重復(fù)交換的步驟，這樣嘗試完所有可能的交換得到的路徑就可以認(rèn)為是算法的解。本文的實(shí)驗(yàn)的算法是三元交換：
　　組成路徑的點(diǎn)集用T表示，Xa（T2a-1，T2a），Ya（T2a，T2a+1）表示，用Z表示交換前后的路徑增益，用Yb段替代Xa段產(chǎn)生的增益 ，如果Z=Z1+Z2+Z3+……+Zk≥0，就顯示交換之后的總路徑比交換之前的總路徑要小，即此次 k 元交換有效，如此往復(fù)最后得到的將是這個(gè)算法下的最優(yōu)解。這里需要注意的是選擇Ya的限定條件：為了簡化編程和減少計(jì)算量，限定Ya只在距離T2a的最近五個(gè)點(diǎn)之中尋找T2a+1。
　　2.2 最近鄰算法
　　最近鄰算法又被稱為貪婪算法。它的思想是每次移動(dòng)前都尋找離當(dāng)前所在點(diǎn)最近的點(diǎn)作為目的地。具體步驟如下：
　　第一步，從任意點(diǎn)a1=1，2，3，……，n出發(fā)尋找與出發(fā)點(diǎn)最近的點(diǎn)a2；第二部，把a(bǔ)2作為起點(diǎn)重復(fù)第一步操作，直到回到a1。
　　對(duì)于 n 點(diǎn)的路徑，這種算法得到的解基一般會(huì)超出最優(yōu)解25%。特別需要注意的是，對(duì)于某些情況下，最近鄰算法得到的解可能會(huì)是個(gè)很差的結(jié)果。
　　3. 結(jié)語
　　K元交換試探算法的步驟和編程實(shí)現(xiàn)均比較繁雜、計(jì)算量較大；而最近鄰算法的特點(diǎn)在于步驟簡單、編程較為容易、且計(jì)算量較小?？梢钥吹皆邳c(diǎn)的個(gè)數(shù)比較小的情況下，兩種算法得到了同樣的最優(yōu)解，這時(shí)可以采取最近鄰算法。但是當(dāng)點(diǎn)的個(gè)數(shù)增加到一定數(shù)目時(shí)，K元交換試探算法更具優(yōu)勢，它的解比最近鄰算法得到的解更優(yōu)，這時(shí)應(yīng)當(dāng)采取K元交換試探算法。
　　參考文獻(xiàn)
　　[1] Johnson DS，McGeoch LA. The Traveling Salesman Problem： A Case Study in Local Optimization. Local Search in Combinatorial Optimization. Chichester；New York： John Wiley and Sons，1997，：215-310.
　　[2] Keld Helsgaun. “An Effective Implementation of K-opt Moves for the Lin-Kernighan TSP Heuristic”. Writings on Computer Science. Roskilde University，2007，Vol.109：225-226.
　　[3] Gregory Gutin，Daniel Karapetyan. “Greedy Like Algo-rithms for the Traveling Salesman and Multidimensional As-signment Problem”. Witold Bednorz(editor). InTech，2008，：pp.2.
　　[4] 郭華芳，劉海利，李海生，張嚴(yán)林. 用變長度染色體遺傳算法優(yōu)化加工路徑的方法[J]. 計(jì)算機(jī)工程與應(yīng)用，2009，(06)：106-108.