摘要
Efficient solvers for traveling salesman problem (TSP) have great significance in the field of consumer electronic systems and devices. Existing studies require independent and repetitive runs for similar TSPs. To utilize useful knowledge buried in the twin TSP which is similar to the target TSP, a twin learning framework based on task matching and mapping strategy is proposed. We use an autoencoder to extract the feature vectors of the historical tasks and the target task to find the twin task. If not found, construct a twin task based on a graph-filter. Further, we get the solution of the target task with the optimized twin task by learning a mapping matrix from the twin task to the target task. Finally, we incorporate local search algorithms into the twin learning framework, which called strategy mapping solver (SMS) to further improve the quality of the solution. The efficacy of the SMS is evaluated through comprehensive empirical studies with commonly used TSP benchmarks, against meta-heuristic algorithms and a learning improvement heuristics algorithm, demonstrating its effectiveness for TSP. Moreover, a real-world combinatorial optimization application, laser engraving path planning, is presented to further confirm the efficacy of SMS.
学科与关键词
- A transfer learning-based particle swarm optimization algorithm for travelling salesman problemZheng, Rui-zhao; Zhang, Yong*; Yang, KangJournal of Computational Design and Engineering, 2022, 9(3): 933-948.被引 25
- Reinforced Lin-Kernighan-Helsgaun algorithms for the traveling salesman problemsZheng, Jiongzhi; He, Kun*; Zhou, Jianrong; Jin, Yan; Li, Chu-MinKnowledge-Based Systems, 2023, 260: 110144.被引 18
- How Good is Neural Combinatorial Optimization? A Systematic Evaluation on the Traveling Salesman ProblemLiu, Shengcai; Zhang, Yu; Tang, Ke*; Yao, XinIEEE Computational Intelligence Magazine, 2023, 18(3): 14-28.被引 15
