Estudio comparativo de algoritmos de solución para el problema de coloración de graficas suaves.
2018Profesores: Dr. Pedro Lara Velázquez y Dr. Miguel Ángel Gutiérrez Andrade
Resumen: La coloración de gráficas suaves es una generalización del problema de coloración en el que se busca encontrar una coloración que minimice la dureza en la gráfica, o dicho de otra forma, reducir la suma de distancias entre vértices con colores idénticos (Lara-Velázquez, et al., 2015). Este modelo se utiliza en la programación de eventos susceptibles de cambios, asignación estable de frecuencias del espectro electromagnético, calendarización de actividades, asignación de recursos en organizaciones, en reconocimiento de patrones en general y en particular en un algoritmo clasificador no supervisado (Flores, 2017). Se ha demostrado que es un problema de tipo NP-Duro, aunque para grafos de orden menor o igual a 20, se pueden utilizar algoritmos exactos que resuelven el problema; caso contrario es necesario el uso de técnicas heurísticas que dan buenas soluciones.
Hay cuatro algoritmos metaheurísticos que se han utilizado para resolver este problema:
1. Recocido simulado.
2. Búsqueda dispersa.
3. GRASP clásico.
4. Híbrido k-medias/GRASP.
Estos algoritmos se han utilizado parcialmente en diferentes aplicaciones, pero no se han realizado un estudio de la calidad de soluciones y tiempos de ejecución que abarque todos los tipos de instancias, por ejemplo, búsqueda dispersa y GRASP solo se ha usado en instancias pseudoaleatorias pero no en problemas reales, y por otra parte los problemas de aplicación solo se ha utilizado modelo binario (un modelo de solución exacto) y recocido simulado.
Objetivo general
- Hacer un estudio de calidad de soluciones y tiempos de ejecución de 4 algoritmos en instancias teóricas y aplicadas del problema de coloración de gráficas suaves.
Objetivos específicos
- Recopilar instancias de prueba realizadas en trabajos anteriores (ver referencias).
- Estudiar los algoritmos de solución que se utilizarán en el estudio comparativo.
- Modificar y en su caso, reprogramar los algoritmos de solución para resolver las instancias de prueba, tomando como funciones de desempeño: dureza, resiliencia y tiempo de ejecución.
- Análisis de resultados usando diseño de experimentos.
- Escritura de un artículo para congreso nacional.
- Reportar los resultados obtenidos en la Idónea Comunicación de Resultados (ICR).
Ultima actualización 13/08/2022 por pcyti