文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > 改进蚁群算法在迷宫路径规划问题中的研究和应用
侵权投诉

改进蚁群算法在迷宫路径规划问题中的研究和应用

基于蚁群算法的电脑鼠研究 主要是针对较大工程的系统研究

第31卷第2期温如春,等:改进蚁群算法在迷宫路径规划问题中的研究和应用

27

和当前全局地图信息的匹配实现机器人的定位,同

地图创建过程如图l所示.

时更新局部地图,最后实现全局地图的更新和创建

回目

图1地图创建过程

2改进蚁群算法原理与在迷宫问题中的实现

其中呜6是两个一维数组,其取值分别为:

2.1迷宫最短路径

越】={0,1,-1,0l,b【】={1,0,0,-1l

路径规划[41的任务是为机器人规划一条从起始2.2蚁群算法模型

点到目标点的无碰撞路径.一般来讲,路径规划方法大致可以分为两类:传统方法和智能方法.传统集合趔伽ed(甜)中的点集,而批d(巧)中的元素

考虑到蚂蚁从节点(0)只能到达当前可到达

方法有可视图法、栅格法、人工势场法等.这些算最多只有4个,故可以用C语言数组分别定义迷宫法在路径搜索效率及路径优化方面尚有待于进一的行数和列数,存储从节点(id)N另一节点(1l,t,)的步改善.而智能路径规划方法包括遗传算法嘲、模信息素以及迷宫中所有节点的信息素.在栅格地图

糊方法16l和蚁群算法等.智能算法可以提高移动机初始化时赋予每个结点相等的信息素,这样可以尽器人路径规划的避障精度,加快规划速度.

可能的扩大蚂蚁最初的搜索范围.

蚁群算法的主要依据是信息正反馈原理和某

例如,对位于节点(0)处的蚂蚁k,选择下一个

种启发式算法同的有机结合,这种算法在构造解的可行节点(z‘’t,),构造决断概率函数如式(2).

过程中,利用随机选择策略.这种选择策略使得进化速度较慢,正反馈原理旨在强化性能较好的解,却

po-{t,∑二毫:襄节点(2)

I

“¨c—h }‘

:,弋【o

容易出现停滞现象圈,这是造成蚁群算法不足之处

的根本原因.

其中,口表示信息素的重要程度,且口>0;

根据比赛规则,迷宫是由256个18cm×18

cln

allowed。为蚂蚁k当前可到达的点集,其元素为大小的方格组成的,迷宫的规模为16行×16列.在

allowed(id")中的点除去蚂蚁k已走过的点;下表示迷宫区域内,对位于(U)节点(1≤i≤16,1≈≤16)

点(0)与点(嵋t,)之间的信息素,其初始值为一较小的蚂蚁,每次只能按图2所示的前、后、左、右4个的正常数,随着算法的运行将会逐渐改变.

方向之一移动一步.迷宫最短路径问题即为:从迷宫2.3改进蚁群算法在迷宫可行解中的构造

区域中的某一节点(o.)出发,沿可行路径到达某一

在利用蚁群算法求解迷宫最优路径问题时,为终点(试),使其经过的路径最短.其中位于节点(0)

了使每只蚂蚁能以尽可能高的概率生成可行解,作

者采用两组数量相等的蚁群分别从迷宫的起点和终点同时出发,每只蚂蚁按式(3)确定的概率在迷宫中漫游.为尽量避免生成无效路径,为蚂蚁k分

配一张禁忌表.该禁忌表记录了蚂蚁k当前走过的点集,以避免选择已经走过的点.对任意一只蚂蚁,

在移动过程中可以定义如下的3种生命周期:①蚂蚁走进死角,除非沿原路返回一步或多步,不能再围2位于节点(U)的蚂蚁四方位移动图

朝前移动,否则将该蚂蚁从系统中删除;②蚂蚁到的蚂蚁可以到达的下一节点的坐标为(嵋t,),即

达另一组蚁群的出发点,此时该蚂蚁走过的路径为一条可行路径;③蚂蚁碰到另一组的某只蚂蚁.如果P竺;一,1,2,39=u(1)

Ll,

任意两只蚂蚁所经过的点没有重复(相遇点除外),l

;

,l,

It,弓+6圆

则将两只蚂蚁所经过的路径相连,可以构成迷宫的

上一页第2页

你可能喜欢

  • 迷宫算法
  • 移动机器人路径规划
  • 最短路径算法
  • 蚁群优化算法
  • 模糊控制算法研究

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email