淺談如何優化數控系統加工路徑

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