蚁群优化算法在TSP中的应用.pdfVIP

第 28卷 　第 11期 　　　　　　　武汉理工大学学报 ·信息与管理工程版 　　　　　　　　Vol. 28 No. 11 2006年 11月 　　　　　JOURNAL OF WU T ( IN FORMA T ION MANA GEM EN T EN G IN EER IN G) 　　　　　　Nov. 2006 文章编号 : 1007 - 144X (2006) 11 - 0024 - 03 蚁群优化算法在 TSP 中的应用 王 　 ,陶洪久 (武汉理工大学 信息工程学院 ,湖北 武汉 430070) 摘 　要 :提出了一种求解 TSP 问题的有效算法 ———蚁群优化算法 。该算法通过模拟蚁群有哪些信誉好的足球投注网站食物的过程 ,求 解 TSP 问题 。算法的主要特点是 ,正反馈 、分布式计算 、与某种启发式算法相结合 。并给出了算法原理及流 程 ;最后用计算机仿真得出结果 ,证明了该算法的有效性 。 关键词 : TSP; 蚁群算法 ; 信息素 中图法分类号 : TP301　　　　文献标识码 : A 题以及 TSP 问题 [ 3 ] 。 1　引　言 2　蚁群优化算法的原理 ( ) 蚁群算法 A n t Co lony Op tim ization , ACO 主 要用于求解不同的组合优化问题 ,一类应用于静 蚁群算法的基本原理是模拟真实蚁群觅食过 态组合优化问题 ,另一类用于动态组合优化问题 。 程寻求最短路径 ,是由意大利学者 DOR IGO M 等 静态问题指一次性给出问题的特征 ,在解决问题 人首先提出的[ 4 ] 。自然界中的蚂蚁 ,在寻找食物 过程中 , 问题的特征不再改变 。这类问题的典型 或遇到障碍物时 ,总能找到一条从食物到蚁巢或 范例就是经典旅行商 问题 ( Traveling Sale sm an 绕过障碍物的最优路径 。其原因在于 ,蚂蚁运动 Prob lem , TSP) [ 1 ] 。 中会在所经过 的路径上释放 出一种 叫信息素 TSP 即旅行商问题 ,指旅行商按一定的顺序 ( ) p heromone 的物质 ,后续蚂蚁可根据前面蚂蚁遗 访问 N 个城市的每一个城市 ,使得每个城市都能 留下来的信息素选择下一条要走的路径 。一条路 被访问且仅能被访问一次 ,最后回到起点 ,而使路 径上的信息素越高 ,说明这条路径被选中的次数 程最短 ,花费的代价最小 。 越多 ,即路径的性能更优 ,后续蚂蚁选择这条路径 TSP是一个典型的 N P难题 , 问题的求解随着 的概率就更大 , 由此构成一个学习信息的正反馈 ( ) 问题规模的扩大 城市数 目的增加 而变得越来 过程 ,从而逐渐逼近最优解 。蚁群算法的原理正 越复杂 ,所需的计算时间也越来越长 ,且倍数是剧 基于此 。 增的。一些传统的算法 ,如穷举有哪些信誉好的足球投注网站法 ,是无法解 蚁群算法吸收了如下蚂蚁群体行为的典型特 决这些难题的。于是出现了一些新的随机有哪些信誉好的足球投注网站算