An Immunological Algorithm for Solving the Traveling Salesman Problem

• Thiago A. S. Masutti UNISANTOS
• Leandro N. de Castro UPM

Abstract

Evolutionary and immune inspired algorithms are presented as efficient approaches to solve combinatorial optimization problems. This report summarizes an immune approach to solve the traveling salesman problem (TSP), one of the most studied vehicle routing problems in the literature. As a benchmark, a genetic algorithm to solve the TSP is also investigated. In this report, both algorithms are described, detailed and compared when applied to several standard instances from the literature. For both algorithms the obtained results show a good performance in relation to the set of instances used, detaching the copt-aiNet, which was able to achieve better quality results.

References

Davis, L. (1991). Handbook of genetic algorithm, Van Nostrand Reinhold Company.

de Castro, L.N. (2007). Fundamentals of natural computing: An overview, Physics of Life Reviews, 4, 1-36.

de Castro, L.N. e Timmis, J.I. (2002). Artificial immune systems: A new computational intelligence approach, Springer-Verlag, Heidelberg.

de Souza, J.S., Gomes, L.C.T., Bezerra, G.B, de Castro, L.N. e Von Zuben, F.J. (2004). An immune-evolutionary algorithm for multiple rearrangements of gene expression data, Genetic Programming and Evolvable Machines, 5, 157-179.

Eiben, A.E. e Smith, J.E. (2003). Introduction to evolutionary computing, Springer.

Garey, M.R. e Johnson, D.S. (1979). Computers and intractability: A guide to the theory of NP-completeness, W. H. Freeman & Co., New York.

Holland, J.H. (1992), Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control and artificial intelligence, MIT Press.

Johnson, D.S. e McGeoch, L.A. (1997). The traveling salesman problem: A case study in local optimization, In Local Search in Combinatorial Optimization, E.H.L. Aarts e J.K. Lenstra (eds.), John Wiley & Sons, 215-310.

Larrañaga, P., Kuijpers, C.M.H, Murga, R.H, Inza, I., e Dizdarevic, S. (1999). Genetic algorithms for the travelling salesman problem: A review of representations and operators, Artificial Intelligence Review, 13, 129-170.

Lin, S. e Kernighan, B.W. (1973). An effective heuristic algorithm for the traveling salesman problem, Operations Research, 21(2), 498-516.

Michalewicz, Z. e Fogel, D.B. (2000). How to solve it: Modern heuristics, Springer.

Reinelt, G. (1991), TSPLIB – A traveling salesman problem library, ORSA Journal on Computing, 3, 376-384.

Whitley, D. (2000), Permutations. In Evolutionary computation 1: Basic algorithms and operators, Bäck, T., Fogel, D.B. e Michalewickz, Eds., Institute of Physics Publishing, Bristol, 274-284.