一种基于随机信息素优化精英蚁群算法的加工路径规划方法

摘要

本发明适用于加工技术领域，尤其涉及一种基于随机信息素优化精英蚁群算法的加工路径规划方法，包括如下步骤：S1.输入数据、参数设置和计算各点间的距离；S2.利用优化算法设置蚁群首坐标；S3.更新待访问列表和禁忌表，计算转移概率并确定每只蚂蚁的路径；S4.更新信息素；S5.判断是否完成迭代次数，若是，则输出最优路径，并生成加工文件；若否，则返回步骤S2。本发明通过对蚁群首坐标和信息素等算法优化，避免进入局部最优，能高效迭代出最优加工路径，大大提高生产效率。

权利要求

1.一种基于随机信息素优化精英蚁群算法的加工路径规划方法，其特征在于：包括如下步骤：S1.输入加工路径上多点位的坐标数据、参数设置和计算各点间的距离；

S2.首次迭代蚁群的初始化坐标使用随机方式设置，后续迭代蚁群的首坐标为上一轮的出发坐标的标签加1，所述首坐标计算公式为：其中，startk(*)记录蚂蚁起始坐标编号，k为迭代轮次，i为蚂蚁编号，n为坐标总数；

S3.更新待访问列表和禁忌表，计算转移概率并确定每只蚂蚁的路径；

S4.更新信息素；先计算信息素增量(Δτ)，然后叠加到前一次迭代的信息素上，完成当前信息素更新；

S5.判断是否完成迭代次数，若是，则输出最优路径，并生成加工文件；若否，则返回步骤S2；

所述步骤S4中信息素增量(Δτ)的计算公式为：

其中，Ck表示第k只蚂蚁的路径长度；rand是随机数，rand∈[0,1]；

更新信息素的计算公式为：

b

其中，ρ表示信息素挥发因子，ρ∈(0,1)；Cbest表示当前最短路径长度，e为系数，T为到k当前迭代为止的最优路径；m表示蚂蚁数量；R表示每只蚂蚁在此轮迭代(k)路径；τ(i,j)表示路段(i,j)上的信息素量。

2.根据权利要求1所述的基于随机信息素优化精英蚁群算法的加工路径规划方法，其特征在于：所述步骤S1中输入的多点位的坐标数据包括起点坐标C0、终点坐标CE、所需加工的各点坐标C(n)，n为坐标总数，坐标为二维坐标，包含横坐标X和纵坐标Y；参数设置包括蚂蚁数量m、信息素重要程度因子α、启发函数重要程度因子β、信息素挥发因子ρ、最大迭代次数iter_max、初始信息素浓度；计算各点间的距离是对上述C0、CE、C(n)坐标点中任意两点进行距离计算，并存在数据表D中，以便后续调用。

3.根据权利要求2所述的基于随机信息素优化精英蚁群算法的加工路径规划方法，其特征在于：所述步骤S3更新待访问列表和禁忌表，是将各蚂蚁已访问过的坐标编号记录在禁忌表tabu中，防止在该轮检索中再次访问；将各蚂蚁未访问的坐标编号记录在待访问列表allow中；每访问过一个节点，就将该点编号加入tabu表，并在allow表中删除。

4.根据权利要求3所述的基于随机信息素优化精英蚁群算法的加工路径规划方法，其特征在于：所述步骤S3中转移概率的计算公式为：其中，τ(i,j)表示路段(i,j)上的信息素量，τ的初始值是全为1的数组；η(i,j)表示蚂蚁从节点i到节点j的启发信息值；allowedk表示蚂蚁下一步允许选择的节点集合；α表示信息素重要程度因子、β表示启发函数重要程度因子；

所述启发信息值的计算公式为：

其中D(i,j)为所述S1中数据表D中i点到j点的距离。

5.根据权利要求1所述的基于随机信息素优化精英蚁群算法的加工路径规划方法，其特征在于：所述步骤S3中确定每只蚂蚁的路径，是指利用所述转移概率，通过轮盘赌策略选择下一个节点，重复执行步骤S3，完成各蚂蚁单次检索路径；同时计算各蚂蚁经过的路径距k离(Ck)，最短路径长度(Cbest)，每只蚂蚁在此轮迭代(k)路径R和记录最短路径编号(Rbest)。

