分步求解切割路径的优化算法研究

徐晟逸，苏 平，邓晖飞

（广东工业大学机电工程学院，广东广州 510006）

分步求解切割路径的优化算法研究

徐晟逸，苏 平，邓晖飞

（广东工业大学机电工程学院，广东广州 510006）

为实现切割路径优化，提升加工效率，提出了分步求解切割路径的思想。第一步：引用坐标中心点概念，确定所有图案切割点，实现切割路径优化问题向旅行商问题的转化。第二步：设计遗传算子，在MATLAB下实现遗传算法对旅行商问题的仿真求解。与采用最邻近算法确定切割点方法的结果对比，前者最优路径（8 845.2 mm）为后者最优路径（9 652.0 mm）的91.6%，证明了提出算法的可行性。

切割路径优化；旅行商问题；遗传算法；最邻近算法

0 引言

切割是加工行业中一项重要的技术，随着科学技术的发展，企业对切割加工效率的要求越来越高，切割加工的效率和质量将直接影响到生产的效率和质量。针对大理石材的大批量切割生产，提高加工效率就显得尤为重要。为提升效率，本文立足于优化切割路径这一点来实现。在切割过程中，刀具的空走行程完全是无效行程，通过减少这些无效行程达到缩短单个产品的生产时间，更是实现批量生产加工效率的跳跃。在切割路径优化这一问题上，大量学者都做出了研究。C Oysu等作者在解决刀具优化问题时，提出了一种把遗传算法与模拟退火算法混合的方法[1]。这种智能算法相结合的混合算法，虽然取得了不错的效果，但是计算起来复杂度高，效率低，不适应快速生产加工的需求。李妮妮等作者提出了一种基于局部搜索和遗传算法结合的切割路径优化算法[2]。该算法从加工轮廓中提取节点，通过局部搜索法对节点进行局部路径优化，再运用遗传算法求得切割最优路径。孙慧平等作者采用增加节点的方法把切割路径优化问题变换为经典旅行商问题，再用遗传算法实现求解[3]。罗辞勇等作者通过建立加工中空走路径优化的数学模型，将问题转化为旅行商问题后，采用自适应邻域遗传算法来求解[4]。这些研究者在求解切割问题时，均采用简化问题的思想，实现问题的分步求解。在计算效率上都有了提升，但是在把问题转为旅行商问题来求解时，局部搜索法和邻近算法都有自身的局部优化的弊端，并在很大程度上经简化后，丢失了最优解空间。为了解决这些问题，本文提出基于坐标中心点实现切割问题向旅行商问题转化的方法，使得简化后的解空间集中在一个包络面积较小的范围内，极大概率的保留了最优解空间，在此基础上用遗传算法实现最优路径的求解，提高了问题求解的准确度与效率。

1 切割路径数学模型

在切割过程中，要求依次加工所有图案且加工路径最短。切割路径总行程由图案轮廓切割行程和刀头空走行程构成。其中，图案轮廓切割行程相对不变且位置固定，刀头空走行程与每个图案切割起始点的选取以及各个图案的切割顺序相关。

已知经排样优化的样板包含N个图案。Vi表示为第i个图案，其中1≤i≤N。ni代表第i个图案包含顶点的个数。Vi,j表示为第i个图案的第j个顶点，其中j∈ ni。

图1 样板示意图

切割路径总行程由图案轮廓切割行程和刀具空走行程组成，即：

其中，LP：刀具切割空走行程；

LM：轮廓切割行程；

ls：切割原点到第一个图案切割起始点的距离；

le：第N个图案切割起始点到原点的距离；第i个图案与第i+1个图案之间的切割空走行程。

分析模型，LM属于切割总行程中固定不变部分，无优化空间。因此模型可简化为：

2 问题的求解

为避免大量复杂计算，针对上述模型，本文对问题进行分步求解，降低求解难度，增加求解效率。具体思路：（1）确定每个图案的切割起始点，将路径优化问题转化为旅行商问题，引入坐标中心点这一概念，利用图案轮廓顶点与坐标中心点的几何关系，找出每个图案的切割起始点，产生一个相对密集、包络面积较小的点群，将问题转化为TSP来求解；（2）确定图案之间的切割顺序，得出最优切割路径。采用遗传算法，在MATLAB下实现求解，得出最优切割路径。

定义第i个图案的第j个顶点的坐标为Pi,j（xi,j，yi,j）。其中1≤i≤N ，1≤j≤ni。坐标中心点M（x，y）的x、y定义如下：

其中， Pi,j：第i个图案的第j个顶点的坐标；

