一种融合模拟退火的改进遗传算法多任务路径规划*

孙丽娜，田军委，刘雪松，王 沁

(1.西安工业大学 机电工程学院，西安 710021；2.内蒙古北方重工业集团有限公司，包头 014033)

在“中国制造2025”飞速发展和创新中国战略实行下，移动机器人技术不断进步[1]。为了提高机器人作业效率和整体效益，常常将多个任务同时赋予单个机器人以实现最佳作业能力[2]。田间作业有任务多样性和环境复杂性的特点，路径规划作为机器人田间正常工作的基础之一，研究工作十分必要。

路径规划是指以顺利到达目标位置的代价最小化为目标，规划出一条机器人行走的路径[3]。遗传算法是机器人路径规划较常用的算法之一，但是经典遗传算法存在局部搜索能力较差、易产生早熟收敛等缺陷，所以不少学者对经典遗传算法进行了改进。文献[4-9]从遗传算法的操作算子进行改进，重新定义各个算子、自适应交叉概率和变异概率。改进后加快算法的收敛速度，但当任务复杂度增加时算法会过早陷入局部收敛。文献[10-13]对适应度函数进行了改进，如添加转弯角度控制因子、路径连贯性，同时考虑多个适应度影响因素时不能有效保证路径值最短。文献[14-16]遗传算法分别与不同算法进行融合，解决了局部最优解的问题，但没有考虑多个任务点的情况，不能验证改进算法在增加任务点后的算法可行性。

本文针对多个任务点的作业环境，将模拟退火算法的进化机制融合至遗传算法,改善遗传算法的局部搜索能力和算法收敛速度。

1 环境地图建模

环境地图包含了大量的空间准确位置信息：机器人的起点、终点、任务点、障碍物等,如图1所示。

图1 栅格地图模型

文中环境是二维平面静态地图，用栅格法来建立环境模型(20 m×20 m的尺寸)，栅格法是环境建模方面应用最广泛的方法之一，它将机器人所在空间抽象为二维空间。每个单元格具备一种环境信息，占据栅格的数值为1，未占据的栅格数值为0。图1中的白色网格表示机器人可以穿越的区域，黑色网格表示障碍物。

2 改进的多任务机器人路径规划

遗传算法作为一种群体智能算法，具有较强的全局寻优能力。文中以遗传算法作为模型求解算法，针对其易于早熟收敛、收敛速度慢等问题进行改进，融合模拟退火算法Metropolis准则提高算法的局部寻优能力。模拟退火算法源于现实的物理退火过程，通过抽象真实物理退火过程中的加温过程、等温过程、冷却过程来求得最优解，通过其特有的接受准则来保证算法局部寻优能力。

2.1 编码方式

栅格序号与栅格坐标相比，具有形式简单的优点。因此，本文对染色体的编码采用栅格序号。即在栅格地图中按照从上到下、从左到右的顺序将小栅格进行编号，0代表机器人移动起点，399代表移动终点，中间任务点的位置编号同样。

为确保机器人路径规划的可靠性，要求每条可行路径不能出现障碍物序号和重复序号。如：P={S,P1,P2,P3…Pn,G}表示一条可行路径，其中S为起点，G为终点，Pi(i=1,2,3…n)是栅格中的可行节点。

2.2 种群初始化

种群初始化时，由机器人移动环境中障碍物信息已知，栅格化环境地图后，自由栅格和障碍栅格容易区分。所以采用在移动机器人运动起点到终点之间，随机选择一系列标记为0的自由栅格作为路径节点。连接起点、终点和选定的路径节点作为机器人移动的一条无障碍路径。

2.3 建立适应度函数

算法的适应度函数即模型优化目标函数。文中以路径距离作为函数评价指标，一条可行路径上是由许多个节点连接而成，则路径距离L为

(1)

式中：n为机器人通过的栅格总数；xi为第i个节点的横坐标；yi为第i个节点的纵坐标。

对机器人路径选择，路径越短则为更优，则目标函数即适应度函数F为路径距离L的倒数。

2.4 遗传算子操作

2.4.1 选择算子

在遗传算法开始时，总是随机的产生一些个体(即初始解)，根据预定的目标函数对每一个体进行评估，给出一个适应度值，基于此适应度值选择一些个体用来产生下一代。较优的个体被留下，经过交叉和变异算子进行组合再生成新的一代，这样逐步朝着最优解的方向进化。文中采用轮盘赌选择方法，个体被选中的概率与适应度函数值大小成正比。即N个的适应值变换为1至N，则编号为m的个体被选中的概率P为

(2)

2.4.2 交叉算子

遗传算法通过交叉算子来维持种群的多样性。文中采用常见单点交叉方法，即随机选择两条父代路径，在两条路径的相同节点处进行交叉操作，不包含起点和终点，若相同节点有多个则随机选择一个节点交叉。当两条父代路径没有相同节点或者交叉后基因相同时，则放弃本次交叉操作，父代个体为

V1={0,23,89,156,235,289,376,399},

V2={0,34,93,158,321,289,364,399}。

选择父代的相同节点289作为交叉点，则生成的两条子代个体为

