内容发布更新时间 : 2024/12/27 12:39:00星期一 下面是文章的全部内容请认真阅读。

基于Hopfield技术的 TSP 问题求解

1 Hopfield原理综述：

首先，网络结构上，Hopfield神经网络是一种单层互相全连接的反馈型神经网络。每个神经元既是输入也是输出，网络中的每一个神经元都将自己的输出通过连接权传送给所有其它神经元，同时又都接收所有其它神经元传递过来的信息。即：网络中的神经元在t时刻的输出状态实际上间接地与自己t-1时刻的输出状态有关。神经元之间互连接，所以得到的权重矩阵将是对称矩阵。

同时，Hopfield神经网络成功引入能量函数的概念，使网络运行的稳定性判断有了可靠依据。基本的Hopfield神经网络是一个由非线性元件构成的全连接型单层递归系统。其状态变化可以用差分方程来表示。递归型网络的一个重要特点就是它具有稳定状态，当网络达到稳定状态的时候，也就是它的能量函数达到最小的时候。这里的能量函数不是物理意义上的能量函数，而是在表达形式上与物理意义上的能量概念一致，即它表征网络状态的变化趋势，并可以依据Hopfield网络模型的工作运行规则不断地进行状态变化，最终能够到达具有某个极小值的目标函数。网络收敛就是指能量函数达到极小值。

在使用递归网络时，必须对其稳定性进行专门的分析与讨论，合理选择网络的参数变化范围，才能确保递归网络的正常工作。

Hopfield神经网络模型有离散型和连续性两种，离散型适用于联想记忆，连续性适合处理优化问题。

2 建模方法

TSP问题就是在一城市集合{A,B,C,…}中找出一个最短且经过每个城市各一次并回到起点的路径。为了将TSP问题映射到一神经网络的动态演化过程，首先必须找到一合适的表示方法。任一城市在最终路径上的次序可用一N维矢量表示。以10

城市为例，如果城市A是第6个访问，则可以用0000010000，即只有第6个神经元的输出为1，其余都是0。为了表示表示所有城市，就需要N×N阶矩阵。例如5个城市，访问顺序顺序是CAEBD，那么可以用这样的方阵表示。

访问距离是：S=Dca+Dae+Deb+Dbd+Ddc

对于走过的每一条可能的路径，每个城市都只能走过一次且需要一一走过每个城市，因此这一方阵中的每一行和每一列都只能有一个元素为1，其余元素为0。这边是TSP问题的约束条件。具有上述约束条件的每一路径可用一换位阵表示。

3 程序设计方案

3.1 Hopfield求解TSP问题的步骤

3.1.1 初始化Hopfield神经网络的初值，包括输入电压U0，迭代次数，权值A

和D 3.1.2 计算n个城市之间的距离矩阵Dxy

3.1.3 初始化神经网络的输入状态，其中的随机相取值正负1之间

3.1.4 利用CHNN动态方程计算输入状态的增量

3.1.5 由

时

3.1.6 由sigmoid函数更新神经网络下一时刻的输出状态

一阶欧拉方法更新神经网络下一刻的状态

3.1.7 计算当前的能量函数E

3.1.8 检查当前神经网络的输出状态集合，看是否满足TSP置换矩阵的规则 3.2 Python编程实现Hopfield