基于IAFSA和AGA混合算法的移动机器人路径规划
刘宁宁 陈志军 闫学勤
关键词： 移动机器人; 路径规划; 改进人工鱼群算法; 自适应遗传算法; 标准人工鱼群算法; 标准遗传算法
中图分类号： TN911.1?34; TP242 ? ? ? ? ? ? ? ? ? ?文献标识码： A ? ? ? ? ? ? ? ? ?文章编号： 1004?373X（2019）03?0157?06
Abstract： The artificial fish swarm algorithm is easy to fall into local optimization， and has the problem of inaccurate result for path planning of mobile robot， and the genetic algorithm has the problems of easy prematurity and slow convergence speed for path planning. Therefore， a mobile robot path planning method based on improved artificial fish swarm algorithm （IAFSA） and adaptive genetic algorithm （AGA） is proposed. The grid method is used to establish the environment model of mobile robot， and then the IAFSA is used to search the initial feasible path of mobile robot. The searched initial feasible path is taken as the initial population of AGA. The AGA is adopted to optimize the global optimal path of mobile robot. The simulation results show that the hybrid algorithm is superior to the standard artificial fish swarm algorithm in the aspects of result accuracy and stability， and is superior to the standard genetic algorithm in the aspects of local optimization avoidance and convergence speed.
Keywords： mobile robot; path planning; improved artificial fish swarm algorithm; adaptive genetic algorithm; standard artificial fish swarm algorithm; standard genetic algorithm0 ?引 ?言
路徑规划被认为是根据距离、时间、成本、能量等标准进行最优路径的计算，距离和时间是最常用的准则。移动机器人能够根据距离和时间这两个准则自主决策出一条连接起始位置和目标位置的避撞最优或次优路径[1]。
目前，基于遗传算法（GA）、蚁群算法（ACO）、人工神经网络算法（ANN）、人工鱼群算法（AFSA）等智能算法的移动机器人路径规划是非常普遍的应用，尽管这些智能算法优化了移动机器人的路径，但是优化效果并不理想。像遗传算法[2]易出现早熟现象且收敛速度慢;蚁群算法[3]的信息素在求解初期比较匮乏，所以蚁群算法的前期求解速度较慢;人工神经网络[4]结构比较复杂，参数也不容易确定，且易生成局部最优路径;人工鱼群算法[5]由于鱼群聚群和追尾而导致算法易陷入局部最优，同时在算法后期由于鱼群随机觅食而不能求取高精度的最优解等。针对单一智能算法的缺陷，现在需要解决的主要问题是如何选择智能算法来优化移动机器人的路径。
通过将两种改进后的算法相结合来实现移动机器人的全局路径规划是近些年研究的热点。因为遗传算法种群进化能力强，所以对全局搜索的范围十分有利，但是这种算法易受种群质量的影响，从而影响算法的计算效率和收敛速度。人工鱼群算法的搜索速度快并且寻优能力强，但由于其存在随机移动的特性，使得该算法较难获取高精度的全局最优路径。通过对上述遗传算法和人工鱼群算法的优点及其存在的缺陷进行分析，提出一种改进人工鱼群算法和自适应遗传算法相结合的混合算法优化移动机器人的路径。该算法用改进人工鱼群算法生成初始种群，解决遗传算法容易受初始种群影响的缺点，用自适应遗传算法弥补人工鱼群算法后期搜索精度差及其后期寻优速度慢的缺陷，从而获得了高精度、高质量、收敛速度快的寻优能力。
式中：[Fmax]表示群体最大适应度;[Fav]表示每代群体的平均适应度值;[F]表示要变异个体的适应度值;[k3]，[k4]表示[0，1]区间内的任意常数。
4） 删除算子
在生成个体路径时，由于初始路径的产生和变异操作的连接过程可能会产生相同的栅格序号，从而影响寻优速度，所以用删除算子删除掉两相同栅格中的一个栅格和两相同栅格之间的冗余栅格，将得到的路径作为下一代种群的个体。
2.2.4 ?移动机器人路径优化流程
首先用改进人工鱼群算法产生移动机器人的初始路径，然后用自适应遗传算法中选择、交叉和变异等操作对生成的初始路径寻优，路径优化步骤如下：
Step1：自适应遗传算法初始化，设种群最大进化代数为MAX，设进化代数初始值[t=1]。
Step2：对移动机器人工作环境进行栅格建模，利用改进人工鱼群算法得到机器人的初始路径，将初始路径作为自适应遗传算法的初始种群。
Step3：采用适应度函数计算种群中的每个个体适应度值。
Step4：用轮盘赌的方法执行选择操作，从而复制出下一代个体。
Step5：任意选择两个个体，判断这两个个体是否满足交叉概率，若满足，则分别在两个个体中随机产生一个交叉位，进而执行交叉操作。
Step6：根据变异概率执行变异操作。
Step7：路径中若有重合路径点，则执行删除操作，直到满足无重合路径点的条件。
Step8：如果[t≥MAX]，转Step9;否则，令[t=t+1]，转Step3。
Step9：循环结束，输出最优个体。3 ?仿真研究
3.1 ?实验1
在10[×]10的栅格环境下对本文混合算法和单一的标准人工鱼群算法进行仿真比较，仿真过程中的相关参数设置为：人工鱼总数[N=10]，视野域Visual=4，拥挤度因子[delta=0.7]，最大选择次数try_number=3，最大迭代次数[M=10]，跳转因子[η]=5，常系数[c=2]，[k1=0.8]，[k2=0.9]，[k3=0.1]，[k4=0.2]，种群最大进化代数MAX=10。在此环境下，仿真结果如图3所示。
通过对图3a），图3b）的对比可以发现，本文算法比标准人工鱼群算法能获得更短的路径。
为了更好地说明本文混合算法在优化精度和稳定性上要优于标准人工鱼群算法，分别对标准人工鱼群算法和本文混合算法进行10次仿真比较，仿真结果如表1所示。
从表1中可以看出，本文混合算法在结果精度和稳定性方面优于标准人工鱼群算法。在最优结果精度上，本文混合算法较标准人工鱼群算法提高4.2%;在稳定性方面，本文混合算法相比标准人工鱼群算法提高了79.7%。
3.2 ?实验2
在15[×]15的栅格环境下，对本文混合算法和标准遗传算法应用到移动机器人路径规划方面进行了仿真比较，仿真过程中的相关参数设置为：人工鱼的总数[N=]10，视野域Visual=4，拥挤度因子delta=0.7，最大选择次数try_number=3，最大迭代次数[M=50]，跳转因子[η]=5，常系数[c=2]，[k1=0.8]，[k2=0.9]，[k3=0.1]，[k4=0.2]，种群最大进化代数MAX=50;遗传算法初始种群大小设置为50，最大迭代次數设置为50，标准遗传算法的交叉概率设置为固定概率[pc]=0.6，变异概率设置为固定概率[pm]=0.01。在此环境下，本文混合算法和标准遗传算法寻找最优路径结果和收敛曲线分别如图4，图5所示。
从图4和图5能够看出，本文混合算法在寻优能力上要优于标准遗传算法。
为了更好地说明本文混合算法的优越性，分别对本文混合算法和标准遗传算法进行多次仿真，仿真结果如表2所示。
通过表2可以看出，本文混合算法与标准遗传算法相比，规划长度、规划时间和所需迭代次数都有明显改善。实验数据有力说明了本文混合算法具有路径规划能力强、搜索效率高以及收敛速度快等优点，验证了本文混合算法的优越性。
4 ?结 ?论
本文所设计的IAFSA?AGA混合算法优化了移动机器人的路径，为今后探索路径规划算法提供了一种思维模式及其较大的参考与学术价值。
关键词： 移动机器人; 路径规划; 改进人工鱼群算法; 自适应遗传算法; 标准人工鱼群算法; 标准遗传算法
中图分类号： TN911.1?34; TP242 ? ? ? ? ? ? ? ? ? ?文献标识码： A ? ? ? ? ? ? ? ? ?文章编号： 1004?373X（2019）03?0157?06
Abstract： The artificial fish swarm algorithm is easy to fall into local optimization， and has the problem of inaccurate result for path planning of mobile robot， and the genetic algorithm has the problems of easy prematurity and slow convergence speed for path planning. Therefore， a mobile robot path planning method based on improved artificial fish swarm algorithm （IAFSA） and adaptive genetic algorithm （AGA） is proposed. The grid method is used to establish the environment model of mobile robot， and then the IAFSA is used to search the initial feasible path of mobile robot. The searched initial feasible path is taken as the initial population of AGA. The AGA is adopted to optimize the global optimal path of mobile robot. The simulation results show that the hybrid algorithm is superior to the standard artificial fish swarm algorithm in the aspects of result accuracy and stability， and is superior to the standard genetic algorithm in the aspects of local optimization avoidance and convergence speed.
Keywords： mobile robot; path planning; improved artificial fish swarm algorithm; adaptive genetic algorithm; standard artificial fish swarm algorithm; standard genetic algorithm0 ?引 ?言
路徑规划被认为是根据距离、时间、成本、能量等标准进行最优路径的计算，距离和时间是最常用的准则。移动机器人能够根据距离和时间这两个准则自主决策出一条连接起始位置和目标位置的避撞最优或次优路径[1]。
目前，基于遗传算法（GA）、蚁群算法（ACO）、人工神经网络算法（ANN）、人工鱼群算法（AFSA）等智能算法的移动机器人路径规划是非常普遍的应用，尽管这些智能算法优化了移动机器人的路径，但是优化效果并不理想。像遗传算法[2]易出现早熟现象且收敛速度慢;蚁群算法[3]的信息素在求解初期比较匮乏，所以蚁群算法的前期求解速度较慢;人工神经网络[4]结构比较复杂，参数也不容易确定，且易生成局部最优路径;人工鱼群算法[5]由于鱼群聚群和追尾而导致算法易陷入局部最优，同时在算法后期由于鱼群随机觅食而不能求取高精度的最优解等。针对单一智能算法的缺陷，现在需要解决的主要问题是如何选择智能算法来优化移动机器人的路径。
通过将两种改进后的算法相结合来实现移动机器人的全局路径规划是近些年研究的热点。因为遗传算法种群进化能力强，所以对全局搜索的范围十分有利，但是这种算法易受种群质量的影响，从而影响算法的计算效率和收敛速度。人工鱼群算法的搜索速度快并且寻优能力强，但由于其存在随机移动的特性，使得该算法较难获取高精度的全局最优路径。通过对上述遗传算法和人工鱼群算法的优点及其存在的缺陷进行分析，提出一种改进人工鱼群算法和自适应遗传算法相结合的混合算法优化移动机器人的路径。该算法用改进人工鱼群算法生成初始种群，解决遗传算法容易受初始种群影响的缺点，用自适应遗传算法弥补人工鱼群算法后期搜索精度差及其后期寻优速度慢的缺陷，从而获得了高精度、高质量、收敛速度快的寻优能力。
式中：[Fmax]表示群体最大适应度;[Fav]表示每代群体的平均适应度值;[F]表示要变异个体的适应度值;[k3]，[k4]表示[0，1]区间内的任意常数。4） 删除算子
在生成个体路径时，由于初始路径的产生和变异操作的连接过程可能会产生相同的栅格序号，从而影响寻优速度，所以用删除算子删除掉两相同栅格中的一个栅格和两相同栅格之间的冗余栅格，将得到的路径作为下一代种群的个体。
2.2.4 ?移动机器人路径优化流程
首先用改进人工鱼群算法产生移动机器人的初始路径，然后用自适应遗传算法中选择、交叉和变异等操作对生成的初始路径寻优，路径优化步骤如下：
Step1：自适应遗传算法初始化，设种群最大进化代数为MAX，设进化代数初始值[t=1]。
Step2：对移动机器人工作环境进行栅格建模，利用改进人工鱼群算法得到机器人的初始路径，将初始路径作为自适应遗传算法的初始种群。
Step3：采用适应度函数计算种群中的每个个体适应度值。
Step4：用轮盘赌的方法执行选择操作，从而复制出下一代个体。
Step5：任意选择两个个体，判断这两个个体是否满足交叉概率，若满足，则分别在两个个体中随机产生一个交叉位，进而执行交叉操作。
Step6：根据变异概率执行变异操作。
Step7：路径中若有重合路径点，则执行删除操作，直到满足无重合路径点的条件。
Step8：如果[t≥MAX]，转Step9;否则，令[t=t+1]，转Step3。
Step9：循环结束，输出最优个体。3 ?仿真研究
3.1 ?实验1
在10[×]10的栅格环境下对本文混合算法和单一的标准人工鱼群算法进行仿真比较，仿真过程中的相关参数设置为：人工鱼总数[N=10]，视野域Visual=4，拥挤度因子[delta=0.7]，最大选择次数try_number=3，最大迭代次数[M=10]，跳转因子[η]=5，常系数[c=2]，[k1=0.8]，[k2=0.9]，[k3=0.1]，[k4=0.2]，种群最大进化代数MAX=10。在此环境下，仿真结果如图3所示。
通过对图3a），图3b）的对比可以发现，本文算法比标准人工鱼群算法能获得更短的路径。
为了更好地说明本文混合算法在优化精度和稳定性上要优于标准人工鱼群算法，分别对标准人工鱼群算法和本文混合算法进行10次仿真比较，仿真结果如表1所示。
从表1中可以看出，本文混合算法在结果精度和稳定性方面优于标准人工鱼群算法。在最优结果精度上，本文混合算法较标准人工鱼群算法提高4.2%;在稳定性方面，本文混合算法相比标准人工鱼群算法提高了79.7%。3.2 ?实验2
在15[×]15的栅格环境下，对本文混合算法和标准遗传算法应用到移动机器人路径规划方面进行了仿真比较，仿真过程中的相关参数设置为：人工鱼的总数[N=]10，视野域Visual=4，拥挤度因子delta=0.7，最大选择次数try_number=3，最大迭代次数[M=50]，跳转因子[η]=5，常系数[c=2]，[k1=0.8]，[k2=0.9]，[k3=0.1]，[k4=0.2]，种群最大进化代数MAX=50;遗传算法初始种群大小设置为50，最大迭代次數设置为50，标准遗传算法的交叉概率设置为固定概率[pc]=0.6，变异概率设置为固定概率[pm]=0.01。在此环境下，本文混合算法和标准遗传算法寻找最优路径结果和收敛曲线分别如图4，图5所示。
从图4和图5能够看出，本文混合算法在寻优能力上要优于标准遗传算法。为了更好地说明本文混合算法的优越性，分别对本文混合算法和标准遗传算法进行多次仿真，仿真结果如表2所示。
通过表2可以看出，本文混合算法与标准遗传算法相比，规划长度、规划时间和所需迭代次数都有明显改善。实验数据有力说明了本文混合算法具有路径规划能力强、搜索效率高以及收敛速度快等优点，验证了本文混合算法的优越性。
4 ?结 ?论
本文所设计的IAFSA?AGA混合算法优化了移动机器人的路径，为今后探索路径规划算法提供了一种思维模式及其较大的参考与学术价值。
