飞机壁板自动钻铆路径规划及仿真研究

宣东军 曲家辰

（1.大连紫曦科技工程有限公司 辽宁省大连市 116033 2.大连交通大学机车车辆工程学院 辽宁省大连市 116028）

近年来，航空制造业发展迅速，作为钻铆技术的应用对象，飞机壁板加工的孔位数量越来越多并且分布较散乱，为了缩短加工时间，需要对钻铆的顺序进行规划。马跃晏等[1]针对机器人制孔路径规划问题，提出动态改变信息挥发因子的方式，改善蚁群算法的无目的性缺陷。萧蕴诗等[2]提出了一种小窗口蚁群算法，使得迭代的初始值较为优秀，有效缩短了计算时间。颜雪松等[3]针对粒子群优化算法容易陷入局部最优的缺点，通过加入精英选择来提高收敛速度的方式以获得更精准的路径。本文针对蚁群算法在搜索时容易陷入局部最优和蚂蚁搜索容易偏离路径终点的情况，提出2-opt 策略以跳出局部最优，加入方向因子为蚂蚁搜索提供方向，提高算法的性能。

1 研究基础

典型的路径规划是在有妨碍机器人正常工作时，机器人需要寻找到一条从初始位置到终点位置的最优路径，评价路径最优的标准就是路径是否最短。针对不合理问题，提出数学模型。

在众多满足条件的路径中选择一条最优路径，从本质上讲就是带约束的组合优化问题，即旅行商问题（Traveling Salesman Problem,TSP)，也是机器人研究中的一个重点方向，本文当中的末端执行器就是商人，制孔点位就是城市坐标，模型保证所有制孔点位均被访问，并且只被访问一次。

首先给定一个赋权图G(V,E,r)，其中V={1,2,…,n}为起始点位的集合，E 为路径的集合，权值定义为路径的长度。

假设：

经典TSP 的数学模型为：

约束条件：

根据公式（2）和公式（4）规定所有点位只会被经过一次，（3）为TSP 的目标函数。约束条件当中的S 为V 的子集V={V1,V2,…,VS}且s＜v。公式（4）第一个约束则保证了没有任何子回路解的产生。第二个约束是对每个孔位而言，仅有一条路径进和一条路径出，保证每个孔位只连接两条路径。于是，满足上述约束的解构成了一条哈密顿回路。

2 改进蚁群算法的实现

2.1 基本原理

以TSP 问题为例[4]，城市的数量为n，蚂蚁的数量为m，dij表示城市i 和城市j 之间的距离，τij(t)表示t 时刻两个城市之间的信息浓度，选择从城市i 到城市j 这条路径的概率为：

其中，allowed 表示蚂蚁下一步允许选择的城市，经过n 个时刻，蚂蚁完成一次循环，每只蚂蚁所走过的路径就是一个解。此时，要根据下面公式对各路径上的信息量作更新：

由上述可知，蚁群算法优化过程的本质在于：

（1）选择机制。路径上信息素浓度越大，后续蚂蚁选择该路径的几率也越大。

（2）更新机制。经过蚂蚁的数量越多，信息素浓度越高，以此同时，信息素浓度也会跟着时间的推移而降低。

（3）协调机制。蚂蚁之间是通过通信进行协调工作，因此蚁群算法得到解的质量很高。

2.2 改进蚁群算法

由于蚁群优化算法作为一种新的启发式搜索算法，自适应性、鲁棒性好，但是在蚁群搜索过程中，当问题规模较大时，需要花费大量的时间，另外易陷入局部解。算法的正反馈机制保证了算法的搜索过程朝着问题最优解的方向进行，然而，由于蚁群算法的正反馈特性，很容易将蚁群搜索集中在某些路径上，导致无法进一步探索其他路径。此时，算法的搜索容易停滞，陷入局部最优解，问题的规模越大，这种现象就越明显。同时初始参数的设置对算法有很大的影响，初始参数的设置虽然不影响收敛性，但对最终的优化结果影响很大。如果在蚁群搜索过程中，能在初始操作阶段得到合理的参数和较好的初始解，就能引导蚁群朝着正确的方向搜索，其速度将大大提高。鉴于以上问题对蚁群算法进行了改进。

