计算智能大作业--蚁群算法解决TSP问题资料.docx

（计算智能大作业） 应用蚁群算法求解 TSP问题 1 目录 蚁群算法求解 TSP问题 ................................................ 3 摘 要： .............................................................................. 3 关键词： .............................................................................. 3 一 、引言 ............................................................................ 3 二、蚁群算法原理 ............................................................ 4 三、蚁群算法解决ＴＳＰ问题 ...................................... 7 四、解决ｎ个城市的 TSP问题的算法步骤 ................ 9 五、程序实现 ................................................................... 11 六、蚁群算法优缺点分析及展望 ............................ 18 七、总结 .................................................................... 18 2 采用蚁群算法解决 TSP问题 摘 要： 蚁群算法是通过蚂蚁觅食而发展出的一种新的启发 算法，该算法已经成功的解决了诸如 TSP问题。本文简要学 习探讨了蚂蚁算法和 TSP问题的基本内容， 尝试通过 matlab 仿真解决一个实例问题。 关键词： 蚁群算法； TSP问题； matlab 。 一 、引言 TSP （Travelling Salesman Problem ）又称货郎担或巡 回售货员问题。 TSP问题可以描述为：有 N 个城市，一售货 员从起始城市出发，访问所有的城市一次，最后回到起始城 市，求最短路径。 TSP 问题除了具有明显的实际意义外，有 许多问题都可以归结为 TSP问题。目前针对这一问题已有许 多解法，如穷举有哪些信誉好的足球投注网站法（ Exhaustive Search Method ） , 贪 心法 （Greedy Method） , 动态规划法 （Dynamic Programming Method） 分 支 界 定 法 （ Branch-And-Bound ）， 遗 传 算 法 （ Genetic Agorithm ）模拟退火法 (simulated annealing), 禁忌有哪些信誉好的足球投注网站。 本文介绍了一种求解 TSP问题的算法—蚁群算法， 并通过 matlab 仿真求解 50 个城市之间的最短距离，经过仿 真试验，证明是一种解决 TSP问题有效的方法。 3 20 世纪 90 年代， 意大利学者 M.Dorigo 等人在新型算法 研究的过程中，通过模拟自然界蚂蚁的觅食过程：即通过信 息素（ pheromone）的相互交流从而找到由蚁巢至食物的最 短路径，提出了一种基于信息正反馈原理的新型模拟进化算 法——蚁群算法（ Ant Colony algorithm ）。 蚁群算法是继遗传算法、人工神经网络等算法之后的又 一种启发式算法，它的基本原理借鉴了这样一个客观事实： 蚂蚁由自组织的合作能力所产生的群体智能来寻找路径，它 被认为是用于解决组合优化问题的又一种新方法。蚁群算法 是一种适应性好、鲁棒性强 , 具有正反馈结构的并行算法。 这些初步研究已显示出蚁群算法在求解复杂优化问题 (特别 是离散优化问题 ) 方面的一些优越性 , 证明它是一种很有发 展前景的方法。蚂蚁算法在各个领