论文总字数：16963字

摘 要

本文通过将船舶调度问题即VRP问题，转化为TSP问题来研究蚂蚁算法和免疫算法在航运上的表现。 TSP问题是组合NP优化的经典问题，无法在多项式时间内解决。如果问题规模较小，则可以穷举的方法完全解决。然而，随着城市数量的增加，穷举的时间也会成倍增加。这时候我们必须借助计算机科学的力量。现如今有许多算法已经应用在了航海上，例如蚁群算法是一种启发式算法，适用于解决这种TSP-NP问题。免疫算法也是解决此类问题的一种常用方法。我们借用MATLAB程序我对两种算法进行实验，并通过两种人工智能算法的比较，来说明二种不同人工智能方法各自的特点，综合对比两种人工智能算法来得出他们在航运中的表现孰优孰劣，更进一步说明他们在航海中的运用。

关键词：蚁群算法，免疫算法，航线优化，TSP问题。

Abstract

This paper studies the performance of ant algorithm and immune algorithm in shipping by transforming ship scheduling problem, namely VRP problem, into TSP problem. TSP problem is a classical problem of combinatorial NP optimization, which can not be solved in polynomial time. If the problem is small, the exhaustive method can be solved completely. However, as the number of cities increases, the time of exhaustion will multiply. At this point we must use the power of computer science. A number of algorithms have been applied to navigation, such as ant colony algorithm, which is a heuristic algorithm to solve this TSP-NP problem. Immune algorithm is also a solution a common method of such problems. By comparing the two artificial intelligence algorithms, we illustrate the characteristics of the two different artificial intelligence methods. By comparing the two artificial intelligence algorithms, we compare the two artificial intelligence algorithms to get their performance in shipping.

Key Words：ant colony algorithm, immune algorithm, route optimization, TSP problem.

目录

第一章 绪论 6

1.1研究背景和意义 6

1.2研究的技术方案 7

第二章 免疫算法的基本介绍 7

2.1免疫算法生物学原理 7

2.2免疫算法的基本原理 8

2.3免疫算法的具体实现步骤 8

2.4免疫算法的应用及现状 10

第三章 蚁群算法的基本介绍 10

3.1蚁群算法的生物学原理 10

3.2蚂蚁算法的基本原理 10

3.3蚁群算法的具体实现步骤 11

3.4蚂蚁算法的现状及应用 12

第三章 数值实验过程 12

4.1 TSP问题的简述 12

4.2实验工具介绍 13

4.3免疫算法的实验过程 13

4.4蚂蚁算法的实验过程 14

第四章 数据对比和结论 15

5.1免疫算法的结果 15

5.2蚁群算法的结果 16

5.3两种算法的对比及结论 16

参考文献 19

致谢 21

第一章 绪论

1.1研究背景和意义

船舶调度的问题一直以来都是航运公司经营的重要问题之一，即VRP问题，如何有效的调度船舶，从而给船舶航行节约时间，争取获得最大的盈利空间？一直都是从事航运公司的人们追求的目标。VRP问题（常见于硕士及博士的论文）是可以通过扫描法将其转化为TSP问题的，在本毕业论文中，我们的讨论的是比较基础的TSP问题，TSP问题是组合NP优化的经典问题之一，无法在多项式时间内有效的解决。如果问题规模比较小，我们可以通过穷举的方法来完全解决。然而，随着城市数量的增加，穷举的时间也会成倍的增加。随着科技的发展，计算机算法已经融入到我们的各方各面，各行各业。我们经常能看到在生活中利用计算机算法来使我们的生活更加方便，例如各种智能的统计数据，机器人，人工智能等等，这些都是依靠计算机的算法来实现的。在航运中我们也利用了许多的计算机算法，无人驾驶是我们在航运中追求的目标之一，而船舶调度问题的解决就是打好这一基础的关键之一。我们要通过计算机的算法来实现路径的选择。蚁群算法就是这样一种启发式算法，适用于解决此类TSP-NP的问题。免疫算法也是解决此类问题的一种常用方法。这两种算法在航运中已经投入使用，本论文中我们将通过两种人工智能算法的比较，来进一步体现出二种不同的人工智能方法在航海中的应用及其各自的特点。

在1990年，蚁群算法是由意大利科学家Dorigo和Maniez首次提出的。在进行蚂蚁觅食的进程中，可以看出蚂蚁的个体行为是相对简单的。但是，当蚂蚁分组进行觅食的过程时，它们又可以表现得非常聪明。例如，一群蚂蚁可以在各种不同的条件下快速的找到通往食物来源的最短路径。这一神奇的现象是因为在蚁群中的蚂蚁有一种通过信息机制传输信息的方法。通过进一步的研究发现，蚂蚁会在寻找途中释放一种叫“信息素”的一种物质，蚁群中的蚂蚁们都可以感知“信息素”，并且本能地遵循高浓度的“信息素”的区域，这样往复下去，每一只蚂蚁在觅食的过程中都会沿途留下“信息素”，这就会导致在蚂蚁族群中形成了一种类似于正反馈的机制。经过一个较短时间之后，基本上大部分的蚂蚁都会通过“信息素”找到这条到达最近食物源的最短路径了。蚁群算法作为一种概率算法，用于求解最佳路径，通常用于解决查找最佳路径的问题之中。

在生命科学的方向，人们对遗传和免疫等自然现象已经进行了诸多的研究。从1960年代，Begley和Rosenberg等学者就分析了这些研究结果，听过对相关的内容和知识的借鉴，尤其是对于遗传学的定义等理论进行了重新的分析，然后在工程科学的方向进行了具体的应用，并将其成功地应用于技术中以取得良好的结果。在了解了效果之后，1980年代中期，Holan教授在美国总结了之前的所有研究结果，进一步总结和推广了以前徐哲提出的遗传算法的定义，并简要精确地解释了该算法的概念，对该算法进行了重新的说明，这是一种常见的遗传算法。遗传算法是具有迭代生成和识别过程的搜索算法。免疫算法是免疫概念及其理论在遗传算法中的应用。由于遗传算法的主要特征得以保留，因此可以有选择地、有针对性地选择特征信息和问题知识来停止优化过程的发展，同时可以通过这种算法进行对TSP问题的解决。

目前；蚁群算法已经逐渐成为一种比较成熟的人工智能方法，新的人工智能方法不断出现，人工智能方法较传统的方法有着巨大的优越性，这一方面，众多文献已做了大量的探索，但不同的实际问题，对诸如收敛快慢，精度等等指标的侧重有所不同，各个启发式算法在各个指标的表现也不尽相同，这样；分析各类方法在不同指标上的差异，不论对于本论文的较基础的TSP问题，还是对于用来处理更复杂问题的如改进免疫克隆算法，改进的相异多蚁群算法等等新型人工智能方法，都具有理论和实际的意义。

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