二进制粒子群算法融合遗传算法路径规划方法

夏梓尧

（安徽理工大学电气与信息工程学院，淮南 232001）

0 引言

路径规划是移动机器人领域的一个研究热点，是实现移动机器人自主导航的关键技术。随着计算机智能技术的发展，机器学习和群体智能优化算法被认为是未来比较适合在复杂环境下进行机器人避障和路径规划的学习方法［1-4］。目前，国内外的许多学者在移动机器人的路径规划领域做了大量的研究工作，并取得了很多成果。文献［5］提出改进的自适应蚁群算法（IAACO），引入启发式信息自适应调节因子和自适应信息素挥发因子提高机器人路径规划的实时性和安全性。文献［6］设计了自适应交叉算子和变异算子，提高规划效果。文献［7］将改进的二进制粒子群算法应用于路径规划。

提出了一种改进的二进制粒子群算法融合自适应遗传算法（PSO-GA）应用于栅格地图路径规划。该算法以粒子群算法（PSO）为主体引入遗传算法（GA）的操作，并采用自适应性的交叉概率，避免了早熟收敛和局部最优的问题，提高了算法适应性。计算结果表明，该算法不仅能够在复杂栅格环境下迅速地得到最优解，而且得到的路径长度更短，收敛更快，从而提高路径规划的效率。

1 栅格环境建模

栅格法［8］是路径规划中常用的环境地图建模方法，该方法简单有效，适应性强。本文采用栅格法建立移动机器人的工作环境时，分别用0、1表示自由区域和障碍物，每一个栅格有唯一序号与之对应，建立20×20的栅格环境作为移动机器人的运动场所，并设定左上角序号为1的栅格作为起点，右下角序号为400的栅格作为终点。

2 二进制粒子群算法

粒子群算法源于对鸟群捕食行为的研究，搜索最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。每个优化问题的潜在解都是搜索空间中的一只鸟，即粒子［9］。所有粒子都有适应度值及包含方向和距离的初速度，适应度值即为路径长度，公式（1）如下：

粒子群算法首先在给定的解空间中生成随机初始化粒子群，每个粒子被赋予初始位置与初始速度，然后通过迭代寻优，通过个体极值和群体极值更新位置与速度。在此基础上，标准粒子群算法引入了惯性权重ω概念，速度V和位置X更新见公式（2）：

其中，c1=0.8为认知系数；c2=0.9为社会学习系数；k为当前迭代次数；r1、r2为［0，1］随机数。对ω进行动态调整，规划初期，ω值较大，全局收敛能力较强；搜索后期，ω值较小，局部收敛能力较强，以此权衡全局和局部搜索能力。目前，采用较多的是线性递减权值策略，其表达式（3）如下：

其中，Tmax表示最大迭代次数；ωmin=0.4，ωmax=0.9；t表示当前迭代次数。

标准粒子群算法局限于连续区间中运用，如果将连续粒子运动空间映射到离散问题空间，并适当修改算法，在计算上仍保留经典粒子群算法速度位置更新运算规则，从而构成二进制粒子群算法［10］。算法通过运用sigmoid函数实现实数与二进制数的映射，粒子在状态空间的取值和变化只限于0和1。

二进制粒子群算法中速度更新公式依然保持不变，但是个体极值和群体极值只在［0，1］内取值，位置更新见公式（4），其中，r为［0，1］中随机数。

3 二进制粒子群算法与遗传算法融合

遗传算法是一种仿生学算法，模仿自然界中生物演化的自然过程，父代经过自然选择把优秀的、更适应环境的遗传信息传递给子代，同时保持一定变异概率，来不断丰富种群整体的基因库。遗传算法的操作包括：

（1）选择操作：以适应度函数值为参照，从第k代种群中选择适应度高的优良个体，将其遗传信息传递给下一代，即第k+1代个体。这里引入动态调整的选择概率，以增强其自适应性。概率的数学表达如式（5）所示：

其中，个体i的适应度为fiti，fitmax为当次迭代最大适应度值，fitaverage为当次迭代平均适应度值。

（2）交叉操作：将之前从种群中选择出来的个体进行随机搭配，通过信息交互提高算法整体的搜索效率，同时避免各项参数过早收敛陷入局部最优。首先选择一对备选个体；然后根据位串长度n，随机选取［1，n-1］中的一个整数作为交叉位置；最后成对个体在交叉位置处交换各自的部分信息，进而产生一对全新的个体。

（3）变异操作：对于种群中的全部个体，以变异概率Pm选择突变个体，随机改变个体信息的值。这里采用运算简便的二进制变异，即0、1变换。

运用二进制粒子群算法融合改进自适应性的遗传算法进行路径规划，两种算法的融合综合了两者的优势，使算法收敛性更好。融合的策略是通过在粒子群算法中引入遗传算法的交叉操作，并用二进制变异算子进行算法的改进，从而构成混合算法。该算法主要有如下特点：

（1）运用二进制粒子群算法结合遗传算法，引入的选择、交叉、变异操作，通过二进制编码降低计算复杂度，增强算法跳出局部最优解的能力。

（2）在遗传算法中引入自适应选择概率，并根据迭代次数自适应调整惯性权重，避免了传统粒子群算法容易早熟收敛陷入局部最优解的问题，提高算法的自适应性。

融合算法流程图如图1所示，运算步骤如下：

（1）初始化粒子群参数，包括群体规模N，每个粒子的适应度值fitness，位置和速度。

（2）运用sigmoid函数进行二进制编码。

（3）迭代更新粒子的适应度值，位置和速度。

（4）对每个粒子，用它的适应度值和个体极值Pbest比较。如 果fitness＜Pbest，则用fitness替 换掉Pbest；同理，更新全局极值Gbest。

（5）选择适应度较高的个体进行复制，然后按照交叉概率选择个体执行交叉，按变异概率执行变异，并形成新的种群。

（6）判断算法终止条件是否满足：如果是，则结束算法并输出优化结果；否则返回步骤（3）。

4 仿真结果与分析

为了验证不同算法应用于路径规划的效果，利用Matlab软件对路径规划过程进行仿真模拟，操作系统为Win10。在20×20的栅格地图区域范围内，分别采用粒子群算法（PSO）、遗传算法（GA）、粒子群-遗传融合算法（PSO-GA）进行全局路径规划。

4.1 简单环境仿真

为验证粒子群-遗传算法的优势，首先在简单环境下利用该算法进行路径规划。设定粒子种群规模为30，最大迭代次数为100次，变异概率Pm=0.1，c1=0.8，c2=0.9。计算结果如图2所示。

图2（a）是粒子群算法规划结果，路径长度30.6569，规划结果整体较为平滑，转角共有7处，在三种算法中最少，基本符合最优解的预期；图2（b）是粒子群算法结合遗传算法规划结果，路径长度30.6569，同样符合最优解预期，但是转角稍多，有9处；图2（c）是遗传算法规划最短路径，转角9处，部分转直角不够平滑，路径长度31.8995，在三种算法中最长，仍有继续优化空间。

综合三种优化路径形状以及图2（d）三种算法进化曲线的对比可以看出，融合算法相较于单一算法，适应度函数值（即最短路径长度）曲线大部分区间位于曲线图底部，起点更低，收敛更快，最终结果较好。但此处融合算法的比较优势并不突出，粒子群算法规划路径长度与融合算法的相同，且整体更加平滑，转角更少。

4.2 复杂环境仿真

进一步把该融合算法应用于复杂环境，分析该算法的适应情况。环境的复杂性主要是由环境中障碍物的比例和密度来定义的。这里种群规模比简单环境仿真小，设定粒子种群规模为10，最大迭代次数为500次，变异概率Pm=0.1，c1=0.8，c2=0.9。仿真结果如图3所示。

图3（a）为遗传算法最优路径，路径前半段迂回较多，转角15处，且存在尖锐折角，路径长度34.3848，在三种算法中路径最长，仍然存在较大优化空间；图3（b）为粒子群算法规划结果，路径长度32.6274，比遗传算法略短，多数转角为钝角，但路径整体较为曲折，转角共16处；图3（c）为融合算法规划结果，路径长度30.6274，在三种算法中结果最好，基本符合最优路径的预期，只有接近起点处的直角转弯仍有局部优化空间，而且路径更为平滑，转角仅有11处。

从图3（d）的适应度值曲线比较中可以明显看到，融合算法的曲线全程位于折线图底端，且起点更低，收敛更快，最短路径长度更小，由此验证了该融合算法在复杂环境中适应性更好，可以获得更好的最优解，路径也相对较为平滑，转角更少，有较强的比较优势。

5 结语

针对传统单一算法在全局静态环境路径规划方面的不足，运用融合算法避免单一算法容易早熟收敛陷入局部最优解的问题。通过融合算法、粒子群算法和遗传算法分别在简单和复杂环境中的仿真实验对比分析，验证了融合算法在保证最优解质量的前提下，具有更快的收敛速度，更好缓解早熟收敛，缩短全局路径总长。