Diseño de un algoritmo memético para resolver el problema de coloración del vértice
Loading...
Date
2022-06-29
Advisors
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad Industrial de Santander
Abstract
El problema de coloración del vértice consiste en colorear todos los vértices de un grafo de
manera que los vértices que están conectados por una arista o borde no compartan el mismo
color, esto dado que son vértices adyacentes y el hecho de tener el mismo color representa un
conflicto en la coloración, a su vez se busca minimizar el número de colores usados. En el
mundo real dicho problema es usado para resolver problemas tales como asignación de asientos,
tareas, horarios, la planificación de actividades, la asignación de recursos, en problemas de
control de producción, para proyectar redes de ordenadores, en la logística, robótica, genética,
sociología, el diseño de redes, el cálculo de rutas óptimas y los problemas de almacenamiento,
donde se tiene un conjunto de elementos que deben ser asignados a determinados recursos
mientras se optimiza una función objetivo y se satisfacen las restricciones planteadas.
En la presente investigación se usa el problema de coloración del vértice para resolver un
problema de programación de horario a través de un algoritmo memético programado en Matlab,
dicho algoritmo es validado con datos aleatorios donde a través de un diseño factorial completo
se evalúan los factores que influyen en el desempeño del mismo con el fin de decidir el valor que
van a tomar al implementar el algoritmo en el caso de estudio de Escuela de Estudios Industriales
y Empresariales de la Universidad Industrial de Santander, se concluye que el algoritmo tiene un
mejor desempeño al emplear un conjunto reducido de datos y a su vez se reduce el tiempo de
ejecución por lo cual se decide dividir los datos del caso de estudio en 4 subproblemas
obteniendo resultados aceptables.
Description
Keywords
problema de coloración del vértice, teoría de grafos, algoritmo memético, programación de horarios