文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 用蚁群优化算法求解中国旅行商问题
侵权投诉

用蚁群优化算法求解中国旅行商问题

用蚁群优化算法求解中国旅行商问题

维普资讯 doc.guandang.net

第 9卷第 3期 20年 6月 04 文章编号: 10:2 9(0 4 0—120 0 70 4 2 0 ) 30 2.5

电路与系统学报 J oURNAL OF CI RCUI TS AND YS S TEM S

Vo . No 3 1 9 . Jn, 2 0 u e 0 4

用蚁群优化算法求解中国旅行商问题 燕忠,袁春伟 (南大学生物医学工程系分子与生物分子电子学教育部重点实验室,江苏南京 2 0 9 )东 10 6

摘要:中国旅行商问题是一个组合优化问题,是一个 N问题。本文提出用蚁群优化算法去解决,同时提出了两 P 种改进的方法,其中,An—能够增强系统的搜索能力,使系统避免早熟,具有正负反馈的功能,仿真简单,容易理 t F解;而 AC+在 An oo y S se ( S的基础上改进而成,它使系统在演化的后期能够通过适当增大系统区分 S是 t ln ytm AC ) C信息素对比强度的方法,尽快找到最优的解。和其它的几种蚁群优化算法、遗传算法和模拟退火算法相比较,实验表明,AC+ S是本文提及的几种算法中最优的一种,它能加快系统收敛的速度,找到问题的最优值。 关键词;蚂蚁系统;蚁群优化算法:旅行商问题

中圈分类号 tT 3 1 1 P9. 4

文献标识码;A

1

引言 旅行商问题就是指旅行商按一定的顺序访问Ⅳ个城市的每个城市,使得每个城市都能被访问且

仅能被访问一次,最后回到起点,而使花费的代价最小。它是图论中具有代表性的优化组合问题,是 一

个 NP问题,问题的求解随着问题规模的扩大 (市数目的增加 )而变得越来越复杂,所需的计算城

时间也越来越长,采用某些传统的算法,例如穷举搜索法,是无法实现的,所以寻找更新的优化算法

是大家所追求的。这样,就出现了一些新的随机的搜索算法,像遗传算法 ( e e c l r h G n t g i m,G、 iA o t A) 贪婪算法 ( ed erh) Gre y S ac、模拟退火 ( i ltd An el g S Smuae n ai, A)等。但是这些算法对系统参数要 n求较高,例如遗传算法就必须选择种群数目、

杂交概率、变异概率等,参数选得好,就会得到比较好 的实验结果,反之,可能导致实验的失败。

