彭 丽，洪 亮

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



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

彭 丽，洪 亮

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

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

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

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

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