Algorithm Methods Comparison on TSP
Download as PDF
Xian Wu, Yu Hao, Kaiyu Guo, Huyu Wu
In the previous research, other researchers focus on the improvement and hybrid algorithms that can be used in solving TSP. However, this article indicates eight different algorithms to solve TSP which includes Advantage Actor Critic (A2C), Deep Q-Network (DQN), Proximal Policy Optimization (PPO) and five number of evolutionary algorithms: Particle swarm optimization (PSO), Ant Colony Optimization (ACO), Simulated Annealing (SA), Genetic Algorithm (GA), Tabu Search (TS). The article states that it’s significant to do research on TSP, and builds a specific question initially. Next, the article shows the principle of each algorithm and fundamental operation step. Then, author do an internal comparison in the evolutionary algorithms, the step is also known as adjusting parameter. This step compares the specific time and distance-cost among different parameter setting. Obviously, it can make the researcher consider the better performance of the algorithms in different conditions. Finally, the author compares the different behavior between those eight algorithms, illustrating the path figure and converge figure of each algorithm. Path figures and converge figures illustrate how the iteration times affect the converge steps and specific path. All the works done contributes to the research of TSP to some extents.
combinatorial optimization, TSP, evolutionary algorithms, reinforcement learning