Revista de Matemática: Teoría y Aplicaciones ISSN Impreso: 1409-2433 ISSN electrónico: 2215-3373

OAI: https://revistas.ucr.ac.cr/index.php/matematica/oai
Un algoritmo evolutivo para resolver el problema de Coloración Robusta
PDF (Español (España))

Keywords

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

How to Cite

Lara Velázquez, P., Gutiérrez Andrade, M. Ángel, Ramírez Rodríguez, J., & López Bracho, R. (2005). Un algoritmo evolutivo para resolver el problema de Coloración Robusta. Revista De Matemática: Teoría Y Aplicaciones, 12(1-2), 111–120. https://doi.org/10.15517/rmta.v12i1-2.255

Abstract

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.

https://doi.org/10.15517/rmta.v12i1-2.255
PDF (Español (España))

References

Glover, F. (1998) “A template for scatter search and path relinking”, in: J.K. Hao, E. Lutton, E. Ronald, M. Shoenauer & D. Snyers (Eds.) Artificial Evolution, Lecture Notes in Computer Science, 1363, Springer: 13–54.

Glover, F.; Laguna, M.; Martí, R., (2004) “Scatter search and path relinking: foundations and advanced designs”, in: G. Onwubolu (Ed.) New Optimization Techniques in Enginneering, Springer Verlag.

Glover, F.; Laguna, M.; Martí, R. (2004) “New ideas and applications of scatter search and path relinking”, in: G. Onwubolu (Ed.) New Optimization Techniques in Enginneering, Springer Verlag.

Laguna, M.; Armentano, V. (2004) “Lessons from applying and experimenting with scatter search”, in: C. Rego & B. Alidaee (Eds.) Adaptive Memory and Evolution: Tabu Search and Scatter Search,

Ramı́rez Rodríguez, J. (2001) Extensiones del Problema de Coloración de Grafos. Tesis de Doctorado, Universidad Complutense de Madrid, Madrid, España.

Ramı́rez Rodríguez J.; Gutiérrez Andrade, M.A.; López Bracho, R.; Yáñez Gestoso, J., (2004) “Heuristics for the robust coloring problem”, Preprint, Universidad Autónoma Metropolitana, México.

Yáñez, J., Ramı́rez, J. (2003) “The robust coloring problem”, European Journal of Operational Research, 148(3): 546–558.}

Comments

Downloads

Download data is not yet available.