Hopfield网络求解TSP两种改进算法的仿真研究
1 引言
用Hopfield神经网络求解旅行商问题(TSP)，给组合优化完备性问题的求解提供新的方法。但该算法会经常生成无效解，因此需进一步改进。有学者通过TSP网络的动态分析修正TSP的能量函数，从而获得有效解，但其能量函数的表达式过于复杂。有人简化该能量函数，进一步提出改进算法。这里拟对典型的两种改进算法进行仿真分析。
用Hopfield神经网络求解旅行商问题(TSP)，给组合优化完备性问题的求解提供新的方法。但该算法会经常生成无效解，因此需进一步改进。有学者通过TSP网络的动态分析修正TSP的能量函数，从而获得有效解，但其能量函数的表达式过于复杂。有人简化该能量函数，进一步提出改进算法。这里拟对典型的两种改进算法进行仿真分析。
2 HopfieId网络的能量函数
为将TSP问题映射成神经网络的动态过程，Hopfield采取置换矩阵的表示方法，用N×N个神经元组成Hopfield人工神经网络表示商人访问N个城市。
网络达到稳定状态时各神经元的状态对应置换矩阵各元素的值(“1”或“0”)。用uxi表示神经元(x，i)的输出，相应的输入用Vxi表示。
若城市x在i位置上被访问，则Vxi=1，否则Vxi=0。Hop-field定义如下形式的能量函数：
式中，A、B、C、D是实系数。dxy为城市x与y之间的距离。
式中前3项是问题的约束项。最后1项是优化目标项。利用动态方程：
式中，VT表示V的转置。
求得A、B、C、D和d描述的连接矩阵和及偏置，的表达式：
Hopfield把能量函数的概念引入神经网络，从而开创求解优化问题的新方法。但该算法会以大百分比生成无效解，因此需进一步改进。
3 改进算法与仿真
3．1 改进算法1
Aiyer等人从理论上证明Hopfield网络不能生成有效解的原因，并提出一个新的连接矩阵：
外部输入
可从理论上证明该算法的有效性，试验也验证它几乎100％可获得有效解。利用上述改进算法对Hopfield的10城市问题进行模拟试验，已知其最短路径为2．690 6。模拟试验采用两种神经元状态更新函数，一种采用S型函数，即
另一种采用如下定义的软限幅函数：
加入微信
获取电子行业最新资讯
搜索微信公众号：EEPW
或用微信扫描左侧二维码