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
接受日期:
2021-09-16
出版日期:
2024-05-28
发布日期:
2024-05-28
ZHU Jianghui1,2,3,4 (朱江辉),YE Hanghang5 (叶航航), YAO Lixiu11,2,3 (姚莉秀), CAI Yunze1,2,3,4 (蔡云泽)
Accepted:
2021-09-16
Online:
2024-05-28
Published:
2024-05-28
摘要: 旅行商问题是一个经典的非确定性多项式难优化问题。本文基于自组织映射网络的特性,从网络更新策略、初始化方法和参数选择等角度对自组织映射网络进行改进。比较了所提出的算法在旅行商问题上的性能与现有自组织映射网络算法的性能,并将其与几种启发式算法进行比较。仿真结果表明,与现有的自组织映射网络相比,本文改进的自组织映射网络提高了收敛速度和算法精度。与迭代局部搜索和启发式算法相比,提出的改进自组织映射网络算法在中规模旅行商问题上具有计算速度快的优势。
中图分类号:
朱江辉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). |
[1] | . 基于表面肌电信号的BP-LSTM混合模型肘部运动实时预测[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(3): 455-462. |
[2] | . 基于基尼不纯度结构优化物理引导神经网络的薄膜型声学超材料传声损失预测[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(3): 613-624. |
[3] | . 基于两阶段卷积神经网络的焊缝缺陷监测[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(2): 291-299. |
[4] | . 基于空间特征学习与多粒度特征融合的行人重识别[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(2): 363-374. |
[5] | . 重复零和博弈中对无遗憾对手进行盘剥的研究[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(2): 385-398. |
[6] | 丁黎辉1, 2, 付立军1, 3, 杨光4, 5, 6, 万林4, 5, 常志军7. 基于视频的婴儿癫痫性痉挛综合征检测:建模、检测与评估[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(1): 1-9. |
[7] | 柯晶1, 朱俊超2, 杨鑫1, 张浩林3, 孙宇翔1, 王嘉怡1, 鲁亦舟4, 沈逸卿5, 刘晟6, 蒋伏松7, 黄琴8. TshFNA-Examiner:甲状腺细胞学图像的核分割和癌症评估框架[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(6): 945-957. |
[8] | 李明爱1, 2, 魏丽娜1. 基于朴素卷积神经网络和线性插值的运动想像分类[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(6): 958-966. |
[9] | 刘月笙, 贺宁, 贺利乐, 张译文, 习坤, 张梦芮. 基于机器学习的移动机器人路径跟踪MPC控制器参数自整定[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(6): 1028-1036. |
[10] | 彭诗玮1, 张希1, 朱旺旺1, 窦瑞2. 融合乘客感受量化指标的智能汽车舒适性研究[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(6): 1063-1070. |
[11] | 刘文1, 3, 许剑新2, 4, 杨根科1, 3, 陈媛芳5. 基于LSTM-BiDBN入侵检测系统的在线车辆取证责任方认定方法[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(6): 1161-1168. |
[12] | 耿宗盛1,赵东东1, 2,周兴文1,闫磊1, 阎石1, 2. 基于全分布式事件驱动控制的多智能体系统领导-跟随一致性研究[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(4): 640-645. |
[13] | 张彦军1,4,5,6,7, 王碧云2,3 , 蔡云泽1,4,5,6,7. 基于注意力的多通道网络红外弱小目标检测[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(3): 414-427. |
[14] | 刘增敏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. |
[15] | 李明爱1,2,3,许冬芹1. 综述:运动想像脑机接口中的迁移学习[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(1): 37-59. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||