J Shanghai Jiaotong Univ Sci ›› 2024, Vol. 29 ›› Issue (3): 463-470.doi: 10.1007/s12204-022-2517-3

• Automation & Computer Technologies • Previous Articles     Next Articles

Algorithm for Solving Traveling Salesman Problem Based on Self-Organizing Mapping Network

基于自组织映射网络解决旅行商问题的算法

ZHU Jianghui1,2,3,4 (朱江辉),YE Hanghang5 (叶航航), YAO Lixiu11,2,3 (姚莉秀), CAI Yunze1,2,3,4 (蔡云泽)   

  1. (1. Department of Automation, Shanghai Jiao Tong University, Shanghai 200240, China; 2. Key Laboratory of System Control and Information Processing, Ministry of Education, Shanghai 200240, China; 3. Shanghai Engineering Research Center of Intelligent Control and Management, Shanghai 200240, China; 4. Key Laboratory of Marine Intelligent Equipment and System, Ministry of Education, Shanghai 200240, China; 5. Huawei Technologies Co., Ltd., Shanghai 201206, China)
  2. (1.上海交通大学 自动化系,上海200240;2. 系统控制与信息处理教育部重点实验室,上海200240;3. 上海工业智能管控工程技术研究中心,上海 200240;4. 海洋智能装备与系统教育部重点实验室,上海 200240;5. 华为技术有限公司,上海 201206)
  • Accepted:2021-09-16 Online:2024-05-28 Published:2024-05-28

Abstract: Traveling salesman problem (TSP) is a classic non-deterministic polynomial-hard optimization problem. Based on the characteristics of self-organizing mapping (SOM) network, this paper proposes an improved SOM network from the perspectives of network update strategy, initialization method, and parameter selection. This paper compares the performance of the proposed algorithms with the performance of existing SOM network algorithms on the TSP and compares them with several heuristic algorithms. Simulations show that compared with existing SOM networks, the improved SOM network proposed in this paper improves the convergence rate and algorithm accuracy. Compared with iterated local search and heuristic algorithms, the improved SOM network algorithms proposed in this paper have the advantage of fast calculation speed on medium-scale TSP.

Key words: traveling salesman problem (TSP), self-organizing mapping (SOM), combinatorial optimization, neural network

摘要: 旅行商问题是一个经典的非确定性多项式难优化问题。本文基于自组织映射网络的特性,从网络更新策略、初始化方法和参数选择等角度对自组织映射网络进行改进。比较了所提出的算法在旅行商问题上的性能与现有自组织映射网络算法的性能,并将其与几种启发式算法进行比较。仿真结果表明,与现有的自组织映射网络相比,本文改进的自组织映射网络提高了收敛速度和算法精度。与迭代局部搜索和启发式算法相比,提出的改进自组织映射网络算法在中规模旅行商问题上具有计算速度快的优势。

关键词: 旅行商问题(TSP),自组织映射(SOM),组合优化,神经网络

CLC Number: