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
Format: Artículo
Language: Español
Published: 2015
Online Access: http://revistas.ucr.ac.cr/index.php/matematica/article/view/255
http://hdl.handle.net/10669/12901
id RepoKERWA12901
recordtype dspace
spelling 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
institution Universidad de Costa Rica
collection Repositorio KERWA
language Español
description 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.
format Artículo
author Lara Velázquez, Pedro
Gutiérrez Andrade, Miguel Ángel
Ramírez Rodríguez, Javier
López Bracho, Rafael
spellingShingle 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
author_sort Lara Velázquez, Pedro
title Un Algoritmo Evolutivo para Resolver el Problema de Coloración Robusta
title_short Un Algoritmo Evolutivo para Resolver el Problema de Coloración Robusta
title_full Un Algoritmo Evolutivo para Resolver el Problema de Coloración Robusta
title_fullStr Un Algoritmo Evolutivo para Resolver el Problema de Coloración Robusta
title_full_unstemmed Un Algoritmo Evolutivo para Resolver el Problema de Coloración Robusta
title_sort un algoritmo evolutivo para resolver el problema de coloración robusta
publishDate 2015
url http://revistas.ucr.ac.cr/index.php/matematica/article/view/255
http://hdl.handle.net/10669/12901
_version_ 1658176315037057024
score 11.790597