资源描述：
《基于遗传算法的机器人路径规划》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、4.3基于遗传算法的机器人路径规划4.3.1遗传算法简介[50][51]在1975年前后，美国Michigan大学JohnHHolland教授根据达尔文的适者生存的进化理论研宄出一种人工智能的方法一一遗传算法，这种算法以生物进化、遗传原理来设计算法的原理，在算法里面还添加Y统计理论学随机过程等数学方法，最终形成Y该算法一种独特的理论。遗传算法在求解时，先从一个初始群体的变量开始，依次求解出最佳解，最后得出满足预设的算法要求的迭代次数为最后结果。这种算法是迭代算法的一种。遗传算法是模拟大自然中生物生存的理念而产生的一种自然选择和群体遗传理论的査找式算法。在这个算法里面把每一个需要
2、求解决的问题尽量编码设计成“染色体”，多个染色体接着可以形成种群，在这个过程会出现选择、变异、交叉、复制等遗传操作。遗传算法初始设定时，首先随机产生一个初值即一个种群，然后依照算法的函数对种群内的个体进行处理评估，并产生相应的对环境适应度数值。接着算法会根据这些适应度值选择优秀的个体进行下一代衍生，然后把选出来的优秀进行变异、交叉处理。目前在机器人的路径设计里面遗传算法得到广泛的应用，而且应用范围不仅在单个机器人的行进里面，而是在多个机器人的合作里面也有广泛应用，并且都取得不错的效果。遗传算法是一种鲁棒性的应用于复杂系统优化的查询式算法，遗传算法与其他只能优化算法相比时，他有以
3、下特点：（1）把决策变量编码化，以一编码做算法处理的对象。（2）在算法里面以计算出的适应值为查询其他数据的信息。（3）遗传算法的查询过程从一个种群开始查询，而不从一个一个体开始。（4）遗传算法的查询是一种依据概率查询，而非确定值查遗传算法的基本流程如下图4.10所示随机产生初始种群按交叉概率执行交叉操作按变异概率执行变异操作图4.10基本遗传算法的流程图4.3.2利用遗传算法进行路径规划4.3.2.1规划空间的栅格法建模假设机器人工作空间为二维结构化空间，障碍物位置、大小己知，且在机器人运动过程中，障碍物的位置、大小均不发生变化。用尺寸相同的栅格对机器人二维工作空间进行划分，栅
4、格大小以机器人能在其内自由运动为限。若某一栅格尺寸范围内不含任何障碍物，则称此栅格为自由栅格，反之，称为障碍栅格。自由空问和障碍物均可表示成栅格块的集合。对划分好的栅格编序号，划分后的机器人工作空间如图4-11所示，图中阴影区为障碍物。栅格标识可采用下述两种方法：(1)直角坐标法。如图1所示，以栅格阵左上角为坐标原点，水平向右为*轴正方向，竖直向下为y轴正方向，每一栅格区问对应坐标轴上的一个单位长度。任一栅格均可用直角坐标(•¥，y)唯一标识。0123456789Y02345678图4.11规划空间及仿真结果之一⑵序号法。如图4.11所示，按从左到右，从上到下的顺序，从栅格阵左
5、上角第一个栅格开始，给每一个栅格一个序号P(从零开始计)，则序号P与栅格块一一对应。上述两种标识，互为映射关系：厂=x+10y(4-26)或（4-27）x=mod（p，10）y=int（p，10）(4-27)式中，mod表示取p/10之余数，int表禾取p/10之整数。在下述讨论中，机器人运动路径的表示将采用序号法，因为序号较直角坐标节省内存，表述简洁明了，并且便于遗传算子的操作。在对路径进行评价时，则将序号转换成坐标形式，因为坐标法更便于表示栅格之间的相对位置，计算路径长度及检验路径可行性［52］。4.3.2.2路径规划方法1.个体编码个体表示机器人在其工作空间中的一条运动路
6、径。编码即是把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法。编码方法可分为三大类：二进制编码方法、浮点数编码方法、符号编码方法。本文采用路径上的一系列栅格序号的顺序排列来表示机器人的一条可移动路径的遗传编码，机器人由起始位置S沿图中粗实线运动到终点位置G的路径，表示成一个个体，即：｛0,1，11，21，22,23,33,44,55,65,66,67,68,78,88,99｝。由于机器人运动路径可变，因此，个体长度不确定。计算机仿真研究中，用个体最大可能长度作为个体数组维数。1.初始种群产生初始种群是遗传算法进化计算的起点，它由一定数目(称种群大小)的个体
7、组成。为了保证遗传算法的全局最优性，初始种群应尽可能随机分布在搜索空间中毎一个区域。当对机器人工作空间划分的栅格数目较大吋，产生初始种群并非易事。若采用人工选择法，则费吋费力；若采用计算机随机生成法，则由于路径具有目的性、无障碍性，使得路径生成算法比较困难。为此，引入间断无障碍路径概念。定义在机器人运动起点S到终点G之间，用一系列随机选择、自由，但不一定连续的栅格序号连接S和G，称为一条间断无障碍路径。据上述定义，下面则为几条间断无障碍路径：｛0,99｝,｛0,20,45,75,87,99｝
