论文总字数：22845字

摘 要

受蚂蚁觅食行为的启发，蚁群算法应运而生，蚁群算法于1992年被Dorigo所提出，该算法是一种用来寻找优化路径的一种仿生算法，在解决组合优化问题上尤为突出。该算法具有易于跟其他方法相结合、分布式计算机系统等优点。在解决TSP问题上面，该算法显得尤为重要。但是，在解决TSP问题的过程中，该算法仍然存在着一些缺陷与不足，例如该算法很容易陷入局部最优解，从而不能得出全局最优解。针对蚁群算法所存在的不足，本文将对蚁群算法的不足进行改进，然后通过蚁群算法和改进后的蚁群算法解决相同的旅行商问题，最后将两种算法所得出的实验结果进行对照分析，以此来验证改进后的蚁群算法的相关性能。

同时为了更好地解决实际航行中的有关问题，考虑航行过程中障碍物等有关因素，论文提出了如下思路：通过运用栅格法来模拟海洋环境，然后使用改进蚁群算法在可通航的区域内进行路径的寻优，使得问题具有实际的讨论意义。同时为后续更高级别的研究，提供了基础研究的支持。

关键词：蚁群算法；试凑法；TSP；栅格法。

Abstract

The ant algorithm was inspired by the way ants look for food. The ant algorithm was proposed by Dorigo in 1992. This algorithm is a kind of bionic algorithm used to find the optimal path, especially in solving combinatorial optimization problems. Ant algorithm has the advantages of easy combination with other methods and distributed computer system .At the same time, it is especially important for solving combinatorial optimization problems,especially TSP problems.But ant algorithm still has some shortcomings when solving TSP problem. For example,premature stagnation and so on.Ant algorithm is easy to get the local optimal solution, so it cannot get the global optimal solution.As for the existing problems of ant colony algorithm, this paper will improve the shortcomings of ant colony algorithm and then solve the same TSP through the improved ant colony algorithm and the basic ant colony algorithm. Finally, the experimental results obtained by the two algorithms will be compared and analyzed, so as to verify the advantages and disadvantages of the improved ant colony algorithm.

At the same time in order to better solve the related problems in the actual sailing, obstacles and related factors in the process of considering navigation, the paper puts forward the following ideas: by using the grid method to simulate the Marine environment, and then use the improved ant colony algorithm in navigable area for path optimization, makes a practical discussion.At the same time, it provides the basic research support for the follow-up higher level research.

Key Words：ant colony algorithm；trail-and-error；traveling salesman problem；grids method..

目录

第1章 绪论 1

1.1蚁群算法研究的目的及意义 1

1.2研究现状 1

1.3研究主要内容和技术路线 2

1.3.1主要内容 2

1.3.2研究的主要内容技术路线 2

第2章 蚁群算法的实现与优化 4

2.1旅行商问题 4

2.2蚁群算法的相关概述 4

2.2.1蚁群算法的基本原理 4

2.2.2基本蚁群算法执行概况描述 5

2.2.3蚁群算法具体实现步骤 9

2.2.4蚁群算法的参数选择 9

2.2.5蚁群算法的优缺点 12

2.3改进蚁群算法的研究 13

2.3.1蚁群算法的改进策略 13

2.3.2改进蚁群算法的描述与实现 14

2.3.3改进蚁群算法的具体步骤 14

2.3.4改进蚁群算法的参数选择 15

2.4两种算法的结果对比 19

2.4.1对比意义 19

2.4.2结果对比与分析 19

第3章 改进蚁群算法在最优路径规划上的应用思路 21

3.1应用策略 21

3.2栅格法的简要概述与基本原理 21

3.2.1简要概述 21

3.2.2栅格法的基本原理 22

3.3实际意义与不足 23

3.3.1实际意义 23

3.3.2不足 23

第4章 总结和展望 24

4.1总结 24

4.2展望 24

参考文献 25

致 谢 27

第1章 绪论

1.1蚁群算法研究的目的及意义

随着人类对世界的认知不断地提高，人类对科学技术的要求也变得越来越高。与此同时，传统的计算方法已经不能很好的解决日益复杂的相关问题，特别是在各个领域内的有关超大规模、非线性、随机性的复杂问题^[1]。因此，人们更加的渴望追求一种更高效的智能计算和更好的优化技术^[2]。伴随着计算机的出现，人们十分希望使用计算机来设计出一种新的计算机程序，并创建以计算机程序形式来进行表示的新型代理。通过来模拟某些生物物种的典型的社会行为^[3]，构建出来了一些新颖的智能算法^[4]。在组合优化，分布式控制，机器学习等一些相关领域内，此类算法的应用潜力相当巨大，各种复杂问题可以基本来被解决。作为这些新颖的算法之一，蚁群算法^[5]是一种比较智能的仿生优化算法，它是一种通过模拟蚂蚁觅食的行为，然后对其进行改进的一种优化算法。与传统的数学原理^[6]不同的是，蚁群算法的开发是通过自然界中生物个体和生态系统的进化而形成的一种算法^[7]。蚁群算法因为其较强的优势而迅速成为人工智能领域的研究热点。蚁群算法具有诸如鲁棒性，出色的分布式计算机系统等一系列优点^[8]。与此同时，因为蚁群算法被越来越多的人所关注和了解，它的应用范围也在一直不断的扩大，因此蚁群算法涉及到了许多工程等相关领域^[9]。虽然到目前为止，蚁群算法取得了较为卓越的研究成果，但是还是有很多只能基于理论方面的成果，而且不能在实践中得以应用上^[10]。与此同时，在蚁群算法的应用上面，蚁群算法也不是很成熟，比如说在效率方面的局限性上，蚁群算法还有很多待提高和加以改进的地方^[11]。本论文主要是通过基于基础蚁群算法的基本原理，来比较改进蚁群算法在工程实践中的应用差异^[12]。其中，旅行商问题是其中一个较为典型的问题^[13]。正式这些仿生算法的出现，从而使得这些看起来比较复杂的问题变得简单很多。它为复杂和困难的系统的优化提供了一种强大的新的解决方案算法^[14]。

1.2研究现状

请支付后下载全文，论文总字数：22845字