下载掌阅APP，畅读海量书库
立即打开
1982年由John Hopfield提出用统计机理解释递归网络的操作并可以用来作为联想存储器，并在TSP问题的解决上取得了很大的成绩。同时，多层感知机的研究也给神经网络的发展带来了新的希望。Hopfield神经网络是一种互联递归神经网络，是一个非线性动力学系统，系统的稳定性可以用所谓的“能量函数”进行分析。随着网络的运行，能量函数不断变小，并最终趋于稳定状态。所以，Hopfield神经网络可以利用这些稳定点来解决一些问题，如将系统稳定点视为一个记忆模式，那么我们给定一个点，网络朝着这个方向收敛的过程就是一个记忆联想过程，经典的应用包括图像和数字等的模式识别问题，在这些领域中，Hopfield神经网络的应用都取得了很好的效果。如果把系统稳定点视为一个能量函数及小点，把能量函数视为一个优化问题的目标函数，那么，从初值点向这个稳定点收敛的过程就是一个求解最优化问题的过程。
CHNN的电路模型如图6-1所示，A i 用来模拟网络神经元，是运算放大器；R i 与C i 并联用来模拟神经元动态特性的时间常数，R i 为电阻，C i 为电容；u i 表示神经元A i 的状态，是运算放大器A i 的总输入；w ij 表示神经元A i 的输出v i 与神经元A j 的连接权值，是导纳；v i 表示神经元A i 的输出；I i 用来模拟神经元阀值θ i ，为外部偏置电流。
根据基尔霍夫电路定律，CHNN网络的动力学方程描述为：
其中，i=1,…,n；u i (t)、v i (t)分别表示神经网络节点i在时刻t处的输入与输出。CHNN的能量函数可定义为：
图6-1 CHNN的电路模型
对于CHNN，具有如下重要性质。
性质1：若c＞0，
且
单调增加
，则E(t)随时间单调减少，且
证明：对E(t)求导可得
由于w ij =w ji ，u i (t)= ϕ i - 1 (v i (t))，因此可得
根据CHNN的动力学方程可进一步得到
由于c＞0， ϕ i - 1 (v)单调增加，因此
且
性质1得证。
性质1很重要，它说明在CHNN运行的过程中，它的能量函数是递减的，若能量函数还有下界，那么E(t)一定是收敛的。因此，若优化问题可以转换为能量函数的表达式，则理论上可以通过CHNN的动力学递推得到最优解。
性质2：若已知能量函数E(t)的表达式，且w ij =w ji ，则CHNN的动力学方程可通过如下方法得到
证明：根据E(t)的表达式可得
由于
，上式可化简为
进而可证性质2。
性质2的作用在于，很多情况下，CHNN的结构是未知的，而且E(t)的表达式十分复杂。如果强行将E(t)的表达式按标准形式展开将十分困难，在此基础上进一步推导CHNN的结构就更困难了，而性质2对CHNN结构的求解一步到位，方法简单，大大减少了推导的工作量。
综上所述，对于CHNN，当其运行至稳定状态时，其能量函数达到极小值，利用这一特性，CHNN可以方便地求解优化问题。首先根据优化问题的目标函数和约束条件获得CHNN的能量函数，对该能量函数进行分析，设计完成连续型Hofield神经网络，由该CHNN来完成求取优化问题解的具体过程。
CHNN求解一般优化问题的流程如下。
Step 1： 根据优化问题的目标函数和约束条件获得CHNN的能量函数E(t)。
Step 2： 对能量函数进行求导，获得神经网络的状态方程，即
Step 3： 根据CHNN的标准形式得到其权值与阈值。
Step 4： 根据神经网络的权值和阀值，设计CHNN，运行至稳定状态，得到问题的优化解。
TSP问题的原始定义是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。TSP由美国RAND公司于1948年引入，该公司的声誉及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题。1856年，哈密尔顿推出了二十城游戏（Leosian Game）。第一次使用旅行商问题（Traveling salesman problem）一词可能是在1931年或1932年，当时A.WTueke从普林斯顿大学Hassler Whitney那里听到了Traveling salesman problem（旅行商问题）一词。不管是被称为骑士周游问题（Knights Tour）、投递问题（Messenger problem）或是旅行商问题（Traveling Salesman Problem），这一问题已让很多著名的数学家为之苦苦思索了几个世纪。同样的问题，在中国还有另一个描述方法：一个邮递员从邮局出发，到所辖街道投递邮件，最后返回邮局，如果他必须走遍所辖的每条街道至少一次，那么他应如何选择投递路线，使所走的路程最短？这个描述之所以称为中国邮递员问题，因为是我国学者管梅古教授于1962年提出的并且给出了一个解法。
TSP问题是组合优化领域中的一个典型问题，涉及求多个变量的函数的最小值。虽然它陈述起来很简单，但求解却很困难，它一直是运筹学中最富挑战性的问题之一，并且已经被证明是NP完全问题。对于具有n个城市的TSP问题，其可能的路径数目为(n-1)!/2，至今尚未找到有效的求解方法，理论上枚举法可以解这一问题，但是当n较大时，解题的时间消耗会使枚举法显得没有任何实际价值。因此，寻求一种求解时间短，能满足实际问题精度要求的解，成为解决该问题的主要途径。
TSP问题的数学描述如下，设巡回路径T=(T 1 ,T 2 ,…,T n )，使得下列目标函数最小：
上式中，t
i
为城市号，取值为1～n之间的自然数；
表示城市i和城市j之间的距离，对于对称式TSP，有
。用图论的语言描述为在一个赋权完全图中找出一个最小权的哈密顿圈。
令G=(V,E)为赋权完全图，V={1,2,…,n}为顶点集，E为边集，各顶点间的距离d ij 已知（d ij ＞0，d ii =0，i,j∈V）。
设
则TSP的数学模型可写成如下的线性规划形式：
这里，s.t.是subjected to的缩写，表示受约束的意思，这是带约束条件最优化问题的常用表达方法。|S|为集合S中所含图G的顶点个数。前面两个约束意味着对每个顶点而言，仅有一条边进和一条边出。后一条约束则保证了没有任何子回路解的产生。于是，满足上述约束条件的解构成了一条遍历所有顶点的哈密顿回路。
通常一个组合优化问题的解可能不是唯一的，即可以同时存在多个，满足条件的赋值使得目标函数达到最大（或最小）值，但目标函数所达到的最大（或最小）值总是唯一的。
TSP的求解方法主要分为两类。一类是精确算法（完全算法）；另一类是近似算法或启发式算法（不完全算法）。完全算法能保证完全搜索问题的整个解空间，从而找到最优巡回，但需要消耗O(n!)级的运算时间；有些完全算法虽然运用一些精巧的技术来减少搜索空间，但本质上还是进行全局搜索的，并没有降低运算时间复杂度。
不完全算法不能保证搜索空间的全部解空间，所以也不能保证能够找到最优解，甚至在某些实例上连解都得不到，但它们与完全算法相比却具有运算时间上的优势，即它们的运算时间复杂度只是多项式，并不随着输入规模的扩大产生“组合爆炸”。这类算法采用的是启发式策略来指导搜索，普遍比完全算法要快。