一种蚁群算法的优化方法

1.本发明涉及agv路径规划技术领域，具体涉及一种蚁群算法的优化方法。


背景技术：

2.自动导引车(automatedguidedvehicle，agv)是一种无人驾驶的运输车辆。因其具有动化程度高、系统运行稳定可靠、运行灵活等特点被广泛应用于仓储物流领域，相比于传统仓储物流运输大大节省了人力成本、提高工作效率。因此，如何高效规划agv路径已成为一个重要的研究课题；路径规划是指移动机器人从起点开始规划出一条到终点的最佳移动路径，且有能力避开环境中存在的障碍物，不与其发生碰撞，防止危险的发生；对于agv路径规划问题，国内外学者做了大量的研究工作，形成了较多成熟的规划方法，其中智能路径规划方法包括有遗传算法、模拟退火算法、粒子群算法和蚁群算法等。蚁群算法(antcolonyoptimization，aco)是一种正反馈群智能优化算法，具有并行性、强鲁棒性、适应性、易与其他算法相结合等特点；蚁群算法最初应用于解决tsp问题，后被应用于其它组合优化问题，如指派问题、车辆路由问题等，但在求解路径时存在搜索效率低、参数较多、易出现算法停滞和陷入局部最优解等缺点，因此许多学者在原蚁群算法基础上进行优化改进：
3.任红格、胡鸿长和史涛提出了基于改进蚁群算法的移动机器人全局路径规划，基于时间空间的信息素更新策略是将路径信息与迭代次数同时应用在信息挥发系数ρ上，动态调整ρ，使信息素满足蚁群在不同时刻，不同区域的取值需求，可以有效避免劣质解的干扰；
4.张天瑞、吴宝库和周福强提出了面向机器人全局路径规划的改进蚁群算法，提出信息素挥发因子自适应更新策略，扩大算法搜索范围，提高收敛速度，但同样也使得运行时间延长；
5.虽然众多学者已经在原蚁群算法基础上进行优化改进，但是现有的蚁群算法在移动机器人路径规划中存在的收敛速度慢、转角次数过多以及易陷入局部最优的问题。


技术实现要素：