说明书

一种基于随机信息素优化精英蚁群算法的加工路径规划方法

技术领域

[0001] 本发明属于加工技术领域，尤其涉及一种基于随机信息素优化精英蚁群算法的加工路径规划方法。

背景技术

[0002] 数控机床加工复杂对象时，设计出合理、较短的加工路径，可以减少机械臂空行程，对提升加工效率具有重要意义。例如，近年来发展迅速的板式家具行业，消费者有定制化、快速化的需求。但是，目前多数的打孔、钻攻等加工路径规划由人工规划，不能很好地适应更多、更快的加工需求。

[0003] 随着人工智能的发展，智能算法被广泛应用在各行业。蚁群算法一种用来寻找优化路径的概率型算法，最早用来求解旅行商问题，它具有分布式特性，鲁棒性强并且容易与其它算法结合等优点。因此，蚁群算法较适合在数控加工中的打孔、钻攻路径规划中使用；精英蚁群算法在基础的蚁群算法上针对收敛速度等进行过改进，但是，传统精英蚁群算法仍存在着收敛速度慢，容易陷入局部最优等问题。

发明内容

[0004] 本发明的目的在于克服上述存在的问题，提供一种基于随机信息素优化精英蚁群算法的加工路径规划方法，通过输入目标点坐标，自动实现最优路径的规划，应用最优路径进行加工，能提高加工效率。

[0005] 为实现上述发明目的，通过以下技术方案实现：一种基于随机信息素优化精英蚁群算法的加工路径规划方法，其特征在于：包括如下步骤：

[0006] S1.输入加工路径上多点位的坐标数据、参数设置和计算各点间的距离；

[0007] S2.首次迭代蚁群的初始化坐标使用随机方式设置。后续迭代蚁群的首坐标为上一轮的出发坐标的标签加1，即每只蚂蚁的起始坐标为上一轮起始坐标的下一个坐标位置。所述首坐标计算公式为：

[0008]

[0009] 其中，startk(*)记录蚂蚁起始坐标编号，k为迭代轮次，i为蚂蚁编号，n为坐标总数。

[0010] S3.更新待访问列表和禁忌表，计算转移概率并确定每只蚂蚁的路径；

[0011] S4.更新信息素；先计算信息素增量(Δτ)，然后叠加到前一次迭代的信息素上，完成当前信息素更新；

[0012] S5.判断是否完成迭代次数，若是，则输出最优路径，并生成加工文件；若否，则返回步骤S2。

[0013] 进一步地，所述步骤S1中输入的多点位的坐标数据包括起点坐标C0、终点坐标CE、所需加工的各点坐标C(n)，n为坐标点个数，坐标为二维坐标，包含横坐标X和纵坐标Y；参数设置包括蚂蚁数量m、信息素重要程度因子α、启发函数重要程度因子β、信息素挥发因子ρ、最大迭代次数iter_max、初始信息素浓度；计算各点间的距离是对上述C0、CE、C(n)坐标点中任意两点进行距离计算，并存在数据表D中，以便后续调用。

[0014] 进一步地，所述步骤S3更新待访问列表和禁忌表，是将各蚂蚁已访问过的坐标编号记录在禁忌表tabu中，防止在该轮检索中再次访问；将各蚂蚁未访问的坐标编号记录在待访问列表allow中；每访问过一个节点，就将该点编号加入tabu表，并在allow表中删除。

[0015] 进一步地，所述步骤S3中转移概率的计算公式为：

[0016]

[0017] 其中，τ(i,j)表示路段(i,j)上的信息素量，τ的初始值是全为1的数组；η(i,j)表示蚂蚁从节点i到节点j的启发信息值；allowedk表示蚂蚁下一步允许选择的节点集合；

[0018] 所述启发信息值的计算公式为：

[0019]

[0020] 其中D(i,j)为所述S1中数据表D中i点到j点的距离。

[0021] 进一步地，所述步骤S3中确定每只蚂蚁的路径，是指利用所述转移概率，通过轮盘赌策略选择选择下一个节点，重复执行步骤S3，完成各蚂蚁单次检索路径；同时计算各蚂蚁k经过的路径距离(Ck)，最短路径长度(Cbest)，每只蚂蚁在此轮迭代(k)路径R 和记录最短路径编号(Rbest)。

