Algoritmos Genéticos

Los algoritmos genéticos tienen su origen en la simulación de la Evolución. La evolución es el proceso en el cual los genes heredados de dos padres aptos son modificados, mejorados o mutados de tal forma que los nuevos individuos son mejores genéticamente hablando.

El proceso de mejoramiento se lleva a cabo al unir dos genotipos para producir un tercero. El genotipo son todas las características que componen al individuo (color de piel, color de cabello, tipo de ojos, tamaño de dientes, etc). Cuando se mezclan dos individuos (dos genotipos),  existen diversas combinaciones que se pueden producir  dependiendo de la misma mezcla y de los mismos genes que tengan los individuos.

A partir de estas mezclas se busca que los nuevos individuos sean cada vez más aptos en su medio ambiente y que su sobrevivencia sea posible.

En Computación, existen algunos problemas que pueden ser resueltos utilizando la teoría de Algoritmos Genéticos. En éste caso el individuo es la representación vectorial de una posible solución al problema planteado.

La evolución se lleva a cabo combinando los individuos o población base, de tal forma que en cada generación obtengamos mejores resultados.

El proceso de evolución de un Algoritmo Genético se puede plantear de a siguiente forma:

Se cuenta con una serie de individuos (vectores) que representarán soluciones parciales o soluciones no óptimas obtenidas por algún método de fuerza bruta o un algoritmo simple, dependiendo del problema será la forma en que se generará ésta primer generación de la población.

Posteriormente se deben evaluar cada uno de los individuos mediante alguna función de evaluación que nos permita saber que tan “buena” es la solución planteada. A partir del resultado de ésta evaluación llevaremos a cabo el ordenamiento de los mismos del mejor adaptado al peor.

Supongamos que generamos 100 individuos de forma aleatoria o mediante un algoritmo simple, usaremos los primero 40 individuos (los más aptos) para que se reproduzcan mientras que los restantes 60 serán eliminados.

A partir de la segunda generación, la obtención de la población se realizará mediante dos métodos:

-          Cruza de los más aptos.

-          Generación aleatoria o con algoritmos simples.

La cruza de los individuos se puede realizar de la siguiente forma:

Donde los dos hijos que se obtienen son resultado de la combinación de los padres por la mitad.

Otra forma de cruza puede ser:

Donde los individuos obtenidos son la combinación de un gen del padre y un gen de la madre de forma alternada.

De esta manera existen muchas combinaciones para que a partir de dos padres podamos obtener una serie de hijos resultados de la cruza de éstos.

A partir de 40 individuos aptos, podemos generar, por ejemplo, otros 100 individuos, que junto con los padres son la nueva generación. De igual forma se pueden generar nuevos individuos absolutamente nuevos a partir de generación aleatoria o usando algoritmos simples.

Ésta nueva generación se debe evaluar y de nuevo obtener los “más aptos”. Éste proceso de evaluación, generación, eliminación y cruza se debe llevar a cabo hasta que se obtenga una solución que se encuentre dentro de los parámetros requeridos o hasta alcanzar una cantidad de generaciones X.

Veremos un ejemplo de aplicación en un siguiente Artículo.