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

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

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

28

江西理工大学学报2010年4月

一条可行路径.

2.4信息素的更新

随着时间的推移,前一代蚂蚁留下的信息素P

逐渐消失,用l叩表示信息素的消逝程度.经过Ⅳ个时段,蚂蚁完成一次搜索,当节点(U)上蚂蚁转移到节点(1‘,口)时,信息量根据式(3)进行调整.

I‰国+1)=(1叩)×弓,(t)+△‰(t)P∈(o,1){l△h(t)=乞T#k

二

(3)

1

0

其中,P∈(0.1)为调节信息素挥发速度的参数;g为蚂蚁繁殖的代数;A

T

F是蚂蚁在本次循环中留

在节点(U)上的信息量;m为蚂蚁的数量.

在信息素更新时,当k只蚂蚁完成一条搜索路径时,按照局部更新规则对信息素进行更新,根据

比赛规则,电脑鼠机器人寻找的是最优路径而不是

最短路径,寻优的标准是耗时最少,但是在算法中并不适于直接考虑“转弯”事件,因此采用惩罚的方式,使转弯耗费的事件折算到路程上,最终表现在路径的信息素上.更新模块如式(4).

f

一

圳m

^,jQ/(L,+K.艺k);蚂蚁在行进的路径上,.

10;其它

(4)

其中,Q为常量,厶为第k只蚂蚁在本次循环中搜

索到的路径长度,蜀(K.≥O)为其权重系数,k表

示在这条路径上的转弯次数.

由于迷宫环境复杂,问题规模比较大,信息量的挥发系数l叩的存在,使那些从未被搜索到的解

上信息量会减小甚至接近到O,降低了全局搜索能力,如果P过大时,当解的信息量增大时,以前搜索

过的解被选择的可能性过大,也会影响到算法的全局搜索能力.通过减/bp虽然可以提高算法的全局搜索能力,但又会使算法的收敛速度降低.

为了解决以上问题,对于挥发系数p,作者采用

自适应方法改变p的值.p初始值为1.

当算法求

得的最优值在JI、r次循环内没有明显改进时,p改变

为O.9劫(如果0.95p>,p幽),其他情况则p取最小设定值P岫,防止p过小而降低算法的收敛速度.3结束语

作者尝试应用局部更新规则和自适应方法改变信息素的方法,解决了蚂蚁在搜索过程中过早陷

入局部最优解的问题.本算法运行在电脑鼠机器人(32位的LPC2138单片机)上,取得了较好的效果,

当机器人遇到障碍时能在不到O.5s秒的时间内迅

速规划新的路径.这种改进蚁群算法提高了机器人在迷宫中路径规划的避障精度,加快了规划速度,

满足了实际应用的需要.

参考文献:

【l】D耐伊MCamGDiAntColony0p临llij崩∞:aNewMeta-heur-

istic.Proceedingofthe1999

Co唧nvolutionary

Computation[C].

1999。(2):1470-1477.

【2】D耐伊M,Maniem

V,CdomiA.TheAntSystem:Optimization

by

a

Colony《CooperatingAgent,.IEEETronsonSystem8【c】.

Man,andCybemetics-PartB:Cybernetics,1996,(26):i-13.

【3】ManYinYee,JackVermark.AGrid-based

PI恻for

Efficient

Global

IJocali刎∞of

Mobile

Robots.ICASSP【c】.2005(5):217-

220.

[41MeteaMB.RoutePlanningforIntelligentAuumonmusLandVeh—

iclesUsingHierarchicalTerrainRepresentation【C】.Int.Proeof

IEEEInto

Conf

oll

RoboticsandAutomation,1987,1947—1952.

【5】KsziloSugiham,JohnSmith.GeneticMgorithn∞forAdaptive

Mot-

ion

PlanningofanAutonomousMobileRobotsProblems【c】.1EE-

ET阳n8SMC.USA:SymposiumComputational

Intelligencein

Robotics

andAutomation,1997,(6):137—143.

[61EmmanuelAM

erchant-Cruz,AlanS.Morris.Fuz巧一训山8ed

majectory

Planner

for

BobotManipulators

Sharing

a

Common

Workspaee叨.IEEETransactions

Oil

Robotic8,2006,22(4):

613-624.

同刘于江,喻泽峰.一种求解旅行商问题的禁忌搜索算法田.江西理

工大学学报,2006.27(4):38枷.

嗍张美玉,黄翰,郝志峰,等.基于蚁群算法的机器人路径规划【刀.

计算机工程与应用,2005,41(25):34_37.

上一页第3页

你可能喜欢

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

热门文档

相关文档

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