6.本发明目的是针对背景技术中存在的问题，提出一种蚁群算法的优化方法。
7.本发明的技术方案：一种蚁群算法的优化方法，包括以下具体步骤：
8.s1、建立栅格地图，参数初始化，并选择m只蚂蚁；
9.s2、对m只蚂蚁进行编号排序，定义为蚂蚁k1、蚂蚁k2....蚂蚁km；
10.s3、蚂蚁k通过转移概率公式选择下一节点；
11.s4、判断蚂蚁k是否陷入死锁，
12.若是，则放弃蚂蚁k，选用下一只蚂蚁k继续执行s3；
13.若否，则继续执行s5；
14.s5、判断蚂蚁k是否达到终点，
15.若否，则放弃蚂蚁k，选用下一只蚂蚁k继续执行s3；
16.若是，则记录蚂蚁k行走的路径，并继续判断蚂蚁k是否为第m只蚂蚁；
17.若是，则继续执行s6；
18.若否，则放弃蚂蚁k，选用下一只蚂蚁k继续执行s3；
19.s6、对得到的所有路径长度从小到大进行排序，按照信息素更新机制进行更新，迭代次数加1；
20.s7、判断迭代次数是否到达最大迭代次数；
21.若是，则继续执行s8；
22.若否，则重新选择m只蚂蚁，并继续执行s2；
23.s8、输出最优路径。
24.优选的，s1中初始化的参数包括蚂蚁总数m、信息素浓度因子α、启发信息强度因子β、信息素初始强度值q、信息素挥发系数ρ、需要更新信息素的蚂蚁比例u和最大迭代次数kmax。
25.优选的，转移概率公式为：
26.其中，q为取自集合(0，1)的随机数；为自适应的动态变量；
27.j1为随机选择的下一节点，j2为采用公式b选择的下一节点，公式b为：
28.其中，a为蚂蚁下一可选节点的集合；表示第k只蚂蚁在i节点时，选择下一节点j的概率；
29.τ
ij
(t)为t时刻节点i到j的信息素浓度；
30.η
ij
(t)表示距离启发函数：
[0031][0032]
其中，d
ij
为节点i与节点j的欧氏距离；d
jd
为节点j与目标点的欧式距离；
[0033]
其中θ为当前节点i与下一节点j的直线和当前节点i与上一节点的直线所组成的夹角。
[0034]
优选的，信息素更新机制的计算公式为：
[0035]
τ
ij
(t+1)＝(1-ρ)τ
ij
(t)+δτ
ij
；
[0036][0037][0038]
z＝μm；
[0039]
其中，δτ
ij
表示两节点上蚂蚁释放信息素的和；表示两节点上信息素增量；lk表示蚂蚁kn经过路径长度；q为常数，表示信息素强度初值；lg为该次迭代的最优路径长度，k
rank
为排序后第kn只蚂蚁序号，z为需进行信息素二次更新的蚂蚁数量；u表示进行信息素二次更新的蚂蚁比例，取值为(0，1)。
[0040]
与现有技术相比，本发明的上述技术方案具有如下有益的技术效果：
[0041]
本发明提供的蚁群算法的优化方法中引入转角启发函数，增加了路径选择的指向性，有效地缩短机器人在转弯过程中不必要时间；重新改进蚁群算法的距离启发函数，有效地缩短了算法的运行时间和最优移动路径的距离；改进了转移概率公式，在迭代前期增加搜索空间，迭代后期加快收敛速度；制定对信息素进行有区别的更新策略，加快寻优速度；设置信息素阈值，避免算法陷入局部最优；本发明提供的蚁群算法的优化方法能在最短路径长度，拐点数量和收敛速度方面都体现出来明显的优势，在复杂程度不同的环境中均能保持极高的收敛速度，本发明提供的算法明显具有优越性和稳健性。
附图说明
[0042]
图1为本发明提出的一种实施例的立体图。
[0043]
图2为本发明提出的一种实施例中转角方向示意图。
[0044]
图3为实验一中四种算法路径规划图。
[0045]
图4为实验一中四种算法迭代收敛曲线图。
[0046]
图5为实验二中四种算法路径规划图。
[0047]
图6为实验二中四种算法迭代收敛曲线图。
具体实施方式
[0048]
现有的蚁群算法中蚂蚁在行走过的路上会散发一种挥发性的激素即信息素，蚂蚁可以通过这种激素进行信息传递，但信息素会随着时间的推移而逐渐挥发，但是蚂蚁趋向于选择激素积累较多的路径，找到最短路径的蚂蚁总是能最早返回巢穴，从而在路上留下较多的激素；同时由于最短路径上积累了较多的激素，所以选择这条路径的蚂蚁就会越来越多，最后所有的蚂蚁都趋向于选择这条最短路径，基于蚂蚁这种行为而提出的蚁群算法具有群体合作，正反馈选择，并行计算等三大特点；
[0049]
蚂蚁在选择下一移动节点时，会依据不同路径信息素浓度及路径启发函数来选择下一节点，蚂蚁k从节点i向节点j移动的概率公式为：
[0050]
其中，α为信息素因子，反映了蚂蚁运动过程中路径上积累的信息素的量在指导蚁群搜索中的相对重要程度；β为启发函数因子，反映了启发式信息在指导蚁群搜索中的相对重要程度；a为蚂蚁下一可选节点的集合；τ
ij
(t)为t时刻节点i到j的信息素浓度；η
ij
(t)表示距离启发函数；
[0051][0052][0053]
在蚁群算法中，蚂蚁会根据信息素选择移动节点，同时自身也会在移动路径上留下信息素，并且信息素会随着时间而挥发。当完成一次迭代后进行全局信息素的更新，更新方式为：
[0054]
τ
ij
(t+1)＝(1-ρ)τ
ij
(t)+δτ
ij
[0055][0056][0057]
其中，ρ为信息素挥发系数，反映了信息素的消失水平，数值越大表示信息素挥发越快；δτ
ij
表示两节点上蚂蚁释放信息素的和；表示两节点上信息素增量；lk表示蚂蚁k经过路径长度，q为常数，表示信息素强度初值；
[0058]
但是现有的蚁群算法中若每条路径的信息素初值相同，蚂蚁选择下一个节点时倾向于随机选择，因此需要较长时间才能发挥正反馈的作用，导致算法初期收敛速度较慢；同时算法中的启发函数仅仅考虑了当前节点与下一节点的距离，从全局角度来看，启发性不强，且易陷入局部最优；为此本发明提出了以下技术方案：
[0059]
实施例一
[0060]
如图1所示，本发明提出的一种蚁群算法的优化方法，包括以下具体步骤：
[0061]
s1、建立栅格地图，参数初始化，并选择m只蚂蚁；
[0062]
初始化的参数包括蚂蚁总数m、信息素浓度因子α、启发信息强度因子β、信息素初始强度值q、信息素挥发系数ρ、需要更新信息素的蚂蚁比例u和最大迭代次数kmax；
[0063]
其中，信息素浓度因子α反映了蚂蚁运动过程中路径上积累的信息素的量在指导蚁群搜索中的相对重要程度；
[0064]
启发信息强度因子β反映了启发式信息在指导蚁群搜索中的相对重要程度；
[0065]
s2、对m只蚂蚁进行编号排序，定义为蚂蚁k1、蚂蚁k2....蚂蚁km；m的数值与m的数值相同，m只蚂蚁都是无差别的；定义蚂蚁k1、蚂蚁k2....蚂蚁km只是为方便理解和说明，m只蚂蚁中的蚂蚁k1、蚂蚁k2....蚂蚁km先从蚂蚁k1进行以下操作，放弃蚂蚁k1后，继续选用蚂蚁k2，放弃蚂蚁k2后，继续选用蚂蚁k3，直至选用放弃蚂蚁km；
[0066]
s3、依次将蚂蚁k(即蚂蚁k1、蚂蚁k2....蚂蚁km)通过转移概率公式选择下一节点；
[0067]
s4、判断蚂蚁k是否陷入死锁，
[0068]
若是，则放弃蚂蚁k，选用下一只蚂蚁k继续执行s3；
[0069]
若否，则继续执行s5；
[0070]
s5、判断蚂蚁k是否达到终点，
[0071]
若否，则放弃蚂蚁k，选用下一只蚂蚁k继续执行s3；
[0072]
若是，则记录蚂蚁k行走的路径，并继续判断蚂蚁k是否为第m只蚂蚁；
[0073]
若是，则继续执行s6；
[0074]
若否，则放弃蚂蚁k，选用下一只蚂蚁k继续执行s3；
[0075]
s6、对得到的所有路径长度从小到大进行排序，按照信息素更新机制进行更新，迭代次数加1；
[0076]
s7、判断迭代次数是否到达最大迭代次数；
[0077]
若是，则继续执行s8；
[0078]
若否，则重新选择m只蚂蚁，并继续执行s2；进行新的一轮迭代，如此反复直到迭代次数达到规定的最大次数时，算法终止，输出最优路径；
[0079]
s8、输出最优路径。
[0080]
实施例二
[0081]
现有的蚁群算法采用轮盘赌的方式选择下一节点，很容易造成蚂蚁较快集中在一条路径上，但该路径不为全局最优的情况，为解决上述技术问题，本发明提出的一种蚁群算法的优化方法，相较于实施例一，本实施例中详细记载了转移概率公式；
[0082]
转移概率公式为：
[0083]
其中，q为取自集合(0，1)的随机数；为自适应的动态变量；
[0084]
j1为随机选择的下一节点，j2为采用公式b选择的下一节点，公式b为：
[0085]
其中，a为蚂蚁下一可选节点的集合；表示第k只蚂蚁在i节点时，选择下一节点j的概率；
[0086]
τ
ij
(t)为t时刻节点i到j的信息素浓度；表示此浓度对节点选择概率的影响程度，因此赋了一个权值α；同理也是；
[0087]
η
ij
(t)表示距离启发函数：
[0088][0089]
其中，d
ij
为节点i与节点j的欧氏距离；d
jd
为节点j与目标点的欧式距离；
[0090]
通过设有的距离启发函数能增加目标节点的启发性，引导蚂蚁向目标节点方向移动，减少算法陷入局部最优的概率，进而能解决现有蚁群算法以当前节点到待选节点的距离的倒数作为唯一的启发因子，目标节点的启发性不强的技术问题；
[0091]
其中θ为当前节点i与下一节点j的直线和当前节点i与上一节点的直线所组成的夹角，夹角越大表示agv转角的角度越小，agv更趋向于选择该路径，如图2所示，改进上述函数定义转角启发函数为，通过引入转角启发函数以解决现有蚁群算法存在转角过大、次数多的问题，增大了路径长度，在实际环境中可能导致所运货物甩落，造成不必要的损失的技术问题；
[0092]
现有的蚁群算法是对一代蚂蚁中所有到达终点的蚂蚁进行更新，较长的路径可以确定为非最优路径，对这部分的路径更新信息素会最大寻找最优解的难度，影响收敛速度；为解决上述技术问题，本技术方案中设计出先对所有找到终点的蚂蚁的路径从小到大进行排序，在原来的基础上对一定比例的蚂蚁进行信息素二次更新，通过增大信息素差异来快速知道最优解的信息素更新机制：
[0093]
信息素更新机制的计算公式为：
[0094]
τ
ij
(t+1)＝(1-ρ)τ
ij
(t)+δτ
ij
；
[0095][0096][0097]
z＝μm；
[0098]
其中，δτ
ij
表示两节点上蚂蚁释放信息素的和；表示两节点上信息素增量；lk表示蚂蚁kn经过路径长度；q为常数，表示信息素强度初值；lg为该次迭代的最优路径长度，krank
为排序后第kn只蚂蚁序号，z为需进行信息素二次更新的蚂蚁数量；u表示进行信息素二次更新的蚂蚁比例，取值为(0，1)。
[0099]
为进一步验证本发明提出的一种蚁群算法的优化方法的可行性、稳定性和优越性，在matlab2022b上进行仿真实验，运行环境为：win10(64bit)操作系统，core
tm
i5-6200u处理器，8gb运行内存；
[0100]
优化蚁群算法中各个参数设置如下：α＝1.5，β＝10，ρ＝0.9，q＝1，m＝100，k
max
＝400；
[0101]
为验证本文算法在机器人路径规划中的有效性，选用了两个对比文件此处即为d1和d2作为对比算法；分别在20
×
20、30
×
30两种不同环境地图中进行仿真对比实验；
[0102]
d1:任红格,胡鸿长,史涛.基于改进蚁群算法的移动机器人全局路径规划[j].华北理工大学学报(自然科学版),2021,43(02):102-109.
[0103]
d2:张天瑞,吴宝库,周福强.面向机器人全局路径规划的改进蚁群算法研究[j].计算机工程与应用,2022,58(01):282-291.
[0104]
实验一：在20
×
20环境地图中进行仿真对比实验
[0105]
在20
×
20的栅格地图中进行仿真实验，分别利用aco、d1、d2以及本发明提出的蚁群算法的优化方法对机器人移动路径进行规划，得到图3和图4；
[0106]
表1 20
×
20栅格地图中4种蚁群算法仿真结果对比
[0107][0108]
由表1可知，四种算法的结果为：本发明提出的蚁群算法的优化方法得到的最短路径长度比应用aco算法、d1中记载的算法以及d2中记载的算法得到的最短路径长度分别缩短了17.3％和12.8％、3.4％，最优路径的迭代次数分别减少了90.1％和89.6％、82.1％，最优路径拐点数量相比于aco和d1中记载的算法分别减少了58.8％和30％。
[0109]
以上结果表明，在此简单环境中，本发明提出的蚁群算法的优化方法寻到的最优解在保证比其他算法的更优的同时收敛速度也有大幅度提升，并且机器人行走路径拐点更少，路径更为平滑，因此，本文提出的iaco算法在机器人路径规划中具有更强的寻优能力。
[0110]
实验二：在30
×
30环境地图中进行仿真对比实验
[0111]
为验证复杂情况下本文提出的优化算法的机器人移动路径规划能力，在30
×
30的栅格地图中进行机器人路径规划仿真。由于地形更为复杂，为保持算法的可靠性，将蚂蚁数量设置为100只，算法最大迭代次数设置为150，其他参数不变，得到图5和图6；
[0112]
表2 30
×
30栅格地图中4种蚁群算法仿真结果对比
[0113]
[0114][0115]
如表2所示，应用本文算法得到的最短路径比aco、d1中记载的算法以及d2中记载的算法分别缩短了17.8％和4.6％、2％，最短路径迭代次数分别减少了93.2％和88.9％，拐点数量减少了38.1％和23.5％；
[0116]
在复杂环境中，aco算法搜索速度较慢，搜索最优路径较长，并难以得到最优解。d1中记载的算法以及d2中记载的算法搜索前期具有一定的盲目性，且算法收敛较慢。而发明提供的算法所寻路径拐点数量较少，路径更为平滑，在两种环境中均能保证较高的收敛速度，表明算法的稳健性较高。
[0117]
上面结合附图对本发明的实施方式作了详细说明，但是本发明并不限于此，在所属技术领域的技术人员所具备的知识范围内，在不脱离本发明宗旨的前提下还可以作出各种变化。

