Algoritmos Genéticos¶
Motivados por la Teoría de la Evolución (adaptación al medio) y por la Teoría Mendeliana (genes, cromosomas).
Se comienza con una población de $n$ individuos ($n\equiv 0 \mod 4$) y se mide el valor de la función de adaptación de cada uno. La mitad con menor valor en la función de adaptación, muere.
La otra mitad se agrupa en parejas y se aparea, dando lugar al entrecruzamiento cromosómico (crossover); cada pareja tiene una descendencia de dos individuos. Cada nuevo individuo compartirá características de cada uno de sus progenitores, determinada a partir de un umbral. También se introduce la (pequeña) probabilidad de que cada uno de los nuevos individuos sufra mutaciones en sus genes. Luego, el procedimiento se repite: se evalúa la función de adaptación para cada individuo de la población, muere la mitad menos apta, el resto forma parejas y se aparea, etc.
Idea general de Algoritmo Genético
Input: tamaño_poblacion, tamaño_problema, param_umbral, prob_mutación
Población $\gets$ Inicializar_población(tamaño_poblacion, tamaño_problema)
función_de_adaptación(población)
mejor_s$\gets$ Mejor individuo de la población
REPETIR hasta que se cumpla el criterio de parada:
Eliminar al 50% de la población menos apto
Formar parejas
Para cada pareja P:
descendiente_1, descendiente_2 $\gets$ apareamiento(P, param_umbral)
Mutación(descendiente_1, prob_mutación)
Mutación(descendiente_2, prob_mutación)
Agregar descendiente_1 y descendiente_2 a población
función_de_adaptación(población)
mejor_s$\gets$ Mejor individuo de la población
DEVOLVER mejor_s
Generalmente, se toma como prob_mutacion = 1/L donde L es el tamaño de una solución. Por ejemplo, si s='0110' entonces prob_mutacion=1/4. Obviamente, esto no es una regla y puede ajustarse según el problema.
Como criterio de parada se puede utilizar un límite de iteraciones. También podría pararse cuando la variabilidad genética de la población es baja, es decir, todos los individuos mejor adaptados son muy parecidos entre sí.
Por la necesidad que surge de representar a las soluciones como cromosomas, es común que se prefiera representarlas como strings de bits (es decir, por ejemplo, '1001010'). En especial cuando se trabaja con variables enteras, una práctica común es codificarlas utilizando el código binario o, preferiblemente, el código de Gray.
A diferencia del binario, con la codificación Gray, un número entero difiere del siguiente sólo en un bit:
Decimal Gray Binario
0 000 000
1 001 001
2 011 010
3 010 011
4 110 100
5 111 101
6 101 110
7 100 111
Si usamos la codificación binaria, una mutación en un bit podría significar un cambio radical en la solución. En cambio, si se utiliza la codificación Gray, el cambio es más sutil.
Este tipo de codificaciones es muy utilizado, especialmente cuando se trata de un problema de optimización combinatoria. Veamos el siguiente ejemplo sencillo:
El dueño de un comercio debe organizar el horario de sus cuatro empleados. El día laboral consta de dos turnos de 6 horas (mañana y tarde). El comercio abre todos los días y requiere que haya un sólo empleado por turno. Por ahora, dejamos de lado otras restricciones naturales del problema para centrarnos en cómo codificar las soluciones.
En total hay 14 turnos en una semana, por lo que una forma de modelar una solución podría ser utilizar un vector de longitud 14 donde cada coordenada corresponde al número del empleado que debe asistir a ese turno. La coordenada 1 corresponde al turno mañana del Lunes y la 14 al turno tarde del Domingo. Por ejemplo, una solución podría ser: $$(1,3,4,1,2,1,2,2,4,1,3,1,2,4)$$
Para utilizar un algoritmo genético es muy preferible utilizar una codificación, es decir, mirar el cromosoma de la solución. Como el número entero más grande es el $4$, el cual tiene una longitud de $3$ es su representación binaria o de Gray, vamos a emplear esa longitud al momento de codificar la solución. Usaremos el código de Gray: $$\begin{array}{rcl} 1 & \rightarrow & 001 \\ 2 & \rightarrow & 011 \\ 3 & \rightarrow & 010 \\ 4 & \rightarrow & 110 \\ \end{array}$$
Entonces la codificación de la solución anterior es:
$$001010110001011001011011110001010001011110$$Notar la codificación es biyectiva, es decir, a partir del string podemos recuperar la solución.
En este ejemplo, podríamos pensar que la función de adaptación está relacionada a medir la satisfacción de cada empleado con el horario que le toca, que es lo que querríamos maximizar.
Si estamos tratando de resolver un problema con variables continuas, podemos omitir la codificación y trabajar directamente con las soluciones expresadas en reales. En este caso, también hay distintas maneras de llevar a cabo el apareamiento y crossover. Vamos a ver algunas, tomando como ejemplo el apreamiento de los cromosomas $(2,1)$ y $(-1,0.5)$ para el problema de minimizar la función $f(x, y) = 2(e^{-x^2-y^2}- e^{-(x-1)^2 - (y-1)^2})$
La primer forma es análoga a la del caso de variables discretas. En el ejemplo, con un umbral igual a $1$, sería: $$\begin{array}{l}Padre= (\color{red}{2,1})\\ Madre = (\color{green}{1,0.5}) \\ Descendiente_1 = (\color{green}{1},\color{red}{1}) \\ Descendiente_2 = (\color{red}{2},\color{green}{0.5}) \end{array}$$
Si bien esto es fácil de implementar, no se está introduciendo información nueva y no se esta aprovechando el hecho de trabajar con variables continuas.
Otro método consiste en efectuar una combinación convexa entre los genes de los padres a partir de un umbral. El $n$-ésimo gen del descendiente viene dado por: $$p_{hn} = \beta p_{mn} + (1-\beta)p_{dn}$$ donde $\beta$ es un número aleatorio en $[0,1]$, $p_{mn}$ es el $n$-ésimo gen de la madre y $p_{dn}$ es el $n$-ésimo gen del padre.
Se puede tomar el mismo $\beta$ para todos los genes del descendiente o distintos. Para realizar el entrecruzamiento del otro descendiente basta reemplazar $\beta$ por $1-\beta$. Tomar $\beta=0.5$ suele dar buenos resultados.
En el ejemplo, con umbral igual a $1$, supongamos que se genera $\beta=0.7636$ para efectuar el crossover entre los cromosomas: $$\begin{array}{l}Padre= (\color{red}{2,1})\\ Madre = (\color{green}{1,0.5}) \\ Descendiente_1 = (\color{green}{1},0.7636\times\color{green}{0.5}+ (1-0.7636)\times\color{red}{1}) = (\color{green}{1},0.6182) \\ Descendiente_2 = (\color{red}{2},(1-0.7636)\times\color{green}{0.5} + 0.7636\times\color{red}{1}) = (\color{red}{2}, 0.8818) \end{array}$$
Finalmente, otro método que se utiliza consiste en definir los genes de los descendientes de la siguiente manera, a partir del umbral: $$\begin{array}{rl} p_{h_1} & = p_{mn} - \beta(p_{mn}-p_{dn}) \\ p_{h_2} & = p_{dn} + \beta(p_{mn}-p_{dn}) \\ \end{array}$$
En el ejemplo, supongamos que el $\beta$ generado para el crossover es $\beta=0.67$: $$\begin{array}{l}Padre= (\color{red}{2,1})\\ Madre = (\color{green}{1,0.5}) \\ Descendiente_1 = (\color{green}{1},\color{green}{0.5} - 0.67\times(\color{green}{0.5}-\color{red}{1})) = (\color{green}{1}, 0.835) \\ Descendiente_2 = (\color{red}{2},\color{red}{1} + 0.67\times(\color{green}{0.5}-\color{red}{1})) = (\color{red}{2},0.665) \end{array}$$
En el caso de las variables reales, también hay varias maneras de definir qué se entiende por mutación.
Una forma de efectuar la mutación es reemplazar el gen por otro aleatorio dentro de un rango. Supongamos que queremos minimizar esa función en la región $[-5,5]\times[-5,5]$. Y que mutaremos el segundo gen del cromosoma $(2,1)$. Entonces generamos un número aleatorio con distribución uniforme en $[-5,5]$ y reemplazamos el gen que muta: $$(2,\color{red}{1})\xrightarrow{mutación}(2,\color{red}{2.7334231101129003})$$
Otra posibilidad es sumarle al gen un número generado a partir de una distribución $\mathcal{N}(0,\sigma^2)$. Esto implica el trabajo extra de encontrar un $\sigma$ adecuado. Además, si tenemos restricciones, esto podría causar que el punto deje de respetarlas y habría que efectuarle correcciones.
Enjambre de Partículas¶
Esta heurística está motivada por el comportamiento social de alimentación de ciertos animales, como una bandada de pájaros o un cardumen de peces. Las partículas vuelan en un medio siguiendo a los miembros en mejor forma del enjambre y teniendo en cuenta las áreas favorables del entorno.
La estrategia consiste en lo siguiente: se inicializan aleatoriamente las posiciones y las velocidades iniciales de todas las partículas. Luego, el algoritmo es ejecutado como una simulación: por turnos, cada partícula se mueve en base a su velocidad, la mejor posición conocida por el enjambre y la mejor posición conocida por la partícula. El valor de la función objetivo se actualiza después de efectuar el movimiento de cada partícula.
En cada iteración, la velocidad de la partícula i-ésima es actualizada de la siguiente manera: $$v_i(t+1) = \alpha v_i(t) + c_1\zeta(p_i^{best}-p_i(t))+c_2\eta(p_{gbest}-p_i(t))$$ Donde $v_i(t+1)$ es la nueva velocidad para la partícula, $\alpha$ es la constante positiva de inercia, $c_1$ y $c_2$ son los pesos que simbolizan cuánto influyen la mejor posición personal y la mejor posición global, $\zeta$ y $\eta$ son números aleatorios en $[0,1]$, $p_i^{best}$ es la mejor posición personal de la partícula y $p_{gbest}$ es la mejor posición conocida por el enjambre.
A continuación, la posición de la partícula se actualiza de la siguiente manera: $$p_i(t+1) = p_i(t) + v_i(t)$$
La naturaleza del método indica que se utiliza con problemas sobre variables continuas.
Idea general de Optimización con Enjambre de Partículas (Minimización)
Input: tamaño_problema, tamaño_población, $\texttt{c}_1$, $\texttt{c}_2$, $\mathtt{\alpha}$
Población $\mathtt{\gets}$ Inicializar posición de las partículas
Velocidades $\mathtt{\gets}$ Inicializar velocidades de las partículas
Mejor_personal $\mathtt{\gets}$ Posición inicial de las partículas
$\mathtt{p_{gbest}} \gets \underset{\mathtt{i}}{\mathtt{arg\,min}}\quad \mathtt{f(p_i)}$
MIENTRAS no se cumpla el criterio de parada:
Para cada $\mathtt{p\in}$ población:
Actualizar velocidad de p
Actualizar posición de p
Si $\mathtt{f(p_i(t))\leq f(p_i^{best})}$ :
Actualizar Mejor_personal de p
Si $\mathtt{f(p_i^{best}) \leq f(p_{gbest})}$ :
$\mathtt{p_{gbest}\gets p_i^{best}}$
DEVOLVER $\mathtt{p_{gbest}}$
Observaciones
- El criterio de parada puede ser un límite de iteraciones.
- Generalmente se utiliza un número pequeño de partículas (entre $20$ y $40$).
- Con respecto a los pesos $c_1$ y $c_2$, se toma $c_1, c_2 \in [0,4]$, generalmente $c_1=c_2=2$
- En vez de tener en cuenta la mejor posición conocida por el enjambre, se puede tener en cuenta, para cada partícula, la mejor posición conocida por sus vecinos, donde el vecindario está definido como las partículas más cercanas en sentido de $\lVert \cdot \rVert_2$
Optimización con restricciones¶
¿Qué ocurre si el problema no es irrestricto?
Todas las heurísticas que vimos hasta ahora son perfectamente adaptables a problemas de optimización con restricciones. Generalmente se utiliza alguna de las siguientes dos ideas:
- Penalización: es la misma idea que vimos hace algunas clases. A la función objetivo se le suma una función de penalidad que vale $0$ para los puntos que cumplen con todas las restricciones. Al momento de evaluar la calidad de una solución, si esta se encuentra fuera de región delimitada por las restricciones, será fuertemente penalizada y descartada por el método. Aplicable a problemas de optimización combinatoria y de optimización continua. Notar que ahora no necesitamos que la función de penalidad sea $C^1$ para derivarla y demás.
- Corrección: si obtenemos una solución que sale del dominio, podemos intentar corregirla. Por ejemplo, podemos reflejarla con respecto a $\partial \Omega$. Otra opción, por ejemplo en el caso de la optimización con enjambre de partículas, es hallar $\beta$ tal que $p_i(t+1) = p_i(t) + \beta v_i(t)$ sea factible.
Más heurísticas: http://www.cleveralgorithms.com/nature-inspired/index.html