[0022] 进一步地，所述步骤S4中信息素增量(Δτ)的计算公式为：

[0023]

[0024] 其中，Ck表示第k只蚂蚁的路径长度；rand是随机数，rand∈[0,1]；

[0025] 更新信息素的计算公式为：

[0026]

[0027]

[0028] 其中，ρ表示信息素挥发系数，ρ∈(0,1)；Cbest表示当前最优的路径长度，e为系数，bT为到当前迭代为止的最优路径。

[0029] 本发明与现有技术相比具有以下有益效果：通过本发明的方法，在加工规划应用中，通过输入目标点坐标，便能自动实现最优路径的规划，应用最优路径进行加工，能提高加工效率。具体是，本发明通过对精英蚁群算法进行改进，除了第一轮迭代随机选择每只蚂蚁的初始出发坐标，对于后续迭代对蚁群出发的第一个坐标进行约束，让每只蚂蚁循环以每一个坐标作为出发点，使每个坐标点都均匀地获得初始遍历起点的机会，降低了随机性，具有更全面的搜索范围，避免存在最优路径被忽略的可能性。

[0030] 另外，在信息素更新处加入随机量，能避免蚁群陷入局部最优解，提高了搜索的有效性，并且能够更快的寻找到最优路径。

[0031] 采用本发明的方法，可以快速获得最优加工路径，适用于打孔、钻攻等多点位加工路径的规划，进而提高加工效率。

附图说明

[0032] 图1为本发明方法的流程示意图。

[0033] 图2为本发明中确定每只蚂蚁路径的流程图。

[0034] 图3为本发明中加工路径示意图。

[0035] 图4为本发明中搜索路径收敛示意图。

[0036] 图5为本发明中算法与精英蚁群算法对比图‑所有实验所得最短路径对比图。

[0037] 图6为本发明中算法与精英蚁群算法对比图‑所有实验搜索到最短路径的迭代步数。

具体实施方式

[0038] 下面对本发明的具体实施方式进行描述，为了使本领域的技术人员很好地理解本发明的技术方案，下面结合实施例和附图对本发明作进一步描述，但本发明的实施方式不仅限于此。

[0039] 本发明提供了一种基于随机信息素优化精英蚁群算法的加工路径规划方法，提出了一种改进的蚁群搜索算法。与精英蚁群算法相比，本算法对蚁群出发的第一个坐标进行约束，使每个坐标点都均匀地获得遍历的机会，降低了随机性，具有更广的搜索范围。同时，在信息素更新处加入随机量，能避免蚁群陷入局部最优解，提高了搜索的有效性。

[0040] 如图1所示，本发明提供一种基于随机信息素优化精英蚁群算法的加工路径规划方法，包括如下步骤。

[0041] S1、输入数据、参数设置和计算各点间的距离。所述输入的数据包括起点坐标C0、终点坐标CE、所需加工的各点坐标C(n)，坐标为二维坐标，包含横坐标X和纵坐标Y，n为坐标点个数。

[0042] 所述步骤S1中参数设置包括蚂蚁数量m、信息素重要程度因子alpha、启发函数重要程度因子beta、信息素挥发因子rho、最大迭代次数iter_max、初始信息素浓度等。设置实例如表1所示：

[0043] 表1

[0044]m α β ρ iter_max
10*n 0.9 3 0.3 300

[0045] 所述步骤S1计算各点间的距离是对上述C0、CE、C(n)坐标点中任意两点进行距离计算，并存在数据表D中，以便后续调用。

[0046] S2、首次迭代蚁群的蚁群出发的初始化坐标设置如下：对上述数量为m的蚂蚁，分别随机分配C(n)中的任意一点为初始出发点，并创建对应的出发表start(i)。

[0047] 第二轮及后续迭代蚁群的首坐标为：将上一轮的每只蚂蚁出发地址标签加1作为本次出发的首坐标；即每只蚂蚁的起始坐标为上一轮起始坐标的下一个坐标位置。所述首坐标计算公式为：

[0048]

[0049] 其中，k为迭代轮次，i为蚂蚁编号。例如一共有4只蚂蚁，4个目标点，第一轮随机出发坐标编号为[1,1,2,3]，则第二轮为[2,2,3,4]，第三轮为[3,3,4,1]，第四轮为[4,4,1,2]。照此规律循环，得到的坐标编号作为每轮迭代的首个坐标。

