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