神经网络及其在TSP问题中的应用6.17分解.doc

神经网络及其在TSP问题中的应用 摘要：TSP问题一直是组合优化中极富活力的研究课题之一。神经网络的发展为这一问题的解决提供了一种新的思路。1985年Hopfield和Tank两人用CHNN网络为解决TSP难题开辟了一条崭新的途径并获得了巨大成功。本文介绍了神经网络的基本知识，给出了TSP问题的描述及数学模型，介绍了神经网络应用于TSP问题的相关理论知识及Hopfield算法在求解TSP问题中的应用分析. 关键词：TSP问题；人工神经元网络；最优路径； Hopfield神经网络； The Application Of Neural Network In The Travelling Salesman Problem Wang Xin College of Aeronautical Engineering，Civil Aviation University of China 1401001 Abstract: The travelling salesman Problem (TSP) is always one of the most vigorous research topics in combined optimization . The development of neural network provided a new way to solve the problem. In 1985 Hopfield and Tank open up a new way for solving the TSP problem by using CHNN and gained great success. This paper will introduce the basic knowledge of neural networks, describe the travelling salesman Problem and its mathematical model. In this paper, the neural network application knowledge in TSP and the related theoretical knowledge is given . Moreover, the paper will talk about the application of Hopfield algorithm analysis in solving TSP problem. Keywords: TSP , artificial neural network ,optimal path ,Hopfield neural network; 自20世纪40年代出现以来，人工神经网络的发展虽不是一帆风顺但始终被人们寄予厚望。因为在智能的，模糊的，随机的信息处理方面，人工神经网络具有巨大优势。神经网络的应用已经渗透到模式识别、图像处理、非线性优化、专家系统等各个领域，并取得了令人瞩目的成果。旅行商的路径优化问题规则虽然简单，但在地点数目增多后求解却极为复杂。，如果要列举所有路径后再确定最佳行程，那么总路径数量之大，几乎难以计算出来。多年来全球数学家绞尽脑汁，试图找到一个高效 图1 神经细胞的结构 1.2生物神经元的信息处理机理 神经细胞利用电-化学过程交换信号。输入信号来自另一些神经细胞。这些神经细胞的轴突末梢（也就是终端）和本神经细胞的树突相遇形成突触，信号就从树突上的突触进入本细胞。信号在大脑中实际怎样传输是一个相当复杂的过程，但就我们而言，重要的是把它看成和现代的计算机一样，利用一系列的0和1来进行操作。就是说，大脑的神经细胞也只有两种状态：兴奋（fire）和不兴奋（即抑制）。发射信号的强度不变，变化的仅仅是频率。神经细胞利用一种我们还不知道的方法,把所有从树突突触上进来的信号进行相加，如果全部信号的总和超过某个阀值，就会激发神经细胞进入兴奋状态，这时就会有一个电信号通过轴突发送出去给其他神经细胞。如果信号总和没有达到阀值，神经细胞就不会兴奋起来。 1.3人脑的功能特点 由于脑神经细胞间数量巨大的连接，使得大脑具备难以置信的能力。尽管每一个神经细胞仅仅工作于大约100Hz的频率，但因各个神经细胞都以独立处理单元的形式并行工作着，使人类的大脑具有下面这些非常明显的特点：? ???能实现无监督的学习。??有关我们的大脑的难以置信的事实之一，就是它们能够自己进行学习，而不需要导师的监督教导。如果一个神经细胞在一段时间内受到高频率的刺激，则它和输入信号的神经细胞之间的连接强度就会按某种过程改变，使得该神经细胞下一次受到激励时更容易兴奋。? ??与此相反的是，如果一个神经细胞在一段时间内不受到激励，那么它的连接的有效