基于改进遗传算法的路径规划问题相关研究综述∗

湛文静 李泳科

（南京理工大学计算机科学与工程学院 南京 210094）

1 引言

1949 年，世界上第一台遥控机器人诞生于美国橡树岭实验室，它被用于搬运和处理核材料。随着科技发展，越来越多的科学家致力于智能机器人的研究，智能机器人也在工业生产、医疗及物流搬运等领域得到广泛的应用。

机器人路径规划［1~5］是实现智能机器人自主工作的关键点之一，因此关于机器人路径规划的研究十分重要。机器人路径规划是指在特定的环境中为机器人规划出一条能够完全避开障碍物并且长度最短的路径。机器人路径规划分为建模、全局规划和局部优化三个部分，其常用的算法分为传统算法和智能算法两类。传统算法有A*算法［6~10］等，智能算法包括蚁群算法［11~16］、遗传算法［17~22］等。根据李少波等［23］的研究表明智能算法中遗传算法运用到路径规划中的研究最多、应用最广。遗传算法拥有全局搜索能力、鲁棒性高等优点，但是遗传算法也有易早熟、易陷入局部最优解等问题。因此，为了提高遗传算法解决路径规划问题的效率和求解质量，针对遗传算法的缺点，研究人员提出了很多改进方法。

本文将综合相关文献，首先介绍基本遗传算法在路径规划中的应用，再详细论述近年来关于如何针对遗传算法存在的问题对其进行改进并将改进的遗传算法应用到机器人路径规划中的研究。

2 遗传算法

2.1 遗传算法介绍

美国的John holland 于20 世纪70 年代提出了遗传算法。遗传算法是根据达尔文生物进化论“物竞天择，适者生存”以及生物遗传机制提出的。地球上的生物通过自然选择、染色体交叉、基因变异不断进化，以适应环境的改变。遗传算法模拟了生物进化的这一过程，把待求解问题的初始解映射为“染色体”，使其经过选择、交叉、变异的过程从而进化为最优解。遗传算法包括初始化种群、个体评价、选择运算、交叉运算、变异运算以及终止条件判断六个过程。图1为遗传算法的运行步骤。

图1 遗传算法运行步骤

2.2 遗传算法求解路径规划问题

机器人路径规划的最终目的是得到一条无碰撞的最短路径。该路径通常是由多个节点组成，包括机器人起始点、目的点及中间节点，将这些节点连接起来即为求解的路径。基于基本遗传算法的路径规划过程：1）建立环境模型，常用的建模方式是栅格法建模。2）初始化种群，根据建模特点随机产生多条从起始点到目的点的初始路径。3）个体评价，首先根据求解问题的要求，定义适应度函数，通常是以最短路径为目标。以用栅格法建立环境模型为例，适应度函数如式（1）所示，路径越短，对应的适应度越高，被选择的概率越大。适应度函数的设置对整个求解过程至关重要，它决定了最终求解出的路径性质。根据对求解路径最短、耗时最少等不同的要求，修改并优化适应度函数才能得到符合要求的解。4）选择运算，这个过程一般采用基于概率的轮盘赌运算，概率公式如式（2）所示。路径适应度越高，被选择的概率越大。此过程的目的是为了从种群中挑选并保留更符合求解要求的路径。5）交叉及变异运算，此过程模拟生物染色体进化中的交叉及变异过程，进行交叉、变异运算的路径称为父代路径，经过交叉、变异运算后产生的路径称为子代路径。由基本遗传算法解决路径规划问题时，通常使用的交叉运算和变异运算为对种群中的路径分别按照一定的概率进行单点交叉和单点变异产生子代路径。6）终止条件判断，基于基本遗传算法的路径规划会重复3）~5）这几个步骤直至达到终止条件，终止条件通常可以设置为循环次数限制或运行时长，也可根据求解问题复杂性自行设置。

式（1）中：f为适应度函数；N为建立的栅格总数；D为路径总长度。

式（2）中：Pi为个体概率；fi为个体适应度。

3 改进遗传算法在路径规划中的应用

由于基本遗传算法存在易陷入局部最优解、收敛速度慢等问题，因此近年来许多学者提出了各种改进的遗传算法用于解决这些问题以求得符合要求的最优路径。基本遗传算法有六个步骤，改进的遗传算法是在其中几个步骤的基础上进行改进与优化，因此，接下来将阐述对于每一个步骤，相关文献是如何进行改进的。

