一种改进的蚁群算法求解最短路径问题
维普资讯 doc.guandang.net
一
种改进的蚁群算法求解最短路径问题 毕军付梦印张字河 (京理工大学自动控制系,北北京 1 0 8 ) 0 0 1 E- i: i n h@2 3 n t ma lb l g c 6 .e i
摘
要
蚁群算法是一种新型的模拟进化算法,求解复杂的组合优化问题提供了一种新的思路 .文应用蚁群算法求为该
解最短路径问题,算法的选择策略,部搜索,息量修改三方面进行改进,算法不易陷入局部最优解,且能较快对局信使并地收敛到全局最优解 .实验结果表明,进方法是合理的,效的 .改有 关键词蚁群系统最短路径模拟进化算法
文章编号 1 0— 3 1 ( 0 3 0— 1 7 0 文献标识码 A 0 2 8 3一 2 0 )3 0 0— 3 中图分类号 T 3 1 P 0. 6
An I p o e t Co o y Al o i m o h h r e t Pa h Pr b e m r v d An l n g r t h f r t e S o t s t o lm BiJ n F e g i Zh n h u u M n yn a g Yu e
( e a me to uo t o t lB in ntue o eh oo y B in 0 0 1 D pr n fA tma c C nr, e ig Isi t fT c n lg, e ig 1 0 8 ) t i o j t j Ab t a t An o o y s se i n v l smua e v l t n r lo t m, h c p o i e e t o o o l ae sr c: t c ln y t m s a o e i lt d e o u i a y ag r h w ih r v d s a n w meh d fr c mp i t d o i c c mb n tra p i z t n p b e . h g r m i s d f r t e h re t p t r b e I s mp v d n h e p rs o o i ao l o tmiai r l msT e a o t i o o l i h s e s o t s a p l m. i u o h h o t i r e i t r e a t f o
s lc i n sr tg,o a e r h, n n o ma in mo i c t n S a t c n n t e sl R n o t e l c p mu a d c n e e to t e y lc l s a c a d i f r t d f ai, O t t i a o a i m it o a o t a o i o h y h l i m n a c n e g t t e g o a p i m. e r s l f e p rme t s o t a h mp v d ag rt m s v l . o v r e a h l b o t l mu Th e u t o x e s i n h w h t t e i r e o h o l i i ai d Ke wo d: An oo y s se, h re t p t S mu ae v l t n r l o t m y rs t c l n y tm S o s a h, i lt d e o u i a y a g r h t o i
l引言 最短路径问题是指在一个赋权图的两个节点之间找出一条具有最小权的路径,图论中研究的一个重要问题 1交通网是" .络的线路分布,游线路的选择,市规划及工程建设中的管旅城道网的铺设等问题都与寻找一个图的最短路径问题密切相关, 因此对最短路径问题的研究具有重要意义和实用价值 .
短,过的蚂蚁越多,径上留下的信息物质越多,后续蚂蚁走路则 选择该路径的概率就越大,且留下相应的信息物质 .后,并最蚂蚁个体之间就是通过这种信息物
质交流,索到一条从蚁巢到搜食物源的最短路径 RI -. s蚁群算法是模拟蚁群行为的一种随机搜索优化算法,要主由四个部分组成:择策略;息量的局部更新;局部最优选信求解的局部搜索算法;息量的全局更新 .信
随着人们对 N— ad组合优化问题的研究,出了许多用 P hr提以解决该类问题的进化算法,遗传算法,化规划,化策略如进进
等.蚁群算法是最近几年才提出的一种新型的模拟进化算法, 它是由意大利学者 M.o g, . a i z D r o V M ne o等人首先提出的 1 i z 2一,他们称之为蚁群系统 ( n ooy S s m, C )并应用该算 A tC ln yt A S . e
3求解最短路径的蚁群算法的实现 31基本算法的设计 . 开始时,有的 m个蚂蚁都集中在起点 S处 .蚂蚁 i S所从 点出发,照选择策略,和 S相关联的边的集合中,择一条按从选边;后,从这条边的另一节点 a开始,和 a相关联的边的然再从
法求解 T P问题,配问题, b so度问题,得了较好的 S分 j—h p调 o取结果 11文改进了基本的蚁群算法,决了基本算法在求解 3 .该 - 5解 最短路径中出现的问题,得了理想的实验结果 .取
集合中,择另一条边;选以此类推,到搜索到终点,是,直于蚂 蚁 i到一个从 S到的解 .每当蚂蚁选择完一条边后,马得就上更新边上的信息量 (部更新 )蚂蚁搜索完后,蚁从 S局 .蚂 出发,照和相同的方法,索出一条从 S到的路径,到按搜得 一
2基本蚁群算法原理 蚁群算法是一种模拟进化算法,受到对真实蚁群行为的是 研究的启发而提出的 .为了说明蚁群系统的原理,简介一下先
个解 .直到所有的 m个蚂蚁都进行完搜索,到 m个解 (得包
蚂蚁搜索食物的具体过程 .象蚂蚁这类群居昆虫,然单个昆虽 虫的行为极其简单,群体却表现出复杂的行为,找到由蚁但能巢到食物源的最短路径 .仿生学家经过研究发现,蚁个体之蚂
括重复的) .以 m个解为基础,用局部搜索算法,行局部搜采进索,到局部最优解 .据局部最优解全局计算信息增量 (局得根全更新 )全局更新后,续迭代直到满足停止条件,止条件为,继停
间是通过一种称为外激素 (hrmo e的物质进行信息传递的 . pe o n) 蚂蚁在运动过程中,能够在它所
经过的路径上留下该种物质, 而且在运动过程中能够感知这种物质,以此指导自己的运动并
最大迭代次数 .在所求得的所有局部最优解中,最小的解为值所求的全局最优解,即最短路径的距离值 .用基本的蚁群算法 求解最短路径问题的主要实现步骤如下 q:
方向,蚁倾向于朝着物质强度高的方向移动 .此,大量蚂蚂因由 蚁组成的群体行为便表现出一种信息正反馈现象:一路径越某
( )息初始化:法开始运行时,予每条边上相等数量 1信算赋 的信息量 .
作者简介:毕军,,9 3年生,士生,男 17博主要从事定位定向技术及网络优化方向的研究.付梦印,,9 4年生,男 16教授,士生导师,博主要从事定位 定向技术的研究 .张宇河,,90年生,授,士生导师,要从事运动控制和导航技术的研究 .男 14教博主
计算机工程与应用
2 0 . 17 0 33 0

