浅谈如何优化数控系统加工路径

　　摘要：将数控车床作为研究对象，重点分析和探讨了数控系统加工路径的优化方法。利用K元交换试探算法以及最近邻算法进行对比，试验结果显示，对数控系统加工路径进行优化之后，数控车床的加工系统显著提高了加工效率。在企业化和规模化的加工领域，优化数控系统加工路径能够为企业创造出更加丰厚的经济回报。
　　关键词：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.