3.1 初始化种群

在使用遗传算法求解问题的时候，第一步就是初始化种群，由于算法后续过程均以初始种群为基础进行运算，因此这个过程产生的初始数据在一定程度上影响了整体收敛速度以及最终结果的优劣。

使用基本遗传算法求解路径规划问题时，在初始化种群这一步采用的是随机选取初始路径的方式。由于初始路径是随机选择的，因此具有一定的盲目性，无法保证初始路径的质量。比如，若产生的初始路径以路径长度较长、路径出现间断以及会经过障碍物的不可行路径为多数，则算法收敛速度会更慢、效率降低甚至最后无法通过算法产生优质求解路径。因此很多学者关于如何改进初始种群生成机制以控制初始数据的质量做了研究。

刘志海等［24］提出了一种可以避免产生不可行初始路径的方法。首先为机器人活动环境建立栅格模型，并标记出可行栅格和不可行栅格。然后从起点所在行、目的点所在行之间的每一行中随机选择一个可行栅格作为中间节点，这些中间节点与起点、目的点一起组成初步初始路径。接下来判断初步初始路径中的各个节点是否相邻，若不相邻则将两点间的中点插入路径直致路径中的每一点均相邻。最后，为简化路径，需要删除路径中的重复节点以及两节点之间的路段。简化后的路径即为产生的初始路径。通过这种改进的方法在一定程度上保证了初始路径的可行性，保证了初始路径的质量，有效地提高了算法的收敛速度。

易欣等［25］提出一种采用随机Dijkstra算法创建初始种群的方法。第一步是构建机器人可行驶路径图。首先将机器人的活动区域用相同大小的网格组成的网格图表示，之后将有障碍物的网格从网格图中删除，通过连接每个网格点相邻四个点的连接方式连接网格图中剩余的网格，并且以连接两点的距离作为其边的权重构建出道路图，最后将起始点和目的点以相同的连接方式加入道路图完成机器人可行驶路径图。第二步以机器人可行驶路径图为基础，使用Dilip 等［26］提到的Dijkstra 算法产生初始路径。采用这种改进初始化种群的方式能够有效地避免产生不可行初始路径，同时由于使用Dijkstra 算法选择初始路径，在一定程度上能够筛选出长度较短的初始路径，提高了初始种群的整体质量，从而有效地提高了求解路径的质量并缓解了遗传算法收敛速度慢的问题。

3.2 设置适应度函数

适应度函数也称评价函数，是用于评价种群中个体优劣的指标。采用基本遗传算法解决智能机器人路径规划问题时通常仅把路径最短作为设置适应度函数的标准，即路径越短，对应的适应度越高。但是在实际生活中，道路情况复杂，不仅会有障碍物，还有弯道、十字路口、拥塞路段等复杂路况。若在为机器人规划路径的过程中仅把路径最短作为最终求解路径的标准，则较大概率会得到不够平滑和有不自然转角的路径，不仅不符合正常行驶习惯，而且会因为大幅转弯浪费时间、降低效率、增加与障碍区碰撞的风险。因此，根据需要解决的具体问题，应该综合考虑路径长短、时间要求、道路路况等方面设置相应的适应度函数。

王功亮等［27］在适应度函数中添加转弯角度控制因子，将转弯角度和路径最短同时作为选择路径的标准。首先按照式（3）计算每条路径中相互节点之间的转动角度值。然后按照式（4）计算每条路径的适应度。按照式（4）所示适应度函数评估路径，路径越短、转弯角度越小，其适应度越大。该适应度函数综合考虑了路径长度和转弯角度的影响，通过减少机器人行驶过程中大幅转弯的次数有效的降低了物理消耗时间，提高了算法效率，得到更为优质的求解路径。

式（3）中：R为转弯角度因子；γ为转弯角度；c为转动角度权重系数。

孙波等［28］为了使规划出的路径更符合实际行驶习惯，全面改进了基本遗传算法的适应度函数，综合考虑从起始点到目的点的行驶时间、路径曲折度、路径繁忙度和车辆负重等多个指标，提高机器人行驶安全性。如式（5）、（6）所示。在这种改进下，机器人的行驶速度根据路况发生相应的改变，机器人从路径起点到目的点的行驶时间越短，该路径的适应度越高。当某段路径有较大弯曲、拥塞情况严重并且机器人负重较多时，机器人会降低其行驶速度以避免与移动障碍物发生碰撞，反之，机器人会增加行驶速度以便更快到达目的地。通过在适应度函数中加入以上评价指标，不仅控制了机器人行驶时间并且可以有效的降低机器人行驶过程中与移动障碍物发生碰撞的概率，使其行驶的过程更符合实际习惯。

