Algoritmo genético para el problema de coloración blanco y negro en gráficas

Autores/as

  • Luis Eduardo Urván Rivero Posgrado en optimización UAM Azcapotzalco
  • Javier Ramírez Rodríguez Departamento de Sistemas, UAM Azcapotzalco. Av. San Pablo 180 Col. Reynosa-Tamaulipas Delegación Azcapotzalco C.P. 02200, Ciudad de México.
  • Rafael López Bracho Departamento de Sistemas, UAM Azcapotzalco. Av. San Pablo 180 Col. Reynosa-Tamaulipas Delegación Azcapotzalco C.P. 02200, Ciudad de México

DOI:

https://doi.org/10.30973/progmat/2018.10.1/3

Palabras clave:

Anticoloración, Algoritmo Genético, BWC

Resumen

Un problema clásico en la teoría de gráficas es el conocido como problema de coloración (GC por sus siglas en inglés). Este problema consiste en asignar colores a los vértices de la gráfica tal que vértices adyacentes deben tener colores diferentes. El objetivo de este problema es encontrar el mínimo número de colores necesarios para colorear la gráfica bajo la mencionada condición de coloración. En el caso del problema de anticoloración (GAC por sus siglas en inglés), la forma de asignar color es opuesta. En este caso vértices adyacentes deben tener el mismo color o al menos uno de ellos no debe tener color. En este problema el objetivo es diferente en el sentido del número de colores que en este caso es fijo. Este problema puede ser convertido en un problema de optimización. El GAC es NP-Completo aun cuando se usen sólo dos colores [2]. En este trabajo trataremos con el caso especial de dos colores del GAC mediante el uso de algoritmos genéticos y se compara con la búsqueda Tabú que es la mejor técnica conocida para la solución de este problema [3].

Biografía del autor/a

Luis Eduardo Urván Rivero, Posgrado en optimización UAM Azcapotzalco

Ingeniero en computación por la Universidad Autónoma Metropolitana (UAM) Azcapotzalco, Maestro en optimización y Candidato a Doctor en Optimización por la misma Institución.

Javier Ramírez Rodríguez, Departamento de Sistemas, UAM Azcapotzalco. Av. San Pablo 180 Col. Reynosa-Tamaulipas Delegación Azcapotzalco C.P. 02200, Ciudad de México.

Actuario por la Universidad Nacional Autónoma de México y Doctor en Ciencias Matemáticas por la Universidad Complutense de Madrid, España. Actualmente se desempeña como profesor investigador en el Departamento de Sistemas de la UAM Azcapotzalco.

Rafael López Bracho, Departamento de Sistemas, UAM Azcapotzalco. Av. San Pablo 180 Col. Reynosa-Tamaulipas Delegación Azcapotzalco C.P. 02200, Ciudad de México

Actuario por la Universidad Nacional Autónoma de México, tiene un Diplome d’études approfondies en investigación de operaciones por la Université Scientifique et Medicale de Grenoble, Francia y Doctor en Informática por la Université de Paris Sud, Francia en el año 1981. Actualmente se desempeña como profesor investigador en el Departamento de Sistemas de la UAM Azcapotzalco.

Citas

Bäck, T., Schütz, M. Intelligent mutation rate control in canonical genetic algorithms. Foundations of Intelligent Systems. 1996, 158–167. https://doi.org/10.1007/3-540-61286-6_141

Berend, D., Korach, E., Zucker, S. A Reduction of the anticoloring problem to connected graphs. Electronic Notes in Discrete Mathematics. 2007, 28 445– 451. https://doi.org/10.1016/j.endm.2007.01.062

Berend, D., Korach, E., Zucker, S. Tabú search for the BWC problem. Journal of Global Optimization. 2012, 54 (4), 649–667. https://doi.org/10.1007/s10898-011-9783-1

Berge, C., Minieka, E. Graphs and hypergraphs. North-Holland publishing company Amsterdam.

Holland, J.H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. MIT Press.

Lipton, R.J., Tarjan, R.E. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics. 1979, 36 (2), 177–189. https://doi.org/10.1137/0136016

López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L.P., Stützle, T., Birattari, M. The irace package: Iterated Racing for Automatic Algorithm Configuration. Operations Research Perspectives. 2016, 1 (3), 43–58. https://doi.org/10.1016/j.orp.2016.09.002

Descargas

Publicado

28-02-2018

Cómo citar

Urván Rivero, L. E., Ramírez Rodríguez, J., & López Bracho, R. (2018). Algoritmo genético para el problema de coloración blanco y negro en gráficas. Programación matemática Y Software, 10(1), 17–23. https://doi.org/10.30973/progmat/2018.10.1/3

Número

Vol. 10 Núm. 1 (2018): Febrero de 2018

Sección

Artículos

Licencia

Derechos de autor 2018 Programación Matemática y Software

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.

Usted es libre de:

Compartir — compartir y redistribuir el material publicado en cualquier medio o formato.
Adaptar — combinar, transformar y construir sobre el material para cualquier propósito, incluso comercialmente.

Bajo las siguientes condiciones:

Atribución — Debe otorgar el crédito correspondiente, proporcionar un enlace a la licencia e indicar si se realizaron cambios. Puede hacerlo de cualquier manera razonable, pero de ninguna manera que sugiera que el licenciador lo respalda a usted o a su uso.
  Sin restricciones adicionales: no puede aplicar términos legales o medidas tecnológicas que restrinjan legalmente a otros a hacer cualquier cosa que permita la licencia.