基于Hopfield神经网络求解较大规模TSP的新方法  

A New Approach for Solving Medium Scale TSP Based on Hopfield Neural Network

作　　者：石红国[1] 饶煜 郭寒英 SHI Hongguo;RAO Yu;GUO Hanying(School of Transportation and Logistics,Southwest Jiaotong University,Chengdu Sichuan 610031,China;School of Automobile and Transportation,Xihua University,Chengdu Sichuan 610039,China)

机构地区：[1]西南交通大学交通运输与物流学院,四川成都610031 [2]西华大学汽车与交通学院,四川成都610039

出　　处：《综合运输》2018年第10期77-82,共6页China Transportation Review

基　　金：国家自然科学基金资助项目:特殊地区高速铁路风致行车灾变控制准则、指挥预警机理及报警控制可靠性研究(U1334201)

摘　　要：利用Hopfield神经网络求解超过100个城市的旅行商问题（TSP）时，由于Hopfield神经网络能量函数局部极小点太多导致求解困难，本文提出一种Hopfield神经网络与归约方法相结合求解较大规模TSP问题的通用方法，通过提取原TSP问题较优解之间的公共边，降低城市规模并构造一个新的TSP问题，再利用Hopfield神经网络求解新TSP问题并在得到较优解后将之还原，以此获得原TSP问题的较优解。计算机仿真表明该方法可以快速获得较大规模TSP问题较优解，提高了使用Hopfield神经网络求解TSP问题的适用城市规模。The number of local minima of the energy function of the Hopfield neural network increases as the number of neurons increases, which result in the Hopfield neural networks is not suitable for solving TSP（traveling salesman problem） problem which with a scale of over 100 cities. An approach for solving medium scale TSP problem by Hopfield neural network based on reduction technology is presented. We construct a new TSP problem by extracting the common sides between the optimal solutions of the original TSP problem. An optimal solution will be obtained by using Hopfield neural network to solve the new TSP

关 键 词：神经网络 旅行商问题 较大规模 公共边 归约 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]