An elitist approach for solving the traveling salesman problem using an animal migration optimization algorithm

This paper presents an improved version of the animal migration optimization (AMO) algorithm for solving the traveling salesman problem (TSP), which is classi ed as a combinatorial NP-hard problem. AMO is one of the recent metaheuristic algorithms inspired by the migration behavior of animals and has been efficiently applied to a variety of optimization problems. The algorithm is improved by reconstructing the neighborhood topology of each animal during the migration. This modi ed algorithm is called the elitist animal migration optimization (ELAMO) algorithm, since elitism is introduced as a way in which the positions of the leaders are considered for the neighborhood scheme. To observe the performance of ELAMO, it is compared with AMO and some efficient algorithms. The experimental results showed that the ELAMO algorithm has improved the solution quality of AMO and has produced effective or even competitive values for the selected TSP data sets.

PDF

___

[1] Robinson J. On the Hamiltonian Game: A Traveling Salesman Problem. No. RAND/RM-303. Arlington, VA, USA: US Department of Defense, 1949.
[2] Geng X, Chen Z, Yang W, Shi D, Zhao K. Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search. Appl Soft Comput 2011; 11: 3680-3689.
[3] Chen SM, Chien CY. Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques. Expert Syst Appl 2011; 38: 14439-14450.
[4] Albayrak M, Allahverdi N. Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms. Expert Syst Appl 2011; 38: 1313-1320.
[5] Peker M, Sen B, Kumru PY. An efficient solving of the traveling salesman problem: the ant colony system having parameters optimized by the Taguchi method. Turk J Elec Eng & Comp Sci 2013; 21: 2015-2036.
[6] Dorigo M, Gambardella LM. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE T Evol Comput 1997; 1: 53-66.
[7] Gunduz M, Kran MS, Ozceylan E. A hierarchic approach based on swarm intelligence to solve the traveling salesman problem. Turk J Elec Eng & Comp Sci 2015; 23: 103-117.
[8] Ouaarab A, Ahiod B, Yang XS. Discrete cuckoo search algorithm for the travelling salesman problem. Neural Comput Appl 2014; 24: 1659-1669.
[9] Karaboga D, Gorkemli B. A combinatorial arti cial bee colony algorithm for traveling salesman problem. In: IEEE 2011 International Symposium on Innovations in Intelligent Systems and Applications, 15{18 June 2011; _ Istanbul, Turkey. New York, NY, USA: IEEE. pp. 50-53.
[10] Wolpert DH, Macready WG. No free lunch theorems for optimization. IEEE T Evol Comput 1997; 1: 67-82.
[11] Li X, Zhang J, Yin M. Animal migration optimization: an optimization algorithm inspired by animal migration behavior. Neural Comput Appl 2014; 24: 1867-1877.
[12] Ma M, Luo Q, Zhou Y, Chen X, Li L. An improved animal migration optimization algorithm for clustering analysis. Discrete Dyn Nat Soc 2015; 2015: 194792.
[13] Zhou Y, Luo Q, Ma M, Qiao S, Bao Z. An animal migration optimization algorithm for constrained engineering optimization problems. J Comput Theor Nanosci 2016; 13: 539-546.
[14] Ulker ED, Ulker S. Antenna design using animal migration optimization algorithm. IET J Eng 2016; 1: D23J.
[15] Cunkas M, Ozsaglam M.Y. A comparative study on particle swarm optimization and genetic algorithms for traveling salesman problems. Cybern Syst 2009; 40: 490-507.
[16] Reinelt G. TSPLIB|A traveling salesman problem library. ORSA J Comput 1991; 3: 376-384.
[17] Ozcan E, Erenturk M. A brief review of memetic algorithms for solving Euclidean 2D traveling salesrep problem. In: 2004 Turkish Symposium on Arti cial Intelligence and Neural Networks; 10{11 June 2004; _ Izmir, Turkey. pp. 99-108.
[18] Masutti TAS, Castro LN. A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem. Inf Sci 2009; 179: 1454-1468.