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

Palabras 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

Cómo citar

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

Resumen

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.

https://doi.org/10.15517/rmta.v12i1-2.255
PDF

Citas

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.}

Comentarios

Descargas

Los datos de descargas todavía no están disponibles.