5 Algoritmo Principal

Los Algoritmos Genéticos trabajan sobre una población de individuos. Cada uno de ellos representa una posible solución al problema que se desea resolver. Todo individuo tiene asociado un ajuste de acuerdo a la bondad con respecto al problema de la solución que representa (en la naturaleza el equivalente sería una medida de la eficiencia del individuo en la lucha por los recursos).

El funcionamiento genérico de un Algoritmo Genético puede apreciarse en el siguiente pseudocódigo:

Inicializar población actual aleatoriamente

MIENTRAS no se cumpla el criterio de terminación
       crear población temporal vacía

  MIENTRAS  población temporal no llena
        seleccionar padres
        cruzar padres con probabilidad Pc
        SI se ha producido el cruce 
            mutar uno de los descendientes con probabilidad Pm
            evaluar descendientes
            añadir descendientes a la población temporal
        SINO
            añadir padres a la población temporal
        FIN SI
  FIN MIENTRAS

  aumentar contador generaciones
  establecer como nueva población actual la población temporal

FIN MIENTRAS

Una generación se obtiene a partir de la anterior por medio de los operadores de reproducción. Existen 2 tipos:

• Cruce: Se trata de una reproducción de tipo sexual. Se genera una descendencia a partir del mismo número de individuos (generalmente 2) de la generación anterior. Existen varios tipos que se detallarán en un punto posterior.

• Copia: Se trata de una reproducción de tipo asexual. Un determinado número de individuos pasa sin sufrir ninguna variación directamente a la siguiente generación.

Una vez generados los nuevos individuos se realiza la mutación con una probabilidad Pm. La probabilidad de mutación suele ser muy baja, por lo general entre el 0.5% y el 2%.

Se sale de este proceso cuando se alcanza alguno de los criterios de parada fijados. Los más usuales suelen ser:

• Los mejores individuos de la población representan soluciones suficientemente buenas para el problema que se desea resolver.

• La población ha convergido. Un gen ha convergido cuando el 95% de la población tiene el mismo valor para él, en el caso de trabajar con codificaciones binarias, o valores dentro de un rango especificado, en el caso de trabajar con otro tipo de codificaciones. Una vez que todos los genes alcanzan la convergencia se dice que la población ha convergido. Cuando esto ocurre la media de bondad de la población se aproxima a la bondad del mejor individuo.

• Se ha alcanzado el número de generaciones máximo especificado.

Sobre este algoritmo inicialmente propuesto por Holland se han definido numerosas variantes.

Quizás una de las más extendidas consiste en prescindir de la población temporal de manera que los operadores genéticos de cruce y mutación se aplican directamente sobre la población genética. Con esta variante el proceso de cruces varía ligeramente. Ahora no basta, en el caso de que el cruce se produzca, con insertar directamente la descendencia en la población. Puesto que el número de individuos de la población se ha de mantener constante, antes de insertar la descendencia en la población se le ha de hacer sitio. Existen para ello diversas opciones:

• Reemplazo de padres: para hacer hueco a la descendencia en la población se eliminan de ella a los padres.

• Reemplazo de individuos similares: cada uno de los individuos de la descendencia reemplazará a un individuo de la población con un ajuste similar al suyo. Para escoger este individuo se obtiene la posición en la que se debería insertar el nuevo individuo para mantener ordenada la población y se escoge para insertarlo una posición al azar de su vecindad (p.e. uno de entre los cinco individuos superiores o inferiores).

• Reemplazo de los peores individuos: los individuos que se eliminarán de la población para dejar paso a la descendencia se seleccionarán aleatoriamente de entre los peores individuos de la población. Por lo general se consideran individuos pertenecientes al último 10%.

• Reemplazo aleatorio: los individuos eliminados se seleccionan al azar.

Evidentemente trabajando con un única población no se puede decir que se pase a la siguiente generación cuando se llene la población, pues siempre está llena. En este caso el paso a la siguiente generación se producirá una vez que se hayan alcanzado cierto número de cruces y mutaciones. Este número dependerá de la tasa de cruces y mutaciones especificadas por el usuario y del tamaño de la población. Así con una tasa de cruces del 90%, una tasa de mutaciones del 0.02% y trabajando con 100 individuos se pasará a la siguiente generación cuando se alcanzasen 45 cruces (cada cruce genera 2 individuos con lo que se habrían insertado en la población 90 individuos, esto es el 90%) o 2 mutaciones.