混合智能算法在机器人路径规划中的应用

代婷婷，董延寿

（昭通学院 数学与统计学院，云南 昭通 657000）

在日常生活中机器人无处不在地影响着我们，给生活带来了许多方便和精彩，在很多领域发挥着重要的不可替代的作用，特别是在节省人力、物力方面发挥的作用日益突出。对它主要研究其通用性和适应性[1-2]。为了满足人类的各种需求，必须深入分析复杂多变的环境，设计合理的算法程序实现其自主导航运动目标，而路径规划是移动机器人实现这一目标的核心技术，在研究领域是热点关注的地方[3]。机器人的智能水平越高表示它的路径规划水平较高。因此，寻找高效的机器人路径规划方法显得非常有意义[4]。尽管蚁群算法在收敛速度等方面有不足和局限，可在求解机器人路径规划方面由于它具有的诸如正反馈性、强鲁棒性、并行性等很多优点可以得到充分利用，使得该算法在很多智能化领域被深入研究和广泛应用。为了充分利用蚁群算法的优势，挖掘文献[5]和文献[6]中改进蚁群算的技巧原理，巧妙地柔和两种改进的优点得出了另外一种新的改进蚁群算法。将得到的融合双因子改进蚁群算法与遗传算法于机器人路径规划实验的不同阶段混合使用得到了良好效果，选择栅格法在不同规模的栅格上使用MATLAB2019 进行机器人路径规划实验进一步突出混合算法的优势。

1 相关理论

1.1 遗传算法

遗传算法是一种广为人知的智能算法，因为其具有强鲁棒性、独立性、可操作性等优点，使得该算法的应用相当广泛，物理、数学、计算机、化学等领域都有涉及[7-8]。其主要原理：产生初始种群后，这些种群通过杂交会逐代演化产生适应生存环境的优秀子代，而这个优秀的子代就可以看成是遗传算法的最优化的近似解，按照达尔文的进化论适者生存优胜劣汰的大自然生物学原理将优秀的个体选择出来，交配挑选出来的个体。在每一代中，按照自然遗传学的相关理论找出相应的算子，然后依据算子原理进行让种群之间进行交叉，在组合交叉的过程中会产变异的种群，一代又一代的种群按照此种方法交叉变异，最后就会产生适应环境能力强的种群，即最为优秀的个体就会产生，当最优秀的个体通过解码后就会对应优化问题的最优解，则代表新的解集就会得到。由于国内外的学者对此方法的研究很深入，在各方面都取得了不错的成就，这使得遗传算法的性能逐步被提高很多，从而使得该算法的应用领域越来越广泛[9-10]。

1.2 关于遗传算法的路径规划

基于以上关于遗传算法的理论可以得到遗传算法在路径规划中的实现步骤[11]:

（1）随机产生一定数目的很多条路经，将这些随机产生的路径看成初始种群，机器人在栅格上行走；

（2）在机器人行走中需要连续的路径，为了将上述间断的路径改成连续的路径需要对相邻的栅格做连续性判断，按照上下左右的顺序取相邻栅格，将无障碍的栅格插入不相邻的栅格，不断调整直到所有的栅格路径连续为止；

（3）按照个体适应度函数求解个体所占的比率从而选择出需要的优秀个体，为了防止算法陷入局部死循环，采用轮盘赌的方式进行；

（4）在路径规划中进行交叉操作，在挑选出两条相同路径的交点时采用单点交叉的方式进行，依此点为目标点将后面的路径进行交叉，同时对路径的连续性进行判断，不断修改判断知道完成所有的交叉操作。

（5）比较变异概率和特定的数值，当变异概率大于给定的数字时，那么路径上的两个栅格随机选取，并对相邻的情况做出判断，使用产生初始种群的方法调整栅格的连续性，直到所有栅格连续完成变异操作。

1.3 改进的蚁群算法

1.3.1 改进启发函数

基于基本蚁群算法的原理分析以及结合相关的参考文献，发现影响最短路径计算结果的主要原因就是节点之间的概率转移以及蚂蚁行走路径上不断更新变化的信息素浓度。而转移概率对最短路径的影响主要是通过它里面的启发函数起作用的。常规遗传算法的概率转移取相邻节点i 与j的欧氏距离倒数作启发函数使用。在最初搜索的时候，行走路径上的蚂蚁数量较少，释放的信息素较少，造成其他蚂蚁偏离正确寻找路径的概率较大，这样很容易形成局部的最优解或者产生无效解甚至进入死循环求不出结果[12]。于是文献[5]在启发函数中引入了当前和目标节点的欧氏距离，从而使两个节点的联系更加的紧密，改进启发函数的数学表达式如公式（1）所示：

在上面的（1）式中dij表示节点i 与j 的欧氏距离；djE是节点j 和目标节 点E 之间的欧氏距离,于是搜索路径的方向性被加强，加强的方向性使得漫无目的的搜寻的时间大大减少，这一改进从时间上来说就比原有的算法具有优势，计算的效率明显提高。

1.3.2 改进的信息素浓度更新方式

大量文献和实验表明，蚂蚁对信息素浓度的更新会对蚁群算法的运行时间、运行效率以及算法的准确性都会产生深远的影响，即信息素浓度的不同更新方式对蚁群算法的计算效果影响是非常巨大的[13]。文献[6]给出了一种特别凑效的方法，避开信息素挥发因子ρ的随机性，对信息素的浓度进行动态的控制。即在算法开始的时候，用统一的方式对所有蚂蚁进行信息素更新，当迭代达到设定的次数之后执行不同的更新策略在不同的蚂蚁身上。对表现优秀的蚂蚁进行奖励，给予正反馈的激励加强它的信息素浓度。相反，对表现不好的蚂蚁进行惩罚，适当的减少其信息素的浓度，防止对后面蚂蚁的路径选择产生误导引起收敛过快只找到局部的最优解。将前面提到的设定次数记为N,在前N 次的循环中增加和 减少最优最差路径的信息素按照（2）式进行计算。

