文章编号:1007-757X (2006)11-0001-03利用Hopfield 神经网络求解旅行商问题研究杨秀梅,a 陈洪亮,a 董得义a摘 要:本文主要研究利用连续的Hopfield 网络求解TSP 问题,从连续的Hopfield 神经网络原理出发,结合TSP 问题的要求,在给定参数要求下求得问题的最优解。
并分析了实际算法的弱点,给出分析改进算法,加快了算法的收敛速度,改善有效解并提高最优解的比例。
关键词:连续的Hopfield 网络;旅行商问题;改进算法;优化中图分类号:TP 301 文献标识码:A1 概述用神经网络解决组合优化问题是神经网络应用的一个重要方面。
所谓组合优化问题,就是在给定约束条件下,使目标函数极小(或极大)的变量组合问题。
将Hopfield 网络应用于求解组合优化问题,把目标函数转化为网络的能量函数,把问题的变量对应到网络的状态。
这样,当网络的能量函数收敛于极小值时,问题的最优解也随之求出。
由于神经网络是并行计算的,其计算量不随维数的增加而发生指数性“爆炸”,因而对于优化问题的高速计算特别有效。
本文针对将Hopfield 理论应用于实践给出了研究性方法。
2 问题的提出TSP 问题,即所谓的旅行商问题。
问题的提法:在N 个城市中各经历一次后回到出发点,使所经过的路程最短。
其不同选择方案有(N -1)!/2种,在城市数较少的情况下可以用枚举等方法,但如果城市数量较大,例如,N=33时,使用枚举法求解就要考虑的情况是1025数量级,计算量如此之大是不可想象的。
将Hopfield 网络应用于求解TSP 问题,效果是显著的。
下面就利用连续的Hopfield 网络求解T SP 问题进行探讨。
3 Hopfield 神经网络及求解TSP 问题算法1)Hopfield 神经网络主要是模拟生物神经网络的记忆机理,是一种全连接型的神经网络,对于每个神经元来说,自己输出的信号通过其他神经元又反馈到自身,所以Hopfield 神经网络是一种反馈型神经网络。
Hopfield神经网络在TSP问题中的应用的开题报告1.研究背景旅行商问题(TSP)是运筹学中的经典问题，它是要找到一条经过所有城市(节点)的路径，使得路径经过的距离最短。
由于该问题是NP难问题，因此解决TSP问题一直是一个热门研究领域。
Hopfield神经网络作为一种反向传播神经网络模型，已经在很多问题中得到了应用，包括TSP问题。
Hopfield神经网络可以使用能量函数描述问题，利用机器学习技术学习问题的解，自适应地调整神经元之间的连接权值，从而达到解决TSP问题的目的。
2.研究意义研究Hopfield神经网络在TSP问题中的应用，可以为人们提供一种新的解决TSP 问题的方法。
Hopfield神经网络的优点是可以处理非线性问题，因此在解决TSP问题这种复杂的非线性问题时非常有效。
通过研究Hopfield神经网络在TSP问题中的应用，可以提高解决TSP问题的效率和精度，为一些实际问题提供有效的解决方案。
同时，这种研究也会推动神经网络领域的发展。
3.研究目标本研究的目标是探讨Hopfield神经网络在TSP问题中的应用，并提出一种有效的Hopfield神经网络解决TSP问题的方法。
具体目标如下：(1)研究Hopfield神经网络原理，并深入了解其在TSP问题中的特点和应用。
(2)分析TSP问题的性质和解决方法，并与Hopfield神经网络相结合，提出一种有效的解决方案。
(3)设计和实现算法，并对算法进行测试和优化。
(4)使用实验数据对算法进行验证和评估，分析算法的优缺点和适用范围。
4.研究方法本研究将采用以下几种方法：(1)文献调研法：通过查阅相关文献，研究Hopfield神经网络在TSP问题中的应用，并了解近年来该领域的研究进展。
(2)模型建立法：根据TSP问题的相关性质，结合Hopfield神经网络的原理，提出一种新的解决方案。
(3)实验方法：通过编写代码实现算法，并使用TSP问题数据进行测试和验证，对算法效率和精度进行评估，并进行优化。
TSP的几种求解方法及其优缺点一、什么是TSP问题旅行商问题，简称TSP，即给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。
其图论描述为：给定图G=（V，A），其中V为顶点集，A 为各顶点相互连接组成的边集，设D=（dij）是由顶点i和顶点j之间的距离所组成的距离矩阵，要求确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短距离。
旅行商问题可分为如下两类：1）对称旅行商问题（dij=dji，Πi，j=1，2，3，⋯，n）；2）非对称旅行商问题（dij≠dji，ϖi，j=1，2，3，⋯，n）。
非对称旅行商问题较难求解，我们一般是探讨对称旅行商问题的求解。
若对于城市V={v1，v2，v3，⋯，v n}的一个访问顺序为T={t1，t2，t3，⋯，t i，⋯，t n}，其中t i∈V（i=1，2，3，⋯，n），且记t n+1=t1，则旅行商问题的数学模型为：minL=。
TSP是一个典型的组合优化问题，并且是一个NP完全难题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发式的搜索、优化算法的间接比较标准。
因此，快速、有效地解决TSP有着重要的理论价值和极高的实际应用价值。
二、主要求解方法基于TSP的问题特性，构造型算法成为最先开发的求解算法，如最近邻点、最近合并、最近插入、最远插入、最近添加、贪婪插入等。
但是，由于构造型算法优化质量较差，迄今为止已开发了许多性能较好的改进型搜索算法，主要有：1）模拟退火算法2）禁忌搜索算法3）Hopfield神经网络优化算法4）蚁群算法5）遗传算法6）混合优化策略2.1 模拟退火算法方法1）编码选择：采用描述TSP解的最常用的一种策略——路径编码。
2）SA状态产生函数的设计：对于基于路径编码的SA状态产生函数操作，可将其设计为：①互换操作（SWAP）；②逆序操作（INV）；③插入操作（INS）。
3）SA状态接受函数的设计：min{1，exp（-△/t）}>random[0，1]准则是作为接受新状态的条件最常用的方案，其中△为新旧状态的目标值差，t为”温度”。
