摘要旅行商问题（TSP）是一类著名的组合优化问题，要求找到一条最短路径，该路径能够遍历所有城市并且每个城市只能经过一次，最后回到出发点。目前TSP问题的求解方法不仅种类繁多，而且模型迥异，其中较为有效的智能算法有：遗传算法、蚁群算法、人工免疫算法、Hopfield神经网络算法、混合优化算法等。本文主要讨论的是Hopfield神经网络算法在TSP问题中的应用，同时对其他智能算法的优缺点进行简单的比较和陈述。65258

毕业论文关键词  TSP问题   Hopfield神经网络  智能算法

毕业设计说明书（论文）外文摘要

Title   The solution of TSP in artificial neural network  

Abstract

Traveling salesman problem (TSP)is a famous combinatorial optimization problem. It need to find a shortest route which can travel all the cities and travel each city once and come back to the starting city. At present,the solving methods of TSP are not only abundant in variety but also in different models. The effective intelligent methods are genetic algorithm,,ant colony algorithm ,the artificial immune algorithm ,Hopfield neural network algorithm , the hybrid optimization algorithm and so on .In this article ,we mainly talk about the application of Hopfield neural network in the TSP problem .In the same time ,we will state and compare the other intelligent algorithms.

Keywords  TSP problem   Hopfield neural network  intelligent  algorithm

目   次

1绪论1

1.1 问题的提出 1

1.2 TSP的应用和价值 1

1.3 TSP问题的研究现状 2

1.4本文的主要安排 3

2 介绍TSP问题及其作为NPC的求解难点4

2.1计算复杂性  4

2.2  TSP问题的描述及其数学模型 5

2.3 TSP问题的分类  6

3对几种求解TSP问题的智能算法的介绍和比较7

3.1遗传算法 7

3.2蚁群算法 8

3.3人工免疫算法算法 11

3.4混合优化算法13

4 Hopfield神经网络算法应用于TSP问题13

4.1Hopfield神经网络13

4.2利用Hopfield神经网络求解TSP问题 17

总结 24

致谢 25

参考文献26

1 绪论

1.1问题的提出

设有n个城市，一个旅行推销员从某城市出发，要经过其余n-1个城市，他怎样选择最短的路线？这就是著名的旅行商（TSP）或货郎担问题。最早是欧拉在1759年研究骑士周游问题时提出的，即对于国际象棋棋盘的64个方格，要经过每个方格一次且仅一次并且最终返回到原点。后来经RAND公司1948年引入，这使得TSP问题成为一个知名并且流行的问题。

TSP问题在图论中是很有代表性的组合优化问题。1936年图灵指出，有一类问题可难到任何算法都无力解决。例如，无法找到一个计算程序，能在任意一种输入下，判定该程序是否会停止，这就是著名的停机理论。而TSP问题被证明具有NPC计算的复杂性。因此，任何能够使该问题求解得以简化的方法，都将受到高度的评价和关注。

1.2 TSP的应用和价值

旅行商问题是组合优化中的典型问题，涉及到求解多个变量的函数的最小值。它在现实生活中应用十分广泛，例如，可以用它来模拟日常生活中的旅行问题，在给定旅游城市参数的条件下，如何使得所花费的时间（金钱）达到最小，从而设计出一条适合自己的旅行路线。论文网