Developing a dynamic neighborhood structure for an adaptive hybrid simulated annealing tabu search algorithm to solve the symmetrical traveling salesman problem
AHSATS d CM: Adaptive Hybrid Simulated Annealing Tabu Search Algorithm with Dynamic Neighborhood Based on Circle directed Mutation.AHSATS 2 opt: Adaptive Hybrid Simulated Annealing Tabu Search Algorithm with 2 opt.Conclusions: This paper develops an adaptive hybrid meta heuristic algorithm that combines simulated annealing and tabu search algorithms with a dynamic neighborhood structure to solve the Traveling Salesman Problem (TSP) The experimental results demonstrated that the proposed algorithm can obtain satisfactory solutions within a reasonable time. Moreover, the proposed algorithm can overcome the individual disadvantages of simulated annealing and tabu search. The new hybrid algorithm provides a fast decrease rate and a clear convergence process, and is not dependent on initial solutions. Furthermore, compared with the classical 2 opt neighborhood, the dynamic neighborhood can significantly reduce computational time by decreasing the number of calculations and simultaneously improve solution quality. Finally, the adaptive parameters are appropriate for solving almost all benchmark test examples.Display Omitted A hybrid simulated annealingtabusearch algorithm is applied to solve the traveling salesman problem.A dynamic neighborhood based on circle directed mutation is developed for the hybrid algorithm.Adaptive parameters are proposed for the hybrid algorithm.Experiments are conducted to verify the accuracy and efficiency of the hybrid algorithm proposed.Experimental results are compared with other algorithms derived from literature. This paper applies a hybrid simulated annealing tabu search algorithm to solve the Traveling Salesman Problem (TSP) Fully considering the characteristics of the hybrid algorithm, we develop a dynamic neighborhood structure for the hybrid algorithm to improve search efficiency by reducing the randomness of the conventional 2 opt neighborhood. A circle directed mutation is developed to achieve this dynamic neighborhood structure. Furthermore, we propose adaptive parameters that can be automatically adjusted by the algorithm based on context specific examples. This negates the need to frequently readjust algorithm parameters. We employ benchmarks obtained from TSPLIB (a library of sample instances for the TSP) to test our algorithm, and find that the proposed algorithm can obtain satisfactory solutions within a reasonable amount of time. The experimental results demonstrate that the proposed hybrid algorithm can overcome the disadvantages of traditional simulated annealing and tabu search methods. The results also show that the dynamic neighborhood structure is more efficient and accurate than the classical 2 opt. Also, adaptive parameters are appropriate for almost all of the numerical examples tested in this paper. Finally, the experimental results are compared with those of other algorithms, to demonstrate the improved accuracy and efficiency of the proposed algorithm.
Appl. Soft Comput.