中国旅行商问题是多种旅行商问题中的一个,它是一种对称式的旅行商问题。目前,有关文献对这个问题进行了求解,例如利用几何算法求得的解为 14 2公里【,采用人机结合的优质穷举法求 59”得的解为 14 9公里【 54,用二叉树描述中国旅行商问题而所求得的解为 14 4公里【,当然,还有其 50 3 1它比较早方法,其结果见文献[,】 45。在这里,介绍一种蚁群优化算法,它不仅具有很好的鲁棒性,良好的正反馈特性,而且具有并行分布计算的特点,适合于解决旅行商问题。将其应用到中国旅行商问 题上,取得很好的实验结果。

2蚁群优化算法 蚁群优化算法 ( t oo yOpi zt n AC【是由意大利学者 DoioM, nez C lri An ln t ai, O) C mi o r MaizoV, oon g

A等人根据蚂蚁群体具有智能的特点而首先提出来的,当时称之为蚁群系统 ( n S s m,A )【, A t yt e S 7 1 并利用该方法去解决离散优化问题【,取得成功,后来 Doio M等为了其他学者研究的方便,将各引 r g种蚂蚁算法统称为蚁群优化算法,并为该算法提出了一个统一的框架结构模型。蚁群优化算法是九十

年代初期才提出的一种新型的进化算法,虽然不很成熟,但是对蚁群优化算法的研究已引起了国际上 学者们的广泛关注。

研究表明,蚁群优化算法具有很强的发现较好解的能力,这是因为该算法不仅利用了正反馈原理,在一定程度上可以加快进化过程,而且是一种本质上分布并行的算法。但是这种算法也存在一些

缺陷,如搜索时间较长,容易出现停滞现象 (t n t nb hvo ),即搜索进行到一定程度后,所有 s g a o ea i a i r

收藕日期 2 0—52修订日期 t 0 31-4 0 30—6 2 0 .10基金项目。国家自然科学基金重点资助项目 ( 9 3 0 0) 68 11

用蚁群优化算法求解中国旅行商问题

第1页

你可能喜欢

  • 遗传算法实例
  • 旅行商问题算法
  • matlab实例教程
  • 遗传算法解决TSP问题
  • 蚁群算法 matlab
  • 算法matlab代码

热门文档

相关文档

  • 基于蚁群优化的中国旅行商问题的求解算法

    2008 基于蚁群优化的中国旅行商问题的求解算法赵 ,郭遂峰 芳 ( 新乡学院 计算机与信息工程学院 ,河南 新乡 453003) 0 引言 蚁群算法 ( Ant Colo ny Algo rit...

  • 旅行商问题描述及其蚁群优化算法

    基于蚁群优化的中国旅行... 暂无评价 2页 免费 一种求解旅行商问题的改......(3):434—444.2010 基于多粒度的旅行商问题描述及其蚁群优化算法冀俊忠 黄 振...

  • 一种快速求解旅行商问题的蚁群算法

    蚁群优化是一种元启发式的随机搜索技术,是目前解决组合优化问题最有效的工具之一.将信 息素更新和随机搜索机制的改进相结合,提出一种快速求解旅行商问题的蚁群算法...

  • 基于蚁群算法解决旅行商问题

    本文采用蚁群算法,充分利用蚁群算法的智能性,求解 旅行商问题,并进行实例仿真。进行仿真计算的目标是,该算法能够获得旅行商 问题的优化结果,平均距离和最短距离。 ...

  • 快速求解旅行商问题的蚁群算法

    在大量通用数据集上的实验表明 ,该算法不仅能获得更好 的最优解 ,而且收敛速度有显著的提高 . 关键词 旅行商问题 ; 蚁群优化 ; 增量模型 ; 扩散模型 ; 变异...

  • 用蚁群算法求解旅行商问题

    用蚁群算法求解旅行商问题_工学_高等教育_教育专区。吉林大学 机器学习... 用蚁群优化算法求解中国... 5页 免费 用蚁群优化算法求解中国... 5页 免费...

  • 基于蚁群算法解决旅行商问题

    基于蚁群算法解决旅行商问题_工学_高等教育_教育专区。蚁群算法,旅行商问题,... 用蚁群优化算法求解中国... 5页 免费 基于模式求解旅行商问题... 5页 免费...

  • 蚁群算法在求解旅行商问题中的改进

    与计算机学院,安徽 合肥 230036 )(2 巢湖学院计算机系,安徽 巢湖 238000 ) 摘 要:蚁群算法是一种启发式优化算法,在求解旅行商问题等多种组合优化问题上有着优 ...

  • 用MAX_MIN蚂蚁算法解决中国旅行商问题

    〔5〕燕忠, 袁春伟. 用蚁群优化算法求解中国旅行商问题〔J〕. 电路与系统学报,2004,9(3):122-126.〔6〕AndreaRoil.AntColonyOptimization.EDITORIAL〔J〕....

  • 基于MATLAB的蚁群算法求解旅行商问题

    20世纪90年代Dorigo M[ 1 ] 最早提出了蚁群优化算法—— 蚂蚁系统 (Ant system, AS) 并将其应用于解决计算机算法 , 学中经典的旅行商问题[ 2 ] 。 从蚂蚁...

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