HOPFIELD网络解决TSP问题.ppt

《HOPFIELD网络解决TSP问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、HOPFIELD网络解决TSP问题蔡佳佳吴凡2006-4-151蔡佳佳吴凡TSP旅行商问题(TSP):有N个城市及它们的距离dij.求最短的哈密尔顿回路。2006-4-152蔡佳佳吴凡Hopfield网络HopfieldNet.vsTSP利用HopfieldNet.来解未必能得到最优解，但可以得到较优解。HopfieldNet.解题的六个方面状态变量◎状态要求◎状态表现◎状态函数◎网络架构◎网络动态◎2006-4-153蔡佳佳吴凡TSP问题建模（状态变量）TSP问题可以描述为：设n个城市A，B，C……两两

2、城市间距离分别为Sij，从任一城市出发，访问每个城市一次并返回起点。假如有4个城市A，B，C，D，顺序为B→A→D→C→B。那么路线排列应该是TSP问题的解是n个城市的有序排列，可以用换位矩阵来表示一条访问路径。矩阵每行决定一个城市的位置，如上面的路径可以表示为：2006-4-154蔡佳佳吴凡TSP问题建模（状态变量）Vxi大写V：状态变量小写x：城市i：拜访的顺序次序城市1234A0100B1000C0001D00102006-4-155蔡佳佳吴凡TSP问题建模（状态要求）设计限制每个城市只去一次每次只

3、去一个城市N个城市都要到找出一条从某城市出发，连贯这些城市，又回到原出发点的最短路径。2006-4-156蔡佳佳吴凡TSP问题建模（状态表现）对于N个城市的旅行推销员的一个解答可用N2个神经元的状态变量来代表状态变量的排列矩阵元素假设有四个城市(其神经元连接方式，以右上角神经元为例)01001000000100102006-4-157蔡佳佳吴凡TSP问题建模（状态函数）每个城市只能经过一次，因此不会有第i站等于第j站的情形每个城市只能经过一次，因此第i站的城市不可能重复每个城市都要到过一次这实际上就是TS

4、P问题用HOPFIELD网络建模的3个限制。即换位矩阵每行只有一个1，每列只有一个1，整个矩阵有N个1。2006-4-158蔡佳佳吴凡TSP问题建模（状态函数）前面理论已经讲过了HOPFIELD模型要有一个能量函数，它和前馈的误差函数很接近。利用Liyapunov函数来构造这里的能量函数。这里能量的一个重要部分是和路径有关的信息，那么可以设定一个式子这个式子要达到一个极小值才可能满足要求。下标要对N取模运算。否则下标就出现无意义值。2006-4-159蔡佳佳吴凡TSP问题建模（状态函数）还要考虑路径的合法

5、性，这样就再加上3个约束条件：第一个是每行不多于一个1，第2个是每列不多于一个1，第3个是矩阵中1的个数是n个2006-4-1510蔡佳佳吴凡TSP问题建模（状态函数）采用Lagrange乘子法，将这个有约束优化问题转化为无约束的优化问题。A，B，C，D都是相应的加权系数。2006-4-1511蔡佳佳吴凡TSP问题建模（状态函数）其中前三项是所有TSP问题都必须有的约束，第四项因问题不同而不同。这里给出的第四项只能解决小规模的TSP问题。HOPFIELD给了一组10城市均匀分布的坐标并用这个公式实现。他声

6、称20次模拟实验中有16次收敛到最优解或较优解。不过Wilson用同样的方法，并不能达到这个效果。总体结果很差。Aiyer通过分析网络特征值，从超空间角度解释了HOPFIELD网络求解TSP常陷入无效解的原因，并修改能量公式如后：2006-4-1512蔡佳佳吴凡TSP问题建模（状态函数）显然这个公式保证网络收敛到有效解是以复杂的能量函数为代价。现在的HOPFIELD网络改进关键都在这个含路径信息的计算块上面。2006-4-1513蔡佳佳吴凡TSP问题建模（状态函数）孙守宇，郑君里，HOPFIELD网络求解

7、TSP的一种改进算法和理论证明，电子学报，,1995,23(1):73～78该论文提出一种改进的方案，首先，能量函数第3项只在网络输出全为0时才起作用，否则前两项已经保证了第3项成立，因此对前两项做修改：这样第3项完全可以省去。那么，TSP能量函数可以简化为下页所示：2006-4-1514蔡佳佳吴凡TSP问题建模（状态函数）2006-4-1515蔡佳佳吴凡TSP问题建模（状态函数）由于行列对称性，B=A。且第四项比Aiyer的简化了很多，式子仍然满足优化目标约束的要求。这些参数的设置需要大量测试，前人的论

8、文仅供参考。论文上设计的参数变化幅度很大，从不足1到数百甚至上千都有。具体情况需要自己测试来确定。2006-4-1516蔡佳佳吴凡TSP问题建模（网络架构）权值矩阵（对应11页的原始能量公式，那个公式隐含的定义了这个矩阵）：当i=j时，为1，否则为0。右边是外部激励电流2006-4-1517蔡佳佳吴凡TSP问题建模（网络架构）同样，改进的那篇论文中的连接权值矩阵也可以写出：外部激励电流为2006-4-1518蔡佳佳吴凡TSP问