Comportamiento Sinérgico En Hiperheurística de Selección para la Solución de los Problemas del Agente Viajero
DOI:
https://doi.org/10.30973/progmat/2016.8.3/5Palabras clave:
Transformadortérmico, Relación de flujo, control automáticoResumen
En este trabajo se muestra el comportamiento sinérgico que se produce en la implementación de una Hiperheurística de selección aplicada al problema del agente viajero (TSP, por sus siglas en inglés). Como órgano rector de la Hiperheurística se utilizó un Algoritmo Genético, y un conjunto de 5 heurísticas de bajo nivel. Para hacer las pruebas se utilizaron instancias de entrenamiento del estado del arte para TSP, y para el análisis de resultados, se hizo una comparación del mejor genotipo obtenido del entrenamiento de la combinación de las heurísticas, contra genotipos que contienen un solo tipo de heurística analizados desde un enfoque de optimización. En las pruebas estadísticas se utilizó como representante estadístico la mediana obtenida de dichos experimentos. Se presentan la explicación del entrenamiento fuera de línea de la Hiperheurística y los resultados que muestran que la hiperheurística es capaz de mejorar los resultados de las heurísticas aplicadas individualmente.
Citas
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
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 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
Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.
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. |
