Resumen
El Problema del agente viajero (TSP) es un problema de optimización combinatoria muy estudiado en el área de computación científica y matemáticas aplicadas. La importancia del TSP radica en que varios problemas de optimización combinatoria se pueden formular con base en él. Hasta la fecha no se ha encontrado un algoritmo determinístico que resuelva el TSP en un tiempo polinomial. En el estado del arte se han reportado soluciones factibles en tiempo polinomial, mediante el uso de algoritmos no determinísticos conocidos como Metaheurísticas. En este trabajo se implementaron: el Algoritmo Genético (AG), Algoritmo Memético (AM), y el Algoritmo de Sistema Inmune (ASI) para resolver el TSP Simétrico. Los algoritmos implementados pertenecen a una familia de Metaheurísticas conocida como Algoritmos Evolutivos los cuales están inspirados en la evolución natural. Para identificar el desempeño de los algoritmos seleccionados, se realizó una comparación entre ellos haciendo uso de estadística no paramétrica para evidenciar el algoritmo con mejor desempeño para resolver el TSP.Citas
G. M. a. J. D, Computers and Intractability, San Francisco, EUA: W.H. Freeman, 1979.
D. Applegate, R. Bixby, V. Chvátal y W. Cook, “ On The Solution Of Traveling Salesman Problems,” Documenta Mathematica, vol. 3, pp. 645-656, 1998.
J. A. Montesino Guerra, H. J. Puga Soberanes, M. Ornelas Rodriguez, J. M. Carpio Valadez y U. E. Bernal Magallanes, “Análisis Comparativos de Metaheurísticas Aplicadas al Problema del TSP,” XII encuentro de Participación de la Mujer en La Ciencia, 2015.
F. Glover y G. A.kochenberger, Handbook Of Metaheuristics, Dordrecht, Alemania: Kluwer Academic, 2003.
E.-G. Talbi, Metaheuristics From Design to Implementation, Hoboken, New Jersey: John Wiley , 2009.
A. Konar, Artificial Intelligence and Soft Computing Behavioral and Cognitive Modeling of the Human Brain, New York, EUA: CRC Press, 2000.
M. Mitchell, An Introduction To Genetic Algorithms, London England: The MIT Press, 1998.
P. Moscato y C. Cotta, “Una Introducción a los Algoritmos Meméticos,” Revista Iberoamericana de Inteligencia Artificial, pp. 131-148, 2003.
L .N. De Castro y F. J. Von Zuben, “The Clonal Selection Algorithm with Engineering Applications,” In Workshop Procedings GECCO, 2000.
G. Reinelt, “TSPLIB 95,”Universität Heidelberg, pp. 1-17, 1995
J. Derrac, S. García, D. Molina y F. Herrera, “A practical tutorial on the use nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms,” Elsevier-Swarm and Evolutionary computation, vol. 1, pp. 3-18, 2011.
D. H. Wolpert y W. G. Macready, «No Free Lunch Theorems For Optimization,» IEEE Transactions on Evolutionary Computation, vol. 1, nº 1, pp. 67-82, 1997
Esta obra está bajo una Licencia Creative Commons Atribución-NoComercial-SinDerivadas 4.0 Internacional.