This paper presents an improved version of the animal migration optimization (AMO) algorithm for solving the traveling salesman problem (TSP), which is classified 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 modified 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.