Diferencia entre revisiones de «Algoritmos genéticos»
| Línea 1: | Línea 1: | ||
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. | 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. | ||
| + | == Planteamiento del problema de optimización == | ||
Consideramos el problema siguiente: Buscamos minimizar la función coste | Consideramos el problema siguiente: Buscamos minimizar la función coste | ||
<math> f_{coste} (a_1,a_2) </math> | <math> f_{coste} (a_1,a_2) </math> | ||
| Línea 16: | Línea 17: | ||
</math> | </math> | ||
| − | + | == 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 | Este tipo de algoritmos está basado en un proceso iterativo en el que se pasa de una muestra aleatoria de | ||
Revisión del 15:18 8 mar 2017
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:
- Selección del mejor o mejores.
- Combinación de los mejores con el resto.
- 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.
