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.

1 Planteamiento del problema de optimización

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]

2 Idea general de un algoritmo genético

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]

A. Selección:

1. Evaluamos la función coste en los puntos de la muestra [math] \{a_i \}_{i=1}^N [/math].
2. Determinamos los M mejores, supongamos [math] \{m_i \}_{i=1}^M [/math].
3. Eliminamos de nuestra muestra los P peores.
4. El resto los llamamos restantes [math] \{r_i \}_{i=1}^R [/math]

B. Combinación: Combinamos los restantes con los M mejores; [math]c_{ij}=(m_i+r_j)/2; [/math]

C. Efecto aleatorio: Añadimos nuevos puntos aleatorios [math] \{l_i \}_{i=1}^L [/math]

D. Construimos la nueva muestra:

[math]\{b_i \}_{i=1}^N = \{m_i \}_{i=1}^M \cup \{c_{ij} \}_{i,j=1}^{M,R} \{l_i \}_{i=1}^L \cup ; [/math]

• Fin del ciclo vital: Renombramos [math]\{b_i \}_{i=1}^N \to \{a_i \}_{i=1}^N[/math] y repetimos el ciclo vital
• Evaluamos la función en los puntos de la última muestra y nos quedamos con el mejor

Observaciones:

1. El algoritmo presentado no tiene por qué dar una aproximación del mínimo. No existe nigún resultado matemático general que garantice este hecho si no se imponen condiciones a la función objetivo y las restricciones. Sin embargo, a menudo si que proporciona una buena aproximación y por ello es un algoritmo bastante popular 2. Este método es muy costoso pero significativamente menos que la fuerza bruta. 3. En el algoritmo anterior hay muchos parámetros que pueden modificarse dando lugar a variantes.