Synergy behavior in hyper-heuristics of selection for the solution in the traveling salesman problem
DOI:
https://doi.org/10.30973/progmat/2016.8.3/5Keywords:
hyper-heuristic, optimization, fitnessAbstract
In this paper the synergistic behavior that occurs in the implementation of a selection Hyper-heuristic applied to the traveling salesman problem (TSP, for its acronym) is shown. As administrator core of the Hyper-heuristic has been used a Genetic Algorithm, and a set of five low-level heuristics were used. For the testing phase were used training instances of the state of the art, and for the analysis of results, a comparison was made between the besttraining obtained genotype from the combination of heuristics, and against genotypes containing only one type of heuristic analyzed from an optimization approach. In statistical tests were used as statistical representative the median obtained from these experiments. Explanation of the offline training of Hyper-heuristic it´s presented and the results show that the hyper-heuristic is able to improve the performance of the heuristics applied individually.
References
Burke, E. K., Hart, E., Kendall, G., Newall, J., Ross, P., and Schulenburg, S. Hyper-heuristics: An emerging direction in modern search technology. Handbook of Metaheuristics, (2003), pages 457–474. https://doi.org/10.1007/0-306-48056-5_16
Burke, E. K., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., Woodward, J. R. A Classification of Hyper-heuristic Approaches. Handbook of Metaheuristics, (2010). (pp 449-468). The University of Nottingham, Nottingham, UK: Springer US. https://doi.org/10.1007/978-1-4419-1665-5_15
Lin, S., and Kernighan, B.W., An effective heuristic algorithm for the traveling salesman problem, (1973) Oper. Res. 21. pp. 498–516. https://doi.org/10.1287/opre.21.2.498
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., and Shmoys, D.B., The Traveling Salesman Problem: The Guided Tour of Combinatorial Optimization, (1985), Wiley and Sons, New York.
Padberg, M. and Rinaldi, G., Optimization of a 532-city symmetric traveling salesman problem by branch and cut, (1987), Oper. Res. 6 pp. 1–7. https://doi.org/10.1016/0167-6377(87)90002-2
Denzinger, J., Fuchs, M., Fuchs, M., High Performance ATP Systems by Combining Several AI Methods. In proc. Fifteenth international joint conference on artificial intelligence (ijcai ’97). (1997). Pages 102–107, CA, USA.
Cowling, P., Kendall, G., Soubeiga, E., A Hyperheuristic Approach to Scheduling a Sales Summit. Springer. In Selected Papers of the Third International Conference on the Practice And Theory of Automated Timetabling, (2000), PATAT 2000, Lecture Notes in Computer Science, pages 176–190, Konstanz, Germany. Springer. https://doi.org/10.1007/3-540-44629-X_11
Ross., P., Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, Hyper-heuristics. In E. K. Burke and G. Kendall, (2005), chapter 17, pages 529–556. Springer, Berlin. https://doi.org/10.1007/978-1-4614-6940-7
Sucupira., I., R., Metodos Heurísticos Genéricos: Meta Heurísticos e Hiper-Heurísticas. Tesis de Maestría. (2004), Universidad de Sao Paulo.
Soubeiga., E., Development and Application of Hyperheuristics to Personnel Scheduling. PhD thesis, June (2003), School of Computer Science and Information Technology, University of Nottingham.
Sucupira., I. R., Un Estudo Empírico de Hiper-Heurísticas. Tesis de Maestría. (2007), Universidad de Sao Paulo. Brasil.
Soria Alcaraz., J. A., Diseño de Horarios con Respecto al Alumno mediante Técnicas de Cómputo Evolutivo. Tesis de Maestría. Julio (2010), Instituto Tecnológico De León. León Guanajuato, México.
Goldberg., D. E., Genetic algorithms in search, optimization, and machine learning. (1989) Addison-Wesley Pub. Co. Reading, Massachusetts.
Yang., X. S., Nature-inspired metaheuristic algorithms. (2010), Luniver press.
Abdoun, O., Abouchabaka, J., Tajani, C., Analyzing the Performance of Mutation Operators to Solve the TSP. International Journal of Emerging Sciences, March (2012), LaRIT Laboratory, Faculty of sciences, Ibn Tofail University, Kenitra, Morocco. JES, 2(1), pages 61-77, https://doi.org/10.48550/arXiv.1203.3099
Lin, S., and Kernighan, B. W., An Effective Heuristic Algorithm for the Traveling-Salesman Problem. (1973). Operations Res. 21, pages 498-516. https://doi.org/10.1287/opre.21.2.498
Simó., F. G., El problema del Viajante de Comercio. Tesis de Licenciatura. (1996). Universidad Tecnológica Nacional. Facultad Regional Córdoba.
Reinelt., G., TSPLIB 95. (1995). Universitat Heidelberg. Pages 1-17. https://doi.org/10.1155/2015/378087
Croes., G. A., A method for solving traveling salesman problems. (1958). Operations Res. 6. pp., 791-812. https://doi.org/10.1287/opre.6.6.791
Derrac, J., Garcia, S., Molina, D., Herrera, F., A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and Evolutionary Computation, (2011) 1(1), 3-18. https://doi.org/10.1016/j.swevo.2011.02.002
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2016 Juan Adolfo Montesino Guerra, Héctor José Puga Soberanes, Marco Aurelio Sotelo Figueroa, Carpio Valadez Juan Martín, Manuel Ornelas Rodríguez, Jorge Alberto Soria Alcaraz, Raúl Santiago Montero
This work is licensed under a Creative Commons Attribution 4.0 International License.
Usted es libre de:
Compartir — compartir y redistribuir el material publicado en cualquier medio o formato. |
Adaptar — combinar, transformar y construir sobre el material para cualquier propósito, incluso comercialmente. |
Bajo las siguientes condiciones:
Atribución — Debe otorgar el crédito correspondiente, proporcionar un enlace a la licencia e indicar si se realizaron cambios. Puede hacerlo de cualquier manera razonable, pero de ninguna manera que sugiera que el licenciador lo respalda a usted o a su uso. |
Sin restricciones adicionales: no puede aplicar términos legales o medidas tecnológicas que restrinjan legalmente a otros a hacer cualquier cosa que permita la licencia. |