El algoritmo genético (simple) funciona basado en el siguiente diagrama:

Un ejemplo de la codificación del problema se ha mostrado en el artículo anterior. En este post trataré sobre las diferentes partes dentro del algoritmo explicando todo con un acercamiento simple.

Antes de entrar de lleno al asunto, es válida una aclaración sobre la respuesta de un algoritmo genético. A diferencia de soluciones estándar que muestran un valor único de respuesta muchas veces los algoritmos genéticos tratan problemas donde no se conoce la respuesta y se espera obtenerla desde este procedimiento.

Cuando la población converge muy rápidamente es casi seguro que solo se ha obtenido un máximo local de la función y no un máximo global. Para entender esta afirmación es necesario mirar una representación gráfica simple:

Población inicial (PI).

La población inicial es un conjunto de individuos a partir de los cuales comenzará todo el proceso. Es la fuente genética primaria de las siguientes poblaciones y tiene dos características muy importantes, el tamaño y la forma de elegir los individuos.

El tamaño de la PI generalmente se corresponde con el tamaño que mantendrá toda la población durante el proceso, no es así cuando se implementan algoritmos más complejos, pero seguimos investigando.

Muchos han especulado respecto al tamaño de la población dado que aumentar la cantidad de individuos aumenta exponencialmente la cantidad de operaciones a realizar, para los casos parecidos al ejemplo del post anterior que se limitan a encontrar permutaciones de ‘n’ posiciones se estima que es suficiente un tamaño de población entre n y 2n. En mi experiencia los mejores resultados los obtengo con n+1 individuos.

El otro aspecto de la población inicial muy debatido es el modo de generar los individuos. Hay dos formas de hacerlo, de modo totalmente aleatorio o mediante un procedimiento de otro tipo. Normalmente cuando los individuos de la población inicial son generados por métodos diferentes al aleatorio el trabajo dura menos tiempo, en menos ciclos se encuentra un máximo, pero también tiene el inconveniente de que la calidad de estos máximos no siempre es la deseada porque se exploran mucho menos posibilidades.

Como en la naturaleza la calidad y variabilidad del material genético de la población inicial será en gran parte responsable del futuro de la población y por consiguiente de la respuesta obtenida. La introducción de individuos cercanos a la solución casi siempre termina empeorando la calidad de la respuesta.

Cruzamiento:

El cruzamiento es la forma de obtener uno o varios “hijos” a partir de la población existente. Siguiendo el modelo natural de sexos se trata de cruzar dos padres para obtener uno o varios hijos, posiblemente se puede incluir el modelo asexual obteniendo hijos a partir de un padre, pero solo se usa en contadas ocasiones porque es un comportamiento muy aleatorio. La obtención de un hijo a partir de tres o más padres también es posible, pero en la naturaleza no ocurre y en los AG conlleva un acercamiento prematuro casi siempre a un máximo local.

Para crear la rutina de cruzamiento hay varias consideraciones iniciales:

a) Número de hijos que se crean a partir de uno, dos o más padres. Puede variar en distintas implementaciones, pero hasta ahora a mí me funciona bien crear dos hijos a partir de dos padres.

b) Forma de selección de los padres dentro de la población. Si nos acercamos al modelo natural deberíamos cruzar el mejor individuo con otros de menor valía, esto se llama un algoritmo elitista, y se puede ver en algunas manadas de animales como normal. Para mí el mejor método ha sido seleccionar aleatoriamente individuos de la población actual para cruzarlos.

c) Método de cruzamiento. También se han estudiado varios, en la naturaleza se eligen puntos aleatorios y se transmiten algunos caracteres ligados al sexo. Para AGs de pocos genes (hasta 20) lo que mejor me ha funcionado es seleccionar un punto aleatorio para intercambiar material genético. En AGs de más genes he optado por dos puntos de cruce, luego de eso aumentar el número de puntos de cruce no me ha dado mejores resultados.

¿Cómo se realiza el cruzamiento desde uno o varios puntos?

Luego de seleccionar el punto de cruce (=7) se crean 4 secciones de genes A1 y A2 a partir del padre A y B1, B2 a partir del padre B. El hijo 1 hereda la porción A1 del padre A y la porción B2 del padre 2.

En el caso de permutaciones hay una gran diferencia, puesto que una condición para que un individuo sea válido es que no se repita un gen será necesario cambiar el proceder ya que será bien difícil encontrar individuos válidos.

Hay varias formas de hacerlo y necesita un estudio detallado. Por ahora solo diré como he obtenido mejores resultados. Primero selecciono el punto de cruce, luego para crear el hijo 1 coloco las partes A1 y B2, elimino de B2 todos los repetidos en A1, trato de colocarlos desde B1 y compruebo si se repiten en B2, elimino los repetidos y completo aleatoriamente. Suena complicado mejor vean la siguiente imagen. Los cuadros rojos representan los genes invalidantes y los amarillos representan genes que no se han heredado de ningún padre y se corresponden con el siguiente operador, la mutación.

Mutación:

Durante una primera parte del proceso el cruce es el generador de soluciones, pero a medida que convergen los genotipos y los individuos se parecen más entre ellos, la mutación comienza a jugar un papel más importante.

La dificultad con el tema de mutaciones estiba que un índice de mutación alto invalida el cruce y se convierte en una búsqueda aleatoria de una combinación.

Los índices de mutación entonces son pequeños. En mi experiencia el valor máximo debe ser 1/(tamaño de población + 1), pero se ha estudiado mucho el tema y una formula bastante recomendada es:

Introducir una mutación es cambiar aleatoriamente un gen dentro de un individuo, la frecuencia con que esto ocurre es el índice de mutación.

En el caso de las permutaciones se introduce una aleatoriedad en el cruzamiento, pero incluso con ella cuando la población converge y se acaba la diversidad genética la mutación es un elemento a tener en cuenta. Para generar una mutación simplemente se seleccionan dos posiciones aleatoriamente y se intercambian los valores.

Selección:

La selección es aquel proceso donde se decide cuales individuos continúan al siguiente ciclo. Es posible generar 100 y seleccionar 15, es posible que los padres sean elegibles, es posible seleccionar una parte al azar.

En mi experiencia es mejor un comportamiento de competencia donde los padres compiten con los hijos por permanecer en la población. La mitad de la población la selecciono por el valor de individuo y la otra mitad aleatoria del resto, para evitar una rápida convergencia hacia máximos locales.

En próximos post se tratarán temas más complejos sobre el uso y los resultados de AGs