Algoritmos Genéticos en Inteligencia Artificial Parte III: Codificando algoritmos genéticos

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 aspectos fundamentales de los algoritmos genéticos: su inspiración biológica, su funcionamiento general, aplicaciones y relevancia en la actualidad. En la segunda parte revisamos con más detalle cada una de las fases del proceso de evolución utilizado por estos algoritmos y describimos mediante un ejemplo práctico, su funcionamiento. En el presente artículo mostraremos una estrategia para su codificación y los hiperparámetros necesarios para implementarlos en C++. Puedes encontrar el código fuente del programa en Github.

Describiendo las clases

Siguiendo algunos principios básicos de programación orientada a objetos (POO) hemos estructurado el código del programa utilizando clases. La primera es la clase Coin, la cual se utiliza para decidir de manera sencilla si las acciones de cruce y mutación se deben realizar o no.

La segunda clase es Individual, la cual representa un individuo de la población expresado como un vector de 1’s y 0’s. Esta clase permite abstraer operaciones de consulta y alteración de los cromosomas. El método más importante en la clase individuo es el de cruce, el cual recibe una posición para cruzar el cromosoma y produce los dos hijos según la estrategia descrita en el segundo artículo de esta serie.

Algoritmo-genético-clases
Fig. 1. Clase de individuo

La tercera clase importante es SimpleGeneticAlgorithm la cual representa la configuración inicial del algoritmo genético con sus hiperparámetros. La clase tiene el método principal runGeneration el cual realiza el proceso de evolución ejecutando en secuencia los pasos de: evaluación, selección, cruce, mutación y reeemplazo.

Algoritmos-Clases
Fig. 2. Esquema de la clase SimpleGeneticAlgorithm

Trabajando con SimpleGeneticAlgorithm

La clase SimpleGeneticAlgorithm se encarga de realizar la evaluación de las generaciones de individuos mediante el método runGeneration. La estrategia de evolución simple realiza de manera secuencial la evaluación, selección, cruce, mutación y reemplazo de acuerdo a los hiperparámetros del algoritmo, los cuales se encuentran en los atributos de la clase: 

population_size: Tamaño de la población para realizar el proceso de evolución.

tournament_size: Tamaño del torneo para que los individuos compitan.

generations: Número de generaciones que se ejecutará el proceso evolutivo.

chromosome_size: Tamaño del cromosoma, utilizado para modelar las posibles soluciones.

mutation_probability: Probabilidad de la mutación, para cada uno de los genes de los individuos seleccionados.

cross_probability: Probabilidad de cruce de dos individuos.

Algoritmos-Genéticos
Fig. 3. Método runGeneration()

La selección se realiza a través del resultado de la función evaluateIndividual() aplicada a cada uno de los individuos de la población en el método evaluate(). Se utiliza una estrategia de torneo para decidir los individuos mas aptos, en la cual, se eligen tantos individuos como el tamaño de torneo definido en el algoritmo y se selecciona al individuo que tenga mejor evaluación para formar parte de los organismos que se utilizarán para dar lugar a la siguiente generación en el proceso evolutivo.

Algoritmos-Genéticos
Fig. 4. Algoritmo de selección utilizando una estrategia de torneo.

Una vez que se han seleccionado, los individuos más aptos se eligen por parejas y de acuerdo a la probabilidad de cruce se determina si los individuos realizarán el cruce, en cuyo caso serán sus descendientes quienes pasen a la siguiente generación, o en caso contrario pasarán sin alteraciones a la siguiente generación. La estrategia para poder realizar el cruce es es seleccionando de manera aleatoria un punto de corte para mezclar los cromosomas de los padres.

Algoritmos-Genéticos
Fig. 5. Estrategia de cruce para los individuos de la población

Una vez que se ha realizado el cruce se determina gen a gen de acuerdo a la probabilidad de mutación si se debe mutar el gen del i-ésimo individuo.

Algoritmos-Genéticos
Fig. 6. Mutación del j-ésimo gen perteneciente al i-ésimo individuo de la generación.

Este ciclo se repite de acuerdo al número de generaciones que hayamos elegido como parámetro para el algoritmo, en cada caso se guarda el mejor individuo encontrado, junto con su evaluación.

Personalizando SimpleGeneticAlgorithm

La selección se realiza elecutando el método evaluateIndividual(), el cual recibe como parámetro un individuo y la función se encarga de evaluar que tan bien se adapta la solución. La función de evaluación aquí presentada se evalúa en términos de error, es decir un individuo que tenga error 0 se encuentra perfectamente adaptado y un individuo con un error de 1 se encuentra completamente desadaptado.

