基于改进遗传算法的多类图元混合加工路径优化方法*

陈光黎 雷欢 吴亮生 高小征 杨阳 周俊伍



基于改进遗传算法的多类图元混合加工路径优化方法*

陈光黎1雷欢1吴亮生1高小征1杨阳1周俊伍2

（1.广东省自动化研究所 广东省现代控制技术重点实验室广东省现代控制与光机电技术公共实验室 2.佛山金皇宇机械实业有限公司）

为解决数控加工中复杂轨迹的排序规划问题，提出基于改进遗传算法的多类图元混合加工路径优化方法。针对不同轨迹段图形进行分类编码设计，将适用多类图元混合路径优化的第二类GTSP模型转化为TSP问题，同时在遗传进化过程中采用线性定标和自适应遗传算子等方式进行全局路径排序，最后通过封闭式与非封闭式轨迹段的起点计算与局部寻优求解最短路径。通过扩展应用开源GAlib库进行了测试，试验证明：算法快速收敛，有效解决多类图元混合路径优化问题，可提升数控机床加工效率。

GTSP模型；遗传算法；多类图元混合轨迹；路径优化

0 引言

在数控加工作业中，通常要求CAM软件能够读取AutoCAD的图形数据并将其转化为数控加工系统所执行的加工G代码。图形交互式文件（drawing interchange format，DXF）是Autodesk公司推出的AutoCAD与CAD/CAM编程系统进行加工图形数据交换的标准格式文件[1]。但DXF文件中的图形元素是依据产品设计人员绘制图元的先后顺序而自动保存的，具有一定的随机性。若CAM系统对读取的DXF文件图元数据不进行优化处理而直接产生加工G代码，会造成数控加工系统刀具的空程路径过长和频繁起落。根据加工对象的复杂度即加工轨迹段数量，非切削时间占整个加工任务周期的15%~30%[2]。当加工轨迹段较复杂时将明显降低加工效率并影响刀具使用寿命，因此对DXF文件中的加工图元信息进行空程路径优化显然尤为重要。

目前，国内外学者对数控加工路径优化做了许多研究，但大多集中在孔群加工路径优化[3-6]，平面加工轮廓的路径优化也有部分相关研究，但主要针对封闭式加工轮廓或支持简单图元类型，而对多图元复杂混合轨迹加工路径优化问题的研究相对较少。通常孔群路径优化问题可当作旅行商问题（traveling salesman problem，TSP）进行求解，即孔群被认为是一系列点来处理，由于处理对象单一，其数学模型较为简单。而平面加工轮廓路径优化可转化为广义旅行商问题（generalized traveling salesman problem，GTSP）求解。针对平面封闭式轮廓轨迹路径优化的研究，相关算法有最短近邻算法[7-8]、结合局部搜索的蚁群算法[9]和遗传算法[10]，但此类研究均没有对非封闭及多类图元混合轨迹图形路径优化进行说明。

根据数控加工行业的需求，本文提出基于改进遗传算法的多类图元混合复杂轨迹加工路径优化策略。针对复杂路径优化问题，引入直线、圆弧、椭圆弧和B样条等图元数据对象，基于GTSP问题模型，应用改进的遗传算法求解全局最短路径，并对封闭式轨迹段和非封闭式轨迹段进行起点计算与局部寻优，以实现多类图元混合轨迹加工路径优化。该方法不仅可显著减少刀具空走路径，提高加工效率，而且可方便扩展图元类型，适用于木工、型材、电子等多个行业。

1 加工路径图元数据读取

为满足CAM编程系统的兼容性与扩展性，采用C++面向对象的思想，并基于开源C++库dxflib构建DXF文件读取类库。其中，dxflib库的可靠性高，可实现任何操作系统上的DXF文件的读取，且不产生任何附加成本[11]。DXF文件具有严格规范的存储格式，由标题段、表段、块段、实体段、对象区段和文件结束段6部分组成，其中加工图形几何信息均定义在实体段中，一个实体对应一个图元。DXF文件读取流程如图1所示。

图1 加工路径图元数据读取流程

2 问题描述与数学模型

在数控加工过程中，通常需要对多个轨迹图形进行一次加工完成，以缩短换刀次数和换刀时间，提高机床加工效率。但在多个轨迹图形加工过程中，相邻两个加工图元之间需要跳刀空走，并从加工图形文件读取的加工图元排列无序，且加工轨迹图形数量通常较庞大，若不进行加工空程路径优化，将严重影响加工效率。

针对木工、型材、电子等行业数控雕刻、切割、钻铣加工，其加工轨迹从曲线类型上一般包含点、直线段、圆弧、椭圆弧和B样条等图元。由于加工路径由一系列轨迹图形组成，路径优化即是对加工轨迹图形进行合理排序，使轨迹间跳刀距离总和最短。由于优化过程中只需关注图元间的距离，因此为简化问题模型及便于遗传算法编码，本文提出将加工图元重构：1) 对于由点、圆、椭圆形成的单轨迹图形，只考虑图元的中心点；2) 对于由直线、圆弧、椭圆弧或B样条形成的单图元轨迹图形，只考虑图元的两端点；3) 对于由多个图元构成的非封闭式轨迹图形，将该多个图元组成一个组合体，忽略图形中间节点，取轨迹图形两端点；4) 对于由多个图元构成的封闭式轨迹图形，取其中任意一点作为初始点。

