An Adaptive Ant Colony System Memorizing Better Solutions (aACS-MBS) For Traveling Salesman Problem

Year 2021, Volume: 25 Issue: 3, 673 - 689, 30.06.2021

Dursun Ekmekci

https://doi.org/10.16984/saufenbilder.822646

Abstract

Choosing the optimal among the many alternatives that meet the criteria is one of the problems that occupy life. This kind of problems frequently encountered by commercial companies in daily life is one of the issues that operators focus on with care. Many techniques have been developed that can provide acceptable solutions in a reasonable time. However, one of the biggest problems for these techniques is that the appropriate values can be assigned to the algorithm parameters. Because one of the most important issues determining algorithm performance is the values to be assigned to its parameters. The Ant Colony System (ACS) is a metaheuristic method that produces successful solutions, especially in combinatorial optimization problems. However, it is very difficult to be able to direct the algorithm to different areas of the search space and, on the other hand, to maintain its local search capability. In this study, a solution proposal is presented that updates the q0 parameter dynamically, which balances the exploitation and exploration activities of the ACS. The method has been tested on the traveling salesman problem (TSP) of different sizes, and the obtained results are evaluated together with the change in the q0 parameter, and the solution search strategy of the algorithm is analyzed. With the pheromone maps formed as a result of the search, the effect of transfer functions was evaluated. Results obtained with aACS-MBS were compared with different ant colony optimization (ACO) algorithms. The aACS-MBS fell behind the most successful solution found in the literature, by up to 4%, in large TSP benchmarks. As a result, it has been seen that the method can be successfully applied to combinatorial optimization problems.

Keywords

ant colony optimization, ant colony system, ant colony system memorizing better solutions, adaptive ant colony system memorizing better solutions

References

• [1] D. EKMEKCİ, “Optimizasyon Problemleri İçin Geliştirilmiş Feromonal Yapay Arı Koloni (gfYAK) Algoritması,” Eur. J. Sci. Technol., no. August, pp. 442–450, Aug. 2020.
• [2] M. Dorigo, V. Maniezzo, and A. Colorni, “Positive feedback as a search strategy,” Milano, Italy, 1991.
• [3] M. Dorigo and T. Stützle, “Ant Colony Optimization: Overview and Recent Advances,” in International Series in Operations Research and Management Science, vol. 272, 2019, pp. 311–351.
• [4] B. Chandra Mohan and R. Baskaran, “A survey: Ant Colony Optimization based recent research and implementation on several engineering domain,” Expert Syst. Appl., vol. 39, no. 4, pp. 4618–4627, Mar. 2012.
• [5] D. Ekmekci, “An Ant Colony Optimization Memorizing Better Solutions (ACO-MBS) for Traveling Salesman Problem,” in 2019 3rd International Symposium on Multidisciplinary Studies and Innovative Technologies (ISMSIT), 2019, pp. 1–5.
• [6] Kwang Mong Sim and Weng Hong Sun, “Ant colony optimization for routing and load-balancing: survey and new directions,” IEEE Trans. Syst. Man, Cybern. - Part A Syst. Humans, vol. 33, no. 5, pp. 560–572, Sep. 2003.
• [7] M. Dorigo and G. Di Caro, “Ant colony optimization: a new meta-heuristic,” in Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406), 1999, vol. 2, pp. 1470–1477.
• [8] D. Zhao, L. Luo, and K. Zhang, “An improved ant colony optimization for the communication network routing problem,” Math. Comput. Model., vol. 52, no. 11–12, pp. 1976–1981, Dec. 2010.
• [9] Z. Zhang and Z. Feng, “A novel Max-Min ant system algorithm for traveling salesman problem,” in 2009 IEEE International Conference on Intelligent Computing and Intelligent Systems, 2009, vol. 1, no. 60875043, pp. 508–511.
• [10] M. Dorigo, V. Maniezzo, and A. Colorni, “Ant system: optimization by a colony of cooperating agents,” IEEE Trans. Syst. Man Cybern. Part B, vol. 26, no. 1, pp. 29–41, 1996.
• [11] M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Trans. Evol. Comput., vol. 1, no. 1, pp. 53–66, Apr. 1997.
• [12] M. Dorigo and T. Stützle, “The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances,” in Journal of the Operational Research Society, vol. 60, no. 7, 2003, pp. 250–285.
• [13] E. Ateş, “Gezgin Satıcı Probleminin Çözümü Ve 3 Boyutlu Benzetimi,” 2012.
• [14] L. Gilbert, “The Traveling Salesman Problem: An overview of exact and approximate algorithms,” Eur. J. Oper. Res., vol. 59, pp. 231–247, 1992.
• [15] M. A. Tawhid and P. Savsani, “Discrete Sine-Cosine Algorithm (DSCA) with Local Search for Solving Traveling Salesman Problem,” Arab. J. Sci. Eng., vol. 44, no. 4, pp. 3669–3679, Apr. 2019.
• [16] S. Rana and S. Ranjan Srivastava, “Solving Travelling Salesman Problem Using Improved Genetic Algorithm,” Indian J. Sci. Technol., vol. 10, no. 30, pp. 1–6, Sep. 2017.