基于离散帝王蝶算法的喷涂路径组合优化*

温记明，熊瑞平，李云秋，苏 俊，谭 平

(四川大学机械工程学院，成都 610065)

0 引言

喷涂作为表面处理的重要环节，对产品的表面质量和性能 有着至关重要的影响。早期机器人喷涂作业多采用的是人工示教的方式。但这种方式需要人工参与到实际喷涂场景中，效率低下，且不适用于复杂结构和复杂曲面的喷涂对象。离线编程作为新兴技术，完全脱离实际生产环境，通过控制算法和计算机图像学完成对喷涂工业机器人的运动控制。目前离线编程大多采用的方法是先对喷涂对象表面进行分片[1]，然后在分片区域上进行路径规划，再将规划出的路径进行排列组合，最终生成一条完整的喷涂路径[2]。而如何高效的实现片区路径的排列组合，对实现喷涂机器人离线编程有着重要意义。

目前所提出的主流方法是将片区路径的排列组合问题转换为路径点的旅行商问题(traveling salesman problem，TSP)[3]，将分片路径的连接过程替换成路径点的连接过程，最终形成喷涂路径。然而TSP模型并没有考虑到路径起点、路径方向和路径顺序对最终路径的影响，因此通过TSP模型并不能对路径的排列组合进行完整描述。黄俊、胡锦楠等[4-7]等将分片路径排列组合问题转换成广义旅行商问题(generalized traveling salesman problem，GTSP)，并将混合粒子群算法(PSO)、遗传算法(GA)、离散灰狼算法、蚁群算法运用到求解广义旅行商问题中，实现了分片路径的排列组合。但这些算法在设计过程中只考虑了在片区表面只存在单一可行局部路径的情况，不适用于表面具有多条可行路径的片区，同时这些算法在解决问题时收敛速度较慢且最终生成的喷涂路径无法避免碰撞。

为提高分片排列组合效率同时避免最终喷涂路径发生碰撞，首先将喷涂路径排列组合问题抽象为路径点的开环广义旅行商问题(open-loop generalized traveling salesman problem，OGTSP)，并建立了路径长度模型和路径碰撞模型，然后重新定义了帝王蝶算法的编码方式、初始化方法和种群更新策略，同时引入贪婪算法思想和模拟退火算法思想，提出了一种适用于求解排列组合问题的离散帝王蝶算法(discrete monarch butterfly optimization，DMBO)。最后将离散帝王蝶算法运用到求解路径点OGTSP过程中，获得了满足实际喷涂条件的最优喷涂路径。

1 问题分析与建模

在喷涂机器人喷枪路径组合问题中，关注的对象是如何规划出一条能够遍历喷涂对象所有片区的开环喷涂路径。目前所有方法都是将片区内路径与片区间路径独立考虑。但实际上，不同的片区内路径与片区间路径所组合出的完整路径长度不相同。因此，本文将喷涂顺序、喷涂方向及喷涂路径起点的选择纳入决策变量，将片区内路径与片区间路径规划问题抽象为路径点的开环广义旅行商问题，所有片区内路径采用Z字形轨迹[8]，所有片区间采用圆弧过渡，并引入路径碰撞问题作为约束，规划出最短路径。

1.1 喷涂路径的OGTSP模型

首先，假设喷涂对象可划分出n个片区，其中每个片区具有m条可行局部喷涂路径，每条局部喷涂路径对应一种该片区上喷枪的喷涂轨迹。由于在分片区域上进行路径规划过程中，路径起点和终点一旦确定，所生成的满足喷涂条件的Z字形路径唯一确定，故对于局部喷涂路径其起点和终点便可替代该路径。因此，如图1所示，喷涂路径的排列组合问题可通过对路径进行抽象，将其转变为开环广义旅行商问题，即在多个点集中，寻找到一条遍历所有点集中所有可遍历点的最短路径[9]。

图1 路径排列组合图

故路径点OGTSP模型的数学描述为：

G=(L,V,E,W)

(1)

式中，L={l1,l2,…,ln,…,ln×m}为片区可选局部路径集合；V={v1,v2,v3,…,vn}为点集，其中vi为V的子点集，vi={vi1,vi2,…,vi×2m}为每个片区中m条可选局部喷涂路径的路径起点via和路径终点vib的集合；E={eij(i,j)|i∈V,j∈V,i≠j}为点集V上任意两点所成路径的集合；W={wij(i,j)|i∈V,j∈V,wij≥0}为定义在路径集E上的赋权矩阵。wij反应了第i个点和第j个点之间的路径距离。当i和j为不同片区上两个点时，wij表示两点之间的空间距离；当i和j是L中同一局部路径上的路径点时，wij表示对应路径的长度；当i和j为同一点集vi中非同一局部路径上路径点时，wij=M，M为一个无穷大值。

1.2 路径长度模型

