摘 要

本文借助java语言，使用基于蚁群算法的思想，编程实现了对TSP问题（旅行商问题）的解决，实现使用蚁群算法寻找最优路径结果，并完成针对该问题所设计的演示程序的设计。所得结果对于蚁群算法在路径寻优方向的研究与发展具有重要的指导意义。

论文主要研究了蚁群算法的产生过程，算法的思想，算法的具体实现步骤，TSP问题的一般处理方法。具体实现了基于蚁群算法对TSP问题的处理，对蚁群算法在TSP问题上的应用做了基本分析和比较，得出使用蚁群算法来处理TSP问题时存在的优点和不足，提供了一些对算法和程序部分的改进方案。

研究结果表明：蚁群算法在解决TSP类问题时有较强的适应能力，但是花费时间较长，准确性需要用大量时间做保障。其次在算法解决问题的过程中，需要考虑到的影响因素较多，某些因素可能严重影响结果准确性。

本文的特色：深入探讨了蚁群算法在解决TSP问题方面的优缺点，提出了影响蚁群算法处理TSP问题过程中的一些影响因素并进行了详细分析，同时也分析了这种算法在解决TSP问题时能够有那些提升。

关键词：蚁群算法；TSP问题；路径寻优

Abstract

With the help of the Java language, based on the idea of ant colony algorithm, and the programming of the solution of the TSP (traveling salesman problem), implemented using ant colony algorithm to find the optimal path results, and the completion of the demonstration program designed for the problems of design. The results have important guiding significance for the research and development of ant colony algorithm in the direction of path optimization.

This paper mainly studies the generation process of the ant colony algorithm, the idea of the algorithm, the specific implementation steps of the algorithm, the general processing method of the TSP problem. The realization of the solution of TSP problem based on ant colony algorithm, the application of ant colony algorithm in the traveling salesman problem (TSP) do basic analysis and comparison, obtained the advantages and disadvantages of the use of ant colony algorithm to solve TSP problem existing, provides some of the algorithm and the program part of the improved scheme.

The results show that the ant colony algorithm has strong adaptability to solve the TSP problem, but it takes a long time, and the accuracy needs a lot of time. In addition, in the process of solving the problem, there are many factors that need to be considered, and some factors may seriously affect the accuracy of the results.

In-depth study of the advantages and disadvantages of ant colony algorithm in solving the traveling salesman problem (TSP), proposed and carried out a detailed analysis of some factors influence of ant colony algorithm in solving TSP problem in the process, and analyzes the algorithm in solving traveling salesman problem (TSP) to those who are ascending.

Key Words：ant colony algorithm; TSP problem; path optimization;

目 录

第1章 绪论 1

1.1 课题研究的背景 1

1.2 目的和意义 1

1.3 国内外研究现状及发展 1

1.4 课题研究内容 2

1.5 预期目标 2

第2章 原理技术介绍 3

2.1 JAVA语言基本介绍 3

2.2 TSP问题 3

2.3 智能算法介绍 4

2.4 蚁群算法的优缺点 5

第3章 程序实现 6

3.1蚁群算法的路径寻优实现 6

3.1.1 算法流程 6

3.1.2 算法具体实现 7

3.1.3 ant类 8

3.1.4 aco类 9

3.2 搭建可视化界面 11

3.2.1 界面搭建流程 11

3.2.2 简单界面扩展 12

3.2.3 主体面板设计 12

3.2.4 主体面板设计流程 12

3.2.5 主体面板功能实现 13

第4章 完善、分析及改进 15

4.1 程序完善 15

4.2 程序设计中的问题分析 16

4.3 改进和拓展 22

第5章 总结 24

致 谢 31

第1章 绪论

课题研究的背景

