Un Algoritmo Evolutivo para Resolver el Problema de Coloración Robusta

Abstract

Let G and \bar{G} be two complementary graphs. Given a penalty function defined over the edges of \bar{G}, it is said that the rigidity of a k-coloring of G is the summation ofthe penalties of the edges of G that join vertices whose endpoint are equally colored. Based on this previous definition, the Robust Coloring Problem is set when searching the valid k-coloring of minimum rigidity. Yáñez and Ramírez proved that this is an NP-hard problem. In this work we present an evolutive algorithm based in the scatter search technique, which obtains optimal solutions for those instances for which an optimal solution is known, and obtains the best known solutions compared to other heuristics, such as: simulated annealing, tabu search and partial enumeration.

Sean G y bar{G} un par de gráficas complementarias. Dada una función de peso definida sobre las aristas de \bar{G}, se dice que la rigidez de una k-coloración válida de G es la suma de los pesos de las aristas de \bar{G} que unen vértices del mismo color. Con base en la anterior definición, se plantea el Problema de Coloración Robusta al buscar la k-coloración válida de rigidez mínima. Yáñez y Ramírez probaron que este problema es NP-duro. En este trabajo se presenta un algoritmo evolutivo basado en la técnica de búsqueda dispersa, la cual obtiene soluciones óptimas, en las instancias para las que se conoce la solución óptima, y obtiene las mejores soluciones conocidas comparadas con otras heurísticas, tales como: recocido simulado, búsqueda tabú y enumeración parcial.