Un Algoritmo Evolutivo para Resolver el Problema de Coloración Robusta

• Lara Velázquez, Pedro ^[1] ; Gutiérrez Andrade, Miguel Ángel ^[1] ; Ramírez Rodríguez, Javier ^[1] ; López Bracho, Rafael ^[1]
  1. [1] Universidad Autónoma Metropolitana

     Universidad Autónoma Metropolitana

     México

     
• Localización: Revista de Matemática: Teoría y Aplicaciones, ISSN 2215-3373, ISSN-e 2215-3373, Vol. 12, Nº. 1-2, 2005, págs. 111-120
• Idioma: español
• DOI: 10.15517/rmta.v12i1-2.255
• Enlaces
  • Texto completo (pdf)
• Dialnet Métricas: 1 Cita
• Resumen
  • español

    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.

  • English

    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.

• Referencias bibliográficas
  • Glover, F. (1998) “A template for scatter search and path relinking”, in: J.K. Hao, E. Lutton, E. Ronald, M. Shoenauer & D. Snyers (Eds.)...
  • Glover, F.; Laguna, M.; Martí, R., (2004) “Scatter search and path relinking: foundations and advanced designs”, in: G. Onwubolu (Ed.) New...
  • Glover, F.; Laguna, M.; Martí, R. (2004) “New ideas and applications of scatter search and path relinking”, in: G. Onwubolu (Ed.) New Optimization...
  • Laguna, M.; Armentano, V. (2004) “Lessons from applying and experimenting with scatter search”, in: C. Rego & B. Alidaee (Eds.) Adaptive...
  • Ramı́rez Rodríguez, J. (2001) Extensiones del Problema de Coloración de Grafos. Tesis de Doctorado, Universidad Complutense de Madrid, Madrid,...
  • 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”,...
  • Yáñez, J., Ramı́rez, J. (2003) “The robust coloring problem”, European Journal of Operational Research, 148(3): 546–558.