模式识别 感知器算法模式别 感知器算法模式识别 感知器算法模式识别 感知器算法.doc

利用Hopfield神经网络的优化解决旅行商问题 摘要：本文主要研究利用连续Hopfield神经网络具有优化的特性，将TSP问题的目标函数与网络的能量函数相对应，并将经过的城市顺序与网络的神经元相对应。当Hopfield神经网络的能量函数趋于最小值且神经元状态趋于平衡点，此时对应的城市顺序即为最佳路线。 关键词：Hopfield；TSP；最佳路线 Solve the traveling salesman problem with Hopfield neural network optimization Abstract: The paper studies the use of continuous Hopfield neural network with optimized features, make the energy function of TSP objective function correspond to network, and get the through-city order corresponded to neurons of the network. When the energy function of Hopfield neural network tends to the minimum and neuron state tends to the equilibrium point, the corresponding order of the city is the best route. Key words: Hopfield; TSP; the best route 1.连续Hopfiled神经网络的概述 1.1网络结构 Hopfield网络是一个具有自反馈的简单人工神经网络，如下图1-1所示。该网络由John Hopfield在1982年提出而得名。 1-1霍普菲尔德网络的连线示意图 Hopfield网络的每个神经元有多个输入，但只能有两种输出：(1(表示抑制)或+1(表示兴奋)，神经元之间的每个连接均被指派一个特定的连接强度，网络中的每个神经元在某一时刻总是对来自其周围的全部连接进行求和。如果这个总和大于0，则该单元的输出为+1，否则输出为-1。计算多次反复进行，直到所有单元的输出都稳定为止。所有单元的状态并不是同时改变的，而是按随机次序一个接一个地进行的。 Hopfield 从理论上证明，如果对Hopfield网络给定一组连接权值和任何输入，该网络将不会无限制地处于漫游状态，也不会进入振荡状态，而是迅速收敛到一个稳定状态。 Hopfield 网络用“赫布规则”调节神经元之间连接权值：如果两个神经元具有相同的输出，则它们之间的相互连接权值都设为+1，反之，如果它们具有相反的输出，则个权值均设为-1。 当Hopfield 网络输入正确的神经元活动模式时，由于此刻它将反映我们所期望的正确答案，所以它的输出将为整个输出的正确模式，网络将稳定在该状态。 特别值得注意的是，如果仅仅给出正确输入模式的部分作为“线索”输入到该网络，它将经过短暂演化、不断调节各单元输出后，会稳定在正确输出模式（也即整个模式）上，于是，网络反映出各个神经元活动的稳定关系。最终Hopfield 网络将从某些仅仅与其存贮的“记忆”接近的信息中恢复出整个记忆，这已经与人们的记忆比较相似了。 1.2网络稳定性 Hopfield神经网络主要是模拟生物神经网络的记忆机理, 是一种全连接型的神经网络, 对于每个神经元来说, 自己输出的信号通过其他神经元又反馈到自身, 所以Hopfield 神经网络是一种反馈型神经网络。连续的Hopfield 神经网络状态的演变过程是一个非线性动力学系统, 可以用一组非线性微分方程来描述。系统的稳定性可用所谓的“能量函数” (即李雅普诺夫或哈密顿函数)进行分析。在满足一定条件下, 某种“能量函数”的能量在网络运行过程中不断地减小, 最后趋于稳定的平衡状态。反馈网络达稳定状态时可以使系统的能量达极小, 因而可用于一些最优化问题的计算, 能量公式如下: （1-1） 1.3组合优化问题的概述 组合优化(combinational optimization)问题的目标是从组合问题的可行解集中求出最优解，通常可 描述为：令为所有状态构成的解空间，C（si）为状态St对应的目标函数值，要求寻找最优解s*, 使得对于所有的si∈，有C（si）=min（C（si））。组合优化往往涉及排序、分类、筛选等问题，是运筹学的一个重要分支。 旅行商问题(TSP)就是典型的组合优化问题，