根据所建立的OGTSP模型，在总数n×2m个路径点中，一条完整的喷涂路径是其中2n个路径点所构成的轨迹，这些2n个路径点以成对的方式来自n个片区，每对路径点对应一条片区上的局部喷涂路径。整条路径的长度为这些路径点连接过程时产生的路径长度总和。如式(2)所示：

minF=∑wij*xij

(2)

式中，xij=(0|1)表示对应的弧eij是否处于最终所形成的路径中，其中0表示不在路径中，1表示位于路径中。

1.3 路径碰撞模型

在分片路径的排列组合过程中，最终喷涂路径由路径点相互连接而成，但是在连接过程中，可能如下碰撞情况：路径点连接过程中，两个路径点所构成的轨迹穿越了模型表面或贴附于模型表面，使得喷枪与喷涂对象发生碰撞。

故在求解最短路径过程中，需要对所获取的路径进行不断的碰撞检测。由于本文所采用的是点云数据，故存在点云轮廓数据集PC。对于喷涂路径，碰撞可通过如下条件进行检测：对于喷涂路径L上的任意点pv(xpv,ypv,zpv)，即∀pv∈L，是否都满足点pv到点集PC之间的最短距离dmin≥dsafe。具体可由式(3)和式(4)进行碰撞检测。

(3)

dmin≥dsafe

(4)

检测过程中，对不发生碰撞的喷涂路径进行保留，对发生碰撞的喷涂路径直接排除。

2 离散帝王蝶算法

2.1 传统帝王蝶算法

帝王蝶算法(monarch butterfly optimization，MBO)是由WANG等[10]提出的一种受帝王蝶迁移行为启发的群体智能元启发式优化算法，其具有兼顾搜索广度和避免陷入局部最优的特点，能够有效的解决全局优化的问题。

2.1.1 帝王蝶行为规则

在帝王蝶算法中，将所有的帝王蝶理想化，每只帝王蝶的位置代表一个可行解，帝王蝶的每个位置维度代表一个优化参数，其行为遵循以下规则[11]：

(1)所有帝王蝶分布在Land1和Land2两个岛屿上，两个亚种群的总和为整个帝王蝶种群大小。

(2)处于Land1和Land2上的两个亚种群的行为不同，Land1上帝王蝶群体行为为迁移，Land2上帝王蝶群体行为为环境适应。

(3)整个帝王蝶种群大小保持固定，迭代时子代与父代通过适应度进行选择，以决定是否保留在种群中。

(4)种群中最优的当代帝王蝶不进行任何行为，直接被保留并进入下一代，保证帝王蝶整体质量最优。

2.1.2 帝王蝶算法

在进入算法时，首先产生一定数量的初始帝王蝶种群，每只帝王蝶的位置标记为X={x1,x2,x3,…,xn}[12]，xn为个体的第n个位置参数。任意一只帝王蝶的初始亚种群位置通过式(5)进行判定：

(5)

式中，rand服从U(0,1)；p为概率因子。帝王蝶种群按照概率p将个体分布在Land1和Land2上，形成两个群体，不同群体根据帝王蝶行为规则进行相应行为。

迁移行为：位于Land1上每只帝王蝶的都有概率p进行位置迁移，如式(6)所示。

(6)

环境适应行为：位于Land2上每只帝王蝶都有概率p进行环境适应，如式(7)～式(9)所示。

若rand1≤p，则帝王蝶按照式(7)进行位置更新：

(7)

若rand1>p&rand2≤BAR，则帝王蝶按照式(8)进行位置更新：

(8)

若rand1>p&rand2>BAR，则帝王蝶按照式(9)进行位置更新：

(9)

2.2 帝王蝶编码方式的改进

在喷涂路径排列组合过程中，每个片区上的路径可由该路径的起点和终点进行代替。为此，提出一种具有3层结构的矩阵编码方法。矩阵的第1层为片区顺序层，第2层和第3层为路径节点层。如图2所示，第1层片区顺序层共有7个片区，编号为1～7，分别对应每个片区在喷涂路径的位置顺序；第2层和第3层为片区顺序层上喷涂路径的起点和终点。最终编码如式(10)所示。

图2 矩阵编码图

(10)

2.3 种群初始化方法改进

不同于连续性问题在可行域上盲目寻优，OGTSP所求结果往往是由相邻路径点所组成的路径，同时，在路径节点连接过程中，应该对同属于同一条局部路径上的点进行绝对的优先考虑。在此基础上，考虑到路径方向和路径顺序对路径长度的影响，本文将贪婪算法思想引入种群初始化过程：首先，计算每个路径点到其它所有路径点间所成路径的长度总和，取出所计算的路径长度和最大的路径点，如有多个路径点路径长度和相等，则采用轮盘赌方法进行抽取，并将最终取出的点标记为路径起点；其次，将路径起点所处的片区编号置于片区顺序层中第一个位置上，该节点本身置于路径节点层1的第一个位置，再搜索与当前路径点可以形成路径的其它未被连接的路径点，若存在与其同属于一条可选局部路径li(li∈L)上的路径点，则该点被一定选取，若不存在这样的点，则采用贪婪算法(greedy-algorithm)搜索与当前路径点所成路径长度最小的路径点，将被搜索到的路径点置于该片区的路径节点层2。最后，逐步搜索，直到所有片区被选择，编码结构完整，则编码数据对应一只帝王蝶。种群初始过程如图3所示。

