Algoritmos Genéticos

Los algoritmos genéticos extienden lo anterior trabajando en cada paso n con un conjunto (población) de aproximaciones y permitiendo más libertad en la transición de una población X_n a la siguiente X_n+1.

La transición de X_n a X_n+1 se lleva a cabo en diferentes etapas (inspirado en la evolución biologica y donde se considera la función f() como el Fitness de cada individuo).

Muchas veces se codifica cada elemento x de como un bitstring de longitud l.

1.

Selección: Se selecciona una nueva población, por medio de la elección de elementos de X_n tales que para un elemento x, entre más grande f(x) , más grande la probabilidad de ser selecionado.
Muchas veces se hace una muestra independiente dónde la probabilidad de seleccionar x es .

2.

Crossover: A partir de la población del paso anterior, se elige por azar parejas x,y y se forma hijos combinando partes de x y y.
La implementación más fácil es tomar los primeros k bits de x (resp. y) y pegarlos con los últimos l-k bits de x (resp. y) dónde k es elegido arbitrariamente.

3.

Mutación: Se cambia cada bit de cada elemento con una cierta probabilidad (en general muy pequeña).

Se debería considerar un algoritmo genético como un último refugio si todos los demás de los métodos de optimización fallan o usarlo en combinación con un método clásico (por ejemplo en cada paso se aplica una optimización local).