Un algoritmo evolutivo para resolver el problema de Coloración Robusta

 

Guardado en:
Detalles Bibliográficos
Autores: Lara Velázquez, Pedro, Gutiérrez Andrade, Miguel Ángel, Ramírez Rodríguez, Javier, López Bracho, Rafael
Formato: artículo original
Estado:Versión publicada
Fecha de Publicación:2005
Descripción:Let G and G be two complementary graphs. Given a penalty function defined over the edges of 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.
País:Portal de Revistas UCR
Institución:Universidad de Costa Rica
Repositorio:Portal de Revistas UCR
Lenguaje:Español
OAI Identifier:oai:portal.ucr.ac.cr:article/255
Acceso en línea:https://revistas.ucr.ac.cr/index.php/matematica/article/view/255
Access Level:acceso abierto
Palabra clave:Scatter search
graph coloring
heuristics
combinatorial optimization
discrete optimization
Búsqueda dispersa
coloración de gráficas
heurísticas
optimización combinatoria
optimización discreta