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

Sean G y G un par de gráficas complementarias. Dada una función de peso definida sobre las aristas de 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 G que unen vértices del mismo color. Con base en la anterior definición, se plantea el Problema de...

Descripción completa

Detalles Bibliográficos
Autores principales:	Lara Velázquez, Pedro, Gutiérrez Andrade, Miguel Ángel, Ramírez Rodríguez, Javier, López Bracho, Rafael
Formato:	Online
Idioma:	spa
Publicado:	Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2005
Acceso en línea:	https://revistas.ucr.ac.cr/index.php/matematica/article/view/255

id	RMTA255
record_format	ojs
spelling	RMTA2552022-01-20T15:32:16Z 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 Scatter search graph coloring heuristics combinatorial optimization discrete optimization Búsqueda dispersa coloración de gráficas heurísticas optimización combinatoria optimización discreta 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. Sean G y G un par de gráficas complementarias. Dada una función de peso definida sobre las aristas de 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 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. Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2005-02-01 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion Article application/pdf https://revistas.ucr.ac.cr/index.php/matematica/article/view/255 10.15517/rmta.v12i1-2.255 Revista de Matemática: Teoría y Aplicaciones; Vol. 12 No. 1-2 (2005): Revista de Matemática: Teoría y Aplicaciones; 111-120 Revista de Matemática: Teoría y Aplicaciones; Vol. 12 Núm. 1-2 (2005): Revista de Matemática: Teoría y Aplicaciones; 111-120 Revista de Matemática; Vol. 12 N.º 1-2 (2005): Revista de Matemática: Teoría y Aplicaciones; 111-120 2215-3373 1409-2433 spa https://revistas.ucr.ac.cr/index.php/matematica/article/view/255/235 Derechos de autor 2005 Revista de Matemática: Teoría y Aplicaciones
institution	Universidad de Costa Rica
collection	Revista de Matemática: Teoría y Aplicaciones
language	spa
format	Online
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_facet	Lara Velázquez, Pedro Gutiérrez Andrade, Miguel Ángel Ramírez Rodríguez, Javier López Bracho, Rafael
author_sort	Lara Velázquez, Pedro
description	Sean G y G un par de gráficas complementarias. Dada una función de peso definida sobre las aristas de 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 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.
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
title_alt	Un algoritmo evolutivo para resolver el problema de Coloración Robusta
publisher	Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA)
publishDate	2005
url	https://revistas.ucr.ac.cr/index.php/matematica/article/view/255
work_keys_str_mv	AT laravelazquezpedro unalgoritmoevolutivopararesolverelproblemadecoloracionrobusta AT gutierrezandrademiguelangel unalgoritmoevolutivopararesolverelproblemadecoloracionrobusta AT ramirezrodriguezjavier unalgoritmoevolutivopararesolverelproblemadecoloracionrobusta AT lopezbrachorafael unalgoritmoevolutivopararesolverelproblemadecoloracionrobusta
_version_	1811744068282089472

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

Ejemplares similares