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

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, th...

Full description

Main Authors: Lara Velázquez, Pedro, Gutiérrez Andrade, Miguel Ángel, Ramírez Rodríguez, Javier, López Bracho, Rafael Artículo Español 2015 http://revistas.ucr.ac.cr/index.php/matematica/article/view/255 http://hdl.handle.net/10669/12901
id RepoKERWA12901 dspace RepoKERWA129012017-08-08T18:50:20Z Un Algoritmo Evolutivo para Resolver el Problema de Coloración Robusta Un Algoritmo Evolutivo para Resolver el Problema de Coloración Robusta Lara Velázquez, Pedro Gutiérrez Andrade, Miguel Ángel Ramírez Rodríguez, Javier López Bracho, Rafael 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. 2015-05-19T18:43:00Z 2015-05-19T18:43:00Z 2012-03-22 00:00:00 2015-05-19T18:43:00Z info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion http://revistas.ucr.ac.cr/index.php/matematica/article/view/255 http://hdl.handle.net/10669/12901 10.15517/rmta.v12i1-2.255 es Revista de Matemática: Teoría y Aplicaciones Vol. 12 Núm. 1-2 2012 111-120 application/pdf Universidad de Costa Rica Repositorio KERWA Español 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. Artículo Lara Velázquez, Pedro Gutiérrez Andrade, Miguel Ángel Ramírez Rodríguez, Javier López Bracho, Rafael Lara Velázquez, Pedro Gutiérrez Andrade, Miguel Ángel Ramírez Rodríguez, Javier López Bracho, Rafael Un Algoritmo Evolutivo para Resolver el Problema de Coloración Robusta Lara Velázquez, Pedro Un Algoritmo Evolutivo para Resolver el Problema de Coloración Robusta Un Algoritmo Evolutivo para Resolver el Problema de Coloración Robusta Un Algoritmo Evolutivo para Resolver el Problema de Coloración Robusta Un Algoritmo Evolutivo para Resolver el Problema de Coloración Robusta Un Algoritmo Evolutivo para Resolver el Problema de Coloración Robusta un algoritmo evolutivo para resolver el problema de coloración robusta 2015 http://revistas.ucr.ac.cr/index.php/matematica/article/view/255 http://hdl.handle.net/10669/12901 1658176315037057024 11.790597