图3 种群初始过程图

2.4 种群更新策略改进

在传统帝王蝶更新过程中，个体进行迁移和环境适应行为时，直接将帝王蝶的同维位置参数进行交换或改变，但这种方式不适用于OGTSP问题。故提出一种名为定向更新的更新策略，如图4所示。

图4 种群更新过程图

首先，由于帝王蝶各维度所对应的片区不同，不能直接进行数据交换，故而在更新时，先获取当前维度在矩阵编码中对应的片区顺序层编号，再定向寻找到要与其进行数据交换的帝王蝶的相同片区顺序层编号数据，再进行路径节点层数据交换。为保证种群大小保持恒定，需要将更新后的帝王蝶与更新前的帝王蝶进行适应度比较，适应度高的帝王蝶被保留，适应度低的帝王蝶进行淘汰，适应度与式(2)计算的路径长度成反相关，比较过程通过式(11)计算：

(11)

其次，位于Land2上的种群个体有一定概率进行LevyFlight，产生随机位移，而这种随机位移在OGTSP中是不被允许的。为保证在迭代过程中能够存在一定的变量来优化整个种群的行为，同时这种优化又不干扰整个帝王蝶种群纯洁性。故引入模拟退火算法思想，修改帝王蝶环境适应行为规则：

若rand1≤p，则帝王蝶按照采用式(7)进行位置更新。

(12)

2.5 离散帝王蝶算法流程

通过所构建的OGTSP模型及约束条件，离散帝王蝶算法的NS图如图5所示。

图5 离散帝王蝶算法NS图

3 实验验证与分析

为了验证离散帝王蝶算法能否有效生成喷涂机器人喷枪路径，同时检验离散帝王蝶算法与粒子群算法[4]、遗传算法[5]、在路径规划问题上的适用性，故设计如下实验：分别用DMBO、GA、PSO三种算法对图6所示工件进行路径规划实验，该工件为桥梁建筑支撑件，具有平面结构和弧形结构，对常见的喷涂工件具有代表性。图6所示工件共有7个面，在每个面上准备3条预先规划出的轨迹，同时采用轨迹的起点和终点对轨迹进行代替并将这些点标注在模型表面如图7所示，标注的路径点中，vi1和vi2，vi3和vi4，vi5和vi6分别对应片区上三条局部喷涂路径的起点和终点。

图6 工件图

图7 路径点图

实验设计如下：设计初始种群大小为40，迭代代数为50次，分别进行20次重复实验并统计收敛时路径长度、迭代代数及碰撞次数，结果如表1所示，最终路径规划结果如图8所示。取某次迭代过程数据如图9所示，图中被填充的图形代表此时路径发生碰撞。由表1、图8和图9可知，在20组数据对比中：根据最终算法收敛路径长度分析，DMBO、GA和PSO三种算法在解决喷涂机器人喷涂路径排列组合问题上都具有一定的适用性，都能够稳定收敛到最短路径上。根据迭代次数分析，DMBO算法的迭代代数稳定且收敛速度较快，而GA和PSO算法的最短路径迭代代数极值较大且平均收敛代数较大，从数据来看，相对于GA和PSO，DMBO的平均迭代次数分别降低了32.3%和21.0%，体现了离散帝王蝶算法相对于GA和PSO算法具有更强的收敛性。在碰撞问题上，DMBO算法无碰撞发生，而GA和PSO算法分别发生了4和9次碰撞，而在实际喷涂过程中，任何碰撞都是不被允许的。故相对于GA和PSO算法，DMBO更适用于解决喷涂机器人喷枪路径排列组合问题。

表1 三种算法路径规划结果比较

图8 实物模型及路径结果图 图9 迭代过程图

4 结束语

本文提出了一种适用于解决组合优化问题的离散帝王蝶算法，并将该算法应用于实际的喷涂路径排列组合问题上，实现了对喷枪路径的高效率、无碰撞规划。主要结论如下：

(1)DMBO是一种有效解决喷枪路径组合优化问题的方法，能够在高效率规划出喷枪路径的同时保证路径的平滑、无碰撞，能够满足生产需求。

(2)以实际工件为研究对象，在喷枪路径组合优化问题上，DMBO相较于GA和PSO，迭代次数分别降低了32.3%和21.0%，在收敛速度和鲁棒性上表现出明显优越性。