下载后可任意编辑4.3 基于遗传算法的机器人路径规划4.3.1 遗传算法简介[50] [51]在 1975 年前后，美国 Michigan 大学 John H Holland 教授根据达尔文的适者生存的进化理论讨论出一种人工智能的方法——遗传算法，这种算法以生物进化、遗传原理来设计算法的原理，在算法里面还添加了统计理论学随机过程等数学方法，最终形成了该算法一种独特的理论。遗传算法在求解时，先从一个初始群体的变量开始，依次求解出最佳解，最后得出满足预设的算法要求的迭代次数为最后结果。这种算法是迭代算法的一种。遗传算法是模拟大自然中生物生存的理念而产生的一种自然选择和群体遗传理论的查找式算法。在这个算法里面把每一个需要求解决的问题尽量编码设计成“染色体”，多个染色体接着可以形成种群，在这个过程会出现选择、变异、交叉、复制等遗传操作。遗传算法初始设定时，首先随机产生一个初值即一个种群，然后依照算法的函数对种群内的个体进行处理评估，并产生相应的对环境适应度数值。接着算法会根据这些适应度值选择优秀的个体进行下一代衍生，然后把选出来的优秀进行变异、交叉处理。目前在机器人的路径设计里面遗传算法得到广泛的应用，而且应用范围不仅在单个机器人的行进里面，而是在多个机器人的合作里面也有广泛应用，并且都取得不错的效果。遗传算法是一种鲁棒性的应用于复杂系统优化的查询式算法，遗传算法与其他只能优化算法相比时，他有以下特点：（1）把决策变量编码化，以一编码做算法处理的对象。（2）在算法里面以计算出的适应值为查询其他数据的信息。（3）遗传算法的查询过程从一个种群开始查询，而不从一个一个体开始。（4）遗传算法的查询是一种依据概率查询，而非确定值查询。。遗传算法的基本流程如下图 4.10 所示：随机产生初始种群计算各个体适应值执行复制操作按交叉概率执行交叉操作按变异概率执行变异操作输出搜索结果算法收敛准则满足否是否下载后可任意编辑图 4.10 基本遗传算法的流程图4.3.2 利用遗传算法进行路径规划4.3.2.1 规划空间的栅格法建模假设机器人工作空间为二维结构化空间, 障碍物位置、大小已知, 且在机器人运动过程中, 障碍物的位置、大小均不发生变化。用尺寸相同的栅格对机器人二维工作空间进行划分, 栅格大小以机器人能在其内自由运动为限。若某一栅格尺寸范围内不含任何障碍物, 则称此栅格为自由栅格, 反之, 称为障碍栅格。自由空间和障碍物均可表示成栅格块的集合。对划分好的栅...
