Volume 44, Issue 2, September 2019, Pages 131–143
Zar Chi Su Su Hlaing1
1 Faculty of Information Science, University of Computer Studies (Magway), Magway, Myanmar
Original language: English
Copyright © 2019 ISSR Journals. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Ant Colony Optimization (ACO) is a recent algorithm used for solving optimization problems and is the model on the behavior of real ant colonies. It has been used exclusively for solving problems in the combinatorial optimization domain. Traveling salesman problem (TSP) is one of the well-known and extensively studied problems in combinational optimization and used to find the shortest roundtrip of minimal total cost visiting each given city (node) exactly once and it can be applied to solve many practical problems in real life. ACO is a good search capability and a high-performance computing method for TSP. But, the traditional ACO has many drawbacks such as stagnation behavior, trapping in local optimal and premature convergence. This paper implements and evaluates a specialized version of ant colony optimization capable of searching in travelling salesman problems and evaluates its performance under a range of conditions and test cases. The proposed system is an improved ant colony optimization algorithm with dynamic candidate set strategy is adopted to rapid convergence speed and adapting parameter to improve the performance in solving TSP. Algorithms are tested on benchmark problems from TSPLIB and test results are presented. From our experiments, the algorithm has better performance on TSP and analysis results are presented.
Author Keywords: combinatorial optimization, stagnation behavior, adaptive behavior, dynamic candidate set, adapting parameter.
Zar Chi Su Su Hlaing1
1 Faculty of Information Science, University of Computer Studies (Magway), Magway, Myanmar
Original language: English
Copyright © 2019 ISSR Journals. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
Ant Colony Optimization (ACO) is a recent algorithm used for solving optimization problems and is the model on the behavior of real ant colonies. It has been used exclusively for solving problems in the combinatorial optimization domain. Traveling salesman problem (TSP) is one of the well-known and extensively studied problems in combinational optimization and used to find the shortest roundtrip of minimal total cost visiting each given city (node) exactly once and it can be applied to solve many practical problems in real life. ACO is a good search capability and a high-performance computing method for TSP. But, the traditional ACO has many drawbacks such as stagnation behavior, trapping in local optimal and premature convergence. This paper implements and evaluates a specialized version of ant colony optimization capable of searching in travelling salesman problems and evaluates its performance under a range of conditions and test cases. The proposed system is an improved ant colony optimization algorithm with dynamic candidate set strategy is adopted to rapid convergence speed and adapting parameter to improve the performance in solving TSP. Algorithms are tested on benchmark problems from TSPLIB and test results are presented. From our experiments, the algorithm has better performance on TSP and analysis results are presented.
Author Keywords: combinatorial optimization, stagnation behavior, adaptive behavior, dynamic candidate set, adapting parameter.
How to Cite this Article
Zar Chi Su Su Hlaing, “Analysis for Travelling Salesman Problem using Improved Ant Colony Optimization Algorithm,” International Journal of Innovation and Scientific Research, vol. 44, no. 2, pp. 131–143, September 2019.
