Algoritmos genéticos

En este artículo presentamos una idea de cómo funcionan los algoritmos genéticos para minimizar problemas con restricciones y mostramos la implementación práctica en un caso sencillo. Supondremos que la función coste y las restricciones dependen sólo de dos variables para simplificar, pero todo se puede trasladar fácilmente a casos más generales.

Consideramos el problema siguiente: Buscamos minimizar la función coste [math] f_{coste} (a_1,a_2) [/math]

cuando los parámetros toman valores en los intervalos

[math] L_i \leq a_i \leq M_i, \quad i=1,2, [/math]

y además verifican las restricciones (supondremos también sólo 2 para simplificar)

[math] \begin{array}{l} g_{rest1} (a_1,a_2)\leq 0,\\ g_{rest2} (a_1,a_2)\leq 0. \end{array} [/math]

Este tipo de algoritmos está basado en un proceso iterativo en el que se pasa de una muestra aleatoria de puntos a otra simulando un ciclo vital:

1. Selección del mejor o mejores.
2. Combinación de los mejores con el resto.
3. Añadir un factor aleatorio.

El proceso es como sigue:

• Elegimos una muestra aleatoria inicial de nuestros parámetros, [math] \{a_i \}_{i=1}^N [/math]
• Elegimos el número de iteraciones J: veces que vamos a modificar la muestra
• Aplicamos el ciclo vital: para j = 1, ..., J; [math] \{a_i \}_{i=1}^N \to \{b_i \}_{i=1}^N[/math]
• * Selección: Evaluamos la función coste en los puntos de la muestra [math] \{a_i \}_{i=1}^N [/math]

   Determinamos los M mejores, supongamos [math] \{m_i \}_{i=1}^M [/math];
   Determinamos los P peores, es decir [math] \{p_i \}_{i=1}^P [/math]
   El resto los llamamos restantes [math] \{r_i \}_{i=1}^R [/math]

• * Combinación: Combinamos los restantes con los M mejores;

   [math]b_{ij}=(m_i+r_j)/2; [/math]

• * Efecto aleatorio: Añadimos
• Fin del ciclo vital: Repetir (j + 1 → j)

Evaluamos la funci´on en los puntos de la ´ultima muestra yi = f(x J+1 i ) con i = 1, ..., n Determinamos el mejor M tal que yM = min{y1, ..., yn}; Escribimos el resultado resultado = x J+1 M Observaciones: 1. El algoritmo presentado no tiene por qu´e dar una aproximaci´on del m´ınimo. No existe nig´un resultado matem´atico general que garantice este hecho. Sin embargo, a menudo si que proporciona una buena aproximaci´on y por ello es un algoritmo bastante popular 2. Este m´etodo tambi´en es muy costoso pero significativamente menos que los anteriores. 3. En el algoritmo anterior hay muchos par´ametros que pueden modificarse dando lugar a variantes: elegir varios como mejores, en lugar de uno; elegir varios como peores; cambiar la forma de combinar el mejor con el resto, etc.