xi,j：第i个图案的第j个顶点的x坐标；

yi,j：第i个图案的第j个顶点的y坐标。

以坐标中心点M（x，y）为基点，定义第i个图案的第j个顶点到坐标中心点的距离为di,j。

其中，i=1，2，3…N，1≤j≤ni。min(di,j)

表示第i个图案中顶点到坐标中心点的最短距离。把min(di,j)中对应的顶点坐标Pi,j确定为图案的切割起始点。至此，得到N个图案的切割起始点集合{Pi,j}，完成了向旅行商问题的转化。

以距离坐标中心点距离最近为原则，产生相对集密的、包络面积较小的点群，区别于最邻近算法的局部优良性，该点群在更大可能保留最优切割路径解空间的前提下，实现在较小包络面积中寻找最优切割路径的可能。

结合生产实际，将已确定N个图案的切割起始点和切割原点看成旅行商问题[5]中N+1个城市的坐标，求解旅行商问题，得到最优切割路径。旅行商问题是一个经典的组合优化问题。由于该问题的可行解数与城市个数是成指数型增长的，故旅行商问题是一个NP难问题，宜采用近似求解。目前，这一问题已研究的比较成熟，大量学者采用智能优化算法来解决。包括模拟退火算法，人工神经网络，蚁群算法，遗传算法，禁忌搜索，粒子群优化算法等。本文采用遗传算法来求解。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法，对于组合优化中的NP完全问题非常有效的。以适者生存为原则，在群体搜索技术下逐代进化，最终得到最优解或次优解。具体步骤如下：（1）确定解空间的编码方式；（2）初始种群的产生及适应度函数的选择；（3）选择、交叉、变异算子的设计。

2.1 编码

遗传算法不能直接处理问题空间的解。为了将问题空间的解转化为由基因按一定结构组成的染色体或个体，本文采用十进制编码[6]。产生随机数列S1S2…SN作为一个个体，其中0＜Si＜1，i= 2，3，…，N-1，S1=0，SN=1。每个随机序列对应种群中一个个体，例如8个图案的切割顺序问题的染色体表示为：[0.15 0.67 0.38 0.64 0.43 0.59 0.89 0.73]，其中编码i位置代表图案i，i位置上的随机数表示图案i在切割路径中的排序，将随机数升序排列得到切割顺序为：

1-3-5 -6-4-2-8-7

2.2 初始种群及适应度函数

为节省进化代数，从一开始就能够获得一个较好的初始群体，本文采用改良圈[7]算法确定初始种群。对于初始圈C：

其 中 2≤u＜v≤N+1，2≤Lu＜Lv≤N+1。逆反u与v之间的顺序，得到新群体：

适应度函数用于评价个体的优劣程度。适度越高，个体越好。每个个体代表一条切割空走路径，为保留较优个体，本文采用切割路径空走行程大小的倒数作为适应度函数，即：

其中，D：切割路径空走行程；

d0d1：切割原点与第一个图案间的空走行程；

dNd0：第N个图案与切割原点间的空走行程；

didi+1：相邻两图案的空走行程。

2.3 选择、交叉、变异算子设计

选择是模拟自然界生命繁殖和优胜劣汰的主要载体，即是一个从当前群体中选择适应值高的个体以生成交配池的过程。依据适应度函数值的大小对个体进行选择，适应度值大的个体被选中的概率高，适应度值小的个体可能被淘汰。本文采用李晨等作者提出的基于排序的多轮轮盘赌选择算子与最佳算子保存法相结合的法[8]。提高算子选优能力同时也减少了随机性所产生的误差，并达到了既能够选出最好个体又能够保证种群多样性的效果。

交叉是把两个父代个体的部分基因加以替换重组而生成新个体的操作，从而使更优个体的出现成为可能。为保持算法的全局优化能力，本文采用单点交叉法[9]来实现两个配对个体部分基因的交换。随机选取配对个体W1、W2的基因i位置处为交叉点，则W1的前i个基因加上W2的后N+2-i个基因构成新的个体Z1，W2的前i个基因加上W1的后N+2-i个基因构成新的个体Z2(1 ＜i＜102)。

变异是通过随机改变个体中的某些基因，产生出新的个体。它可以防止求解过程中过早收敛产生局部最优解而非总体最优解，决定遗传算法的局部搜索能力。在本文，对于选定的个体，采取 产 生 两 个 随 机 整 数 α、β ，1≤α＜β≤N+1，交换α、β基因位上对应基因的策略实现变异。

3 实例应用

图2 待切割样板图

对样板图中的图案依次进行编号，列出每个图案中的各个节点坐标：

