《毕业论文（设计）蚁群算法求解旅行家问题（tsp）的设计与实现》由会员分享，可在线阅读，更多相关《毕业论文（设计）蚁群算法求解旅行家问题（tsp）的设计与实现（51页珍藏版）》请在金锄头文库上搜索。
1、山东大学本科毕业论文目录摘要1ABSTRACT2第1章 绪论31.1 课题背景及意义31.2 论文的主要工作31.3 论文的组织结构4第2章 求解TSP的蚁群算法52.1蚂蚁觅食行为原理52.2蚁群算法原理52.3解决TSP问题的蚁群算法52.3.1 蚁群优化算法52.3 .2最大最小蚁群算法9本章小结9第3章 算法的实现103.1编程语言及工具103.2数据结构103.3算法的详细设计103.4算法实现113.4.1 类的实现113.4.2初始化实现123.4.3蚂蚁的移动133.4.4 选择下一个城市实现143.4.5 更新信息素实现163.4.6求最短距离实现17本章小结20第4章 实验
2、结果与分析214.1 实验数据214.2实验结果与分析224.2.1算法的效率分析224.2.2 算法的健壮性24本章小结25第5章 总结与展望26致谢27参考文献：28附录一：论文原文30附录二：论文译文382蚁群算法求解旅行家问题（TSP）的设计与实现摘要 旅行商问题（TSP）的内容为已知有n个城市，现有一个旅行家想要从其中一个城市出发，遍历其他所有的城市，然后再回到出发点，求旅行家需要经过的最短距离。其中遍历过程中每个城市只经过一次。 蚁群算法是一种求解复杂组合优化问题的启发式算法,该方法通过模拟蚁群进行搜索食物的过程，达到求解最优结果的目的。除却最为经典的蚁群算法外，还有很多蚁群算法的
3、优化算法，这里我选择其中效率最高的一种算法最大最小蚂蚁系统同经典的蚁群算法做比较，验证两者的实际效率。对于信息素的更新，目前有三种模型，我采用了其中效率最高的蚁周模型，另外两种分别是蚁密模型和蚁量模型。 旅行家问题是一个经典的NP难问题，现在并没有一种方法能准确地给出旅行家问题的最优解，最常用的方法还是用一些仿生算法，如遗传算法，粒子群算法等来得到一个较优解，而蚁群算法求得的较优解更逼近最优解。 旅行家问题可以应用于现实生活中的很多问题，如一个邮递员要从邮局出发，到N个邮箱投递信件，最会再回到邮局，怎样走的路程最近，还有快递公司送快递，以及飞机调整航程等。蚁群算法能很好地求解旅行家问题。这样，
4、就能节省更多的人力物力，取得更好的经济效益。 关键字：TSP；蚁群算法；NP难 ABSTRACT The content of Traveling salesman problem (TSP) is:There has N city,then a traveling salesman want arrive all of the city from one of them,each city can only arrive one time .And in the end,he must arrive the city he first arrive.The question is that
5、how can he get the shortest path. The ant colony algorithm is a heuristic algorithm for solving complex combination optimization problems.By simulating the process of ant colony searching for food, the method can reach the goal of solving the optimal result. Except the classic ant colony algorithm,
6、I choose one of the most efficient algorithm - max min ant system compared with the classic ant colony algorithm to verify the actual efficiency of the two.For the trial update, there are three models, I used the highest efficiency of the ant week model, the other two are the ant density model and t
7、he ant quantity model. The traveler problem is a typical NP hard problem,now there have not an optimal method can give the exact solution of the traveler,the most common way is to use some bionic algorithm, such as genetic algorithm, particle swarm algorithm to get a better solution,and ant colony a
8、lgorithm to obtain the optimal solution is more approximate optimal solution. Traveler can be applied to many problems in real life, such as a postman to starting from the post office, the n a mailbox to deliver letters, most will go back to the post office, to go away recently,and courier companies
9、 to send courier, as well as aircraft to adjust the range and so on.The ant colony algorithm can well solve the issue. In this way, we can save more human and material resources, and achieve better economic benefits.Keyword：TSP ；Ant colony algorithm ；NP hard第1章 绪论1.1 课题背景及意义 TSP（Traveling salesman p
10、roblem），即旅行商问题。旅行商问题的内容为：现在已知有N个城市，城市的位置已知。现在有一个旅行商，他想从其中一个城市出发，然后经过其余N-1个城市，且每个城市只经过一次，最后再回到出发的城市。这个商人出于各种原因的考虑，想要找到一条线路，当他沿着这条线路依次访问这N个城市时，他所经过的路程是最短的。问怎样找出这样一条最短路径。 了解了旅行商问题之后，我们现在要用数学描述来表示旅行商问题。 首先，城市的位置可以用二维坐标系中的点来表示，一个点对应一个坐标。一条线路即一串数字，每串数字对应有一个距离，即旅行商遍历N个城市所要走的距离，问题就是找到所需要走的距离最短的那一条路径。TSP是现实中
11、很多最短路径问题的数学模型。TSP属于NP完全问题的一种。NP完全问题就是随着问题中模型个数的增加，没有一个公式可以准确的得到最优结果。现在，NP完全问题一般都是用智能算法来求解，从而得到较优解。比如蚁群算法，粒子群算法，遗传算法等。本文主要讨论蚁群算法。蚁群算法，是由意大利学者M.多瑞格在20世纪90年代提出的一种模拟蚂蚁群体觅食行为的优化算法。该算法思路新颖，具有鲁棒性并行性等优点，已得到人们的广泛关注和应用，并在应用中表现出优异的性能和广阔的应用前景，成为人工智能和最优化领域中的研究热点和前沿性课题之一。目前，除却基本的蚁群算法外，还有很多蚁群算法的优化算法。在这些优化算法中，效果最好的
12、是最大最小蚁群算法。本文中，主要谈论基础的蚁群算法，另外，还介绍了一些最大最小蚁群算法的知识。1.2 论文的主要工作 本论文研究的内容是用蚁群算法求解TSP(旅行商问题）的设计与实现。 首先介绍了TSP问题及蚁群算法的研究现状，包括其应用与发展前景。然后分别简单介绍了TSP问题与蚁群算法的具体内容。其中主要介绍的蚁群算法。包括蚁群算法的由来，以及蚁群觅食行为对算法的启示以及蚁群算法的原理。随后，设计如何实现蚁群算法，针对蚁群算法的设计，进行了详细的介绍。 之后，采用JAVA语言具体实现了蚁群算法对TSP问题的求解。在这一部分，先整体介绍了蚁群算法如何求解TSP问题，并用伪代码给出了其中一部分方
13、法的实现，随后详细分析了蚁群算法的核心代码。实现了用蚁群算法求解TSP问题之后，对算法进行了测试，并根据测试结果对算法进行了改进。1.3 论文的组织结构 本论文共分六个篇章，分别是绪论、TSP问题简介、蚁群算法简介、算法的实现、算法的测试和总结与展望。 第1章节主要描述了TSP问题的由来以及国内外 相关的研究现状，以及蚁群算法的种类，主要解决的问题以及研究现状。总结和概括论文的研究意义以及主要作用。阐述了论文的主 要工作，并进一步介绍本文的组织结构，简述本文的框架架构。 第2章着重介绍了TSP问题以及蚁群算法的内容，其中主要介绍了蚁群算法的原理与实现。 第3章描述了算法的实现过程。本章节将首先
14、介绍实现算法、编写程序所 使用的编程语言 JAVA 以及编程工具 Eclipse,简述 Java 的特点，以及 Eclipse 的 使用；然后根据算法的理论流程，编写算法实现的伪代码，并对算法色时间复 杂度进行分析，接着进行介绍实现程序的数据结构，通过比较数组和链表的优 缺点，进行适当数据结构的选择，并分析程序中用到的数组和链表结构。最后， 本文对寻找最大包算法的实现代码进行分析，给出程序实现的核心代码，从包 的判断、元素的替换、终止条件的判断等方面进行核心代码解析。 第4章是对实现程序的测试过程。通过设计不同的测试数据，进行相关测试目标的测试，以获得测试结果，通过对测试结果的分析，对程序进行
15、修改和 改进，以得到更准确的结果，从而是程序尽可能正确。 第5章是对论文的研究进行了工作总结和归纳整理，对寻找集族最大包的近 似算法的研究进行总结，整理研究过程中发现的问题；最后，对该算法的研究进 行了未来展望，以求在未来的研究中有进一步的改进。第2章 求解TSP的蚁群算法 2.1蚂蚁觅食行为原理 蚁群算法是模拟蚁群觅食行为的仿生算法。那么，蚂蚁是怎样通过群体的合作找到从蚁群到食物源之间的最短路径呢？原因在于：蚂蚁在运动时，会分泌并在经过的路径上留下一种被称为信息素的化学物质。所有的蚂蚁都能感知信息素的存在并朝着信息素浓度高的地方移动。 例如，现在在距离蚁巢一段距离的一点发现一处食物。在没有阻隔的情况下，蚂蚁会沿直线从蚁巢出发到达食物源。但是，当在蚁巢和食物源之间存在一个障碍时，蚂蚁就要想办法绕过障碍，从而到达食物源。现在有两条道路能够绕过障碍，一条路径较短，设为A道路。一条路径较长，设为B道路。刚开始，两条道路之中都没有信息素。蚂蚁随机选择一条路径通过。这时会有几乎同等数量的蚂蚁选择两条道路。在蚂蚁找到食物后，蚂蚁会沿原路返回蚁巢，这时，蚂蚁同样会撒下信息素。因为A路径较短，在A路径上的蚂蚁往返一圈的用时就更少，那么，同等时间内，通过A路径的蚂蚁就更多，所以A路径上的信息素浓度就会更高。当再有蚂蚁到