C1={0,23,89,156,235,289,364,399}，

C2={0,34,93,158,321,289,376,399}。

2.4.3 变异算子

采取随机变异的方法进行变异操作。从个体中除终点和起点之外随机选择一个序号视为变异点，然后删除该序号，这样可避免出现不可行解。

2.5 融合Metropolis准则

模拟退火算法具有较强的局部寻优能力，为了解决遗传算法易陷入局部最优解的问题，文中将模拟退火算法的进化机制融合至遗传算法中。

模拟退火算法存在一定的容错能力，能以一定概率接受劣质解，概率P为新解接受概率，大小受当前温度T及新旧解适应度E差的影响，总的趋势是温度越低接受概率越低，差值越大接受概率越低。

当E(xnew)

当E(xnew)≥E(xold)时，

(3)

得到接受概率后随机产生一个随机数，介于0到1之间，当其大于接受概率P时，不接受新解，当其小于P时，接受新解。故在遗传算法操作产生新解后可采用Metropolis准则决定是否保留新解。

2.6 多任务分解

文中设置了多个任务点，机器人在移动过程中从起点出发经历多个任务点最终到达终点。要使机器人行走的总路径最短，将多任务路径分解成单任务路径，保证单任务路径最短则总路径即为最短。栅格图中起点编号为0，终点编号为399，两个任务点编号分别为110和246，则可以分解为：[0,110],[110,246],[246,399]，总路径即为三段路径之和。

3 仿真结果及分析

为验证文中提出算法的合理性和有效性，运用Matlab软件在20 m×20 m的栅格环境模型中进行仿真分析。参数设置见表1。

表1 参数设置

在仿真实验中分别设置障碍物个数为31个和69个，在不同任务点个数下对移动机器人进行路径规划，实验图中路径长度取单位为米。

3.1 双任务实验

障碍物个数为31个时的仿真实验结果如图2和图3所示，经典遗传算法在进化8代得到路径值为39.799 0 m。改进遗传算法在进化第5代后趋于稳定，得到路径值为37.799 0 m。为了验证本文所提出改进遗传算法的有效性，与文献[7]提出的自适应改进遗传算法选择相同的工作环境，即障碍物的个数设置为31个。双任务点下三种算法的仿真实验结果对比见表2。

表2 仿真实验结果对比

图2 实验运动轨迹图

图3 算法收敛曲线图

当障碍物数量增加到69个时，三种算法的仿真实验结果如图4和图5所示，结果对比见表3。

图4 实验运动轨迹图

图5 算法收敛曲线图

表3 仿真实验结果对比

经典遗传算法在进化11代陷入了局部最优解，自适应改进算法在进化6代收敛，而文中的改进遗传算法进化4代达到稳定。由此可得，改进遗传算法的收敛速度优于这两种算法，且路径值更短。

3.2 三任务实验

障碍物个数为31个时，机器人在工作时需要经历三个任务点的仿真实验结果如图6和图7所示，标准遗传算法的路径长度为37.799 0 m，自适应改进算法的路径长度为37.799 0 m，而文中的改进算法路径长度为36.627 4 m。经典遗传算法在12代时陷入了局部最优解，自适应改进算法在8代达到收敛，实验结果如图8所示，而改进后的算法在4代时候趋于稳定状态，改进后的算法对移动机器人的静态最优路径优于标准遗传算法。三种算法在收敛速度、最短路径长度方面的对比见表4。

图6 实验运动轨迹图

图7 算法收敛曲线图

图8 自适应改进算法仿真实验结果

表4 仿真实验结果对比

移动机器人作业需要在69个障碍物下遍历三个任务点时，实验结果如图9和图10所示。自适应改进算法的实验结果如图11所示。经典遗传算法在进化18代得到路径值为36.727 9 m；自适应改进算法算法在进化9代得到路径值35.313 7 m，而本文的改进遗传算法克服了局部最优解的缺陷，在进化7代后趋于稳定，得到路径值为34.729 7 m。三种算法的仿真实验结果对比见表5。

图9 实验运动轨迹图

图10 算法收敛曲线图

图11 自适应改进算法仿真实验结果

表5 仿真实验结果对比

4 结 论

1) 本文以遗传算法为求解算法模型，提出一种融合模拟退火的改进算法。

2) 在双任务作业要求下，障碍物个数设置为31个和69个时，文中提出的算法较经典遗传算法的路径值分别缩短了约5%和9%，收敛速度分别提高了约44%和64%；对比自适应改进算法，路径值分别缩短了约5%和2%，收敛速度分别提高了约29%和33%。

3) 任务点增加到三个时，同样在障碍物个数为31个和69个中验证改进算法，对比遗传算法路径值分别缩短了约3%和5%，收敛速度分别提高了约67%和61%；与自适应改进算法作比较，路径值分别缩短了约3%和2%，收敛速度分别提高了约50%和22%。

4) 文中提出的融合模拟退火改进遗传算法适用于二维环境下的地面移动机器人路径规划，尚未扩展到无人机以及水下机器人的应用，可将多任务路径规划问题逐步拓展到如海洋探测、山林探险、自然灾害救灾等三维环境。