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

基于改进蚁群算法求解最短路径和TSP问题

基于改进蚁群算法求解最短路径和TSP问题

第君蕊耜期2010年4月

cC}MPlrrER

计算机技术与发展

nC刖010(、Y

AND帆l

v01.20

01)MENT

Apr.

N().4

2叭O

基于改进蚁群算法求解最短路径和TSP问题

宋世杰,刘高峰,周忠友,卢小亮

(内江师范学院数学与信息科学学院,四川内江641112)

摘要:为了能高效地求解最短路径和TSP问题,利用速度恒定的蚂蚁群,行走最短路径的蚂蚁首先达到终点这个基本原理,提出了一种改进的蚁群算法。因为只要有一个蚂蚁达到终点,算法停止,所以该算法避免了蚂蚁往返爬行所消耗的时间。针对一定规模的最短路径和TSP问题,设置足够量的蚂蚁群,通过该算法能较快地求出全局最优解或者能很好逼近最优解的近似解,算法的时间复径杂度是线性级的,迭代次数较少,而且该算法是并行处理的。通过实验仿真,结果表明算法是可行有效的。

关键词:蚁群算法;最短路径;TSP问题;并行性中围分类号:TPl83

文献标识码:A

文章编号:1673—629X(2010)04—0144—04

AnImpr0VedAntColonyAlgorithmSolVingtheShortestPath

andTSPProblem

soNG

(sch∞l0f

Sh¨ie,LIUQ恰feng,ZHOUZhong—you,UJXia争liallg

MathematbandInfomati∞,N两iangNI)nnalCollege,N蜘iang641112,China)

the∞nscantspeedof

an

Al葛tr叠d:Inord盯tothethe

ant

effid∞tly鲥vet11e宣horte吼pathandTSPpr0_blefn,∞∞rding

to

ant∞咖,thepath

0n

w}lich

fi哪托瓤h∞thedestinati0Ilistheshortest.An

imp∞删ant∞lony

oran

alg嘶thmisp∞posed.If

and

ant

h勰∞Ilie、^edthedestinat;on,

a190^thrn蚰0pped。3D出e蛔^thrnhas狮idedthetin砖that锄协伽t

k肌ecrawl.Fbfthecerta洫s嗣esIDrt酋tp8thandTSP

probl锄。t}砖alg谢th锄obtajnt}圯glDbaloptimal90111tion

its

t.m℃唧Iexi锣is

approximate30lutionWhichisgr∞tlycI∞e∞theoptimal30lutbn,and

Iine盯.Ith皓le翳ita胃tiol坞andthis

a丑驴dthmispa瑚lel

pm痢ng.S.mulat两re踟k

3}髓鸭that

this蛔rithrn

is

fe商bleandeffecti豫.

Key帅r凼:肌t∞blyaIg丽thm;shortest

path

pmbl酮;TSP;paralleli锄

O引言

以及二次分配问题(Q心)、车间任务调度问题(JsP)、

