基于离散神经网络的TSP问题研究

基于离散神经网络的TSP问题研究

摘要：

TSP问题一直是组合优化中极富活力的研究课题之一。七十年代中期，计算复杂性理论的出现和数学规划的发展大大推动了组合优化的前进。计算复杂性理论表 明，被称作NP完全问题的旅行推销员问题以及其它类似的组合优化问题在计算上是等价的。也就是说，不能用任何已知的多项式算法求解这种问题。从这个新发现 可以看出：最优化方法的能力是有限的，这使得研究人员不得不寻求更好的解决办法。 神经网络的发展为这一问题的解决提供了一种新的思路。Hopfield神经网络算法是解决这一问题的经典算法，这一算法最初具有的不足之处也得到了不断的 改进。

对于离散神经网络而言 ,通过引入网络状态图 ,可以很清楚地看到该网络的运行机理: 网络是否收敛 ,网络有多少个稳定吸引子 ,有多少个环吸引子 ,并能清楚地反映各类吸引子的吸引域.在这篇文章里 ,比较详细地讨论了网络状态图的一些基本性质 ,诸如网络的分支数等于网络稳定吸引子与环吸引子数目之和;对称离散神经网络、反对称离散神经网络在全并行运行条件下网络状态图的结构特征等.

一、神经网络理论与旅行商问题

神经网络可分为两类 ,一类是生物神经网络 ,另一类是人工神经网络 .生物神经网络是客观世界中的一种客观存在 ,是生物神经系统中神经细胞按照一定的连接方式连接而形成的网络.如人脑神经系统中神经细胞之间按照一定的方式连接而成的人脑神经系统是一种典型的 ,到目前为止所发现的最具有智慧的生物神经网络;人工神经网络并非客观存在 ,而是科学工作者利用电子技术 ,光学技术等模拟生物神经网络的某些结构 ,特征以及功能而人为地研究制造的网络.人工神经网络亦可分为离散与连续型两大类.离散型人工神经网络是目前神经网络中的一个主要的核心研究领域 .由于最近几年神经网络的飞速发展 ,难免在发展过程中对有些问题遗漏或者论证粗糙与不足.目前 ,离散神经网络的数学理论欠佳.基于此 ,将以系列文章对离散型神经网络的数学理论进行较为深入的研究 .该文属首篇 ,引入了一种新的研究工具—— 网络状态图 ,并详细地讨论了网络状态图的一些基本性质 ,特别是对称与反对称离散型神经网络.利用神经网络解决组合优化问题是神经网络应用的一个重要方面。

神经网络应用于组合优化问题是从Hopfield和Tank[2]用他们提出的Hopfield网络解决旅行商问题(TSP)开始的。由于神经网络具有内在的并行计算性和容错性，因此在这一领域得到广泛的应用。但是Hopfield网络存在不稳健性，网络的初始条件严重影响计算结果，甚至得不到最优或是可行解。这主要是由于Hopfield网络的核心依然是梯度下降法，它使得在计算能量函数时，神经元的变化总是导致网络能量的下降，最终网络能量可能陷入局部最小值或是不可行解。近年来，为了改善这一缺陷提出了许多方法。Feng等[3]提出了一种称

为稳定状态分析技术来设置Hopfield网络能量函数的约束条件和距离的权值，从而在求解TSP时，能得到比较好的结果。Cooper等[4]提出了一个高维神经网络(HONN)来映射TSE并且分析了得到可行解的稳定条件。Tan等[5]给出了稳定标准，这些标准可以保证Hopfield网络在求解TSP时，收敛到可行解，减少收敛到不可行解的次数。为了提高收敛速度，韦岗等[6]给出了使得Hopfield网络指数收敛的条件。

旅行商问题(TSP)是典型的组合优化问题，利用神经网络解决组合优化问题是神经网络应用的一个重要方面。Hopfield神经网络作为一种全连接的神经网络，曾经为神经网络的发展开辟了新的研究途径。它的独特结构特征和学习方法，使它能够较好的模拟生物神经网络的记忆功能，并获得令人满意结果。正是基于需解决问题的代表性以及手段方法的先进性，我们开展利用Hopfield网络解决经典组合优化问题的研究。