[0050] S3、每只蚂蚁的路径选择的流程如图2所示。

[0051] 首先，更新待访问列表和禁忌表，是将各蚂蚁已访问过的坐标编号记录在禁忌表tabu中，防止在该轮检索中再次访问；将各蚂蚁未访问的坐标编号记录在待访问列表allow中。每访问过一个节点，就将该点编号加入tabu表，并在allow表中删除。

[0052] 例如有5个坐标点，均未访问，则该蚂蚁开始的allow列表为[1,2,3,4,5],tabu列表为空。蚂蚁到达第3号坐标点后，allow列表变为[1,2,4,5]，tabu列表变为[3]。

[0053] 然后，计算各点的转移概率，转移概率的计算公式为：

[0054]

[0055] 其中，τ(i,j)表示路段(i,j)上的信息素量，τ的初始值是全为1的数组；η(i,j)表示蚂蚁从节点i到节点j的启发信息值；allowedk表示蚂蚁下一步允许选择的节点集合。

[0056] 所述启发信息值计算公式为：

[0057]

[0058] 其中D(i,j)为所述S1中数据表D中i点到j点的距离。

[0059] 所述S3确定每只蚂蚁的路径，是指利用上述转移概率P，通过轮盘赌策略选择选择下一个节点，每个节点均按照上述方法完成。重复执行上述S3步骤，完成所有蚂蚁单次检索路径，同时计算各蚂蚁的路径距离和记录最短路径编号。

[0060] S4、更新信息素；先计算信息素增量(Δτ)，然后叠加到前一次迭代的信息素上，完成当前信息素更新；

[0061] 所述信息素增量计算公式为：

[0062]

[0063] 所述更新信息素计算公式为：

[0064]

[0065]

[0066] 其中，Ck表示第k只蚂蚁的路径长度；rand是随机数，rand∈[0,1]；ρ表示信息素挥k发系数，ρ∈(0,1)；Cbest表示当前最优的路径长度，e为系数，R为每只蚂蚁在当前迭代(k)的b
路径，T为到当前迭代为止的最优路径。

[0067] S5、判断是否完成迭代次数，若是，则输出最优路径，并生成加工文件。若否，则返回步骤S2；并清空路径记录表。

[0068] 下面以22个节点做路径优化进行说明，如表2所示：

[0069] 表2

[0070] 序号 X坐标 Y坐标 序号 X坐标 Y坐标1 43 432 12 6 459
2 43 612 13 6 568
3 282 432 14 6 588
4 282 612 15 916 456
5 577 432 16 916 474
6 577 612 17 916 584
7 871 432 18 916 603
8 871 612 19 1119 441
9 1109 432 20 1119 459
10 1109 612 21 1119 568
11 6 441 22 1119 588

[0071] 输出的路径图形如图3所示，搜索路径收敛示意图如图4所示，本实例最短距离:在第71次迭代，距离为:2598.0634，路径为：1→3→5→7→15→16→9→19→20→21→22→10→17→18→8→6→4→2→14→13→12→11→1。经验证，此距离为当前坐标群的最短路径距离。

[0072] 为比较本发明改进的精英蚁群算法与传统的精英蚁群算法，对此数据坐标分别运行500次寻找最优路径，每次寻优迭代300次。两组算法使用同样的参数设置，实验记录两种算法找到最优路径的迭代步数和所计算出的最优路径长度。

[0073] 本发明与精英蚁群的对比如图5、6所示，图5为最短路径对比图，图6为迭代步数对比图。通过500次实验进行统计，可得本发明得到的最优路径大于真实最优路径2598.0634次数为零，即全部实验均找到真实最优路径；传统精英蚁群算法找到的最优路径大于真实最优路径的次数158，即有158次未找到真实最优路径。本发明平均找到最优路径的迭代步数为71，传统精英蚁群平均找到最优路径的迭代步数为151。实验结果显示本发明的最短路径搜索性能显著优于传统精英蚁群算法。

[0074] 上述为本发明较佳的实施方式，但本发明的实施方式并不受上述内容的限制，其他的任何未背离本发明的精神实质与原理下所做的改变、修饰、替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。