《智能机器人创新设计》 课件 第14章 智能算法综合比较

第14章智能算法综合比较智慧物流系统：从设计到实现教学内容CONTENTS1单路径规划算法效果比较2任务分配算法效果比较3

章节目标掌握机器人路径规划三种算法的原理与结论；掌握三种任务分配算法的原理与结论。4单路径规划算法的总结路径规划是规划出一条连接起点到终点的序列点或者曲线。单机器人路径规划是为单个机器人规划出一条从起点到终点的通行路线。1单路径规划算法效果比较本书前章共讲述了三种单路径规划的方法：广度优先搜索算法(BFS)、深度优先搜索算法(DFS)和A*搜索算法，接下来将概述这三种单机器人路径规划算法的差异。5一、原理比较1.广度优先搜索算法将地图中所有的节点系统地展开并检查，直到找到结果为止。2.深度优先搜索算法“不撞南墙不回头”，一条路走到黑，走不通掉头往回走，回到路口之后进入另一条路，直到找到结果为止。3.A*搜索算法根据F(n)=G(n)+H(n)公式，计算估值函数并且选择函数值小的方向前进，走不通的路，就返回路口重新选择函数值小的方向前进，直到找到结果为止。1单路径规划算法效果比较6一、原理比较1.广度优先搜索算法将地图中所有的节点系统地展开并检查，直到找到结果为止。1单路径规划算法效果比较7一、原理比较2.深度优先搜索算法“不撞南墙不回头”，一条路走到黑，走不通掉头往回走，回到路口之后进入另一条路，直到找到结果为止。1单路径规划算法效果比较8一、原理比较3.A*搜索算法根据F(n)=G(n)+H(n)公式，计算估值函数并且选择函数值小的方向前进，走不通的路，就返回路口重新选择函数值小的方向前进，直到找到结果为止。1单路径规划算法效果比较9二、效果比较以物流机器人执行下述任务为例，确保三种算法执行任务条件相同，如下表所示。1单路径规划算法效果比较机器人数量1机器人编号R00机器人初始位置R00（0,0）机器人初始朝向R00右订单情况（任务）取C06货物1个货架位置S06（5,6）任务条件10分别执行三种算法，从路径长度上去分析不同算法的路径长度。图1为广度优先搜索算法路径规划效果，图2为深度优先搜索算法路径规划效果，图3为A*搜索算法路径规划效果。1单路径规划算法效果比较图1图2图311二、效果比较从规划效果上分析，在不加入转向时间等因素的情况下，广度优先搜索算法和A*搜索算法规划出的路径长度是一样的。广度优先搜索算法的一层层搜索特点，会将终点之前所有的点都搜索完才能规划出路径；深度优先搜索算法“不撞南墙不回头”的特点，规划出的路径绕了很远；A*算法根据估值函数较小值选择前进方向的特点规划出的路径会有较多的转弯。1单路径规划算法效果比较12三、时间比较分析三种算法各自的①计算时间、②预计执行时间、③实际执行时间、从执行时间上分析，广度优先算法的执行时间最短。1单路径规划算法效果比较广度优先搜索算法计算时间A*搜索算法计算时间深度优先搜索算法计算时间13一、分配算法的随机性分析遗传算法、粒子群算法与蚁群算法都是随机搜索算法。2任务分配算法效果比较（1）遗传算法：遗传算法的随机性体现在基因进化时交配和变异会产生和父代基因不同的基因个体，也确保基因不会很快的收敛到一个局部最优解。（2）粒子群算法：其随机性体现在粒子原本的初始速度，每个粒子在向最优粒子靠近时都有自己原本的速度，这样可防止粒子群收敛时出现“自锁”现象，收敛到局部最优解。（3）蚁群算法：其随机性体现在选择路径中，计算完每条路径选择的概率后，蚂蚁会根据“转盘抽奖”的规则选择路径，同样是为了防止快速收敛到局部最优解。14一、分配算法的随机性分析遗传算法：遗传算法的随机性体现在基因进化时交配和变异会产生和父代基因不同的基因个体，确保基因不会很快的收敛到一个局部最优解。2任务分配算法效果比较计算机解释交配设置一个交叉概率，从种群中随机选择两个基因个体，这两个基因个体按照交叉概率进行基因交换，基因交换的位置随机选取。变异设置一个变异概率，从种群中随机选择一个个体，该个体按照变异概率进行基因变异，变异的基因位置是随机的。15一、分配算法的随机性分析粒子群算法：其随机性体现在粒子原本的初始速度，每个粒子在向最优粒子靠近时都有自己原本的速度，可防止粒子群收敛时出现“自锁”现象，收敛到局部最优解。2任务分配算法效果比较属性描述速度当前粒子所具有的速度由两部分组成：由先前速度影响遗留下来的惯性速度w；若当前粒子不是粒子群中最接近目标的粒子时，该粒子有向着最优方向移动的趋势速度。位置当前粒子所在的位置，用以衡量粒子与目标的距离历史最优位置当前粒子在搜寻目标的过程中，距离目标最近时的位置。16一、分配算法的随机性分析蚁群算法：其随机性体现在选择路径中，计算完每条路径选择的概率后，蚂蚁会根据“转盘抽奖”的规则选择路径，同样是为了防止快速收敛到局部最优解。2任务分配算法效果比较转盘抽奖示意图17二、分配算法结果比较以物流机器人执行下述任务为例，控制三种算法的输入值不变，执行任务相同，路径规划算法均选择D*算法。任务条件如下表所示。2任务分配算法效果比较机器人数量3机器人编号R00、R01、R02机器人初始位置R00（0,1）、R01（0,0）、R02（7,0）机器人初始朝向R00右、R01右、R02左订单情况（任务）取C02货物1个、C04货物1个、C07货物1个货架位置S02（1,6）、S04（3,6）、S07（6,6）18（1）遗传算法结果：

