Algoritmos Genéticos en Inteligencia Artificial Parte II: Funcionamiento

Share on facebook
Share on twitter
Share on linkedin

Parte de la serie Algoritmos Genéticos en Inteligencia Artificial:

En la primera parte de este artículo describimos algunos de los aspectos fundamentales de los Algoritmos Genéticos (AG): su inspiración biológica, su funcionamiento general y algunas de sus aplicaciones y relevancia en la actualidad. En el presente artículo estudiaremos con más detalle cada una de las fases del proceso de evolución utilizado por estos algoritmos.

Funcionamiento de los AG

Con el fin de poder explicar de mejor manera los conceptos relacionados a los AG, diseñemos un problema de ejemplo. En este problema vamos a intentar representar el mayor número posible utilizando 6 dígitos binarios. El sistema binario representa sus números como potencias de 2, de acuerdo a la posición que ocupen en el número de derecha a izquierda, siendo que la primera posición representa el valor 1 o 0, la segunda representa 2 o 0, la tercera 4 o 0, 8 o 0 para la cuarta, 16 o 0 para la quinta y así sucesivamente. El valor del número se obtiene sumando los valores de las posiciones con el bit encendido (establecido a uno), como se ilustra en las figuras 2 y 3:

Representación de número binario
Fig. 1. Ejemplo de representación de un número en binario

Números binarios
Fig. 2. Primeros 8 números binarios

La solución al problema propuesto es trivial (el individuo 111111, que representa el número 63), sin embargo, nos puede servir para intuir y explicar el funcionamiento de los AG. Para el uso de éstos, es necesario expresar nuestras posibles soluciones como individuos. Cada individuo estará representado por una secuencia de símbolos. Esta secuencia de símbolos es llamada cromosoma, y cada uno de los símbolos que la componen recibe el nombre de gen.

En biología nuestros genes determinan nuestro fenotipo, es decir, nuestras características físicas, como nuestro color de ojos, altura, color de piel, entre otras. Estos genes los heredamos de nuestros progenitores quienes combinan su código genético para generar nuevos individuos con características de ambos y a la vez nosotros los heredamos a nuestra progenie. En nuestro ejemplo el cromosoma consta de una cadena de 6 caracteres de longitud en donde cada gen puede ser un 0 o un 1. El fenotipo del individuo es el valor del número que representa. Por ejemplo el fenotipo del individuo 101101 es 45.

Para poder mejorar a los individuos, tenemos que evaluar su desempeño en la tarea. Dado que nuestra tarea es encontrar el máximo valor que podamos representar, la evaluación de cada individuo consistirá en el valor del número que representa. Está función de evaluación es una de las partes más importantes del proceso de modelado en AG y puede llegar a ser tan compleja como necesitemos.

Así por ejemplo, una función de evaluación que busque un número grande solo evaluará el valor del número, mientras más grande sea el valor del número, mejor será su evaluación. Sin embargo, si quisiéramos un número que se forme exactamente por 5 unos, nuestra evaluación será perfecta cuando el individuo tenga 5 genes (bits) establecidos a 1 en el cromosoma, fallará en 1 de 6 cuando solo hayan 4, 2 de 6 cuando solo hayan 3 y así sucesivamente.

Para que el algoritmo funcione, se inicializa una población (conjunto de individuos) de manera aleatoria con un tamaño determinado, el cual es uno de los hiperparámetros del algoritmo. En nuestro ejemplo usaremos una población de tamaño 100, es decir, generaremos 100 cadenas diferentes de 1’s y 0’s. Esta población inicial servirá para comenzar el proceso de evolución.

Existen estudios interesantes respecto a las mejores formas de inicializar la población, ya que si conocemos “buenos” individuos, podemos utilizarlos para crear inicializaciones que se acerquen a la solución global, sin embargo, es necesario balancear esos individuos previamente diseñados con un buen porcentaje de variación para permitir que la mutación y cruce exploren varias partes del espacio de búsqueda del problema y no perder la esencia exploratoria del algoritmo.

