基于Hopfield网解决TSP问题

基于Ｈｏｐｆｉｅｌｄ网解决ＴＳＰ问题

作者：崔学忠 宋玉珍 曲付勇 来源：《现代电子技术》2008年第07期

摘 要：利用神经网络解决组合优化问题是神经网络应用的一个重要方面。组合优化问题，就是在给定约束条件下，使目标函数极小(或极大)的变量组合问题。首先介绍了Hopfield神经网络的工作原理，然后具体介绍了TSP问题，然后给出了Hopfield神经网络解决TSP问题的实例，最后的结果表明利用Hopfield神经网络解决TSP问题可以求得问题最优解的次优解。

关键词：神经网络；Hopfield网；TSP问题；能量函数 中图分类号：TP18文献标识码：B 文章编号：1004-373X(2008)07-027-

Using Hopfield Network to Solve TSP Problem

(1.91 Team of 92941 Arm

2.The Management of Graduates Students,Naval Aeronautical Engineering

3.91 Team of 91550 Army,Liaoning,116023,China)

Abstract：Using neural network to solve combination optimize problem is one importance side of neural networks′ application.Combination optimize problem is the variable combination problem which makes the goal function minimum or maximum under the given constraint condition.Firstly,this paper introduces the operating principle of Hopfield neural network.Secondly,this paper introduces travelling salesman problem.Thirdly,this paper gives the example of travelling salesman problem

using Hopfield neural network.The result shows that using Hopfield neural network to solve travelling salesman problem can obtain optimum solution′s second-rate solution.

龙源期刊网 http://www.qikan.com.cn

Keywords：neural network;Hopfield network;TSP problem;energy function

利用神经网络解决组合优化问题是神经网络应用的一个重要方面。所谓组合优化问题，就是在给定约束条件下，使目标函数极小(或极大)的变量组合问题。将Hopfield网络应用于求解组合优化问题，把目标函数转化为网络的能量函数，把问题的变量对应到网络的状态,这样，当网络的能量函数收敛于极小值时，问题的最优解也随之求出。由于神经网络是并行计算的，其计算量不随维数的增加而发生指数性“爆炸”，因而对于优化问题的高速计算特别有效。 1 Hopfield网的工作原理

目前，人工神经网络常利用渐进稳定点来解决某些问题［1,2］。例如，如果把系统的稳定点视为一个记忆的话，那么从初态朝这个稳定点的演变过程就是寻找记忆的过程。初态可以认为是给定的有关记忆的部分信息。如果把系统的稳定点视为一个能量函数的极小点，把能量函数视为一个优化问题的目标函数，那么从初态朝这个稳定点的演变过程就是一个求该优化问题的过程。这样的优点在于他的解并不需要真的去计算，而只要构成这种反馈网络，适当的设计其连接值和输入就可达到目的。

循环网络对输入信号的处理是一个逐渐“修复”、“加强”的过程，称为Hopfield网。 图1 最基本的Hopfield网(n=m=h) 联接：神经元之间都是互联的

，每个神经元都没有到自身的联接

，h≥n，h≥m，n≥1，m≥1。

。

神经元个数h，输入向量维数n，输出向量维数 神经元：输入、输出、隐藏。 状态变化：非同步、同步。 输入向量： 输出向量： 2 TSP问题

。。

TSP问题，即所谓的旅行商问题(Traveling Salesman Problem)。问题的提法是：在N个城市中各经历一次后回到出发点，使所经过的路程最短。其不同选择方案有N!/2N种，在城市数较少的情况下可以用枚举等方法，但如果城市数量较大时，使用枚举法求解就要考虑的情况是数量级，计算量之大是不可想象的。将Hopfield网络应用于求解TSP问题，效果是显著的［3,4］。

龙源期刊网 http://www.qikan.com.cn

在1985年，J.J.Hopfield和D.W.Tank用循环网求解TSP。试验表明，当城市的个数较少时，可以给出最优解；当城市个数较多而不超过30时，多可以给出最优解的近似解。而当城市的个数超过30时，最终的结果就不太理想了。 解决问题需要说明的是以下几个量： 设问题中含有N个城市,用

个神经元构成网络。

个城市间存在N!/2N条可能路径。为城市x与城市y之间的距离；为城市x的第i个神经元的状态；城市x在第i个被访问

城市x不在第i个被访问

为城市x的第i个神经元到城市y的第j个神经元的连接权。

－

－

网络的能量函数

其中

的路径的总长度。

为惩罚因子。

仅当所有的城市最多只被访问一次时取得极小值0。仅当每次最多只访问一个城市时取得极小值0。

－

当且仅当所有的n个城市一共被访问n次时才取得最小值0。

－

表示按照当前的访问路线的安排，所需要走

3 Hopfield网解决TSP问题实例 部分源程序：

龙源期刊网 http://www.qikan.com.cn

distance

distance(i,j) =sqrt(loc(i,:) -

energy = sum(distance((path-1)*NumCity + ［path(2:NumCity) path(1)］ n

all[CD#*2]dE(i) = abs(energy -

sum(sum(diff(loc(［new[CD#*2]path new[CD#*2]path(1)］

dE = max(all[CD#*2]dE); 运行结果:

龙源期刊网 http://www.qikan.com.cn

［minE maxE］ = ［4.260261 4.281659］

最小路径的次优解(即最优解的次优解)

path=23 27 29 12 13 20 19 18 5 4 2 30 8 16 7 3 1 6 9 17 21 11 10 14 22 24 26 28 25 15 23

如图2所示。

图2 Matlab运行结果的图形

由图2可以看出，最小路径的走法没有重叠的，也充分说明了Hopfield网解决TSP问题的有效性。因为取的城市个数为30,个数较多，所求得的解是最优解的次优解。 图3 初始点的分布图 4 结 语

本文主要通过利用Hopfield网络求解TSP问题，在给定要求下求得问题的最优解。该系统的扩展性能也比较好，当改变神经元个数，适当改变参数，也能达到比较好的效果。 参 考 文 献［1］胡守仁.神经网络应用技术［M］.长沙:国防科技大学出版社,1993. ［2］张乃尧,阎平凡.神经网络与模糊控制[M].北京:清华大学出版社,1998.

［3］党建武,靳蕃.神经网络方法在解C-TSP中的应用[J].兰州铁道学院学报,1994,13(1):65-71.

［4］郭鹏.Hopfield 网络在优化计算中的应用［J］.计算机仿真,2002(3):37-40. ［5］张建航,李国.模拟退火算法及其在求解TSP中的应用［J］.现代电子技术,2006，29(22):157-158.

龙源期刊网 http://www.qikan.com.cn

作者简介 崔学忠 男，1965年出生，湖北石首人，军事学硕士，工程师。主要从事靶场试验测控总体技术方面的研究。宋玉珍 女，1980年出生，山东潍坊人，博士研究生。主要从事雷达信号恒虚警检测的研究，海杂波建模分析等。曲付勇 男，1984年出生，山东聊城人，硕士研究生。主要从事雷达分布式检测等研究。