Tesis profesional presentada por

Juan Ricardo Rugerio Bretón [juan.rugeriobn@udlap.mx] Marco Antonio Sánchez Ortega

Miembro del Programa de Honores. Licenciatura en Actuaría. Departamento de Actuaría, Física y Matemáticas. Escuela de Ciencias, Universidad de las Américas Puebla.

Jurado Calificador

Presidente: Dra. Dolores Edwiges Luna Reyes
Vocal y Director: Dr. Juan Antonio Díaz García
Secretario: Dra. Luz María García Ávila

Cholula, Puebla, México a 7 de diciembre de 2018.

Resumen

El Problema de Coloreado de Grafos es un problema de optimización combinatoria ampliamente estudiado en la literatura, ya que muchos problemas de aplicación práctica se pueden formular como problemas de Coloreado de Grafos. Ejemplos de estos son la programación de tareas, la asignación de frecuencias en redes o la asignación de registros de memoria de una computadora. Dado que el problema pertenece a la clase de problemas NP-duro, se justifica el uso de métodos heurísticos para obtener soluciones factibles del problema, sobre todo para instancias de gran tamaño. A lo largo del tiempo se han desarrollado distintos métodos aproximados para obtener soluciones de buena calidad con un esfuerzo computacional razonable. En este trabajo se realizaron experimentos con dos heurísticas constructivas y un metaheurístico de Temple Simulado, con el fin de determinar cual de ellos presenta un mejor comportamiento con respecto a la calidad de las soluciones y el esfuerzo de cómputo requerido. Se supuso inicialmente que el algoritmo de temple simulado presentaría mejores resultados, ya que es un método metaheurístico que utiliza estrategias de diversificación e intensificación durante el proceso de búsqueda, mientras que los otros dos son heurísticas de tipo constructivo. Para comprobar esto se implementaron estos tres algoritmos y mediante un experimento computacional donde se utilizaron instancias de prueba del problema disponibles en la literatura, se observó que en la mayoría de los casos proporciona soluciones de buena calidad mejores a los proporcionados por los otros dos métodos heurísticos.

Palabras clave: Problema de Coloreado de Grafos, métodos heurísticos, algoritmos voraces, búsqueda local, Temple Simulado.

Índice de contenido

Portada

Índices

Capítulo 1. Introducción

Capítulo 2. Justificación

Capítulo 3. Objetivos

Capítulo 4. Marco Teórico

  • 4.1 Historia
  • 4.2 Trabajos destacados
  • 4.3 Algoritmos voraces
  • 4.4 Algoritmos basados en el mejoramiento de una solución inicial
  • 4.5 Métodos exactos
  • 4.6 Métodos Híbridos
  • 4.7 Aplicaciones

Capítulo 5. Metodología

  • 5.1 Descripción del problema
  • 5.2 Modelo matemático
  • 5.3 k-Coloreado
  • 5.4 Algoritmos voraces
  • 5.5 Búsqueda Local
  • 5.6 Temple Simulado

Capítulo 6. Implementaciones

  • 6.1 Algoritmo Secuencial: SEQ
  • 6.2 Algoritmo Recursivo RLF
  • 6.3 Algoritmo basado en la metodología de temple simulado
  • 6.4 Instancias

Capítulo 7. Resultados y Discusión

  • 7.1 Estadístico para la comparación de métodos
  • 7.2 Análisis e interpretación

Capítulo 8. Conclusiones y Recomendaciones

Referencias

Rugerio Bretón, J. R., Sánchez Ortega, M. A. 2018. Comparación de métodos heurísticos para el problema de Coloreado de Grafos. Tesis Licenciatura. Actuaría. Departamento de Actuaría, Física y Matemáticas, Escuela de Ciencias, Universidad de las Américas Puebla. Diciembre. Derechos Reservados © 2018.