基于改进遗传算法的模具零件孔群加工路径优化

杨彩虹 林守金 杨明

摘要：为提高孔群模具的加工效率，提出了一种最近邻、遗传算法和禁忌搜索相融合的改进遗传算法。采用最近邻算法选取一系列好的初始种群，同时将禁忌搜索中“禁忌”的思想引入到遺传算法中，并在进化过程中随机引入部分新个体，进行迭代搜索。根据孔群加工特点建立了类似旅行商问题的数学模型，并用改进算法求解最短加工路径，在分布复杂的孔类模具上进行数值实验。轮胎实例应用结果表明，改进算法优化后路径长度比CAM系统算法优化后路径长度缩短5.31%，比X向路径法缩短77.88%，比Y向路径法缩短77.63%，比最近邻算法缩短4.52%;当实验参数相同时，改进算法路径长度比遗传算法缩短14.65%，且运行时间平均缩短了63.60%。改进算法的路径长度明显缩短，有效提高了孔群的数控加工效率。其通用性较好，在提升数控系统孔群加工效率方面具有参考价值。

关键词：应用数学;孔群加工;最近邻;禁忌搜索;遗传算法

中图分类号：TP399文献标志码：A

文章编号：1008-1534（2019）02-0091-07

在数控加工中，孔群加工占比较大，通过优化算法实现对孔类模具数控加工路径的优化显得尤为重要[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集的每个顶点的最短线路。则加工路径的数学模型为

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

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

2.1编码方式

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

2.2适应度函数的选择

对于一条路径的优劣，判断的标准是看其适应度函数的值，针对该问题，用其路径长度的倒数作为其适应度函数的值，即

当Fitness（x）值越大时，F（x）值就越小，表明加工路径总长度越短，对应加工路径越好。一般迭代次数作为终止条件，因此，在最后一代中最好的染色体可能是局部最优解或是全局最优解。

2.3种群选择策略

种群选择策略采用精英保留策略，此方法是比较种群中所有个体的适应度值，从中择优选择一部分个体作为父体，并利用选择的个体进行交叉和变异操作。

1）交叉交叉是父代將自身优秀基因遗传给子代的一种繁殖操作，对于每一个交叉操作，利用选择策略选出的个体参与交叉操作，产生适应度值高的新个体的可能性更高。常用交叉算子有顺序交叉（orderedcrossover，OX），部分映射交叉（parliallymappedcrossover，PMX），循环交叉（cyclecrossover，CX）[11];改进算法选择顺序交叉算子，在父代F1中随机选择2个交叉点，将父代F1交叉点之间的基因片段作为子代K相同位置的基因片段，把F2中非F1交叉点之间的基因按顺序分别放在子代K的基因片段两边的位置，生成新的子代个体。以染色体长度n=10为例，选择父代F1和F2，若随机选择交叉点位置为4，7，则具体交叉操作如下。

父代F1：[WB]238（9675）1014，

父代F2：[DW]65374210198，

子代K：[DW]342（9675）1018，（6）

2）变异变异是在保留父代优秀基因并保持种群多样性的一种进化手段。常用变异算子有：移位变异（displacementmutation，DM），交换变异（exchangemutation，EM），逆转变异（inversionmutation，IVM）[11];改进算法采用交换变异算子进行变异操作，随机作用在一个父代染色体上，在父代F中随机选择4个变异点，按升序排列n1<n2<n3<n4，将父代F中[n1，n2]之间基因片段与其[n3，n4]之间基因片段互换生成新的子代K。以染色体长度n=10为例，选择父代F，若随机选择变异点位置为2，3，7，9，则具体变异操作如下：

父代F：[WB]6（51）742（1038）9，

子代K：[DW]6（1038）742（51）9。（7）

2.4改进遗传算法流程

考虑到最近邻算法和遗传算法各自具有优缺点，最近邻算法生成的路径的基因总体是比较优良的，而遗传算法本身具有很高的并行性等。鉴于此，笔者设计了结合最近邻和禁忌搜索思想的遗传算法来求解加工路径优化问题。改进遗传算法的流程如下，算法流程如图1所示。

Step1.设定种群大小Numpop、设定交叉概率crate、变异概率mrate、选择率srate和随机概率rrate，并且设定算法的终止条件r=Iteration，置进化代数r=0，禁忌表tabu=[];

Step2.将每一个孔作为出发点，由最近邻算法生成的路径所构成的集合记为P，并计算个体的适应度，从P中随机选择Numpop个个体初始化第一代种群S（r）;

Step3.更新禁忌表tabu，禁忌表中存放已经搜索过的路径;

Step4.择优选择，比较种群S（r）中所有个体的适应度值，从中择优选择一部分个体作为父体F;

Step5.执行交叉操作产生新的路径[AKS-]（r），且新的路径不与禁忌表中路径重复;

Step6.执行变异操作产生新的路径[AKS=]（r），且新的路径不与禁忌表中路径重复;

Step7.更新父代和子代的并集Srecent（r）;

Step8.随机生成新的路径S*（r），且新的路径不与禁忌表中路径重复（引入新个体，增加种群多样性）;

Step9.r←r+1，在Srecent（r）∪S*（r）择优选择Numpop个个体作为新的种群S（r）;

Step10.若满足终止条件，则停止并输出最短路径F（xbest）;否则转Step3。

3轮胎实例应用

3.1遗传算法与改进算法对比实验

为测试改进遗传算法在路径优化中的性能，以大型轮胎模具孔群加工为例，提取轮胎模具Step文件几何信息得到模具俯视面孔位分布[12-15]，如图2所示。

针对图2中平面孔进行路径的加工优化，通过对轮胎模具Step文件分析可知，该平面孔为同一类型孔，且孔群规模为

408个，采用提出的改进算法和遗传算法分别对该孔群加工路径进行优化，在实验中，2种算法参数设置相同，且参数设置如下：种群大小Numpop=180，设定交叉概率crate=0.9、变异概率mrate=0.02、选择率srate=0.3和随机概率crate=0.9，并且设定算法的终止条件Iteration=500。通过实验，数据如表1所示。

由表1可知，经过10次路径优化实验，遗传算法的平均路径长度为Sgamean=23356.3994mm，最优路径长度为Sgamin=22400.5508mm，平均运行时间Tgamean=10547.4750s，改进算法的平均路径长度为Simgamean=19934.0159mm，最优路径长度为Simgamin=19930.7042mm，平均运行时间Timgamean=3839.2024s。与遗传算法相比，改进算法的平均路径长度缩短了14.65%，最优路径长度缩短了11.03%，平均运行时间缩短了63.60%。为了更好地对比算法性能，利用Matlab软件绘制出2种算法适应度进化曲线图，如图3所示。

从图3中可以看出，在迭代次数相同时，改进算法的适应度值更大，故而路径更优，且与传统遗传算法相比，能更快收敛到全局最优。图4为遗传算法在上述参数下的最优加工轨迹图，图5为改进算法最优加工轨迹图。

3.2其他优化算法对比实验

为验证改进算法的先进性，分别采用自主研发的CAM系统算法、X向路径法、Y向路径法对该模具孔群进行路径优化。其中X向路径法是按照孔群X坐标值升序排列进行加工的过程，Y向路径法是按照孔群Y坐标值升序排列进行加工的过程。图6a）为CAM系统算法生成的轨迹图，图6b）为X向路径法生成的轨迹图，图6c）为Y向路径法生成的轨迹图。

3.3实验结果及数据分析

由表2中不同优化方法孔群加工最优路径长度对比可知，改进算法优化后路径长度比CAM系统算法优化后路径长度缩短5.31%，比X向路径法缩短77.88%，比Y向路径法缩短77.63%，比最近邻算法缩短4.52%，进化代数500次且参数相同时，比遗传算法路径长度缩短14.65%。由此可见，改进算法优化后路径长度最短，能够有效缩短孔群加工路径长度，减少加工时间，从而提高了加工效率。

4其他模具实例应用

为验证改进算法的通用性，对非均匀，变化比较复杂的某孔类模具实例进行路径优化实验，该模具实例由197个非均匀分布的孔构成，分别用最近邻算法，自主研发的CAM系统算法，X向路径法，Y向路径法，遗传算法以及改进遗传算法对该模具孔群进行路径优化，不同算法最优加工轨迹见图7。表3为不同优化方法的最优路径长度结果及比较。

从表3可知，提出的改进遗传算法相较其他算法加工路径长度明显缩短，可以有效提高加工效率。

5结语

提出的改进遗传算法，结合了最近邻和禁忌搜索的思想。采用最近邻算法选取一系列好的初始种群，加快了种群的搜索速度，同时将禁忌搜索中“禁忌”的思想引入到遗传算法中，使得种群在进化过程中保证了多样性，增强了算法的爬山能力，避免了算法出现早熟。轮胎实例以及其他模具实例表明，采用改进遗传算法进行孔群加工路径优化能以较快的速度找到更优的解，极大地提高了生产效率和节省资源消耗，在实际生产轮胎模具中已得到证实。同时，在其他类型实例的加工路径的优化问题中可利用本算法进行路径优化，也能取得较好的结果。但当孔群规模特别大时，算法运行效率有待提升，下一步的研究重心将放在提高超大规模孔群路径优化的运行效率方面。

参考文献/References：

[1]LUONGLHS，SPEDDINGT.Anintegratedsystemforprocessplanningandcostestimationinholemaking[J].TheInternationalJournalofAdvancedManufacturingTechnology，1995，10（6）：411-415.

[2]龚玉玲，武美萍，徐晓栋，等.基于改进遗传算法的孔群数控加工路径优化[J].组合机床与自动化加工技术，2017（11）：52-56.

GONGYuling，WUMeiping，XUXiaodong，etal.Researchonpathoptimizationofholegroupmachiningbasedonimprovedgeneticalgorithm[J].ModularMachineTool&AutomaticManufacturingTechnique，2017（11）：52-56.

[3]段振云，孔令斌，赵文辉，等.覆盖件模具数控加工方法的研究[J].组合机床与自动化加工技术，2015（4）：123-125.

DUANZhenyun，KONGLingbin，ZHAOWenhui，etal.ResearchonthemethodsofcoveringpartsmouldNCmachining[J].ModularMachineTool&AutomaticManufacturingTechnique，2015（4）：123-125.

[4]周正武，丁同梅.基于TSP和GA孔群加工路径优化问题的研究[J].组合机床与自动化加工技术，2007（7）：30-32.

ZHOUZhengwu，DINGTongmei.ResearchonholesmachiningpathplanningoptimizationwithTSPandGA[J].ModularMachineTool&AutomaticManufacturingTechnique，2007（7）：30-32.

[5]ZHANGWeibo，ZHUGuangyu.Drillingpathoptimizationbyoptimalforagingalgorithm[J].IEEETransactionsonIndustrialInformatics，2017（99）：1-1.10.1109/TII.2017.2772314.

[6]文永軍.旅行商问题的两种智能算法[D].西安：西安电子科技大学，2010.

WENYongjun.TwokindsofIntelligentAlgorithmsforTravelingSalesmanProblem[D].Xi′an：XidianUniversity，2010.

[7]汪定伟.智能优化方法[M].北京：高等教育出版社，2007.

[8]潘晓萌，李冰.蚁群算法优化和路径规划问题的应用研究[J].科技通报，2016，32（6）：99-103.

PANXiaomeng，LIBing.Applicationofantcolonyoptimizationandpathplanning[J].BulletinofScienceandTechnology，2016，32（6）：99-103.

[9]王磊，肖人彬.基于免疫记忆的人工免疫算法模型及其应用[J].模式识别与人工智能，2002，15（4）：385-391.

WANGLei，XIAORenbin.Analgorithmicmodelofartificialimmunesystembasedonimmunologicalmemoryanditsimplementation[J].PatternRecognitionandArtificialIntelligence，2002，15（4）：385-391.

[10]肖军民.一种改进遗传算法在孔群加工路径中的优化[J].组合机床与自动化加工技术，2015（2）：151-153.

XIAOJunmin.OptimizationofNCmachiningpathforholesbasedonimprovedgeneticalgorithm[J].ModularMachineTool&AutomaticManufacturingTechnique，2015（2）：151-153.

[11]王春香，郭晓妮.基于遗传蚁群混合算法的孔群加工路径优化[J].机床与液压，2011，39（21）：43-45.

WANGChunxiang，GUOXiaoni.Holesmachiningpathoptimizationbasedonahybridalgorithmintegratedgeneticalgorithmwithantcolonyoptimization[J].MachineTool&Hydraulics，2011，39（21）：43-45.

[12]赵继俊.优化技术与MATLAB优化工具箱[M].北京：机械工业出版社，2011.

[13]SUHSH，CHOJH，HONGHD.OnthearchitectureofintelligentSTEP-compliantCNC[J].InternationalJournalofComputerIntegratedManufacturing，2002，15（2）：168-177.

[14]盛濱.基于STEP-NC的信息提取系统的研究与实现[D].厦门：厦门大学，2008.

SHENGBin.ResearchandImplementationofInformationExtractionSystembasedonSTEP-NC[D].Xiamen：XiamenUniversity，2008.

[15]ISO10303-21.Industrialautomationsystems-Productdatarepresentationandexchange-Part21：Implementationmethod：Cleartextencodingoftheexchangestructure[S].1997.