Publication:
Performance Analysis of Metaheuristics and Hybrid Metaheuristics for the Travel Salesman Problem

Thumbnail Image
Files

Files

Performance Analysis of Metaheuristics and Hybrid Metaheuristics for the Travel Salesman Problem.pdf (833.31 KB)
View Statistics
Reference Managers
Mendeley
Indexers
Google Scholar CORE
QR Code
QR Code
Authors

Authors

Gutiérrez Hernández, David A.
Escobar, Marco A.
Del Valle Hernández, Josué
Gómez Díaz, Miguel
Villanueva Rodríguez, José Luis
López López, Juan Manuel
Lara Rendón, Claudia
Rodríguez Montero, Rossana
Nava Martínez, Héctor
Abstract (Spanish)
Se presenta un análisis de desempeño de metaheurísticas y metaheurísticas híbridas para el problema del viajante de comercio. Se utilizaron cuatro metaheurísticas clásicas individuales (algoritmo genético, algoritmo memético, búsqueda local iterada y recocido simulado). Además, se utilizaron variaciones híbridas utilizando nueve técnicas heurísticas diferentes para la búsqueda local, la mutación y la intensificación. El análisis de desempeño se realizó utilizando la prueba de Friedman, y para los algoritmos de recocido simulado y búsqueda local se encontró evidencia estadística de que la hibridación proporciona una diferencia en el desempeño, mientras que no se encontró evidencia para los algoritmos genéticos y meméticos. Se encontraron hasta seis combinaciones que mejoran el desempeño, cinco de ellas basadas en la búsqueda local y una más basada en recocido simulado.
Abstract (English)
A performance analysis of metaheuristics and hybrid metaheuristics for the travel salesman problem is presented. Four single classical metaheuristics (genetic algorithm, memetic algorithm, iterated local search, and simulated annealing) were used. In addition, hybrid variations using nine different heuristic techniques for the local search, the mutation, and the intensification were used. The performance analysis was made using the Friedman test, and for the simulated annealing and local search algorithms statistical evidence was found that hybridization provides a difference in performance, while no evidence was found for the genetic and memetic algorithms. Up to six combinations were found to improve performance, five of them based on local search and one more based on simulated annealing.
Extent
6 páginas
URI: https://repositorio.escuelaing.edu.co/handle/001/3378
Collections

Collections

AA. Gibiome
References

Abdoun, O., Abouchabaka, J., & Tajani, C. (2012). Analyzing the Performance of Mutation Operators to Solve the Travelling Salesman Problem. International Journal of Emerging Sciences, 2(1), 61–77

Bang-Jensen, J., Gutin, G., & Yeo, A. (2004). When the greedy algorithm fails. Discrete Optimization, 1(2), 121–127. http://doi.org/10.1016/j.disopt.2004.03.007

Bendall, G., & Margot, F. (2006). Greedy-type resistance of combinatorial problems. Discrete Optimization, 3(4), 288–298. http://doi.org/10.1016/j.disopt.2006.03.001

Blazinskas, A., & Misevicius, A. (2009). Combining 2-Opt, 3-Opt and 4-Opt With K-Swap-Kick Perturbations for the Traveling Salesman Problem. Kaunas University of Technology, Department of Multimedia Engineering, Studentu St, 50–401.

Cook, W. (2011). In pursuit of the traveling salesman: mathematics at the limits of computation. Chemistry & …, 635–638. Retrieved from http://books.google.com/books?hl=en&lr=&id=S3bxbr_- qhYC&oi=fnd&pg=PP2&dq=In+pursuit+of+the+traveling+salesman+ :mathematics+at+the+limits+of+computation&ots=jDzfyEkzKs&sig= 13_GiNHiPpLZDgM4p6tAtI4OOLs

Dorigo, M., & Tutzle, T. (2010). Handbook of Metaheuristics. In M.Gendreau, J.-Y. Potvin (eds.), Handbook of Metaheuristics, International Series in Operations Research and Management Science (Vol. 146, p. 648). http://doi.org/10.1007/978-1-4419-1665-5.

Gutin, G., & Punnen, A. (2007). The Traveling Salesman Problem and its Variations. … of Combinatorial Optimization: Problems and …, 749. http://doi.org/10.1007/b101971

Talbi, E. G. (2009). Metaheuristics: From Design to Implementation. Metaheuristics: From Design to Implementation. http://doi.org/10.1002/9780470496916

Zanakis, S. H., & Evans, J. R. (1981). Heuristic “Optimization”: Why, When, and How to Use It. Interfaces, 11(5), 84–91. http://doi.org/10.1287/inte.11.5.84o. 2, pp. 415–420, 2008.