Este método se utiliza para definir el problema que se optimizará por medio del AG. Para el ejemplo de encontrar el número más alto posible podemos definir la función de evaluación en términos del número de 1’s que tenga esta. Es decir para un ejemplo con un individuo de tamaño de cromosoma diez penalizaremos en una décima a los genes que no contengan 1.

Algoritmos-Genéticos
Fig. 7. Función de evaluación del individuo.

La función de evaluación del individuo es la que orienta la evolución de los organismos presentados en el programa. Se puede personalizar el funcionamiento de la clase SimpleGeneticalgorithm heredando de la clase base y personalizando el método virtual evaluateIndividual().

Algoritmos-Genéticos
Fig. 8. Personalización de la clase SimpleGeneticAlgorithm

En la personalización presentada en la figura 8, se evalúan los primeros 7 bits del cromosoma para que sean 0’s sin importar los cromosomas restantes. Esto producirá soluciones que tengan al menos los primeros 7 genes del cromosoma establecidos a 0. Se puede traducir el genotipo de este cromosoma como aquellos números menores o iguales a 7.

Algoritmos-Genéticos
Fig. 9. Resultados de evolucionar a los individuos con los siete primeros genes establecidos a 0’s

En la figura 9 se aprecia como todos aquellos individuos con valores menores o iguales a 7 resultan en una evaluación perfecta. De igual manera podemos realizar funciones más complejas, por ejemplo en la figura 10 se presenta una función de evaluación que favorece aquellos individuos que estén formados por exactamente siete 1’s, lo cual genera un rango de soluciones muy particular ya que los valores pueden resultar muy disímiles entre sí.

Algoritmos-Genéticos
Fig. 10. Personalización de la clase SimpleGeneticAlgorithm para individuos con exactamente siete 1’s

Esta función de evaluación de individuos produce algunas soluciones como las presentadas en la figura 11:

Algoritmos-Genéticos
Fig. 11. Evaluación de los individuos con exactamente siete unos

Como vemos hay un gran rango de números que cumplen con la condición. En esta línea particular de evolución el 995 se repite como solución pasando sus genes dominantes. Una variante es la que se da con el número 967 que también es solución y también cumple con todos los requisitos. El algoritmo escoge como mejor al individuo 1111111000 (1016) dado que fue el primero en alcanzar una evaluación perfecta y ningún individuo lo superó después, aún cuando vemos que el algoritmo ha tomado preferencia por los individuos con genética similar al 995.

Un aspecto interesante es que el algoritmo va a formar diferentes poblaciones de acuerdo a como haya marchado el proceso evolutivo. En una segunda ejecución del algoritmo obtenemos los resultados mostrados en la figura 12:

Algoritmos-Genéticos
Fig. 12. Evaluación de los individuos con exactamente siete unos por una ruta alternativa de evolución.

En la figura anterior vemos como existen una variedad de individuos que alcanzan el score perfecto siendo evaluado como mejor individuo el 1111001011 (971), sin embargo se aprecia que los números: 974, 926, 743, 631, 755 y 1009 también son soluciones de este problema alcanzando evaluaciones perfectas. Esto es interesante ya que nos permite apreciar diferentes soluciones y utilizar la que mejor se adapte a nuestra problemática.

Un aspecto importante es saber si nuestro algoritmo está funcionando, para tal efecto es necesario que monitoreemos el comportamiento del error. Dado que la función de evaluación devuelve el error, en el método evaluate() se contabiliza el error de cada individuo y se promedia de acuerdo al número de la población para calcular el error promedio en cada generación y se asigna al parámatro mse. En el código proporcionado se encuentra la función crossValidation(), la cual se encarga de correr el AG el número de veces necesario de acuerdo a las generaciones definidas e ir guardando el error promedio para cada generación en un archivo de texto. 

Para saber que el algoritmo está encontrando individuos más eficientes debemos observar que el error promedio va reduciendo conforme transcurren las generaciones. En la figura 13 se muestra el error acumulado para cada generación. Una curva descendente que comienza a estabilizarse cerca de 0 es deseable puesto que indica que los individuos son cada vez mejores. Las fluctuaciones abruptas pueden ser síntoma de valores de mutación y cruce muy altos por lo cual se deben de ir adaptando estos parámetros hasta obtener los resultados deseados.

Resultado-Algoritmos-Genéticos
Fig. 13. Error acumulado de acuerdo a las generaciones.
Share on facebook
Share on twitter
Share on linkedin

2 Replies to “Algoritmos Genéticos en Inteligencia Artificial Parte III: Codificando algoritmos genéticos”

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!