蚁群算法于1991年由意大利学者Dorigo M等人提出，该算法通过模拟蚂蚁觅食行为，得出的一种模拟优化算法。算法被提出后，又进行系统的研究，主要包括对算法原理的进一步发展以及数学模型的研究，并结合其他智能算法，对TSP问题尝试进行解决，并取得了一定的成功。这些研究，对蚁群算法的发展起到了关键的推动作用，引起了许多学者的关注和研究。^[1]

蚁群算法是一种仿生进化系统，同时他也是基于种群的。最早被应用于解决TSP问题，取得了较大成功，算法的特点在于简单，稳定，且通过正反馈并行运算方法。^[2]。

目的和意义

在本次设计中，目的旨在使用java编程，完成蚁群算法在路径寻优方面的实际应用，这里我采用TSP问题作为背景，设计完成基于java解决TSP问题中的路径寻优算法及演示程序。具体内容是，在N个随机分布的点中，每个点经过一次，完成所有点的遍历，且得到的路径长度最短，每两个点之间的距离以直线距离为准。

设计意义在于能过通过使用蚁群算法对TSP问题的处理，来估计蚁群算法在TSP路径寻优中的实用性，同时和其他各种算法进行简单对比，得出蚁群算法在解决TSP类问题时的优点和存在的问题。同时，本次设计是对实际问题的处理，加强了理论知识的运用，提高了知识的实用性。

国内外研究现状及发展

蚁群算法在一些经典的问题中取得了比较好的反响，例如TSP问题和QAP等NP难的组合优化问题。^[17]而现在蚁群算法已经被使用到了很多全新的实际工程领域中：

(1)被应用在许多工程和工业生产中。使用蚁群算法来解决大规模集成电路的综合布线问题。在布线过程中，各个引脚对蚂蚁的引力可根据引力函数来计算。每个线网都可以根据启发策略，像蚂蚁搜索的方式一样在开关盒的网格上爬行，并在经过的位置布上金属线，在遍历完整个线网的所有引脚之后，线网就布置完毕。^[3]

(2)蚁群算法也被使用在一些实际规划问题中。其中之一的一用便是可以应用在机器人路径规划中^[6]。机器人不具备人类的智慧，最为一种智能体，在较为复杂的环境中解决问题或者在和其他机器人之间进行协作解决路径规划时，很大程度上类似于蚂蚁觅食中的路径寻优特点以及蚂蚁群体中个体之间通过信息素形成协作。路径规划算法是实现机器人控制和导航的基础之一，试验证明使用蚁群算法解决该问题有很大的优越性。^[3]

其次，ACO在动态优化组合问题中也有应用，具体是在有向连接的网络路由和无连接网络系统路由中的应用。其他应用还包括蚂蚁人工神经网络、车辆路线问题（Vehicle Routine Prob-lem,VRP）、在图像处理和模式识别领域的应用等等。^[3]

随着蚁群算法在各种实际应用中的深入和复杂性的增大，数据的量也逐渐增大，导致蚁群算法处理的复杂程度变大，而这些问题的影响愈演愈烈，往往单纯使用一两种智能算法完全无法解决问题。^[16]然而蚁群算法可以很好的和其他算法进行结合，例如蚁群算法易与其他进化算法或者局部搜索算法结合。故结合蚁群算法或者结合多种智能算法将成为主流之路，也将成为研究的热点。目前，蚁群算法的研究大多集中在算法、模型的更新，以及软件的开发上，所处理的数据也都是静态的。当今时代，硬件的运行速度和空间已经足以提供较好的环境，可以牺牲空间换取时间。故如何利用现在硬件高速发展的又是，便成为了蚁群算法今后继续发展的一个方向。 ^[4]

课题研究内容

本次课题主要研究蚁群算法的工作过程，TSP问题的历史解决，并结合蚁群算法对TSP问题进行解决。其次研究如何设计一个完整的程序，其功能不仅能完成算法程序的设计，同时要完成对算法实现过程的显示，直观的显示蚁群的搜索过程，以便评估算法在处理TSP问题上的优缺点，并对算法及演示程序做出相应的改进措施。