除此之外，为了促使路径朝着最优化的方向前进，在每次循环中将本次迭代中最佳路径上的信息素进一步加强，增强值具体依据公式（3）的表达式计算，使得蚁群算法的正反馈机制得到充分的利用。

结合以上两种改进算法的优势，在基本蚁群算法中同时使用文献[5]的启发函数改进与文献[6]的信息素浓度更新方式改进，于是就得到了双因子改进蚁群算法。

2 双因子改进蚁群算法与遗传算法的混合

2.1 混合智能算法原理

结合遗传算法的优点，将上文中通过同时改进启发函数和信息素浓度的更新方式形成的改进蚁群算法结合，构造出了一种新的智能优化算法.为了充分利用这两种算法的优点，本文中的混合算法在算法的初期选择遗传算法，在后期选用蚁群算法，两种算法在整个混合算法中的总体趋势如图1：

图1 速度-时间曲线图Fig.1 Speed-time curve

2.2 新智能算法步骤

通过图1 可以发现，在机器人路径规划寻优实验中前半段使用 遗传算法，而后半段使用文献[5]和文献[6]结合得到改进蚁群算法，可以使得混合算法的效率达到最大。基于此理论可得到两种算法结合混合算法的步骤如下：

Step1：对遗传算法的各个参数进行初始化；

Step2：寻找出初始的路径，依据遗传算法的理论随机生成初始种群;

Step3：通过适应度函数对每一个体所占的比率逐个计算，根据比率值的大小找出当代中最优个体；

Step4：选择规划路径中的各值进行交叉变异，找到更好的下一代种群最优路径；

Step5：适应度值的计算，计算完之后与当前的最优值对比，对当前最优个体是否更新；

Step6：判断遗传算法停止的条件最大循环次数N是否出现，若是转向步骤7执行改进蚁群算法，否则转步骤4；

Step7：放置所有蚂蚁在初始点，运用遗传算法得到最优路径长度lmax，把lmax作为改进蚁群算法的信息素部分初值；

Step8：所有蚂蚁都从S 点出发，随后将S 加入到禁忌表中；

Step9：依据公式（1）寻找下一个节点，将找到属于可行节点集合的节点作为下一个可行节点，并且将其放入到禁忌表中；

Step10：对蚂蚁当前的行走路径做标记，判断蚂蚁是否已到终点，如果否，返回至Step9；若是蚂蚁到达了终点，接对是否已走完全程进行判断，若是全部走完则执行Step11，否则返回到Step8 安排另外一只蚂蚁重新出发；

Step11：等到全部蚂蚁到达目标节点之后，求解出蚂蚁行走过的路径中的最优和最差路径，然后增加迭代次数并对信息素更新；

Step12：在迭代次数最大时输出最短路径，否则转到Step8。

3 实证分析

虽然从理论上讲混合的智能算法综合了遗传算法和改进蚁群算法的优点，但是方法的优劣最终需要在实际案例中验证，使用得到的混合智能算法在规模为20×20 和30×30 的机器人规划路径问题上，实验的具体操作是寻找路径的开始阶段要用到遗传算法，因此需要对该算法的实验参数进行设置，即初始化遗传改进蚁群混合算法的各个参数，下面的表1 是具体的参数设置。

表1 遗传改进蚁群混合算法的参数设置Tab.1 Parameter setting of genetically improved ant colony hybrid algorithm

设置完遗传改进蚁群混合算法的参数之后，在规模为20×20 和30×30 栅格的环境地图中应用混合遗传改进蚁群算法进行实验，设置相同的迭代次数，从寻找最短路径所用的时间上寻找该方法的优势。两种环境下机器人从起点到终点无碰撞的寻找最短路的实验结果如图2 和图3所示。

图2 20×20 栅格下混 合算法的收敛曲线Fig.2 Convergence curve of hybrid algorithm under grid

图3 30×30 栅格下混合 算法的收敛曲线Fig.3 Convergence curve of hybrid algorithm under grid

由图2 和图3 可以看出，应用遗传改进蚁群混合算法使机器人在20×20 栅格环境中寻找最优路径时，在第3 次迭代时算法就会收敛即可得到最短路径；在30×30 栅格环境下，第5 次迭代时算法收敛就会得到最短路径。这只时说明了此算法在求解机器人路径规划方面具有较快的速度，大大缩短了求解最优解的时间。通过文献[5]和文献[6]可知改进的蚁群算法比基本的蚁群算法具有优势，所以要说明混合了遗传算法的改进蚁群算法比其他方法优秀，只需要与改进的蚁群算法在相同的实验和环境下作如表2 的比较。

表2 改进蚁群算法与混合智能算法求解结果比较Tab.2 Comparison of the solution results of the improved ant colony algorithm and the hybrid intelligent algorithm

由表2 可以看出混合算法可以用较少的迭代次数求解出最短路径，算法的复杂度较低，也更节省时间。

4 结束语

本文主要内容是阐述遗传算法的原理以及如何得到改进的蚁群算法，并且将两种智能算法结合起来形成一种解决机器人路径规划的问题的遗传改进蚁群混合算法，其原理是在整体求解过程中先采用遗传算法求解最短路，对于双因子改进蚁群算法信息素的部分初值使用最短路的长度，这样加强了改进蚁群算法的方向性，减少了搜索的盲目性。这对蚂蚁尽快找到最优路径起到了促进作用。将这种混合的算法分别使用于20×20 栅格和30×30 栅格环境下对机器人规划路径问题进行了求解，得到结果显示此方法的求解结果更令人满意。