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

doi:10.1007/s12204-022-2517-3

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

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

朱江辉1,2,3,4，叶航航5，姚莉秀1,2,3，蔡云泽1,2,3,4

（1.上海交通大学自动化系，上海200240；2. 系统控制与信息处理教育部重点实验室，上海200240；3. 上海工业智能管控工程技术研究中心，上海 200240；4. 海洋智能装备与系统教育部重点实验室，上海 200240；5. 华为技术有限公司，上海 201206）

接受日期:2021-09-16 出版日期:2024-05-28 发布日期:2024-05-28

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

ZHU Jianghui^1,2,3,4 (朱江辉),YE Hanghang⁵ (叶航航), YAO Lixiu1^1,2,3 (姚莉秀), CAI Yunze^1,2,3,4 (蔡云泽)

(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)

Accepted:2021-09-16 Online:2024-05-28 Published:2024-05-28

摘要/Abstract

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

关键词: 旅行商问题（TSP），自组织映射（SOM），组合优化，神经网络

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

中图分类号:

TP18

朱江辉1,2,3,4，叶航航5，姚莉秀1,2,3，蔡云泽1,2,3,4. 基于自组织映射网络解决旅行商问题的算法[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(3): 463-470.

ZHU Jianghui(朱江辉),YE Hanghang(叶航航), YAO Lixiu1(姚莉秀), CAI Yunze(蔡云泽). Algorithm for Solving Traveling Salesman Problem Based on Self-Organizing Mapping Network[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(3): 463-470.

参考文献

[1] WANG J W, DAI G M, XIE B Q, et al. A survey of solving the traveling salesman problem [J].Computer Engineering & Science, 2008, 30(2): 72-74 (in Chinese).
[2] WANG D C. Improved genetic algorithm in the application of the TSP [J]. Journal of Liaoning Institute of Technology (Natural Science Edition), 2019, 39(4): 235-239 (in Chinese).
[3] LUO H R, XU W D, TAN Y. A discrete fireworks algorithm for solving large-scale travel salesman problem [C]//2018 IEEE Congress on Evolutionary Computation. Rio de Janeiro: IEEE, 2018: 1-8.
[4] ZHAO L, JIN X, WANG N, et al. Depth genetic algorithm solve ultra-large-scale traveling salesman problem [J]. Computer Engineering and Applications, 2009, 45(4): 56-58 (in Chinese).
[5] WANG D, WU X B, MAO X C, et al. Accurate solving hybrid algorithm for small scale TSP [J]. Systems Engineering and Electronics, 2008, 30(9): 1693-1696 (in Chinese).
[6] ZHOU X M, XU X M. Modified self-organizing map network for Euclidean travelling salesman problem [J]. Journal of Computer Applications, 2012, 32(7): 1962- 1964 (in Chinese).
[7] GUAN L, ZHANG B, HUANG D. An improved selforganizing algorithm for solving the traveling salesman problem [J]. Journal of Shanghai Second Polytechnic University, 2012, 29(1): 48-52 (in Chinese).
[8] ZHANG J, ZHOU B. Self organizing map with generalized and localized parallel competitions for the TSP [J]. Chinese Journal of Computers, 2008, 31(2): 220- 227 (in Chinese).
[9] TIAN P, WANG H, ZHANG D. Solving the travelling salesman problem by simulated annealing [J]. Journal of Shanghai Jiaotong University, 1995, 29(S1): 111-116 (in Chinese).
[10] DONG R Y, WANG S S, WANG G Y, et al. Hybrid optimization algorithm based on wolf pack search and local search for solving traveling salesman problem [J]. Journal of Shanghai Jiao Tong University (Science), 2019, 24(1): 41-47.
[11] DENG Y L, XIONG J X, WANG Q H. A hybrid cellular genetic algorithm for the traveling salesman problem [J]. Mathematical Problems in Engineering, 2021, 2021: 6697598.
[12] PHU-ANG A. An improve artificial immune algorithm for solving the travelling salesman problem [C]//2021 Joint International Conference on Digital Arts, Media and Technology with ECTI Northern Section Conference On Electrical, Electronics, Computer and Telecommunication Engineering. Cha-am: IEEE, 2021: 261-264.
[13] BAI Q Y, LI G Z, SUN Q H. An improved hybrid algorithm for traveling salesman problem [C]//2015 8th In ternational Conference on Biomedical Engineering and Informatics. Shenyang: IEEE, 2015: 806-809.
[14] AHMAD R, KIM D. An extended self-organizing map based on 2-opt algorithm for solving symmetrical traveling salesperson problem [J]. Neural Computing and Applications, 2015, 26(4): 987-994.
[15] BROCKI L, KORˇZINEK D. Kohonen self-organizing map for the traveling salesperson problem [M]//Recent advances in mechatronics. Berlin, Heidelberg: Springer, 2007: 116-119.
[16] MODARES A, SOMHOM S, ENKAWA T. A selforganizing neural network approach for multiple traveling salesman and vehicle routing problems [J]. International Transactions in Operational Research, 1999, 6(6): 591-606.
[17] MASUTTI T A S, DE CASTRO L N. A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem [J]. Information Sciences, 2009, 179(10): 1454-1468.
[18] VIEIRA F C, D′ORIA NETO A D, COSTA J A F. An efficient approach to the travelling salesman problem using self-organizing maps [J]. International Journal of Neural Systems, 2003, 13(2): 59-66.
[19] LOURENCO H R, MARTIN O C, STUTZLE T. Iterated local search [M]//Handbook of metaheuristics. Boston: Springer, 2003: 320-353.
[20] HASEGAWA M, IKEGUCHI T, AIHARA K. Combination of chaotic neurodynamics with the 2-opt algorithm to solve traveling salesman problems [J]. Physical Review Letters, 1997, 79(12): 2344-2347.
[21] JIANG D M. Improved particle swarm optimization for traveling salesman problem and LabVIEW implementation [J]. Informatization Research, 2018, 44(4): 24-29 (in Chinese).
[22] PAPALITSAS C, GIANNAKIS K, ANDRONIKOS T, et al. Initialization methods for the TSP with Time Windows using Variable Neighborhood Search [C]//2015 6th International Conference on Information, Intelligence, Systems and Applications. Corfu: IEEE, 2015: 1-6.
[23] LIU J. Applied research of hybrid genetic algorithm and simulated annealing algorithm in traveling salesman problem [D]. Guangzhou: South China University of Technology, 2014 (in Chinese).
[24] ZONG D C, WANG K K, DING Y. Review of ant colony algorithm for solving traveling salesman problem [J]. Computer & Digital Engineering, 2014, 42(11): 2004-2013 (in Chinese).
[25] WANG X, PENG S. Method for solving traveling salesman problem based on improved tabu search algorithm [C]//The 3rd China Conference on Command and Control. Beijing: Chinese Institute of Command and Control, 2015: 487-491 (in Chinese).

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

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

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	. 面向交通流量预测的多尺度动态超图卷积网络[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(5): 880-888.
[2]	. 具有视觉伪装性的人脸识别对抗性图案生成方法[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(5): 911-922.
[3]	. 基于异步事件流超图网络的运动目标识别方法[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(5): 952-961.
[4]	. 基于语义动态超图卷积的三维手姿态估计[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(5): 855-865.
[5]	. 基于Transformer对比学习的自动睡眠分期方法[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(4): 720-732.
[6]	. 基于深度学习的肺癌病例文本结构化算法[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(4): 778-789.
[7]	. 基于CatBoost特征选择和Stacking集成学习的磨玻璃肺结节识别[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(4): 790-799.
[8]	. 基于表面肌电信号的BP-LSTM混合模型肘部运动实时预测[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(3): 455-462.
[9]	. 基于基尼不纯度结构优化物理引导神经网络的薄膜型声学超材料传声损失预测[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(3): 613-624.
[10]	. 基于两阶段卷积神经网络的焊缝缺陷监测[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(2): 291-299.
[11]	. 基于空间特征学习与多粒度特征融合的行人重识别[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(2): 363-374.
[12]	. 重复零和博弈中对无遗憾对手进行盘剥的研究[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(2): 385-398.
[13]	丁黎辉1, 2, 付立军1, 3, 杨光4, 5, 6, 万林4, 5, 常志军7. 基于视频的婴儿癫痫性痉挛综合征检测：建模、检测与评估[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(1): 1-9.
[14]	柯晶1, 朱俊超2, 杨鑫1, 张浩林3, 孙宇翔1, 王嘉怡1, 鲁亦舟4, 沈逸卿5, 刘晟6, 蒋伏松7, 黄琴8. TshFNA-Examiner：甲状腺细胞学图像的核分割和癌症评估框架[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(6): 945-957.
[15]	李明爱1, 2, 魏丽娜1. 基于朴素卷积神经网络和线性插值的运动想像分类[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(6): 958-966.