基于解空间优化的遗传算法的路径规划

王尧山 朱毅 卢军

摘要

针对传统遗传算法在移动机器人路径规划方面存在早熟收斂问题，对遗传算法生成的初始种群和解空间进行研究，提出了一种基于解空间优化的遗传算法最后通过仿真实验证明该优化算法在一定程度上能解决此问题。

【关键词】遗传算法 机器人 路径规划 解空间优化

1 引言

遗传算法具有良好的全局搜索能力，可以快速地将解空间中的全体解搜索出，而不会陷入局部最优解的快速下降陷阱;并且利用它的内在并行性，可以方便地进行分布式计算，加快求解速度。但是遗传算法的局部搜索能力较差，导致单纯的遗传算法比较费时，在进化后期搜索效率较低。在实际应用中，遗传算法容易产生早熟收敛的问题。采用何种选择方法既要使优良个体得以保留，又要维持群体的多样性，一直是遗传算法中较难解决的问题。

2 基于解空间优化的遗传算法

2.1 优化初始种群

遗传算法最终计算结果和达到收敛值的迭代次数，和初始生成的种群，有直接的关系。一般遗传算法的初始种群都是随机生成的，特定环境下，可以对初始种群中的个体，进行优化。

假设图1中ABCD四个导航点对应的x坐标分别为1、2、3、5。A-B-C是三个相邻的导航点，那么，在路径规划中，A-B-C就是一段最优子基因片段，D与A-B-C之间距离较远，不算到一起。如果在个体中出现了A-C-B这样的基因组合，那么这段基因组合，是最优基因组合的概率，就比较低了。对于这种本身可能是最优基因片段的，在生成随机路径的时候，把该片段当成一个整体进行操作。如果按照传统方法对其进行处理，那么会有12种不同的基因排列顺序，产生很多无效个体，而如果把A-B-C基因片段看成一个整体A'，那么就可以得到一个非常好的个体A'D。

引入一个新的模型：每一个基因由基因序号、入口点和出口点组成。

定义：基因融合之后产生的新点的序号叫基因序号。进入该基因的第一个点叫入口点，离开该基因的第一个点，叫出口点。比如A'点的模型构造为A'（A，C），D点生成新的D的模型构造为D'（D，D）。

在将原来的需要遍历的集合进行处理之后，我们可以很容易得到一个新的集合，在这个集合中，由于有出口点和入口点，所以，所有的路径集合都变成了矢量，而非以前的标量。在集合中任意两个点M'和N'，M'N'之间的距离为：，也就是M基因的出口点到N点入口点的距离，加上M基因本身的长度。相对的，N'M'之间的距离为：

2.2 寻找最优基因片段

（1）将所有点，按y坐标从小到大进行排序。

（2）从Y坐标最小的点y₁开始，判断有没有与其y坐标相同的点，如果没有，则将该点构造成一个新的点，入口点和出口点都是本身。如果有，则将这些点按x坐标的值，从小到大排列。

（3）从x值最小的点x₁开始，将其构造为一个新的点X₁'，入口点为x₁，出口点为x₁，再查询与其相邻点x₂的距离，如果这个距离小于阈值，则将出口点替换为x₂.然后再查询x₂下一个点x₃-若x₂和x₃之间的距离大于阈值，则X，'构造完成，将x₃构造成新点x₃'，重复之前步骤，终止条件为，x的下一个点查找为空。

（4）当下一个点查找为空时，对y₂执行相同操作，重复执行，直到y的霞一个点查找为空。

最优基因片段生成流程如图2。

3 仿真实验

对于改进后的遗传算法，主要是对其生成种群时，结合特定条件进行了改进，并且这种改进，只针对于有最优基因片段的情况，当没有最优基因片段时，还是按照传统方法进行计算。下面，假设导航点有29个，和出发点一起，共30个点，根据最优基因片段的多少，进行30点TSP问题模拟实验。

3.1 极端情况

此种情况假设所有的点均在一条直线上。数据融合以后，只剩下一个点A'，其距离为A'A'=A_outA_in+|A|'，路径为P1-P30，不需要查找就可直接得出最优结果。

而按照传统的TSP处理过程需要经过183次迭代后，才能得到最优路径。

显然，当处于极端情况时，优化后的算法比传统的算法有着极大的优势，所有点都集合成一个点，连查找过程都省略了。

3.2 理想情况

此种情况假设具有比较多的点可以融合成最优基因片段，但是不像极端状况那样可以将初始集合的点数降低到只有几个的程度。

用传统方法直接计算，在351次迭代之后，达到最小值84.其查找过程如图3传统TSP搜索过程所示。经过优化算法后的新点集合为：

Q1（P1，P3），Q2（P4，P6），Q3（P7，P9），Q4（P10，P12），Q5（P13，P15），Q6（P16，P18），Q7（P19，P21），Q8（P22，P24），Q9（P25，P27），Q10（P28，P30）在经历5次迭代之后，找到最小值840其搜索过程如图4优化TSP搜索过程所示。

4 结论

本文对遗传算法的种群初始化和解空间进行优化，基于此提出了一种最优基因片段生成方法。最后通过仿真实验模拟求解TSP问题，实验结果证明所提方法优于传统遗传算法，对解决室内移动机器人路径规划问题有一定帮助。

参考文献

[1]National Institute of Standards andTechnology，Valiated FIPS 140-1 andFIPS 140-2 Cryptographic Modules，2011.

[2]Holland J H.Adaptation in naturaland artificial systems.The Universityof Michigan Press，1975.

[3]李静.基于改进遗传算法的数据特征分类[J].现代电子技术，2018，14：1004-373.