式（5）中：V为机器人最终行驶速度；Vi为机器人正常行驶速度；μ为机器人的负重系数；α为路径曲折度等级；β为路径繁忙度等级。

式（6）中：Mt为个体；Dij为个体中节点i、j之间路段的路径长度；μij为机器人在该路段中的负重系数；αij为该路段的曲折度等级；βij为该路段的繁忙度等级。

Wang Rui 等［29］修改自适应函数，综合考虑路径长度、障碍物及路径连续性几点，旨在求解出一条无碰撞、不间断的最短路径。其适应度函数如式（7）所示，路径越符合求解要求，其适应度越小。通过改进适应度函数，提高了种群的质量，能够生成一条连续且无碰撞的路径。

式（7）中：Wd、Wp、Wc分别为路径长度、碰撞惩罚函数、路径间断函数的权重；d(p)表示路径p的长度；pe(p)表示路径p的碰撞惩罚函数，当路径与障碍物的中心点间距越小时越容易发生碰撞；c(p)表示路径p的间断函数，用于衡量路径p是否连续。

3.3 选择运算

在基本遗传算法中采用的传统选择运算为轮盘赌的方式。选择运算模拟了自然界“物竞天择，适者生存”的进化法则，越适应环境的个体越容易存活。将此法则应用到求解路径规划问题，就能筛选出更符合求解要求的路径。进行选择运算首先需要依据概率公式，通过由适应度函数得出的个体适应度计算出每个个体被选择的概率，再根据轮盘赌的规则随机选择个体。通常情况下，路径越符合求解要求，适应度越高，被选择的概率越大。依据轮盘赌的选择规则，保留下来的路径大多数都是种群中更契合要求、更相似的路径，虽然保证了算法的效率，但是也让保留下来的个体失去多样性，容易给遗传算法造成“早熟”的现象［30］，陷入局部最优。

为了提高种群的差异性，缓解遗传算法的“早熟”现象，孙波等［28］引用模拟退火算法（Simulated Annealing，SA）进行选择运算。模拟退火算法来源于固体退火原理，由N.Metropolis 等于1953 年提出。根据模拟退火算法的运作原理，该算法在当前解的基础上进行变化产生一个比当前解更不符合要求、更差的解，使计算有可能跳出局部最优。根据孙波等［28］的研究，改进的选择算法为首先使用模拟退火算法产生路径作为新解，然后使用路径的适应度值计算新解的接收概率，接收概率计算如式（8）所示，新解的适应度越低，越容易被接受。通过模拟退换算法进行选择运算为种群添加较差的解能够在一定程度上使遗传算法跳出局部最优，有效地缓解“早熟”现象。但是由于在种群中加入了较差的解会影响种群质量，因此孙波等人对新产生含有较差路径的种群采用精英保留策略，即复制种群中的优秀个体，被复制的优秀个体不用参与交叉、变异操作直接保留至下一代，同时按照比例淘汰种群中的较差个体以保证种群整体质量。通过精英保留策略不仅提高了种群的多样性缓解“早熟”现象，同时控制了种群中较差路径的数量，维系了种群的质量。

式（8）中：Pk为新解的接收概率；m、n分别为原始解和新解；f(m)、f(n)分别为原始解和新解的适应度；T为系统当前温度。

3.4 交叉、变异运算

遗传算法中的交叉、变异运算模拟了自然界生物繁衍遗传的过程。在自然界中，父母生物通过繁衍产生子代胚胎，在这个过程中，子代胚胎会继承分别来自父母的部分基因，由这些基因组成了子代胚胎的染色体。子代胚胎经过发育生长为生物，在成长过程中，子代胚胎的部分基因会随着环境等原因发生改变。交叉、变异运算正是模拟生物繁衍的以上两个过程为算法产生新种群。合理地进行交叉、变异运算可以提高种群的差异性、增加种群的多样性，从而缓解遗传算法易“早熟”的现象，但由于基本遗传算法使用的是单点交叉，不仅容易形成环路同时容易引发种群退化现象，导致算法对解空间重复搜索，降低算法效率。因此，近年来许多学者进行了相关研究，对基本的交叉、变异算法进行改进以达到优化遗传算法的目的。

