Um Algoritmo Imunológico para a Solução do Problema do Caixeiro Viajante
Resumo
Algoritmos evolutivos e imunológicos são apresentados como abordagens eficientes para a solução de problemas combinatórios. Este relatório apresenta um algoritmo imunológico para a solução do problema do caixeiro viajante (PCV). Para efeitos comparativos (benchmarking) também é investigado o uso de um algoritmo genético aplicado ao PCV. Neste relatório, a descrição de ambos algoritmos é apresentada e os resultados de experimentos computacionais com instâncias comumente utilizadas na literatura são descritos. Os resultados obtidos com as duas ferramentas demonstram um bom desempenho para o conjunto de instâncias avaliadas, com destaque para a coptaiNet, que obteve resultados de melhor qualidade.Referências
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.
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.
Publicado
20/07/2009
Como Citar
MASUTTI, Thiago A. S.; CASTRO, Leandro N. de.
Um Algoritmo Imunológico para a Solução do Problema do Caixeiro Viajante. In: CONCURSO DE TRABALHOS DE INICIAÇÃO CIENTÍFICA DA SBC (CTIC-SBC), 28. , 2009, Bento Gonçalves/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2009
.
p. 137-144.