多图元混合加工路径可看作不同类型轨迹段图形（包括单个非封闭图元、单个封闭图元、多图元非封闭式图形和多图元封闭式图形）的集合。对于单个非封闭图元或多图元非封闭式图形，两端点均可作为加工轨迹段起始点；对于单个封闭图元，轨迹段图形上任一点可为加工起始点；对于多图元封闭式图形，任一节点都可以作为加工轨迹段的起始点。加工路径的优化即通过算法对所有加工轨迹段进行排序及加工轨迹起点与方向选择，使得按所排顺序形成的加工回路最短。

因此，多图元混合加工路径优化问题的数学模型为：给定个点集1,2,…,V,…,V，把V内的点数记作n，则个点集的总点数=1+2+…+n+…+n(=1,2,…,)。从每个点集V中取1~2点（如对于非封闭轨迹段取两端点，对于封闭轨迹段任取一点）构成赋权图G(=1,2,…,1,2,…,n)，需要找到一条可遍历个点集的最短Hamilton回路L，则刀具的最短加工路径应满足[10]

(1)

其中()、(L)分别表示路径和L的长度。

由数学描述可见，多图元混合加工路径优化问题是一个带约束且节点可变的第二类GTSP问题。目前针对该类问题的研究相对较少，文献[12]提出了基于最短路径思想的重构距离矩阵算法，将第二类GTSP转化为第一类GTSP，再利用混合遗传算法进行求解，该算法复杂，实现过程较困难。本文针对加工路径中不同轨迹类型进行个性化编码设计，直接将多图元混合加工路径优化问题转化为TSP问题求解，然后通过轨迹段（包括封闭式与非封闭式）起点计算和路径自调整简易算法对优化后的轨迹段序列进行后处理，从而获得多图元混合加工路径最短空程距离。

3 多类图元混合加工路径优化策略

遗传算法是一种通过模拟自然界的进化过程，搜索全局最优解或近似最优解的方法，具有良好的鲁棒性、隐式并行性和全局搜寻能力，对于加工路径的优化具有良好效果，但也存在易于过早收敛和难以跳出局部最优解的不足。文献[13]与贪心算法结合，提高了搜索效率和结果，但增加了程序运行成本。为将多图元混合加工路径优化复杂问题转化为数学模型简单的TSP问题，对不同轨迹段图形进行分类编码设计，并采用线性定标及自适应遗传算子等方式进行初步路径排序，最后通过加工路径后处理算法求解最短加工路径。

3.1 基于改进遗传算法的全局路径优化

3.1.1 染色体编码

实数序列编码相对于二进制编码、参数编码等方式，具有良好的适用性和可操作性，可解决多图元轨迹混合路径编码带来的复杂问题，故本文采用实数序列编码。由于多图元混合加工路径存在直线、圆弧、椭圆弧和B样条单个图元以及非封闭轨迹图形，为适用TSP问题的遗传算法求解，故根据加工轨迹段图形类型进行分类编码，染色体编码见表1，P表示第个编码点对象。

表1 多类图元混合轨迹图形编码表

3.1.2 初始化种群

当染色体编码完成后，需产生一个初始种群当作遗传进化的初始解。对于加工路径优化问题，种群大小一般随着轨迹段数目而改变，取值范围50~200[8]。根据轨迹段数量自适应调整种群大小的函式定义：

其中，表示种群数目；表示加工轨迹段数目；表示不同加工轨迹所对应的取值。

如式(2)所示，种群个数在50~200之间随加工轨迹段数目不同而自动变化。

3.1.3 适应度函数

适应度函数是评判种群中个体优劣程度的指标，根据所求问题的目标函数进行评估。适应度值大的个体被遗传到下一代的概率较大，适应度值小的个体被遗传到下一代的概率较小。由于每段加工轨迹本身长度不变，其长度总和可视为常数C。为保持良好个体的竞争力并且抑制早熟情况的出现，针对适应度函数引入线性定标方式进行调整，由此个体适应度函数为

其中，和为适应度调整系数。

3.1.4 选择、交叉和变异

1) 交叉和变异概率的自适应处理

通常遗传算法中的交叉和变异概率均采用固定数值，无法反映种群的进化过程。为进一步避免出现早熟现象，防止算法在搜索空间中陷入局部最优情况，对交叉和变异概率在平均适应度值处进行自适应缓慢调整处理，提高适应度接近平均适应度个体的交叉和变异概率，保证当代种群中优良个体仍具一定的交叉和变异概率。为了能在算法演化后期尽可能地保留较优个体，应平滑最大适应度值处的自适应调整曲线，改进后的交叉和变异概率自适应处理函数为