((0,0),(3,6),(2,0))：机器人(0,0)—>货架(3,6)—>取货点(2,0)；((0,1),(1,6),(2,0))：机器人(0,1)—>货架(1,6)—>取货点(2,0)；((7,0),(6,6),(5,0))：机器人(7,0)—>货架(6,6)—>取货点(5,0)。2任务分配算法效果比较GA-机器人分配到货架GA-货架分配到取货点19（2）粒子群算法结果：

((0,0),(1,6),(2,0))：机器人(0,0)—>货架(1,6)—>取货点(2,0)；((0,1),(6,6),(5,0))：机器人(0,1)—>货架(1,6)—>取货点(5,0)；((7,0),(3,6),(2,0))：机器人(7,0)—>货架(3,6)—>取货点(2,0)。2任务分配算法效果比较PSO-机器人分配到货架PSO-货架分配到取货点20（3）蚁群算法结果：

((0,0),(3,6),(2,0))：机器人(0,0)—>货架(3,6)—>取货点(2,0)；((1,0),(1,6),(2,0))：机器人(1,0)—>货架(1,6)—>取货点(2,0)；((7,0),(6,6),(5,0))：机器人(7,0)—>货架(6,6)—>取货点(5,0)。2任务分配算法效果比较ACO-机器人分配到货架ACO-货架分配到取货点21二、分配算法结果比较从分配效果来看，遗传算法和蚁群算法本次的分配方案是相同的，也是最优的分配方案。而粒子群本次的分配方案相对于遗传算法和蚁群算法来说就不是最优的，机器人行进的路径长度也不是最短。当然，算法是存在随机概率的，可能下一次规划出的路径就会是最优或者较优的解。2任务分配算法效果比较22三、分配算法的时间对比遗传算法：算法的平均计算时间976.36ms，实际平均执行时间82s；粒子群算法：算法平均计算时间501.96ms，实际平均执行时间82.05s；蚁群算法：算法平均计算时间491.49ms，实际平均执行时间79.34s2任务分配算法效果比较粒子群算法时