Diferencia entre revisiones de «Algoritmos genéticos»

Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/mat/public_html/w/includes/diff/DairikiDiff.php on line 434

Revisión del 18:52 12 mar 2017 (ver código) Carlos Castro (Discusión | contribuciones) (→‎Idea general de un algoritmo genético) ← Edición anterior		Revisión del 19:06 12 mar 2017 (ver código) Carlos Castro (Discusión | contribuciones) (→‎Idea general de un algoritmo genético) Edición siguiente →
Línea 29:		Línea 29:
	* Elegimos el número de iteraciones J: veces que vamos a modificar la muestra		* 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>		* 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>	+	# 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 M mejores, supongamos <math> \{m_i \}_{i=1}^M </math>;
−	Determinamos los P peores, es decir <math> \{p_i \}_{i=1}^P </math>	+	Eliminamos de nuestra muestra los P peores.
	El resto los llamamos restantes <math> \{r_i \}_{i=1}^R </math>		El resto los llamamos restantes <math> \{r_i \}_{i=1}^R </math>
−	* * Combinación: Combinamos los restantes con los M mejores;	+	# Combinación: Combinamos los restantes con los M mejores;
−	<math>b_{ij}=(m_i+r_j)/2; </math>	+	<math>c_{ij}=(m_i+r_j)/2; </math>
−	* * Efecto aleatorio: Añadimos	+	# Efecto aleatorio: Añadimos nuevos puntos aleatorios <math> \{l_i \}_{i=1}^L </math>
−	* Fin del ciclo vital: Repetir (j + 1 → j)	+	# Construimos la nueva muestra:
−	Evaluamos la funci´on en los puntos de la ´ultima muestra yi = f(x	+
−	J+1	+	<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>
−	i	+
−	) con i = 1, ..., n	+	* Fin del ciclo vital: Renombramos <math>\{b_i \}_{i=1}^N \to \{a_i \}_{i=1}^N</math>  y repetimos el ciclo vital
−	Determinamos el mejor M tal que yM = min{y1, ..., yn};	+	* Evaluamos la función en los puntos de la última muestra y nos quedamos con el mejor
−	Escribimos el resultado resultado = x	+
−	J+1	+
−	M	+	Observaciones:
−	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	+	1. El algoritmo presentado no tiene por qué dar una aproximación del mínimo.
−	que proporciona una buena aproximaci´on y por ello es un algoritmo bastante popular	+	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
−	2. Este m´etodo tambi´en es muy costoso pero significativamente menos que los anteriores.	+	que proporciona una buena aproximación y por ello es un algoritmo bastante popular
−	3. En el algoritmo anterior hay muchos par´ametros que pueden modificarse dando lugar a variantes:	+	2. Este método es muy costoso pero significativamente menos que la fuerza bruta.
−	elegir varios como mejores, en lugar de uno; elegir varios como peores; cambiar la forma de combinar	+	3. En el algoritmo anterior hay muchos parámetros que pueden modificarse dando lugar a variantes.
−	el mejor con el resto, etc.	+
	[[Categoría:Trabajos fin de Máster]]		[[Categoría:Trabajos fin de Máster]]

---

Revisión del 19:06 12 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:

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]

1. 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];
   Eliminamos de nuestra muestra los P peores.
   El resto los llamamos restantes [math] \{r_i \}_{i=1}^R [/math]

1. Combinación: Combinamos los restantes con los M mejores;

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

1. Efecto aleatorio: Añadimos nuevos puntos aleatorios [math] \{l_i \}_{i=1}^L [/math]
2. 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.