文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 研究生入学考试 > 一种改进的蚁群算法求解最短路径问题
侵权投诉

一种改进的蚁群算法求解最短路径问题

一种改进的蚁群算法求解最短路径问题

维普资讯 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

一种改进的蚁群算法求解最短路径问题

第1页

你可能喜欢

  • 蚁群算法 matlab
  • 算法代码
  • 算法matlab代码
  • 最短路径算法
  • 蚁群算法原理

热门文档

相关文档

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