1.1 人工神经网络概念的提出

在宇宙中所有已知的信息处理系统中，人的大脑是最复杂的、最完美的和最高效的。人脑是人类高级精神活动如人类智能、思维处理和情绪等赖以生存的物质基础，也是生物进化过程中出现的最高产物，并且是当前人类发展过程中认识较少的领域之一。长期以来，人们不断在一系列学科的基础上对大脑的神经网络结构进行分析和研究，利用人类大脑神经网络的一些独特性质，研究和提出一系列智能系统来模拟人类大脑某些功能来进行各种信息处理以及相关问题的解决。这些研究包括神经学、生物学、认知学、心理学、电子学、数学和计算机科学等各个领域。

随着当今社会科学技术的发展，人类将各种复杂和繁琐的问题交由机器解决，自己来处理各种有创新性的活动，而如何快速的利用机器代替人类解决问题已经成为科技水平的重要标志。计算机就是采用电子元件来模拟人脑去完成某些复杂计算和判断的信息处理系统。目前世界上最先进的计算机处理系统的速度已经达到了非常高的水平，其每个电子元件的计算速度在纳秒（10s）级左右。与此相对应的是，人的大脑中的每个神经细胞的反映时间在毫秒（10s）级左右，尤其在进行某些高级处理过程，包括人类视觉识别、语言的理解和表达、记忆的回溯和重构以及直觉推理等，往往需要1s左右的时间即可以完成极其复杂的处理过程。因此，人们希望可以实现一种高级信号处理系统，它在计算能力超过人类大脑，同时又可以模拟人的识别、判断、联想和决策的能力。

人工神经网络（Artificial Neural Network，简称ANN）是当今迅速发展的一门高级科学，它是人工构造的能够实现计算功能的神经网络。人工神经网络的发展源于人们在对人脑的神经网络的不断认识和人类对大脑的理解，它以理论化的人脑神经网络为数学模型、以大脑复杂的神经网络结构为基础，建立了一种高效信息系统。在特征上，它是一个具有高速的非线性特征的复杂网络，由大量简单神经元相互连接而成。在功能上，它能够进行非线性关系实现、复杂的逻辑操作。

人工神经网络的发展基础是人的大脑，它在2个方面与人脑相似： [5][5][4]-3-9[3][2]

（1）和人脑的学习途径类似，外界环境是人工神经网络进行知识获取的唯一途径。

（2）和人脑的信息传递和存储类似，以突触权值，即互连神经元的连接强度来存储获取的信息。

1.2 人工神经网络的发展史

ANN作为一门前沿交叉学科，在国际上得到了迅速的发展。人工神经网络的模型的研究基础是现代神经科学研究，而现代神经科学研究的神经网络理论又是大规模并行计算以及巨量信息并行处理的基础。人工神经网络作为描述认知、决策及控制的智能行为的一种工具，它不仅是高度非线性动力学系统，同时又是自适应组织系统。

