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

• Parte 1: Introducción.
• Parte 2: Funcionamiento.
• Parte 3: Codificando algoritmos genéticos (lo estás leyendo ahora).
  

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.

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.

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.

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.

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.

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.

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.

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().

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.

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í.

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

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:

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.