这个演示程序，主要包含两大部分组成：蚁群算法的具体实现，演示界面设计。结合两大部分即完成整个演示程序的设计。

1.5 预期目标

本次设计所设定的基础目标为：完成蚁群算法的设计实现，理解TSP问题的具体内容和基本解决方法，完成对图形界面编程的设计以及设计完成可运行的演示程序。

具体来说，是以java语言基础，设计一套蚁群算法用来解决TSP问题，找到最优路径，并对该算法处理TSP问题的效率、性能、准确度等方面进行简要分析，对处理结果进行对比分析，得出算法在处理该问题下的优劣性。对影响蚁群算法的准确性的主要因素进行分析，得出何种因素占有主导地位，并提出对算法影响因素的解决方案。

第2章 原理技术介绍

2.1 JAVA语言基本介绍

本部分将简单介绍java技术的各种特点。

Java语言最主要的特点是完全的面向对象，同时它具有很强的跨凭他特性，非常适合于分布式情况下的计算环境。下面我们来看看他的具体特性有哪些：

　　（1）面向对象：面向对象就是现实世界中的各种模型的映射。在现实世界中，任何事物都是对象，对象之间的相互作用，是通过传递消息来实现的。同样的，任何事物即对象都可以拥有统一的归类，都可以找到反映他的实例。将传统的编程语言是一种过程的算法作为核心，面向对象的编程方法则是一对象为中心。^[5] 面向对象的特点可以采用下面的公式来反映：程序=消息 对象。而过程类的语言则可以表示为：程序=数据 算法。

　　(2)平台无关性：Java语言可以在各种平台上进行使用，具有较强的平台无关性即移植性。使用Java写出来的用用程序很多都可以直接在各种平台上运行。同时，平台无关性大致可以分为两种：其一是源代码级的平台无关性，代表语言是c和c ，其二是目标代码级，其代表语言是Java。^[15]

(3)分布式：分布式具体来说可以分为两种，第一种是数据分布，这种类型下，可以将待处理的数据分散到不同的网络主机中进行处理，第二种则是操作式分布，这种分布式方法，则是把数据分散在相同主机上进行处理。对于Java语言来说，它有一套较为完整的网络类库，在开发人员进行软件开发的过程中，可以利用这套类库来进行各种软硬件的设计，为Java的设计提供了很大便利。^[5]

　　(4)可靠性和安全性：Java语言最初被发现并逐渐成熟的原因是为了开发一些电子类的消费产品，然而电子产品所需要的可靠性性能很高。众所周知，Java语言是经过C 语言的改进发展而来，它在某些方面性能不入C ，但是他解决了在C 中的一些不稳定因素，阻止程序员访问内存，对内存进行实际操作，大大提高了编程的可靠性，一定程度上保证了程序的正确性。其次，Java市一中强调类型的语言，在编程过程中，编译器要求编程人员对方法进行显式的生命，这可以保证在程序运行前，编译器能发现方法的调用错误，提高正确性；再者Java删除了C 中的全部指针用法，使程序员完全不用解除内存部分就可以完成编程，阻止了对内存的非法访问，大大提高安全性；最后，Java内部解释器对程序会执行实时检查，在编译中可以找到非法字符或者数组越界等问题，同时Java提供了很多异常处理方法，在编程中，我们可以把一些错误的程序放在某处，简化了程序的任务，同时也便于对错误代码的修正。^[5]

2.2 TSP问题

说到TSP问题，它的全称是Travelling Salesman Problem，中文译为旅行商问题，这个问题是数学领域中一个很著名的问题。^[8]现在有一个商人需要推销货物，他有n个城市可选，每个城市必须且仅能经过一次，最后需要返回到初始的城市，则选择出一条最佳的路径，这便是旅行商旅问题。^[7]最终需要得到的目标结果是要求在经历所有目标后的路径为最小路径。^[8]