针对蚁群算法在求解交通网络两点之间最短路径时存在收敛速度慢和容易出现停滞现象等缺点,为提高搜索效率,提出了一种改进的蚁群算法。通过在初始化信息素时加入方向引导...
龙源期刊网 http://www.qikan.com.cn 改进蚁群算法求解最短路径问题 作者:张...本文提 出一种改进策略的蚁群算法——自主复制蚁群算法(Auto Copy Ant Colony ...
如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 加入阅读会员!获取下载券 一种改进的蚁群算法求解车辆的最短路径问题...
蚁群算法在求解最短路径问题上的改进策略_专业资料。蚁群算法是一种新型的模拟进化算法,为求解复杂的组合优化问题提供了一种新的思路,但基本的蚁群算法收敛速度慢,...
最短路径问题是智能交通:交通网络分析中的一个重要问题.文章分析了基本蚁群算法在求解交通网络两点之间最短路径时 所出现的问题,并针对这些问题,在方向引导及信息素...
11.毕军,付梦印,张宇河.一种改进的蚁群算法求解最短路径问题[J].计算机工程与应用,2003,39(3):107-109. 12.吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法...
要 使用传统蚁群算法求解图的最短路径问题时 ,随着节点的增加会出现搜索速度变...针对这个问题 ,提出一种改进的蚁群算法 ,通过引入搜索方向和搜索热区机 制提高...
一种改进的蚁群算法求解最... 3页 10财富值 基于改进蚁群算法的物流配......由于全连通网络具有最强的抗毁性,且节点间最短路径数对于网络抗毁性有重要意义,...
一种求解高校最短路径的改进的启发式蚁群算法_专业资料。启发信息是地理信息系统(GIS)中的关键,针对蚁群算法易陷入局部最优的缺陷,提出一种带有启发信息的改进蚁群...
热门文档