1943年，心理学家W.S.McCulloch和数理逻辑学家W.Pitts建立了神经网络和数学模型，成为MP模型。他们通过MP模型提出了神经元的形式化数学描述和网络结构方法，证明了单个神经元能执行逻辑功能，从而开创了人工神经网络研究的时代。1949年，心理学家提出了突触联系强度可变的设想。20世纪60年代，人工神经网络得到了进一步的发展，更完善的神经网络模型被提出，其中包括感知器和自适应线性元件等。M.Minsky等仔细分析了以感知器为代表的神经网络系统的功能和局限后，与1969年出版了《Perceptron》一书，指出感知器不能解决高阶谓词问题。他们的论点极大地影响了神经网络的研究，加之当时串行计算机和人工智能所取得的成就，掩盖了发展新型计算机和人工智能新途径的必要性和迫切性，使人工神经网络的研究处于低潮。在此期间，一些人工神经网络的研究者们仍然致力于这一研究，提出了适应谐振理论（ART网）、自组织映射、认知机网络，同时进行了神经网络数学理论的研究。以上研究为神经网络的研究和发展奠定了基础。1982年，美国加州工学院物理学家J.J.Hopfield提出了Hopfield神经网络模型，引入了“计算能量”概念，给出了网络稳定性判断。1984年，他又提出了连续时间Hopfield神经网络模型，为神经计算机的研究做了开拓性的工作，开创了神经网络用于联想记忆和优化计算的新途径，有力地推动了神经网络的研究。1985年，又有学者提出了玻尔兹曼模型，在学习中采用统计热力学模拟退火技术，保证整个系统趋于全局稳定点。1986年进行认知微观结构的研究，提出了并行分布处理的理论。人工神经网络的研究受到了各个发达国家的重视：美国国会通过决议将从1990年1月5日开始的十年定为“脑的十年”，国际研究组织号召它的成员国将“脑的十年”变为全球行为；在日本“真实世界计算（RWC）”项目中，人工智能的研究成了一个重要的组成部分。

1987年，在美国加州召开了第一届国际神经网络学术会议。此后，每年召开的国际联合神经网络大会，成为神经网络研究者的学术交流平台。另外，十几种国际著名的神经网络学术刊物相继问世，如：《IEEE Transaction on Neural Networks》、《IEEE Transaction on Circuit and Systems》、《Networks:Computation in Neural Systems》等，神经网络理论研究在国际学术领域获得了其应有的地位。

随着人工神经网络20世纪80年代在世界范围内的复苏，国内也逐渐掀起了研究热潮。[8][7][6]

1989年10月和11月分别在北京和广州召开了神级网络及其应用讨论会和第一届全国信号处理-神经网络学术会议：1990年2月由国内八个学会，及即中国电子学会、人工智能学会、自动化学会、通信学会、物理学会、生物物理学会和心理学会联合在北京召开“中国神经网络首届学术会议”。这次大会以“八学会联盟，谈智能奥秘”为主题，收到了300多篇学术论文，开创了中国人工神经网络及神经计算机方面科学研究的新纪元。2004年10月在合肥召开的“人工神经网络学术会议”已是第十四届学术年会。2004年8月在中国大连召开的ISSNN20034（Itenational Symposium on Neural Networks）国际会议，引起了国内外研究神经网路的学者的广泛关注，产生了较大的影响。另外，国内外许多的学术会议都设有人工神经网络专题，经过十几年的发展，中国学术界和工程界在人工神经网络的理论研究和应用方面取得了丰硕成果。 [9]

二、线性二次型控制器方法

线 性二 次 型 控 制 器 的 设 计 方法是 现 代控制 理 论 中最有 效 的 设 计 方法之 一,它 适 用于 线性 多变量 系统,在有关 的文 献 中 已 得到 充 分论 述 `]1 9 8 2 年,o Hp i f e l d提 出一种 反 馈 型 神经 网络离 散 型 o Hp i f e d l网络,并 给 该 网 络 引 人 了 能量 函 数 的概 念I ’ 3.1 9 8 4年,o Hp i f e d l又 相继 提 出 模 拟o Hp i f e d l网 络,并 成功地 用 于 解决 旅行 商 问 题l ` 」.19 9 7年,阮晓 钢提 出一 种 应 用 离 散 型H o p i f e l d 网 络 解 决动 态 最 优控 制的方 法 [ ’].作 者致 力 于 求 解线 性 二次 型 最 优控制 问 题 的另 一种 新 方 法.

三、离散神经网络

离散 Hopfield网络应属于整个离散型神经网络的最基本的模型.p阶离散 Hopfield网络共有 2p个状态 ,因而 ,以图论为工具来研究离散 Hopfield网

络是一件很自然的思想 .基于此 ,文中提出了网络状态图的概念 ,并讨论了与其有关基本性质.可以看到网络状态图作为研究散射 Hopfield网络的一个工具具有直观、清晰、简捷等优点 .离散Hopfield 网络是单层全互连的，其表现形式有两种：