蚁群算法最优路径

机器人的路径规划机器人的路径规划 蚁群算法蚁群算法 1 蚁群算法 众所周知 蚁群算法是优化领域中新出现并逐渐引起重视的一种仿生进 化算法它是群体智能的典型实现 是一种基于种群寻优的启发式搜索算法 自 从 M Dorigo 等意大利学者在 1991 年首先提出蚁群算法 Ant Colony System ACS 以来 这种新型的分布式智能模拟算法已逐渐引起人们的注意并 得到广泛的应用 蚁群算法的特点主要表现在以下五个方面 1 蚂蚁群体行为表现出正反馈过程 蚁群在寻优的过程中会释放一定量的 信息素 蚁群的规模越大 释放的信息素的量也就越大 而寻优路径上存在的 信息素浓度越高 就会吸引更多的蚂蚁 形成一种正反馈机制 然后通过反馈 机制的调整 可对系统中的较优解起到一个自增强的作用 从而使问题的解向 着全局最优的方向演变 最终能有效地获得全局相对较优解 2 蚁群算法是一种本质并行的算法 个体之间不断进行信息交流和传 递 有利于最优解的发现 并在很大程度上减少了陷于局部最优的可能 3 蚁群算法易于与其他方法结合 蚁族算法通过与其他算法的结合 能够 扬长避短 提高算法的性能 4 蚁群算法提供的解具有全局性的特点 一群算法是一种群只能算法 每 只蚂蚁巡游的过程相对独立 他们会在自己的活动空间进行搜索 蚂蚁在寻优 过程中通过释放信息素 相互影响 互相通信 保证了解的全局性 5 蚁群算法具有鲁棒性 蚁族算法的数学模型易于理解 可以广泛应用在 很多复杂的优化问题中 蚁族算法区别于传统优化算法的一个特点在于该算法 不依赖于初始点的选择 受初始点的影响相对较小 并且在整个算法过程中会 自适应的调整寻优路径 由此可见 在机器人寻找最优路径的过程中 采用蚁群算法实现路径的规 划问题 可以高效 准确的找到最优的路径 2 移动机器人的路径规划 2 1 环境信息处理 假设机器人运行环境为边长分别为x和Y的矩形区域 在矩形区域内分布有 n个异形障碍物 显然对于该获取的实际环境信息 首先 由于障碍物大小不一 而且形状也各不相同 为了减少机器人处理地图信息的负担 需要对工作环境 行一些必要的预处理 其次 在后续章节中 描述机器人的路径规划方法是基 于把障碍物近似成质点的基础上进行的 而要把障碍物近似成质点也同样需要 对工作环境的信息进行适当预处理 环境信息预处理遵循以下原则 1 移动机器人作二维平面运动 障碍物不考虑高度信息 2 小问距障碍物作合并处理 即如果两个障碍物相距太近 障碍物之间距离小 于机器人通过的最小安全距离 则将两个障碍物合并作为一个障碍物处理 3 作出障碍物的外接矩形 并对障碍物外接矩形进行径向扩张且对环境边界向 内作径向扩张 因此可把移动机器人退化成运动质点处理 2 2环境建模 设机器人工作空间为二维结构化空间记为RS 并且障碍物位置 大小已知 用尺寸相同的栅格对RS进行划分 栅格大小以机器人能在其内自由运动为限 设机器人能自由运动的范围为 0 R 若某一栅格尺寸范围内不含任何障碍物 则称此栅格为自由栅格 反之称为障碍栅格 自由空间和障碍物均可表示成栅 格块的集合 我们将障碍物栅格集记为OS 栅格标识可采用下述两种方法 1 直角坐标法 以栅格阵左上角为坐标原点 水平向右为x轴正方向 竖 直向下为Y轴正方向 每一栅格区间对应坐标轴上的一个单位长度 任一栅格均 可用直角坐标 x y 唯一标识 2 序号法 按从左到右 从上到下的顺序 从栅格阵左上角第一个栅格开 始 给每一个栅格一个序号n 从0开始计 则序号以与栅格块一一对应 2 3具体方法 给定一个有弹个节点的城市道路网的路径规划问题 我们可以把指定的起 始点s假设为人工蚁群 以下简称为蚁群 的巢穴 把目标点t假设为要寻找的食 物 则此路径规划问题就可以转化为蚁群寻找食物的路径寻优问题 假定人工 蚂蚁 以下简称为蚂蚁 的数量为m只 则每只蚂蚁的行为要符合以下的规则 1 能够释放出两种类型的信息素 食物 信息素和 巢穴 信息素 2 根据与当前节点相连接的各个路径上的信息素浓度和路径长度 以相应的概 率来随机选择下一个节点 3 不再选择已经走过的节点为下一个节点 这可以通过一个结构数组来实现 4 在寻找食物时 通过 食物 信息素寻找下一个节点 同时释放 巢穴 信 息素 5 在寻找巢穴时 通过 巢穴 信息素寻找下一个节点 同时释放 食物 信 息素 6 按一定的路径长度释放相应的信息素浓度 并且所释放的信息素浓度会随着 时间的推移而逐步减少 3 程序设计流程 在主程序流程中 地图数据库是从实际地图中抽象出来的城市道路网相关 的 数据信息 其中包括城市道路网的节点信息 道路信息和相应道路的信息素信 息 每部分信息都各自形成一个数据表 在节点表中 包括了各个节点的编号 对应的地点名称和经纬度坐标等数据 在道路表中 包括了每条道路的起点和 终点对应的编号 道路的长度 级别和所经过的路线等数据 在信息素表中 包括了对应道路上的 巢穴 信息素和 食物 信息素等数据 所需要输入的 参数包括 节点的数量n 起始节点的编号OriNode 目标节点的编号DesNode 最大循环次数MaxCount 蚂蚁的数量m 蒸发信息素的相对重要程度 每只蚂 蚁所释放的信息素总量Q 信息素浓度的相对重要程度口 启发式信息的相对重 要程 所需要初始化的参数包括 巢穴 信息素和 食物 信息素等值 每 条道路对应的 巢穴 信息素和 食物 信息素的值分别仞始化为1 这是为了 在计算下一个节点的选择概率时 分母不为0 在程序开始时 首先连接地图数据库 然后输入 初始化各个参数并开始 进行循环 在每次循环中 每只蚂蚁依次进行寻食过程 如果有蚂蚁找到了食 物即找到了一条寻食路径 将此路径与本次循环中其它蚂蚁找到的寻食路径进 行比较 将最小的寻食路径更新为最优路径 并判断是否满足所给定的精度 如果满足则退出循环 否则进行下一次循环 当循环次数达到最大次数时 结 束循环并判断是否找到了最优路径 如果找到了最优路径 则输出最优路径的 路线及其权值 否则显示没有找到最优路径 最后 关闭地图数据库并结束程 序 在每只蚂蚁进行寻食的过程中 首先判断蚂蚁是否正在寻找食物 如果是 则进行寻找食物的过程 否则进行寻找巢穴的过程 在进行寻找食物的过程中 首先从地图数据库的道路表中读取与当前节点所连接的节点数 以及每个节点 的编号和权值 判断每个节点是否已经走过 如果此节点已经走过 则读取下 一个节点 从地图数据库的信息素表中读取对应边的 食物 信息素值 从当 前点到下一可行点的转移是由基于信息量的状态转移概率和和距离启发式信息 概率综合决定的 而这里采用的综合决定方法是基于比例选择策略即 轮盘赌 的方式 从地图数据库的道路表中读取对应边的权值 并计算所走过路径的权 值 从地图数据库的信息素表中读取对应边的 巢穴 信息素值 并重新计算 对应边的 巢穴 信息素值 当所得的值小于1时 将此值设置为1 这是为了 保证下一回计算选择概率时分母不为0 将重新计算的 巢穴 信息素值更新到 信息素表中 判断下一个目标节点是否为食物 如果是的话 则保存各个记录 如蚂蚁所走过的节点 此蚂蚁找到食物的次数以及整个路径的总权值等数据 并为寻找巢穴做准备 如清空内存中的历史数据 将食物作为起始节点等 否 则设置下一个目标节点为当前节点 在进行寻找巢穴的过程中 大部分的操作都跟上面蚂蚁进行寻找食物的过 程一样 只不过将 食物 信息素和 巢穴 信息素进行对调 在判断下一个 目标节点是否为巢穴的时候 不需要保存各个记录 只需为寻找食物做准备 如清空内存中的历史数据 将巢穴作为起始节点 并将此蚂蚁上次找到食物的 路径记录 程序流程图如下 4 Matlab 仿真 4 1参数介绍 地图数据库是从实际地图中抽象出来的城市道路网相关的数据信息 其中 包括城市道路网的节点信息 道路信息和相应道路的信息素信息 每部分信息 都各自形成一个数据表 在节点表中 包括了各个节点的编号 对应的地点名 称和经纬度坐标等数据 在道路表中 包括了每条道路的起点和终点对应的编 号 道路的长度 级别和所经过的路线等数据 在信息素表中 包括了对应道 路上的 巢 穴 信息素和 食物 信息素等数据 本仿真系统的静态地图数据假设在机器 人出发之前就已经得到 而动态地图数据假设按一定的频率可以得到 在机器人整个仿真系统中所需要输入的参数包括 节点的数量栉 起始节 点的编号OriNode 目标节点的编号DesNode 最大循环次数MaxCount 蚂蚁的 数量m 蒸发信息素的相对重要程度 每只蚂蚁所释放的信息素总量Q 信息素 浓度的 相对重要程度 启发式信息的相对重要程 所需要初始化的参数包括 巢穴 信息素和 食物 信息素等值 每条道路对应的 巢穴 信息素和 食物 信 息素的值分别初始化为1 这是为了在计算下一个节点的选择概率时 分母不为 0 4 2程序介绍 4 2 1G2D m 用于把障碍物分布图转化为图的赋权邻接矩阵 地形图矩阵是一个01矩阵 里面的所有元素要么为0 要么为1 为0即表示机器人可以到达的节点 为1即 表示其对应的栅格是障碍物 源程序如下 function D G2D G a 1 N size G 1 D inf ones N 2 N 2 for i 1 N 2 x ceil i N 0 00001 y mod i N if y 0 y N end x1 x 1 y1 y 1 if x1 1 D i j 1 414 a D j i 1 414 a end x2 x 1 y2 y if x2 1 j x2 1 N y2 D i j a D j i a end x3 x 1 y3 y 1 if x3 1 D i j a D j i a end x5 x y5 y 1 if y5 N j x5 1 N y5 D i j a D j i a end x6 x 1 y6 y 1 if x6 1 j x6 1 N y6 D i j 1 414 a D j i 1 414 a end x7 x 1 y7 y if x7 N j x7 1 N y7 D i j a D j i a end x8 x 1 y8 y 1 if x8 N D i j 1 414 a D j i 1 414 a end end for x 1 N for y 1 N if G x y 1 J x 1 N y D J inf ones N 2 1 D J inf ones 1 N 2 end end end for i 1 N 1 x i N 1 y i 1 N D x y inf D y x inf end 4 2 2ACASP m 障碍物可以动的情况设计的蚁群算法 其主要功能就是通过派遣若干批蚂 蚁 来搜索动态环境下的最短路 程序内部设计准则完全按照前面的设计要求 进行 包括启发式信息规则 信息素更新规则 等等 当然 此程序可以单独 运行 主要用于解决静态环境下的蚂蚁寻路问题 程序把各批次所有蚂蚁的行 走路线都记录下来 可以据此绘出蚂蚁寻路的动态图形 源程序如下 function ROUTES PL Tau Route G Tau K M S E Alpha Beta Rho Q D G2D G N size D 1 MM size G 1 a 1 Ex a mod E MM 0 5 if Ex 0 5 Ex MM 0 5 end Ey a MM 0 5 ceil E MM Eta zeros 1 N for i 1 N ix a mod i MM 0 5 if ix 0 5 ix MM 0 5 end iy a MM 0 5 ceil i MM if i E Eta 1 i 1 ix Ex 2 iy Ey 2 0 5 else Eta 1 i 100 end end ROUTES cell K M PL zeros K M for k 1 K disp k for m 1 M W S Path S PLkm 0 TABUkm ones 1 N TABUkm S 0 DD D DW DD W DW1 find DW inf for j 1 length DW1 if TABUkm DW1 j 0 DW j inf end end LJD find DW 1 PP zeros 1 Len LJD for i 1 Len LJD PP i Tau W LJD i Alpha Eta LJD i Beta end PP PP sum PP Pcum cumsum PP Select find Pcum rand to visit LJD Select 1 Path Path to visit PLkm PLkm DD W to visit W to visit move to the next point for kk 1 N if TABUkm kk 0 DD W kk inf DD kk W inf end end TABUkm W 0 DW DD W DW1 find DW inf for j 1 length DW1 if TABUkm DW1 j 0 DW j inf end end LJD find DW inf Len LJD length LJD end ROUTES k m Path if Path end E PL k m PLkm else PL k m inf end end Delta Tau zeros N N for m 1 M if PL k m inf ROUT ROUTES k m TS length ROUT 1 PL km PL k m for s 1 TS x ROUT s y ROUT s 1 Delta Tau x y Delta Tau x y Q PL km Delta Tau y x Delta Tau y x Q PL km end end end Tau 1 Rho Tau Delta Tau pheromone evaporates some and accumulates some end plotif 1 control parameter determine if plot or not if plotif 1 plot convergence curve meanPL zeros 1 K minPL zeros 1 K for i 1 K PLK PL i Nonzero find PLK inf PLKPLK PLK Nonzero meanPL i mean PLKPLK minPL i min PLKPLK end figure 1 plot minPL r hold on plot meanPL g legend 最小路径长度 平均路径长度 grid on title 收敛曲线 平均路径长度和最小路径长度 xlabel 迭代次数 ylabel 路径长度 Plot Passing Graph figure 2 axis 0 MM 0 MM for i 1 MM for j 1 MM if G i j 1 x1 j 1 y1 MM i x2 j y2 MM i x3 j y3 MM i 1 x4 j 1 y4 MM i 1 fill x1 x2 x3 x4 y1 y2 y3 y4 0 2 0 2 0 2 hold on else x1 j 1 y1 MM i x2 j y2 MM i x3 j y3 MM i 1 x4 j 1 y4 MM i 1 fill x1 x2 x3 x4 y1 y2 y3 y4 1 1 1 hold on end end end hold on ROUT ROUTES K M LENROUT length ROUT Rx ROUT Ry ROUT for ii 1 LENROUT Rx ii a mod ROUT ii MM 0 5 if Rx ii 0 5 Rx ii MM 0 5 end Ry ii a MM 0 5 ceil ROUT ii MM end plot Rx Ry LineWidth 2 end title Shortest Path axis 0 MM 0 MM plotif2 1 Plot route for every iteration if plotif2 1 figure 3 axis 0 MM 0 MM for i 1 MM for j 1 MM if G i j 1 x1 j 1 y1 MM i x2 j y2 MM i x3 j y3 MM i 1 x4 j 1 y4 MM i 1 fill x1 x2 x3 x4 y1 y2 y3