蚁群算法及其在求解TSP问题中的应用
时间:2019-08-08 18:27 来源:毕业论文 作者:毕业论文 点击:次
| 摘 要：根据蚂蚁生态学提出的蚁群算法是一种新颖的用于求解复杂组合优化问题的模拟进化算法,具有典型的群体智能特征,表现出较强的学习能力和适应能力. 本文阐述了该算法的基本原理、算法模型和在TSP( Traveling Salesman Problem，旅行商)问题中的具体应用过程,并对算法进行了总结和展望. 38319 毕业论文关键词：蚁群算法；组合优化问题；旅行商问题 Ant Colony Algorithm and its Application in Solving the TSP Problem Abstract: According to the ecology of an ant colony algorithm is a novel simulated evolutionary algorithm for solving complex combinatorial optimization problems, has the typical characteristics of swarm intelligence, showed a strong ability to learn and adapt. This paper describes the basic principle, the algorithm of the model and algorithm in the TSP (Traveling Salesman Problem, the traveling salesman problem) in the specific application process, and the algorithm is summarized and prospected. Keywords：Ant colony algorithm；Combinatorial optimization problem；TSP 目 录 摘 要 1 Abstract 1 引 言 2 1. 预备知识 3 1. 1 遗传算法 3 1. 2 模拟退火算法 3 1. 3 蚁群算法 3 2. 蚁群算法的基本原理和模型 4 2. 1蚁群算法的基本原理 4 2. 2 蚁群算法的模型 5 3. 基于蚁群算法的TSP求解 6 3. 1 TSP问题的描述 7 3. 2 基于蚁群算法的TSP求解 7 3. 3蚁群算法在Matlab中的实现 8 4. 蚁群算法的改进 12 4. 1 优选参数m 13 4. 2 参数的调整 13 4. 3 信息素的更新 13 4. 4 信息素链表 L 和禁忌链表 TL 的构建 14 4. 5 改进的算法基本流程 14 5. 总结 14 参考文献 16 致 谢 17 蚁群算法及其在求解TSP问题中的应用 引 言 研究昆虫的一些学者在研究蚁群的群居性现象时发现蚁群之间的合作相对是比较简单的，但是他们很多时候却可以解决人们比较难解决的问题. 有种算法可以行驶群体的智能然后用于解决组合的优化相关题目，而蚁群算法正是这样的. 蚁群算法最先是由意大利学者V. Mzniezzo，M. Dorigo，A. Colorni等人20世纪90年代初提出的. 文献[1]-[6]介绍蚁群算法相对模拟退火算法、遗传算法等算法而言提出的比较晚，但同样是应用于组合优化问题. 该算法有全局优化、智能搜索等优点，容易与其它的算法结合，稳健性A也是该算法的特点之一，鲁棒性较强，具有正反馈的特点，能够进行分布式计算；正反馈原理能够加快该算法的进化速度；分布式计算让蚁群算法更容易同时实现，蚁群中蚂蚁之间的信息传递与交流让蚂蚁很快的找到最优解，不易陷入局部最优解. 文献[7]-[10]蚁群算法能与很多算法进行结合，通过结合可改善它的算法性能；该算法鲁棒性强，蚁群算法的基本模型可以应用于许多问题. 由于蚁群算法，所以许多复杂优化问题得到求解. 旅行商问题（TSP）指的是一个销售商从 n 个城市中的某一城市出发，走完其余 n﹣1 个城市而且都不重复并能够回到原来的出发点，找出所有可能的路径中最短的一条. TSP是一个特别的组合优化问题. 本文将会讲述基本原理和蚁群算法的模型，并基于求解TSP问题的蚁群算法在MATLAB是如何实现的，如何引进参数以及对参数的改进. (责任编辑：qin) |