“机器人”路径改进型单亲遗传算法规划及其仿真

彭 丽，洪 亮

(吉首大学信息科学与工程学院，湖南 吉首 416000)



“机器人”路径改进型单亲遗传算法规划及其仿真

彭 丽，洪 亮

(吉首大学信息科学与工程学院，湖南 吉首 416000)

在中国机器人大赛“机器人游中国”比赛项目的路径规划基础上，为克服遗传算法在有约束组合优化问题中计算效率不高的问题，提出了改进的单亲遗传算法.该算法在传统单亲遗传算法的计算步骤中，引入了交换算子、提前算子和修复算子，较大程度地提高了单亲遗传算法的搜索效率.Matlab仿真试验表明，改进的单亲遗传算法计算效率和路径规划能力得到大幅度提高.

单亲遗传算法；机器人；路径规划

“机器人游中国”比赛项目包含16个景点，其景点位置参照地图放置，每个景点对应不同的分值，分值的高低由到达该景点的难易程度决定.比赛要求“机器人”在60 s时间内游历至少1个景点后返回出发点，得分多者获胜[1].要想在“机器人游中国”比赛中取得良好的成绩，机器人的路径规划能力是比赛获胜的关键.

遗传算法是一种常用的路径规划方法，适合解决无约束的函数优化问题.然而，对于“机器人游中国”路径规划这样有约束的组合优化问题，其计算效率不高.文献[2]中提出了单亲遗传算法概念，其遗传操作中没有交叉算子，所有操作只作用于单个染色体，与其他染色体没有关系.序号编码的遗传算法采用交叉操作，出现基因重复或者基因缺失的现象[3-4].单亲遗传算法正好弥补这一缺陷，在处理复杂的工程优化问题时，单亲遗传算法能快捷地处理约束条件.

1 基于路径规划的遗传算法

1.1 环境信息的表示

图1 “机器人游中国”竞赛地图

组委会提供的“机器人游中国”竞赛地图如图1所示.对竞赛地图中景点之间的距离进行量化，制作景点之间的计算距离表[1].

1.2 路径编码

路径编码影响遗传算法的计算性能.“机器人游中国”比赛项目的路径规划问题将采用序列号进行编码，先对每个景点进行编号，之后对编号进行无重复随机排列，其个体即为移动机器人从开始出发并游完某些景点再回到出发点的一条路径.

1.3 目标函数和适应度函数

根据组委会的比赛规则可得到参赛机器人得分公式[5]，该公式即为路径优化问题的目标函数.算法的约束条件为比赛时间60 s，参赛“机器人”的目的是在这60 s内得到尽量多的分值，每个个体的适应度大小就是所得到的分值.得分公式既是目标函数，也是个体适应度函数.适应度越高，得分越高.高分的个体将留下来继续进行迭代，低分的个体则被淘汰.

2 改进的单亲遗传算法

2.1 交换算子

基因交换算子是基因之间进行位置交换的一种遗传操作.它有3种交换方式：基因片段的内部交换(图2)，内部的基因“5”和基因“7”进行位置交换；基因片段的外部交换(图3)，基因片段“5，6，7”和基因“c4”进行位置交换；基因片段的整体交换(图4)，基因片段“5，6，7”和基因片段“c1，c2，c3，c4”进行整体交换.2.2 提前算子

提前算子先确定个体中某些被提前的优良基因片段，并对其进行保护，最后进行适当的提前操作(图5).因此，提前算子有保护和提前2个操作步骤.提前算子使优良基因被利用起来，能更好地提高计算效率.

2.3 修复算子

某些个体经历了很多操作后，可能变成不可行解，修复算子能对这样的个体进行修复操作，使被淘汰个体重新回到种群中，从而大大提高计算效率.

3 Matlab仿真测试

3.1 遗传算法仿真

图6 旅行路径1

遗传算法的初始种群一般是由计算机随机生成的.针对“机器人游中国”比赛项目，计算机随机生成的初始种群将出现某些个体中有重复序号现象，这些个体将直接成为不可行解.因此，初始群体只能由所有序号进行无重复随机排列来产生，种群大小一般取20个左右.运用比例选择算子进行选择运算时，采用先“繁殖”后选择的方式进行，这种方式计算效率更高.遗传算子选用比例选择算子和CX交叉算子[5]进行变异操作，交叉概率可以取0.7～0.9，变异概率一般取0.1左右.采用传统遗传算法进行多次仿真的最优结果见图6.由图6可知，最佳“机器人”共经过了12个景点，旅途中花费时间累计54 s，得分271分.

