Después de unos días me he decidido a postear esta primera parte de una serie de artículos sobre algoritmos genéticos (GA por sus siglas en inglés). Principalmente voy a tratar de explicar en este post el fundamento teórico (de manera muy básica) del funcionamiento de este tipo de algoritmos. Después en los siguientes posts crearemos un ejemplo de GA utilizando como siempre nuestro amado Hello World!

Los algoritmos genéticos o GA se utilizan básicamente para realizar búsquedas en un espacio de soluciones amplias y con muchos máximos y mínimos locales, generalmente en funciones no derivables o de derivación muy compleja. Cabe destacar que el hecho de utilizar un GA no implica hallar la solución óptima puesto que la búsqueda puede converger prematuramente en un mínimo o máximo local y no poder encontrar el máximo/mínimo general.

Algunos ejemplos de uso de este tipo de algoritmos son:

  • Diseño automatizado de sistemas de comercio en el sector financiero.
  • Optimización de carga de contenedores.
  • Diseño de topologías de circuitos impresos.
  • Aprendizaje de comportamiento de robots.
  • Infraestructura de redes de comunicaciones móviles.
  • Predicción.
  • Aplicaciones en planificación de procesos industriales.
  • Construcción de horarios en grandes universidades, evitando conflictos de clases.
  • Optimización de producción y distribución de energía eléctrica.

Los GA se inspiran en la evolución biológica para realizar la búsqueda creando una analogía entre el conjunto de soluciones de un problema, llamado fenotipo, y el conjunto de individuos de una población natural, codificando la solución del problema en forma binaria, u otro tipo de codificación, en una cadena llamada cromosoma. Cada símbolo que conforma el cromosoma es un gen.

La búsqueda de la solución óptima del problema se realiza mediante iteraciones llamadas generaciones, en cada generación se realiza una serie de operaciones sobre los cromosomas o ciudadanos de la población.

Ahora vamos a ver el proceso que sigue un algoritmo genético para buscar una solución:

  1. Generamos aleatoriamente los ciudadanos (cromosomas) que van a conformar nuestra población inicial.
  2. Realizamos una evaluación (fitness) de los ciudadanos para saber que tan “buena” es la solución.
  3. Verificamos si debemos acabar la ejecución del algoritmo ya sea mediante el número máximo de generaciones o habiendo encontrado la solución óptima ya sea con tolerancia o no.
  4. Una vez conocemos la calidad de nuestros ciudadanos seleccionamos a los mejores para reproducirlos.
  5. Aplicamos operadores genéticos ya sea el de cruzamiento u otros para reproducir a los mejores ciudadanos y obtener descendencia de estos.
  6. Aplicamos operadores de mutación para ampliar la zona de búsqueda no cubierta por los ciudadanos actuales.
  7. Reemplazamos la generación actual con la descendencia recién obtenida de los mejores ciudadanos.

El proceso se repite ejecutando los pasos del 2 al 7 hasta encontrar la solución o llegar al máximo de generaciones. A modo de apunte cabe destacar que hay diferentes métodos de selección tales como el elitismo, la ruleta de selección, etc. Por otra parte también existen diferentes métodos de reproducción tales como crossover sexual, asexual, etc.

Más adelante y para no hacer más denso este post,  explicaré detalladamente cada punto de los vistos aquí.

Una vez visto esto y con una pequeña idea del funcionamiento de los GA construiremos nuestro GA Hello World, para ello utilizaremos PHP (la explicación es extensible a otros lenguajes tales como C) ya que al ser interpretado nos permitirá cambiar valores sin necesidad de recompilar el GA cada dos por tres. La programación de este GA esta realizada mediante POO con lo cuál el próximo post se basará en crear la primera clase necesaria que representará al cromosoma o ciudadano.

Evidentemente cuando un GA se va a utilizar en alguna aplicación se desarrolla en un lenguaje que se pueda compilar para ganar velocidad y minimizar los recursos ya sea C, C++, Java, etc.