在数控加工中，孔群加工占比较大，通过优化算法实现对孔类模具数控加工路径的优化显得尤为重要[1-2]。目前，数控加工程序的编写多采用人机交互方式实现，后置处理可选择的路径一般有2～3种可选。利用后置软件处理加工路径时，有时会导致刀具在几个区域间来回跳转，同时又要抬高刀具，极其浪费时间且不能保证路径的优越性。因此，孔群的加工路径规划往往依靠人工经验制定，极大地浪费了人力物力资源。随着机械制造业的快速发展，传统人工制定加工路径的方法难以满足实际生产需要，尽量缩短刀具空行程，减少走刀的时间，提高加工生产效率已成必然趋势[3]。因此，数控编程实现孔群加工路径的优化是目前亟待解决的关键问题。

孔类模具数控加工路径的优化过程可以看作是旅行商问题[4-5]，旅行商问题是一个经典的NP难度的组合优化问题，对于大规模的TSP问题，得到最优解非常困难，因此人们提出了许多常见的近似解法，如最近邻算法、插入算法、r-opt算法、Clark & Wright算法、双生成树启发式算法、Christofides算法[6]，但由于这些算法的缺陷可能不适用于某些特定问题，获取的近似解可能会偏离于最优解。随着科学技术的不断发展，许多实际问题不可能在有效的时间内找到相对较优的解，促使启发式算法的出现，如遗传算法[7]、粒子群优化算法、蚁群优化算法[8]、模拟退火算法、人工神经网络、进化策略、进化编程、禁忌搜索和免疫计算[9]等。

遗传算法是建立在自然选择和自然遗传机理基础上的迭代自适应概率性搜索算法，模拟自然界优胜劣汰的进化现象，将搜索空间映射为遗传空间，把所有可能的解经过编码使之成为一个向量(染色体)，向量里的每一个元素称为基因，然后通过不断的计算各染色体的适应度函数值，选择最好的染色体，获得最优解[7]。遗传算法涉及到的概念有编码、解码、适应度函数和遗传操作等概念。采用遗传算法进行路径规划在目前已成为研究热点，遗传算法的优点在于能很好地处理约束、鲁棒性强，具有潜在的并行性，全局搜索能力强；缺点是收敛较慢，甚至迭代难以收敛，局部搜索能力弱，运行时间长，且当问题规模较大时，迭代过程中会占用很大的内存空间，再加上遗传算子中的交叉算子使得染色体之间具有很大的相似性，可能导致搜索停滞不前，使种群多样性减少，同时，由于变异的力度不够，遗传算法的爬山能力很弱，导致种群多样性得不到补充，使算法出现早熟特征[6-7]。

笔者针对传统遗传算法出现的收敛慢及早熟现象，提出了一种改进的遗传算法，该算法采用最近邻算法选取一系列好的初始种群，加快了种群的搜索速度，同时将禁忌搜索中“禁忌”的思想引入到遗传算法中，并在进化过程中随机引入新个体，保证了种群多样性，增强了算法的爬山能力，避免了算法出现早熟现象。

1孔群加工路径模型

针对多孔型模具的加工，同一平面上存在大量的待加工孔，孔群中也可能会存在不同类型孔。对于同一平面内的K种不同类型的孔，数控加工过程中必须要进行换刀操作。但由于换刀必须要回到刀具参考点，可以将每一类孔的加工看作是单一的旅行商问题[10]，对同类孔样的加工，由于对各个孔的尺寸参数设定、加工方法都是相同的，因此路径优化可以看成简单的点位优化，故只考虑一类孔的路径优化问题。设孔群加工模型集合为G=(V，E)，其中V={0，1，2，…，n}，0为数控机床刀具参考点，1～n代表待加工孔的集合；E为边的集合，边(i,j)的权值为dij，i,j∈V，在该问题中dij取欧氏距离；孔群数控加工路径优化的目标为寻找G的优化巡回路线，该巡回路线是经过图V集中每个顶点恰好一次的路径，即寻找经过V集的每个顶点的最短线路。则加工路径的数学模型为

式中F(x)为孔群加工路径总长度，且

其中：i,j∈V,i≠j；lstart为刀具参考点距起始点的欧氏距离；lend为刀具参考点距路径终点的欧氏距离，

因此，该优化问题的目标是寻找一条不重复的全排列X=(x1,x2,…,xn),xi∈V且xi≠0，使得min{F(x)}。

2改进遗传算法在孔群加工路径中的应用

针对孔群加工路径问题，笔者提出了一种改进遗传算法，该算法是一种基于最近邻、禁忌搜索和遗传算法的新型遗传算法。算法的编码方式，适应度函数的选取，种群选择策略，交叉变异的方式都影响整个算法的运行效率。

2.1编码方式

针对n个孔的加工路径问题，求解的一个重要环节是对其进行编码。在该问题中采用路径表示法的编码方法。二进制编码不适合孔群加工问题，这是由染色体长度n和每一个后代解验证的复杂性所决定。种群中每个染色体长度为n，染色体中的每个基因由1～n的数字组成，0为数控机床刀具参考点，1～n代表待加工孔的集合，染色体为1～n的全排列。染色体的每个基因排序即表示对每个孔进行排序。