TSP问题的解及模拟程序.pdfVIP

6～48 TSP问题的解及其模拟程序 林雄 (琼州大学572200) 摘要本文阐述了Hopfidd—Tank的连续神经网络模型及用此模型解决TSP问题的方法．并给出相 应的模拟程序。 关键词能量函数Hopfield—Tank连续神经网络模型TSP问题 1 Hopfield—Tank连续神经网络模型 1984年．Hopfield和 Ia I。 Tank用模拟电子线路构造 了反馈人工神经网络的电路 模型【1-2】．见图1。组成此 k 电路的基本元件如图1所 Rn 示。 (1)具有正、反相输出的 C 运算放大器用来模仿神经元 的非线性函数关系。第i个 神经元输出电压v；与输入 V． v2 vJ 电压Ui之间的转移特性呈 图1 Hopfield—Tank连续神经网络模型 Sigmoid函数曲线，如图2所 示．表达式为 V；=舀(Ui，=爿…柚㈨ 其中，Ⅶ为归一化基准 值。当u0一O时。gi成为幅值 函数，其取值范围为0≤gi(Ui) ≤1。 (2)放大器的输入电容C． 和输出电阻R；对于放大器的 输出与输入信号之间产生延迟 作用．以此模仿神经元的时间 常数，构成神经元的动态特性。 图2神经元转移特性曲线 (3)外加偏置电流以l表示，相当于神经网络的阈值0。 神经网络电路产生的作用电势与电路相似。第i个放大器的输入可以用下面的微分方程表 式： c．五dui=一瓦ui+毒wbVi“ (2) 其中。Vi是放大器j的输出电压，且vj=gj(uj)，wⅪ是突触电导(连接矩阵)。 C也写成为w日和Ii得： l崇一{+言w。vj“ (3) {vj=g(uj) IT：RC 在给定初始条件下．这个运动方程完全描述电路的性质。如果方程的解为一组确定值．表示系 网络，网络达到稳定状态时有 vj一∑I．Ci (4) E=÷；军w4Vi 2 TSP问题及其算法 Salesmall Problem，巡回推销员问题)的提法为[4I：如果一个人要对n个城市A， TSP(Traveling B，C。…，中的每个城市都访问且仅访问一次，那么，怎样安排访问的次序才能使总的行程d最短? 示之，则本问题可归结为求方程 d=d盯+drE+dec+…+dwB (5) 的最小值问题。 当城市的数目为n时．各种可能的方案数目为 m=n!／2n=(n一1)!／2 (6) 这是由于n个城市有n!种排列，但两个顺序完全相反的方案行程相同，故要除以2；以哪个城 市开始旅行都是一样的，故还要除以n。随着城市数目n的增加，问题的复杂性将急剧增加，例如， mined Problem，完全非多项式问题)问题。为了用神