改变初始种群，加入文献[1]中由启发式路径规划算法得到的最优解(291分)，遗传算法的计算步骤、终止条件和遗传操作都不变.再运行Matlab仿真，仿真结果表明，经过多次迭代，得到的最好结果还是由启发式路径规划算法得到的最优解(291分)，即没能产生更优秀的个体，没有完成路径规划问题的优化.

3.2 单亲遗传算法仿真

图7 旅行路径2

采用无重复序号随机排列方式产生初始种群，并使用新构造的3种遗传算子更新种群中的个体.在进行交换操作时，取基因整体交换概率为0.1，基因内部交换和外部交换概率为0.45，即每次迭代时只使用3种交换方式中的一种.由于基因整体交换对提高搜索效率意义不大，因此基因整体交换概率取得比较小.提前算子针对优良基因片段进行保护并适当提前.经多次实验，基因片段提前概率取0.7左右比较合适.需要修复的染色体无法预判，为保险起见取修复概率为0.99，迭代次数G=1 000.这样对每个个体进行修复操作时，及早迭代产生优良个体，从而提高计算效率.

采用改进的单亲遗传算法进行多次仿真的最优结果如图7所示.由图7可知，游历11个景点共用时58 s，得分301分.同样对初始种群进行变换，在原来的初始种群中加入优良个体，单亲遗传算法的其他条件都不变，对新初始种群的改进单亲遗传算法进行仿真实验，得到最优解的旅行路径和没有改变初始种群时所得到的旅行路径完全相同(图7)，得分也是301分.当初始种群中包含优良个体时，迭代次数大大减少，计算时间缩短了，也就在一定程度上提高了计算效率.

3.3 仿真结果分析

在无重复序号随机排列所产生的初始种群中，改进的单亲遗传算法和传统遗传算法的仿真计算结果分别为301分和271分；当初始种群中加入优良个体时，改进的单亲遗传算法和遗传算法的仿真结果分别为301分和291分.仿真结果表明：传统的遗传算法在解决路径规划问题时，虽能发挥其作用，但效果并不理想.究其原因是，常规变异算子和交叉算子不适合序号编码的传统遗传算法，且计算效率很低，经过多次迭代才能搜索到一个得分无明显优势的可行解.因此，传统遗传算法所得最优解(非全局最优解)在比赛中没有竞争力.当初始群体中有较好的可行解时，传统遗传算法优化作用不能凸现出来，而改进的单亲遗传算法不论在初始群体中有无优良个体，都能通过各种遗传操作搜索到问题的最优解.

4 结语

针对“机器人游中国”的实际路径规划问题提出的改进单亲遗传算法，不但继承了传统遗传算法的优良性能，而且有其自身独特的高效搜索能力.构造的3种遗传算子能提高搜索效率，且算法的所有遗传操作只针对一个个体，操作简单，它能搜索到最优解，从而达到路径规划的目的.Matlab仿真结果验证了改进的单亲遗传算法针对“机器人游中国”所设计的遗传算子解决路径规划问题的有效性和合理性.

[1] 彭 丽，李茂军.“机器人游中国”路径优化方法[J].工业控制计算机，2012，25(12):1-3.

[2] 李茂军.单亲遗传算法理论及应用[D].长沙：湖南大学电气与信息工程学院,2002:13-23.

[3] 彭 丽.基于遗传算法的移动机器人路径规划[D].长沙：长沙理工大学电气与信息工程学院,2013:25-37.

[4] 姜明洋.基于遗传算法的移动机器人路径规划方法的研究[D].沈阳：沈阳理工大学信息学院，2008：6-42.

[5] TIAN Lianfang，COLLINS C.An Effective Robot Trajectory Planning Method Using a Genetic Algorithm[J].Mechatronics,2004，14(5)：455-470.

(责任编辑 陈炳权)

Robot Path Planning Based on Improved Partheno-Genetic Algorithm

PENG Li,HONG Liang

(College of Information Science and Engineering,Jishou University,Jishou 416000,Hunan China)

The improved partheno-genetic algorithm is proposed based on the path planning in the Chinese Robot Competition “Robot Tourism in China”,which is aimed at the problem of low computational efficiency of constrained combinational optimization.Three genetic operators of partheno-genetic algorithm-commutating operator,operator in advance,and repair operator,were established without changing the calculation steps of traditional partheno-genetic algorithm;as a result,the search efficiency of partheno-genetic algorithm is largely improved.Simulation experiment shows that compared with genetic algorithm，the proposed improved partheno-genetic algorithm has greatly increased computation efficiency and path planning ability.

partheno-genetic algorithm；robot；path planning

1007-2985(2015)04-0037-03

彭 丽(1987—)，女，湖南益阳人，吉首大学信息科学与工程学院教师，硕士，主要从事智能控制和机器人研究.

TP249

A

10.3969/j.issn.1007-2985.2015.04.010