宋启松等［31］使用改进单点交叉方式和多向变异方式以增加种群多样性。改进的单点交叉运算分为两种情况：1）若父代两条染色体中没有相同点，则随机选择一个基因作为交叉点，将父代染色体交叉点后的部分进行交换产生子代染色体。2）若父代染色体中有相同点，则选择相同点作为交叉点，交换父代染色体交叉点后的部分，产生子代。进行改进的多向变异首先设置变异概率，依据变异概率选择需要进行变异的个体作为父代，在父代中随机选择一点作为变异点，其变异操作也分为两种情况：1）以变异点为起点、路径起点为终点进行逆向搜索。即重新生成一段由变异点到路径起点的路段一，将路段一与变异点到目的点的路段组合形成新路径。2）以目的点为起点、变异点为终点进行逆向搜索。即重新生成一段由目的点到变异点的路段二，将路段二与路径起点到变异点的路段组合形成新路径。最后比较新路径与父代路径的适应度，将适应度高的路径最为子代路径保留下来。宋启松等［31］通过使用改进的交叉、遗传运算，提高了种群的多样性、缓解了遗传算法的“早熟”现象，并且在一定程度上避免了种群退化的问题。

在遗传算法进行交叉、变异运算的过程中，交叉、变异概率有着至关重要的作用。交叉、变异的概率太小，不利于种群产生新个体易使算法陷入局部最优，概率太大容易破坏种群的优良基因影响种群质量。为了保证种群质量及避免算法陷入局部最优，徐力等［32］使用新的自适应策略对遗传算法交叉、变异的概率进行调整。通过引入自适应交叉概率和自适应变异概率，在算法运行的不同阶段自主调整交叉概率、变异概率以提高种群多样性、维系种群质量。交叉概率和变异概率的计算如式（9）、（10）所示。交叉概率和变异概率是依据遗传算法各个阶段的不同特性设置的。在算法运行前期，种群内各个路径差别较大，其适应度相对而言比较分散，此时为了保留种群的优良基因、保证种群的质量应该适当降低交叉和变异的概率。而到了算法运行后期，种群中的路径趋于一致，各路径适应度分布也比较集中，此时为提高种群的多样性，应适当增加交叉、变异概率为种群添加新个体，从而有效地避免算法陷入局部最优解。

式（9）中：Pc1、Pc2分别为交叉概率的最大值和最小值；fc为进行交叉运算个体的适应度；favg、fmax分别为现阶段种群平均适应度和最大适应度。

式（10）中：Pm1、Pm2分别为变异概率的最大值和最小值；fm为进行变异运算个体的适应度。

4 结语

随着时代的发展和科技的进步，关于如何运用遗传算法解决机器人路径规划这一问题经过学者们的研究已经有所成果。但是由于遗传算法具有收敛速度慢、易“早熟”、易陷入局部最优解等问题，因此使用传统的遗传算法解决路径规划问题往往得不到质量较好的解。为解决使用传统遗传算法求解路径规划问题时存在的问题，近年来许多学者进行了相关研究并取得了一定的成果，通过改进初始种群的生成方式，加快了算法的收敛速度，提高算法的效率；通过设置更为合理的适应度函数，有效地降低与障碍物发生碰撞的概率并且使得规划出的路径更符合实际生活习惯；通过改进选择、交叉、变异运算，在保证种群质量的前提下成功地提高了种群的多样性，有效地缓解了遗传算法的“早熟现象”，避免陷入局部最优。

值得注意的是改进遗传算法也可以在同一次运算中同时改进多个步骤以便更为高效地完成求解得到优质路径。Zhang Yi 等［33］综合路径最短和避免碰撞两个要求改进自适应函数。然后在选择操作中，结合轮盘赌和精英选择策略。之后优化交叉、变异算法，并为遗传算法添加插入算子及删除算子，目的是通过为间断路径添加节点的方式使路径连续并避免出现环路。

虽然当前取得部分成果用于处理传统遗传算法的弊端，但是如何进一步提高算法的效率和性能将理论和实际应用相结合依旧是学者们研究的重点和热点。