由坐标中心点 M（x，y）的计算公式得到中心坐标点：M（750.000，750.000）。

由min(di,j)确定切割点集合：

在MATLAB中实现遗传算法的程序设计[10]。取种群大小M=50，交叉概率Pc=0.95，变异概率Pm=0.05，进化代数1 000。仿真求解结果如图3，得到优化路径的大小为8 845.2 mm。对应的最短切割路径中，原点的编号为0，具体如下：

0-16-36 -17-18-19-20-38-37-45

46-47-48 -43-44-35-15-14-34-33

13-32-12 -31-11-10-30-42-41-29

28-9-27 -8-26-25-40-39-24-7-6

23-5-22 -4-21-3-2-1-0

同样的包含48个图案的待切割样板，采用邻近算法实现切割路径优化问题对TSP问题的转化，得到切割点集合：

图3 基于中心坐标点的最优切割路径图

取相同的种群大小、交叉概率、变异概率以及进化代数，在MATLAB下实现遗传算法仿真求解，结果如图4。得到最短路径大小为：9 652.0 mm。对应的最优切割路径为：

0-16-15 -14-34-35-43-33-13-12

32-31-11 -30-29-28-10-27-9-8

26-40-25 -24-6-5-4-21-22-23

24-39-41 -42-48-47-45-46-38-20

3-2-19 -18-37-44-36-17-1-0

经仿真对比可知，采用本文提出的中心点坐标对切割问题实现转化的方法比由最邻近算法实现切割问题转化的方法效果更佳，得到的最优切割路径空走行程大小为后者的91.6%。进一步缩短了切割路径的空走行程，达到了切割效率的提升。

图4 基于最邻近算法的最优切割路径图

4 结束语

针对切割路径优化这一问题，本文遵循将复杂问题简单化的思想，通过引入坐标中心点这一概念，实现切割路径优化问题向TSP问题的转化。最终通过实例对比分析，验证算法的可行性。

［1］ Oysu C，Bingul Z.Application of heuristic and hy⁃brid-GASA algorithms to tool-path optimization problem for minimizing airtime during machining［J］.Engineer⁃ing Applications of Artificial Intelligence，2009，22（3）：389-396.

［2］李妮妮，陈章位，陈世泽.基于局部搜索和遗传算法的激光切割路径优化［J］.计算机工程与应用，2010（2）：234-236.

［3］孙慧平，李健，郭伟刚.遗传算法在束流切割路径优化中的应用［J］.农业机械学报，2008，39（39）：158-160.

［4］罗辞勇，卢斌，韩力.求解空走优化路径的自适应邻域遗传算法［J］.重庆大学学报，2009，32（12）：1477-1481.

［5］刘荷花，崔超，陈晶.一种改进的遗传算法求解旅行商问题［J］.北京理工大学学报，2013，33（004）：390-393.

［6］张晓缋，方浩，戴冠中.遗传算法的编码机制研究［J］.信息与控制，1997，26（2）：134-139.

［7］曹旭.旅游线路优化设计研究［D］.西安：西北工业大学，2012.

［8］李晨，宁红云.改进的遗传算法选择算子［J］.天津理工大学学报，2009，24（6）：1-4.

［9］运筹学，树栋，遗传学.遗传算法原理及应用［M］.北京：国防工业出版社，1999.

［10］储理才.基于MATLAB的遗传算法程序设计及TSP问题求解［J］.集美大学学报：自然科学版，2001，6（1）：14-19.

Research on Optimization Algorithm for Solving the Cutting Path Step by Step

XU Sheng-yi，SU Ping，DENG Hui-fei
（School of Mechatronic Engineering，Guangdong University of Technology，Guangzhou510006，China）

To achieve the cutting path optimization and improve processing efficiency，this paper proposes a thought of solve the cutting path step by step.The first step is to cite the conception of center point of coordinates,determine all pattern’s cutting point to achieve the transformation of the cutting path optimization problem to the TSP.The second step is to design the genetic operators and realize the simulation of solving the TSP by GA in the MATLAB.Compared the method using the nearest neighbor algorithm to determine all the cutting points,the best path(8845.2mm)of use the center point of coordinates is 91.6%of the latter’s best path(9655.8mm).Demonstrated the feasibility of the proposed algorithm.

cutting path optimization；TSP；GA；nearest neighbor algorithm

TP312

A

1009－9492(2014)09－0081－04

10.3969/j.issn.1009-9492.2014.09.022

徐晟逸，男，1987年生，湖南株洲人，硕士研究生，研究领域：生产加工优化，组合优化问题。

(编辑：向 飞)

2014－03－15