基于Hopfield网络学习的多城市旅行商问题的解法  

An Algorithm for Solving a Multi-city Traveling Salesman Problem Based on Learning of Hopfield Network

作　　者：金海和[1] 陈剑[2] 唐政 郑国旗 

机构地区：[1]内蒙古大学公共管理学院,内蒙古呼和浩特010021 [2]清华大学经济管理学院,北京100084 [3]富山大学工学部 [4]内蒙古大学电子工程系,内蒙古呼和浩特010021

出　　处：《系统工程理论与实践》2003年第7期100-105,共6页Systems Engineering-Theory & Practice

基　　金：留学回国人员科研启动基金 ( 2 0 0 1第一批 )

摘　　要：针对 Hopfield神经网络 ( HNN)学习算法难以求解大规模组合优化问题的不足 ,提出了基于HNN学习的多城市旅行商问题的求解算法 .它是把 HNN学习算法作基本算子 ,对城市群体按一定的规则进行有效的分割、计算和连接 ,来寻找巡回路径的最优解或满意解 .并以 1 0 0城市的旅行商问题为例进行了仿真实验 ,验证了算法的有效性 .该算法不受求解问题的规模限制 ;还可通过并列运算实现高速化 ;同时因算法简明 ,易于硬件实现 .This paper proposes an algorithm of solving the multi-city traveling salesman problem based on Hopfield network learning. The algorithm uses the Hopfield network learning as basal arithmetic operators, to look for the optimal or better solution by dividing up, calculation and linking the group of cities with the given rules. The algorithm is applied to a 100-city traveling salesman problem, and its effectiveness is confirmed by simulation. This algorithm is free from limitation of the city number; and speedup can be implemented by parallel operation; and hardware can be achieved easily because of simplicity and clarity in algorithm.

关 键 词：Hopfield神经网络学习 学习算子 组合优化问题 极小值问题 多城市旅行商问题 

分 类 号：TP183[自动化与计算机技术—控制理论与控制工程]