图的着色问题、网络路由等许多复杂的组合优化问题[5~81。

目前,蚁群算法在求解最短路径和TSP问题时容易陷入局部最优、迭代次数多、时间复杂度高【9q引。文中利用速度恒定的蚂蚁群,行走最短路的蚂蚁首先达到终点这个基本原理,在问题空间中同时构造问题的多个解,很好地解决了蚁群算法在求解最短路径和

TsP问题的局限性。

随着社会的不断发展,最短路径问题已广泛应用于交通运输、物流配送、网络分析、管道铺设、厂区选址与布局等与生产实践息息相关的问题。以交通运输为例,搜索城市路网中两点间的最短路径就显得极其重要。但在实际运用中发现,当城市路网结点过多时经典算法就会导致计算量急剧增加,搜索开销相当大,效率很低。

蚁群算法是由意大利学者&rigo等人于20世纪

90年代初期通过模拟自然界中蚂蚁集体寻径的行为而提出的一种基于种群的启发式随机搜索算法[卜4l,蚁群算法具有并行性、鲁棒性、正反馈性等特点。蚁群算法最早成功应用于解决著名的旅行商问题(TSP),

收稿日期:2009一08—02;修回日期:2009—10一30基金项目:四川省教育科研计划项目(07ZB043)

作者简介:宋世杰(1987一),男.四川成都人,研究方向为线性规划;刘高峰,硕士。讲师,研究方向为启发式算法。

1蚁群算法的基本原理

生态学家发现蚂蚁在寻找食物时总是可以找到食物源到巢穴之间的最短路径,这是因为蚂蚁在搜寻食物源时。能在其走过的路径上释放一种蚂蚁特有的信息素,可以将信息传递给其它蚂蚁并影响其对路径的选择。当蚂蚁碰到一个还没有走过的路口时就随机地挑选一条路径前行,并释放与路径有关的信息素,通常

第1页

你可能喜欢

  • 蚁群算法 matlab
  • 遗传算法分析
  • 算法代码
  • 最短路径算法
  • 算法matlab代码

热门文档

相关文档

  • 基于改进蚁群算法求解最短路径和TSP问题

    基于改进蚁群算法求解最短路径和TSP问题_IT/计算机_专业资料 暂无评价0人阅读0次下载举报文档 基于改进蚁群算法求解最短路径和TSP问题_IT/计算机_专业资料。第...

  • 求解TSP问题的改进蚁群算法

    求解 TS P 问题的改进蚁群算法张军英 1, 2 , 敖 磊 , 贾江涛 , 高 琳 1 1 1 摘要 : 分析了标准蚁群算法易于出现早熟停滞现象的主要原因 ,在原有算法...

  • 求解TSP问题的改进蚁群算法

    5 求解 TSP 问题的改进蚁群算法张 军英 , 敖 1, 2 磊 , 贾江 涛 , 高 710071; 1 1 琳 1 ( 11 西安电子科技大学 计算机学院 , 陕西 西安 21 西 ...

  • 一种改进的蚁群算法求解TSP问题及实验结果分析

    一种改进的蚁群算法求解TSP问题及实验结果分析_IT/计算机_专业资料。一种改进...在周游过程中,会使它经过的路径上的信息量减少,同时,增强 蚂蚁在最短路径上的...

  • 【论文】基于自然选择策略的蚁群算法求解TSP问题

    基于自然选择策略的蚁群算法求解TSP问题_物理_自然科学_专业资料。第3 4卷第 4期 201 3年 4月 通 信 学 报 、,ol_34 No.4 Journi aon Comlnunic ...

  • 求解TSP问题的蚁群算法改进探讨

    新的启发算法.基于群体的协作与学习,该算法已经成功地 解决诸如TSP问题等多种组合优化问题.本文提出了一种 改进蚁群算法.该算法根据人工蚂蚁所获得解的情况,应用 ...

  • 蚁群算法求解TSP问题

    智能优化算法 李小燕 S131020016 计算机科学与技术 信息科学与工程学院 杨圣洪 2014 年 6 月 8 日 蚁群算法求解 TSP 问题摘要:蚁群算法是一种分布式内在并行算法...

  • 基于改进蚁群算法对最短路径问题的分析与仿真(1)

    ( 2009 ) 02 - 0150 - 04 基于改进蚁群算法对最短路径问题的分析与仿真杨... 信息正反馈和启发式搜索的特 征 ,已经成功地用于解决 TSP (旅行商 )组合...

  • 蚁群优化算法在解决TSP问题中的应用

    蚁群优化算法在解决TSP问题中的应用_信息与通信_工程科技_专业资料 暂无评价0人阅读0次下载举报文档 蚁群优化算法在解决TSP问题中的应用_信息与通信_工程科技_...

  • 基于蚁群算法的TSP的改进求解算法

    ( 华东理工大学模式识别与智能系统 上海 200237) ① 摘 : 基于一种已有的用于连续空间问题的蚁群算法 ,将其修改为可以应用于 TSP 问题的算法 ,并付诸于试验当中...

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