A continuación para evolucionar a los individuos repetiremos iterativamente los siguientes pasos:

Algoritmo Genético
Fig. 3. Pasos de un algoritmo genético

En la etapa de evaluación se utilizará la función previamente definida para verificar que tan apto es cada individuo para su tarea, es decir el valor de su cromosoma. Una vez que se han evaluado todos los individuos, se pasa a la etapa de selección en donde por medio de una estrategia, se escogen a los individuos más fuertes. A menudo se utiliza una estrategia de torneo en donde cada individuo es enfrentado con otros y el que tenga mejor evaluación sobrevivirá. Por ejemplo si tenemos un torneo entre 5 individuos siendo:

Algoritmos genéticos
Fig. 4. Ejemplo de torneo para la selección en un AG

Se comparan los individuos entre sí teniendo la mejor evaluación el individuo D con un fenotipo de 35. Al ser el ganador del torneo se selecciona una copia del organismo para poder reproducirse en la siguiente fase. A continuación se escogen otros 5 individuos y se realiza de nuevo el proceso de selección. Este proceso se repite hasta seleccionar tantos individuos como el tamaño de la población, permitiendo que se repitan los individuos, de manera que los más fuertes tendrán mayores probabilidades de reproducirse.

A partir de ahí se realiza la fase de recombinación o cruzamiento en donde se combinan los cromosomas de los individuos seleccionados de acuerdo a una probabilidad de cruce. Una estrategia sencilla para realizar esto es por medio de la combinación de cromosomas usando un punto de cruce.

Supongamos que los siguientes individuos han sido seleccionados para cruzarse:

Algoritmos genéticos
Fig 5. Individuos seleccionados para recombinación

A continuación “arrojamos una moneda cargada” de acuerdo con la posibilidad de cruce. En caso de ser positiva, combinamos los cromosomas, en caso contrario los individuos pasan sin modificarse a la siguiente generación. Una alternativa para seleccionar el punto de cruce es eligiendo un punto de corte aleatorio y combinar los cromosomas. Por ejemplo, supongamos que se selecciona el cromosoma 3 como punto de corte, se formarán los siguientes genes:

Algoritmos genéticos
Fig. 6. Genes de los padres a partir del punto de cruce

A continuación generamos dos hijos; uno compuesto por la primera parte del cromosoma del individuo 1 y la segunda del individuo 2. El otro, compuesto por la primera parte del segundo individuo y la segunda parte del primero es decir:

Algoritmos genéticos
Fig. 7. Hijos producto de la recombinación genética

Algoritmos genéticos
Fig. 8. Hijos producto de una recombinación genética con corte en el gen 2

Los hijos H1 y H2 pasan a la siguiente generación para iniciar nuevamente el proceso de evaluación y selección. Este proceso se repite hasta que se tiene toda la población que pasará a la siguiente generación. A continuación para cada individuo y para cada gen se elige la posibilidad de mutarlo de acuerdo a una probabilidad de mutación, el cual es otro hiperparámetro del algoritmo.

En caso de que se decida mutar un gen se altera su valor, es decir si se encontraba en 1 se pasa a 0 y viceversa. Este proceso introduce variabilidad que permite experimentar con nuevas características las cuales en caso de ser exitosas generarán individuos aún mejor adaptados. Finalmente se reemplaza la generación anterior con la nueva generación de individuos, la cual es una recombinación y mutación de aquella. Este proceso se repetirá hasta que alcancemos una condición de paro, la cual puede ser alcanzar una meta de desempeño de la solución o un número de iteraciones fijo.

En la siguiente parte de la publicación examinaremos algunos de los aspectos importantes de la codificación de los algoritmos genéticos.

Share on facebook
Share on twitter
Share on linkedin

One Reply to “Algoritmos Genéticos en Inteligencia Artificial Parte II: Funcionamiento”

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

¡Conozcámonos mejor!

Te haremos llegar las novedades de SoldAI, ofertas exclusivas, notificaciones, y mucho más.

¡Deja tu correo, tenemos mucho que contarte!