基于Hopfield网络求解TSP问题的研究和改进.pdfVIP

2002中国控制与斑策学术年会论文集 基于Hopfield网络求解TSP问题的研究及改进 郭鹏，韩璞，周黎辉 (华北电力大学．河北保定071003) 摘要：针对Hopfield网络束解TSPJ可点时存在曲困难，以及随意性大面导致生成非法样较 多．解的质量较差等|可舟，通过分析Hopfield网络的袖恋特性，拽出了学响解台法性和质量的因 素，并根据这些影响目素，童新槽造了网络敦值矩庠，碧出了选择軎事撤的指导公式．实验结果 表明，采用改进后的Hopfield阿络束解TsP『可是，其解的合法性和质量大大提高，结果夸人满 意． 美蕾词；Hopfield网络；TsP『可是；特征向量 1引 言 TSP(旅行商问题)是一个典型的组合优化问题。在应用Hopfield求解TSP问题时，存在 易收敛于非法解或不收敛的情况，即以大百分比生产无效解答。本文基于Hopfield网络的动 力学特性，分析了网络模型的不稳健性及各参数对网络收敛性和优化效果的影响，并提出了改 问题合法解的比例和优化效果。 2 TSP问题描述 给定Ⅳ个城市以及它们之间的两两直线距离，要找出一个闭合路径，使每个城市刚好经 过一次且总的旅行距离最短。对于该问题，通常用一个N×N的矩阵y来代表旅行商经过的 城市，当该矩阵中的某一个元素％一1时，则代表城市z在路径的第i个位置上。为满足问题的 约束条件，该矩阵的每一行及每一列必须有且仅有一个1，整个矩阵为1的元素的和为Nm。 为满足上述各约束条件，并保证所得路径最优或较优，取TSP网络能量函数为 2+ E一告∑∑∑。。。。+导∑∑∑”。w，+导(∑∑。。一ⅣJ 等∑∑∑d。％(屯一+口y,i-I) (1’ (2) W…一一A3．，(1一最，)一B盈，(1一占习)一C—Dd对(也抖·+占¨一·)(1一以，) 最后得到网络运行方程为 fc。警—～意一A蚤w。一B至vj--C(莩翠aa一Ⅳ)一。互屯c％一十‰。 1 1 l口，一g(“，)，g扛)一音(1+th(k)) (3) 406 3 常规Hopfield求解中的一些问题 Hopfield的10城市的TSP实验如下： 表1 10城市的二雄坐标 10个城市的二雄坐标如表1所示。 Hopfield推荐的一组参数为团：A；B一 500，C一200，D一500，^一20。采用Hopfie|d 推荐的参数做实验，每次实验进行50次寻 优，并统计生成的合法解和非法解(非法解包 括不收敛解)的个数。对合法解记录旅行路 径，并计算出路径长度。对于上述10城市 TSP问题，对应的最短距离应为2．601Ⅲ。 实验1参数A—B=500，C=200， D一500，^一20。合法解为6(见表2)，非法解 为44，合法解路径的平均长度为3．48，最优 路径长度为2．95615l，合法解比饲为12％。 襄2台涪解 路 径 路径长度 参戥D音法解非岳解 最优路径 平均路径 H，F·ooBD—E—A—I—J3．319456 B-C-BD-A—G-IJ—F斗I 3．620286 3．86】814 I—A—H—G--F—c-BD—E-J F—H—JI—D—A—oBG—E 702 3．540 oA—H—F—G-BD-I—J—B3．308988 B_D—E—F、H—I—j—G—A—C 2．956151 我们采用推荐参数做了多次实验，结果与实验1类似。改变Hopfield网络参数得到的结果 如表3～表6所示。