Optimización global

Se plantea resolver heurísticamente el problema

$$\left. \begin{array}{ll} \text{Min.} & f(x) \\ s.a. & x \in X \end{array} \right\} .$$

Llamaremos valor incumbente en un iteración al mejor obtenido hasta dicha iteración.

a) Búsqueda aleatoria pura

Se toman puntos al azar (pero uniformemente) sobre X y nos quedamos con aquel que dé mejor valor.

b) Multicomienzo

1.

$f^* = +\infty$.

2.

Se repite N veces: se genera $x \in D(X)$ (de acuerdo con una distribución D).

Se usa x como punto de inicio de cualquier método de búsqueda local, obteniéndose x_i^*. Si f^*(x_i)<f^*, entonces $f*= f(x_i^*), \, x^*=x_i^*$.

c) Direcciones aleatorias

Se selecciona un punto de partida. Se generan direcciones aleatorias y se optimiza en cada una de esas direcciones. Para cada dirección se toma como punto de partida el óptimo obtenido con la dirección anterior.

d) Métodos que imitan procesos naturales

(i) Recocido simulado (simulated annealing)

1.

Se elige $x_1 \in X, \, f^* = f(x_1), x^* = x_1, i=1$. Se elige T₁>0.

2.

Se repite el siguiente proceso el número de de iteraciones que resulte apropiado:

• Se genera $y\in \varepsilon(x_i)$ (un entorno de x_i).
• Se genera $u\equiv U(0,1)$.
• Si $e^{\frac{f(x_i)-f(y)}{T_i}} > u$, entonces se hace x_i=y.
• Si f(x_i)<f^*, entonces se hace $f^*=f(x_i), \, x^*=x_i, \, x_{i+1}=x_i, \, i=i+1$.
• Se actualiza T_i.

Se recomienda mantener T_i constante durante las primeras iteraciones y luego hacer $T_{i+1} = 0,95\cdot T_i$.

(ii) Algoritmos genéticos.

Un algoritmo genético parte de un conjunto (población) de N soluciones (individuos) que evolucionan de modo que se mantiene su tamaño.

• Población: N individuos.
• Iteración i-ésima: $X^{(i)}= \{ x_1^{(i)},\dots,x_N^{(i)} \}$.
• Regla de selección: se eligen individuos x⁽ⁱ⁾ de modo que los mejores (mejor valor objetivo) tengan mayor probabilidad.
• Regla de cruce: dos individuos se parten e intercambian sus partes.
• Mutación: mediante una regla específica se modifican los resultados del cruce.
• Selección de malos individuos y muerte: se deja el tamaño de la población en N individuos.