TSP-Hopfield教学讲义.ppt

旅游商问题优化计算 导师：师黎 姓名：郑延玲 1、组合优化问题 2、连续Hopfield神经网络 3、模型建立 4、matlab实现 1.组合优化 组合优化问题，就是在给定约束条件下，求出使目标函数极小（或极大）的变量组合问题。组合优化往往涉及排序，分类，筛选等问题，是运筹学的一个重要分支。 典型的组合优化问题有旅行商问题（TSP），加工调度问题，0-1背包问题，装箱问题，图着色问题，聚类问题等。这些问题描述简单，并且有很强的工程代表性，但最优化求解很困难，其主要原因是求解这些问题的算法运行时，需要极长的运行时间与极大的存储空间，以至根本不可能在现有的计算机上实现，即会产生所谓的“组合爆炸”问题。正是这些问题的代表性和复杂性激起了人们对组合优化理论与算法的研究兴趣。 研究现状 经典算法：线性规划，动态规划，整体规划，分支定界等运筹学算法，适用于小规模的问题，而且计算量很大； 构造型算法:Johnson法，CDS法，快速接近法等； 改进算法：局部有哪些信誉好的足球投注网站法(爬山法，最陡下降法等）；指导性算法（模拟退火，遗传算法，禁忌有哪些信誉好的足球投注网站，人工神经网络，进化策略，进化规划，DNA算法等） TSP问题 国外成立许多专门研究TSP问题的小组，他们建立了网站收集相关算法和 TSP研究成果以供交流。其中有代表性的是，美国普林斯顿大学数学系的 TSP 小组网站，德国海德尔堡大学的 TSPLIB 的公开数据库。目前该数据库已成为国际上 TSP 算法研究的基准数据。 现在有效的求解方法有免疫算法、遗传算法、蚂蚁算法、模拟退火算法、Hopfield 算法、LKH 算法等等。国内的研究还缺乏这种有组织的研究小组，研究相对滞后。 旅行商问题，简称TSP（Traveling Salesman Problem）。问题的提法是：设有N个城市， ,记为： ,用dij表示ci和cj之间的距离， dij0,(i,j=1,2,…n) 。 有一旅行商从某一城市出发，访问各城市一次且仅一次后再回到原出发城市。要求找出一条最短的巡回路线。 目前，人工神经网络常利用渐进稳定点来解决某些问题。例如，如果把系统的稳定点视为一个记忆的话，那么从初态朝这个稳定点的演变过程就是寻找记忆的过程。初态可以认为是给定的有关记忆的部分信息。如果把系统的稳定点视为一个能量函数的极小点，把能量函数视为一个优化问题的目标函数，那么从初态朝这个稳定点的演变过程就是一个求该优化问题的过程。这样的优点在于它的解并不需要真的去计算，而只要构成这种反馈网络，适当的设计其连接值和输入就可达到目的。 -设计思路 由下图可以看出，u,y的变化过程为一个非线性动力学系统。 图 反馈网络的结构 对于非线性系统进行稳定性分析，基于网络的能量函数。下面介绍Hopfield能量函数法 当网络神经元的传递函数单调递增,并且网络权系数矩阵对称时,则随时间的变化网络的能量会下降或不变；而且仅当输出电位随时间变化不变时,网络的能量才会不变。 3.模型建立 第一步就是将问题映照到一个神经网络。 假定每个神经元的放大器有很高的放大倍数，神经元的输出限制在二值0和1上，则映射问题可以用一个换位矩阵来进行，换位矩阵可如下图所示。 若N=5，并用字母A、B、C、D、E、分别代表这5个城市。当任选一条路径如B-D-E-A-C,则换位矩阵如下： 次序 城市 1 2 3 4 5 A 0 0 0 1 0 B 1 0 0 0 0 C 0 0 0 0 1 D 0 1 0 0 0 E 0 0 1 0 0 第二步构造网络能量函数和动态方程 设计的Hopfield神经网络的能量函数是与目标函数（即最短路径）相对应的。同时，应该考虑到有效解（路径）的实际意义，即换位矩阵的每行每列都只能有一个1.因此，网络的能量函数包含目标项（目标函数）和约束项（换位矩阵）两部分。这里，将网络的能量函数定义为：