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

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

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics

本文评价

[1]	张彦军1,4,5,6,7, 王碧云2,3 , 蔡云泽1,4,5,6,7. 基于注意力的多通道网络红外弱小目标检测[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(3): 414-427.
[2]	刘增敏1,2,3,4,6，王申涛5，姚莉秀1,2,3，蔡云泽1,2,3,4,6. 基于目标检测和特征提取网络的运动无人机平台下多目标跟踪[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(3): 388-399.
[3]	李明爱1,2,3，许冬芹1. 综述：运动想像脑机接口中的迁移学习[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(1): 37-59.
[4]	王玉娟1，李文刚2，刘建勇3，陈广学4，汪军1. fiber;麻灰色原配色丝织物的颜色预测模型[J]. J Shanghai Jiaotong Univ Sci, 2023, 28(6): 802-808.
[5]	. [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(5): 638-648.
[6]	. [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(5): 715-722.
[7]	. [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(5): 737-746.