2.3 局部优化

蚁群算法的信息素更新方式具有正反馈性。正反馈能够提高算法的收敛速度，但也易陷入局部最优，无论后续增加多少的迭代次数，仍然无法跳出。为此，在蚁群算法中加入k-optimization(k-opt)策略，能够改善这一情况，增强蚁群算法跳出局部最优的能力。其中2-opt 在面对城市的数量较少的情况下，既可以跳出局部最优，又可以花费较少的时间，提高算法效率，因此而得到推崇。2-opt方法的基本原理就是在一条完整的汉密尔顿回路(Hamilton Tour)上通过改变连接两个城市之间的路径，算法会在一定范围之内进行搜索。假设全局最优路径为1-2-3-4-5-6-7-8-9-1，子路径2-3-4-5 变为2-4-3-5 如图1所示，交换之后的路径长度大于交换之前，则保持路径，继续搜索，直至搜索到比交换之前路径短的情况或者交换之前的路径为最短路径停止，继续下一阶段的搜索。

图1：2-opt 路径交换示意图

这种局部优化虽然能够提高解的质量，但是同时消耗过多时间。鉴于其中只有少部分路径能够成为当前的最优路径。为了提高效率，我们可以将这些路径从短到长进行排列，选择路径长度位于前25%的路径进行优化。

2.4 方向因子的引入

根据图2 显示，从城市1 到达城市7 到路径有很多，在搜索初期，每条路径的信息素浓度基本相同，此时位于城市1 的蚂蚁选择城2和城市3 都存在可能性，如果选择了城市2 作为下一站就会偏离原本的最优路径，从而失去找到最优解，降低了收敛于最优解概率。

图2：无向图

此时将城市1 投影到城市2 到城市3 的路径上会发现，城市1向城市2 运动增加不必要的路径，引进方向因子就是将这种与路径终点相反的选择去除，提高搜索优质解的几率。

A 点为起点，B 点为终点，C 点为搜索域中的一点，设他们的坐标分别为(XA,YA)，(XB,YB)，(XC,YC)，则向量AB 的坐标为(XB- XA,YB-YA)，则向量AC 的坐标为(XC- XA，YC- YA)，最短路径与搜索路径的夹角为θ，如图3所示。

图3：最短路径与搜索路径的夹角

向量之间的夹角变大的时候，夹角的余弦值将会变小，方向因子也会变小，对于方向偏移的路径指导性将会变弱。

根据方向因子的特点，加入激励函数 Sigmoid 函数：，将两者结合起来，得到方向因子的数学模型。

根据公式显示，当起始点到终止点的直线距离和当前路径的夹角越大，选择这条路径的几率会越小。经过改进处理后的蚂蚁选择概率如下：

对于γ 的值，表明了方向因子对选择概率的影响。通过方向因子的加入，蚂蚁选择相反方向的几率大大降低，去除一些劣质解的出现。

3 算法的仿真及分析

该仿真的主要目的是验证本文提出的改进蚁群算优于基本蚁群算法和遗传算法。

改进蚁群算法的参数alpha=2，beta=3，ρ=0.7，m=2，其仿真结果如图4所示。

图4：各算法路径长度

在其他参数不变的情况下，重复实验30 次，根据经典蚁群算法和改进之后的蚁群算法仿真结果的对比，如表1所示，改进蚁群算法在计算效率方面明显优于经典蚁群算法，而且能够搜索出更加优秀的路径。从收敛曲线中可以得到，改进蚁群算法的收敛性明显优路径长于基本蚁群算法。

表1：各算法最优路径长度和迭代次数

4 结语

本文针对飞机壁板钻铆过程中刀具空行的路径进行了规划。首先对走刀的路径规划问题进行了数学描述，对于蚁群算法搜索容易偏离路径终点和容易陷入局部最优解的缺陷，提出一种改进蚁群算法(IACO)。通过加入2-opt 策略，改变了两个“城市”间的路径，提高解的质量，同时将激励函数Sigmoid 与方向因子相结合，为蚂蚁搜索提供方向保证，减少较差解的产生。通过比较改进前后算法的迭代次数、路径长度，证实改进算法确实对路径的规划起到优化作用。