技术特征：
1.一种蚁群算法的优化方法，其特征在于，包括以下具体步骤：s1、建立栅格地图，参数初始化，并选择m只蚂蚁；s2、对m只蚂蚁进行编号排序，定义为蚂蚁k1、蚂蚁k2....蚂蚁km；s3、蚂蚁k通过转移概率公式选择下一节点；s4、判断蚂蚁k是否陷入死锁，若是，则放弃蚂蚁k，选用下一只蚂蚁k继续执行s3；若否，则继续执行s5；s5、判断蚂蚁k是否达到终点，若否，则放弃蚂蚁k，选用下一只蚂蚁k继续执行s3；若是，则记录蚂蚁k行走的路径，并继续判断蚂蚁k是否为第m只蚂蚁；若是，则继续执行s6；若否，则放弃蚂蚁k，选用下一只蚂蚁k继续执行s3；s6、对得到的所有路径长度从小到大进行排序，按照信息素更新机制进行更新，迭代次数加1；s7、判断迭代次数是否到达最大迭代次数；若是，则继续执行s8；若否，则重新选择m只蚂蚁，并继续执行s2；s8、输出最优路径。2.根据权利要求1所述的一种蚁群算法的优化方法，其特征在于，s1中初始化的参数包括蚂蚁总数m、信息素浓度因子α、启发信息强度因子β、信息素初始强度值q、信息素挥发系数ρ、需要更新信息素的蚂蚁比例u和最大迭代次数kmax。3.根据权利要求2所述的一种蚁群算法的优化方法，其特征在于，转移概率公式为：其中，q为取自集合(0，1)的随机数；为自适应的动态变量；j1为随机选择的下一节点，j2为采用公式b选择的下一节点，公式b为：其中，a为蚂蚁下一可选节点的集合；表示第k只蚂蚁在i节点时，选择下一节点j的概率；τ
ij
(t)为t时刻节点i到j的信息素浓度；η
ij
(t)表示距离启发函数：
其中，d
ij
为节点i与节点j的欧氏距离；d
jd
为节点j与目标点的欧式距离；其中θ为当前节点i与下一节点j的直线和当前节点i与上一节点的直线所组成的夹角。4.根据权利要求3所述的一种蚁群算法的优化方法，其特征在于，信息素更新机制的计算公式为：τ
ij
(t+1)＝(1-ρ)τ
ij
(t)+δτ
ij
；；z＝μm；其中，δτ
ij
表示两节点上蚂蚁释放信息素的和；表示两节点上信息素增量；l
k
表示蚂蚁kn经过路径长度；q为常数，表示信息素强度初值；l
g
为该次迭代的最优路径长度，k
rank
为排序后第kn只蚂蚁序号，z为需进行信息素二次更新的蚂蚁数量；u表示进行信息素二次更新的蚂蚁比例，取值为(0，1)。

技术总结
本发明涉及AGV路径规划技术领域，具体为一种蚁群算法的优化方法，步骤为S1、建立栅格地图，参数初始化，并选择M只蚂蚁；S2、对M只蚂蚁进行编号排序；S3、蚂蚁通过转移概率公式选择下一节点；S4、判断蚂蚁是否陷入死锁，若是则放弃蚂蚁继续执行S3；若否则继续判断蚂蚁是否达到终点，若否则放弃蚂蚁继续执行S3；若是则记录蚂蚁行走的路径，并继续判断蚂蚁是否为第M只蚂蚁；若是则对得到的所有路径长度从小到大进行排序，按照信息素更新机制更新；若否则执行S3；S5、判断迭代次数是否到达最大迭代次数；若是则输出最优路径；若否则重新选择M只蚂蚁并继续执行S2。本发明提供的算法能提高蚁群算法的收敛速度，减少拐点数量。减少拐点数量。减少拐点数量。


技术研发人员：罗子灿 何广
受保护的技术使用者：湖南工业大学
技术研发日：2023.05.05
技术公布日：2023/7/21