用蚁群优化算法求解中国旅行商问题
维普资讯 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

2008 基于蚁群优化的中国旅行商问题的求解算法赵 ,郭遂峰 芳 ( 新乡学院 计算机与信息工程学院 ,河南 新乡 453003) 0 引言 蚁群算法 ( Ant Colo ny Algo rit...
基于蚁群优化的中国旅行... 暂无评价 2页 免费 一种求解旅行商问题的改......(3):434—444.2010 基于多粒度的旅行商问题描述及其蚁群优化算法冀俊忠 黄 振...
蚁群优化是一种元启发式的随机搜索技术,是目前解决组合优化问题最有效的工具之一.将信 息素更新和随机搜索机制的改进相结合,提出一种快速求解旅行商问题的蚁群算法...
本文采用蚁群算法,充分利用蚁群算法的智能性,求解 旅行商问题,并进行实例仿真。进行仿真计算的目标是,该算法能够获得旅行商 问题的优化结果,平均距离和最短距离。 ...
在大量通用数据集上的实验表明 ,该算法不仅能获得更好 的最优解 ,而且收敛速度有显著的提高 . 关键词 旅行商问题 ; 蚁群优化 ; 增量模型 ; 扩散模型 ; 变异...
用蚁群算法求解旅行商问题_工学_高等教育_教育专区。吉林大学 机器学习... 用蚁群优化算法求解中国... 5页 免费 用蚁群优化算法求解中国... 5页 免费...
基于蚁群算法解决旅行商问题_工学_高等教育_教育专区。蚁群算法,旅行商问题,... 用蚁群优化算法求解中国... 5页 免费 基于模式求解旅行商问题... 5页 免费...
与计算机学院,安徽 合肥 230036 )(2 巢湖学院计算机系,安徽 巢湖 238000 ) 摘 要:蚁群算法是一种启发式优化算法,在求解旅行商问题等多种组合优化问题上有着优 ...
〔5〕燕忠, 袁春伟. 用蚁群优化算法求解中国旅行商问题〔J〕. 电路与系统学报,2004,9(3):122-126.〔6〕AndreaRoil.AntColonyOptimization.EDITORIAL〔J〕....
20世纪90年代Dorigo M[ 1 ] 最早提出了蚁群优化算法—— 蚂蚁系统 (Ant system, AS) 并将其应用于解决计算机算法 , 学中经典的旅行商问题[ 2 ] 。 从蚂蚁...
热门文档