8.9 基于Hopfield网络的路径优化 (1).ppt

8.3.2基于Hopfield网络的路径优化旅行商问题（TravelingSalesmanProblem，简称TSP）可描述为：已知N个城市之间的相互距离，现有一推销员必须遍访这N个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，使其旅行路线总长度最短。旅行商问题是一个典型的组合优化问题，其可能的路径数目与城市数目N呈指数型增长的，一般很难精确的求出其最优解，因而寻找其有效的近似求解算法具有重要的理论意义。另一方面，很多实际应用问题，经过简化处理后，均可化为旅行商问题，因而对旅行商问题求解方法的研究具有重要的应用价值1旅行商问题的描述旅行商问题是一个典型的组合优化问题，特别是当N的数目很大时，用常规的方法求解计算量太大。对庞大的有哪些信誉好的足球投注网站空间中寻求最优解，对于常规方法和现有的计算工具而言，存在着诸多的计算困难。使用Hopfield网络的优化能力可以很容易地解决这类问题。Hopfield等[1]采用神经网络求得经典组合优化问题（TSP）的最优解，开创了优化问题求解的新方法。TSP问题是在一个城市集合中找出一个最短且经过每个城市各一次并回到起点的路径。为了将TSP问题映射为一个神经网络的动态过程，Hopfield采取了换位矩阵的表示方法，用N?N矩阵表示商人访问个城市。例如，有四个城市，访问路线是：则Hopfield网络输出所代表的有效解用下面的二维矩阵表8-2来表示：2求解TSP问题的Hopfield网络设计表8-2四个城市的访问路线次序城市12340100000100101000表8-2构成了一个4?4的矩阵，该矩阵中，各行各列只有一个元素为1，其余为0，否则是一个无效的路径。采用Vxi表示神经元(x,i)的输出，相应的输入用Uxi表示。如果城市x在I位置上被访问，则Vxi=1，否则Vxi=0。针对TSP问题，Hopfield定义了如下形式的能量函数：式中，A,B,C,D是权值，dxy表示城市x到城市y之间的距离。式（8.38）中，E的前三项是问题的约束项，最后一项是优化目标项,E的第一项为保证矩阵V的每一行不多于一个1时E最小（即每个城市只去一次），E的第二项保证矩阵的每一列不多于一个1时E最小（即每次只访问一城市），E的第三项保证矩阵V中1的个数恰好为N时E最小。Hopfield将能量函数的概念引入神经网络，开创了求解优化问题的新方法。但该方法在求解上存在局部极小、不稳定等问题。为此，文献[17]将TSP的能量函数定义为：Hopfield网络的动态方程为：采用Hopfield网络求解TSP问题的算法描述如下：(1)置初值:t=0,A=1.5,D=1.0,μ=50；(2)计算N个城市之间的距离dxy(x,y=1,2,…,N)；(3)神经网络输入Uxi(t)的初始化在0附近产生；(4)利用动态方程（8.23）计算；(5)根据一阶欧拉法计算(6)为了保证收敛于正确解，即矩阵V各行各列只有一个元素为1，其余为0，采用Sigmoid函数计算其中μ0，μ值的大小决定了Sigmoid函数的形状。(7)根据式（8.22），计算能量函数E；(8)检查路径的合法性，判断迭代次数是否结束，如果结束，则终止，否则返回到第（4）步；(9)显示输出迭代次数、最优路径、最优能量函数、路径长度的值，并作出能量函数随时间的变化的曲线图。在TSP的Hopfield网络能量函数（8.39）式中，取A=1.5，D=1.0。采样时间取?T=0.01，网络输入Uxi(t)初始值选择在[-0.001,+0.001]间的随机值，在式（8.25）的函数中，取较大的，以使函数比较陡峭，从而稳态时Vxi(t)能够趋于1或趋于0。以8个城市的路径优化为例，其城市路径坐标保存在当前路径的程序cities8.txt中。如果初始化的寻优路径有效，即路径矩阵中各行各列只有一个元素为1，其余为0，则给出最后的优化路径，否则停止优化，需要重新运行优化程序。如果本次寻优路径有效，经过2000次迭代，最优能量函数为Final_E=1.4468，初始路程为Initial_Length=4.1419，