Algoritmos genéticos y coloraciones

Los algoritmos genéticos (AG) son una heurística computacional muy utilizada en ingeniería, pero también resultan sorprendemente útiles en matemáticas. En 1989, Jong y Spears mostraron que los AG pueden aplicarse con éxito a problemas NP-Completos, lo que esencialmente significa que, si te dan una solución para el problema, puedes verificar rápidamente si esa solución es correcta o no. Sin embargo, encontrar una solución óptima puede llevar mucho tiempo. En matemáticas, y en particular en teoría de gráficas y digráficas, aparecen muchos problemas de este tipo. Por ejemplo problemas de coloración, problemas de dominación, problemas de localización y el problema del agente viajero.

En esta charla quiero contar cómo hemos utilizado AG para explorar, mejorar y resolver problemas de coloración en gráficas y digráficas. El enfoque de la plática es desde la mirada de un “usuario matemático” que no es experto en programación, pero que ha encontrado en esta herramienta una manera creativa de exploración. La idea es mostrar cómo esta heurística permite resolver cierto tipo de problemas y cuáles son las características del tipo de problemas que son “naturales” para los AG. El objetivo es que se animen a considerar los algoritmos genéticos como una herramienta creativa y accesible para avanzar en la investigación matemática.

Este es un trabajo conjunto con Jorge Cervantes Ojeda y Juan Carlos García Altamirano