NATURE INSPIRED METAHEURISTICS COMPARATIVE STUDY TO SOLVE TRAVELING SALESMAN PROBLEM

Authors

  • Agung Chandra Universitas Mercu Buana

DOI:

https://doi.org/10.21776/ub.jemis.2021.009.02.1

Keywords:

TSP, ACO, ABC, PSO

Abstract

There are numerous optimization method to solve the traveling salesman problem, TSP. One of methods is metaheuristics which is the state of the art algorithm that can solve the large and complex problem. In this research, three of well-known nature inspired population based metaheuristics algorithm: Ant Colony Optimization – ACO, Artificial Bee Colony – ABC and Particle Swarm Optimization – PSO are compared to solve the 29 destinations by using Matlab program. The ACO produces the shortest distance, 94 kilometers and is more efficient than ABC and PSO methods.

References

Bonyadi M.R., Azghadi M.R., Shah-Hosseini H. Population Based Optimization Algorithm for Solving the Traveling Salesman Problem. In: Greco F. (eds.). Traveling Salesman Problem. In-Tech. Croatia; 2008. p.001-034.

Saud S., Kodaz H., Babaoglu I. Solving Traveling Salesman Problem by Using Optimization Algorithm. The 9th International Conference on Advances in Information Technology: IAIT Conference Proceedings volume 2017.

Talbi E.G. Metaheuristics: From Design to Implementation. New Jersey: John Wiley and Sons; 2009.

Teodorovic D., Selmic M., Davidovic T. Bee Colony Optimization Part II: The Application Survey. Yugoslav Journal of Operations Research; 2015: 25 (2): 185-219. Available from: DOI: 10.2298/YJOR131029020T.

Baluja S., Caruana R. Removing the genetics from the standard genetic algorithm. In: Prieditis A., Russell S. (eds). Proceedings of the Twelfth International Conference on Machine Learning (ML-95); Palo Alto, California; 1995.

De Bonet J.S., Isbell C.L., Viola P. MIMIC: Finding optima by estimating probability densities. In: Mozer M.C., Jordan M.I., Petsche T. Advances in Neural Information Processing System; 1997: Vol 9: 424-431.

Larranaga P., Lozano J.A. Estimation of Distribution Algorithms. A New Tool for Evolutionary Computation. Genetic Algorithms and Evolutionary Computation. Dordrecht, Netherlands, Kluwer Acedmic Publishers; 2001.

Robbins H., Monroe H. A Stochastic approximation method. Annals of Mathematics and Statistics; 1951: 22: 400 – 407.

Rubinstein R.Y. The cross entropy method for combinatorial and continuous optimization. Methodology and Computing in Applied Probability; 1999: 1: 1(2): 127-190.

Dorigo M., Stutzle T. Ant Colony Optimization. Massachussetts Institute of Technology; 2004.

Onder E, Ozdemir M., Yildirim B.F. Combinatorial Optimization Using Artificial Bee Colony Algorithm and Particle Swarm Optimization. KAU IIBF Dergisi; 2013: 4(6): 59-70.

Boussaid I., Lepagnot J., and Siarry P. A Survey On Optimization Metaheuristics. Information Sciences; 2013: 237: 82 – 117.

Gharib A., Benhra J., and Chaouqi M. A Performance Comparison of Particle Swarm Optimization and Genetic Algorithm Applied to Traveling Salesman Problem. International Journal of Computer Applications; 2015: Vol.130 no.15: 35 – 39.

Clerc M. Standard Particle Swarm Optimization From 2006 to 2011. 2012. Available from: http://www.mauriceclerc.net. [Accessed 26th August 2020].

Clerc, M. 2000. Discrete Particle Swarm Optimization: Illustrated by the Traveling Salesman Problem. Available from: http://www.mauriceclerc.net. [Accessed 26th August 2020].

Downloads

Published

2021-11-30

Issue

Section

Articles