TSP-Hopfield教程教案.ppt

旅游商问题优化计算;1、组合优化问题 2、连续Hopfield神经网络 3、模型建立 4、matlab实现 ;1.组合优化; 典型的组合优化问题有旅行商问题（TSP），加工调度问题，0-1背包问题，装箱问题，图着色问题，聚类问题等。这些问题描述简单，并且有很强的工程代表性，但最优化求解很困难，其主要原因是求解这些问题的算法运行时，需要极长的运行时间与极大的存储空间，以至根本不可能在现有的计算机上实现，即会产生所谓的“组合爆炸”问题。正是这些问题的代表性和复杂性激起了人们对组合优化理论与算法的研究兴趣。;研究现状;TSP问题;旅行商问题，简称TSP（Traveling Salesman Problem）。问题的提法是：设有N个城市， ,记为： ,用dij表示ci和cj之间的距离， dij0,(i,j=1,2,…n) 。 有一旅行商从某一城市出发，访问各城市一次且仅一次后再回到原出发城市。要求找出一条最短的巡回路线。;2.连续Hopfield神经网络; 目前，人工神经网络常利用渐进稳定点来解决某些问题。例如，如果把系统的稳定点视为一个记忆的话，那么从初态朝这个稳定点的演变过程就是寻找记忆的过程。初态可以认为是给定的有关记忆的部分信息。如果把系统的稳定点视为一个能量函数的极小点，把能量函数视为一个优化问题的目标函数，那么从初态朝这个稳定点的演变过程就是一个求该优化问题的过程。这样的优点在于它的解并不需要真的去计算，而只要构成这种反馈网络，适当的设计其连接值和输入就可达到目的。 -设计思路;由下图可以看出，u,y的变化过程为一个非线性动力学系统。; 对于非线性系统进行稳定性分析，基于网络的能量函数。下面介绍Hopfield能量函数法;; 当网络神经元的传递函数单调递增,并且网络权系数矩阵对称时,则随时间的变化网络的能量会下降或不变；而且仅当输出电位随时间变化不变时,网络的能量才会不变。;3.模型建立; 若N=5，并用字母A、B、C、D、E、分别代表这5个城市。当任选一条路径如B-D-E-A-C,则换位矩阵如下：;第二步构造网络能量函数和动态方程 设计的Hopfield神经网络的能量函数是与目标函数（即最短路径）相对应的。同??，应该考虑到有效解（路径）的实际意义，即换位矩阵的每行每列都只能有一个1.因此，网络的能量函数包含目标项（目标函数）和约束项（换位矩阵）两部分。这里，将网络的能量函数定义为：;第三步初始化网络 在总结前人经验及多次试验的基础上，网络输入初始化选取如下：取A=200，D=100;采取时间设置step=0.0001，迭代次数为10000；U0=0.1；;第四步优化计算 当网络的结构及参数设计完成后，迭代优化计算的过程就变得非常简单，具体步骤如下： 步骤1：导入N个城市的位置坐标并计算城市间的距离； 步骤2：网络初始化； 步骤3：利用动态方程计算，并利用一阶欧拉法计算下式;  步骤4;根据 计算；; 步骤5：计算能量函数E; 步骤6：判断迭代次数是否结束，若迭代次数k10000，则终止，否则k=k+1返回步骤3。;4.MATLAB实现;经过连续型Hopfield神经网络优化后，寻找到的优化路径为4-9-6-5-3-2-1-7-8-10-4，其长度为3.0383.;能量函数随迭代过程变化的曲线如图，可以看出，网络的能量随着迭代过程不断减少。当网络的能量变化很少时，网络的神经元状态也趋于平衡点，此时对应的城市顺序即为待求的优化路径。;Thank you！