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