欧阳玲

(中原工学院， 郑州 450007)

某公司决定派遣调查员调查市场行情，现有N个城市，要求调查员调查每一个城市，并且不能重复，最后返回公司所在城市。如何安排调查顺序，使其路程最短呢? 这正是旅行商问题(Traveling Salesman Problem，TSP)[1]研究的范畴。由于路径数目会随着城市数目的增加呈指数增长，当N很大时，用常规方法在庞大的搜索空间寻找最优解变得非常困难。本文基于Hopfield神经网络对旅行商问题进行研究，建立能量函数，提出设计方法，给出路径优化的解决算法，并对城市数目N分别为8、20、40的旅行路径进行计算机MATLAB模拟仿真。

1 Hopfield神经网络模型能量函数

Hopfield神经网络模型由许多互联的神经元组成，如图1所示。

对于一个神经元i，ui为其状态输入；R与Ci分别为输入电阻和输入电容；Ii为输入电流；wij为j神经元和i神经元之间的连接权值；vi为神经元的输出，是神经元状态变量ui的非线性函数。

对于Hopfield神经网络的第i个神经元，可采用微分方程建立其输入、输出关系[2]，即：

(1)

图1 Hopfield 人工神经网络模型

在状态空间中考虑Hopfield神经网络的动态特性，分别令U=(u1,u2,…,un)T为具有n个神经元的Hopfield神经网络的状态向量，V=(v1,v2,…,vn)T为输出向量，I=(I1,I2,…,In)T为网络的外加输入向量。为了描述Hopfield网络的动态稳定性，可定义标准能量函数为[2]：

(2)

针对旅行商问题，将式(2)转化，以便与神经网络对应。这里，采用N阶换位矩阵表示调查者访问N个城市[1]。例如，当城市数目N=4时，集合表示为{A，B，C，D}，要求经过的路线是从城市D出发，中间依次经过城市C、B、A，最终返回城市D。若用矩阵来表示输出的有效解，“1”代表到达，“0”代表未到达，则有表1所示4个城市访问路线的二维矩阵。……