Optimización por "enjambres"

Todos hemos escuchado de los algoritmos genéticos.

Básicamente, se usan para ver, dentro de un espacio matemático, qué punto es el "mejor". Para saber cuando un punto es mejor que otro, simplemente se evalúa cierta función en ese punto, y se ve cuanto vale. Por lo general, se busca que sea lo mayor posible, o lo menor posible (problemas de maximización y minimización, respectivamente). Esa función la podemos llamar "Aptitud", o como se le nombra clásicamente en Investigación de Operaciones: Función Objetivo (puede ser minimizar costos, riesgos, distancias, o maximizar ganancias, flexibilidad, robustez, etc).

(NOTA: si tienen flojera de leer, pasen al final del post, que hay un video EXCELENTE!)

Subiendo (o bajando) montañas...

Esa solución es un vector "x". Usualmente en optimización, uno se busca un "x-inicial", y evalúa la "aptitud"de los puntos que están en los alrededores de ese lugar, y se sigue alguna estrategia para suponer hacia dónde hay que moverse para encontrar un mejor valor de la función. Una vez se determina hacia dónde se busca una mejor solución, se "avanza" un poco (una distancia a escoger juiciosamente), y tenemos una nueva "x". El proceso se repite, hasta que  uno ve que en los alrededores no hay nada mejor, y supone que llegó al "mejor" lugar (el que tiene menor valor o mayor valor en la función objetivo). Puede ocurrir que se llegó a un óptimo local (había otro máximo mejor, pero éste se encontró más rápido).

La competencia para "sobrevivir"...

En Algoritmos Genéticos, no se hace esto. Los pasos son más o menos los siguientes:

1. Generar a los competidores. Aleatoriamente creamos una cantidad grande de posibles soluciones, es decir, no una "x", sino (pongamos un número) 100 diferentes soluciones, x1, x2,..., x100. Estos serán nuestra "población".
2. Selección "natural". Ahora toca jugar a la madre naturaleza, y determinar cuáles son los mejores de ellos, es decir los más aptos. Pongamos un número: seleccionamos a los 20 mejores (se evalúa la función objetivo en cada uno y tomamos los que tienen los 20 valores más pequeños o más altos de esa función). A los que no entren en este grupo, los "matamos" (eliminamos esas variables).
   
3. Sexo libre, 100% de fertilidad, y la aparición de mutantes.  Cada uno de estos 20 ganadores, es apareado con los otros 19 (aunque pueden seguirse estrategias menos promíscuas ;D ), con un 100% de posibilidad de embarazo. Es decir, siempre se genera uno o más hijos en cada apareamiento. Puede haber apareamiento entre más de dos de los competidores, cosa que en la biología no ocurre! (aquí si tendría sentido la serie de televisión "Mis dos papás"). Cada hijo es una "x" nueva, cuyas características genéticas (valores de cada posición del vector "x"), son una mezcla de las de sus padres. Adicionalmente, aleatoriamente algunos de los hijos producidos en esta etapa tienen alguna característica genética cambiada aleatoriamente, lo que corresponde a una mutación. La población crece hasta tener 100 indivíduos nuevamente, donde están los 20 padres, y los demás son los hijos.
4. Ahora se repite el proceso, porque se vuelve a ver cuáles son los 20 más aptos, y el resto se muere, y se produce nuevamente un apareamiento... Esto se repite hasta que las diferencias de aptitud entre los miembros de la población son muy pequeñas, y están todos muy cerca (tienen genes casi iguales). En ese momento se supone que el promedio de los genes de la población es la solución al problema (el mejor valor de "x" en el espacio matemático, según esa función objetivo fijada).

Importante es notar que en este método, hay dos componentes del comportamiento del algoritmo: la exploración (generando aleatoriamente "x" por todo el espacio, y aleatoriamente generando indivíduos mutantes, de forma ciega), y la explotación (siempre matando a los peores, y dejando a los mejores, hace que se aglomeren cada vez más arriba en las "montañas" de la función objetivo). Esto hace que sea menos probable que la solucion encontrada sea un óptimo local, y en eso puede resultar mejor que la optimización clásica.

Vuelen, hijos míos, exploren, ayúdense y destruyan al enemigo!

Ahora entonces tenemos a las técnicas de Optimización por "enjambres". Estas no son una población en la que se mueren los menos aptos. Por el contrario, siguen vivos, y el que no mueran agrega ese componente de "exploración" del que hablamos en los algoritmos genéticos, pero el que compartan información, hace que busquen las partes altas del espacio matemático, lo que equivale a un comportamiento de explotación. Dicen que nadie aprende de la experiencia ajena, lo cuál es verdad en el genético, pero acá se rompe esa regla!

1. Enjambre en caos. Cada "x" nace, inicialmente, en una posición aleatoria, con una velocidad aleatoria, volando hacia una dirección aleatoria. Es decir, la locura y el caos total!
   
2. Corran la voz!... la versión matemática de un chisme. Cada indivíduo (que es una posible solución "x" al problema), se entera de en qué posición está el que, dentro de toda la población, ha conseguido un mejor espacio para explorar (el que tenga mejor valor para la función objetivo). También se entera, de entre los que estén más cerca de él, cuál es el que mejor posicionado está.
3. La información es de quién la usa!. Cada uno de los indivíduos de la población ahora decide cómo usa la información que tiene, y la pondera respecto a lo que él ya venía haciendo (por algo venía en esta dirección, no?). Aleatoriamente le da más o menos importancia al chisme de dónde está el mejor de toda la población, dondé está el mejor de sus vecinos, y hacia dónde iba cuando se enteró de estos dos chismes. Según la información, elige una nueva dirección, y camina por ahí, llegando a una nueva posición. Allí vuelven a llegarle los chismes actualizados, y se repite el proceso.
4. Cuando todos más o menos están en el mismo sitio, el promedio de los lugares en los que están se asume como la respuesta al problema.

Interesante, no?

Ahora vean un video de unos robots que tienen la tarea de arrimar un objeto hacia su base. Ninguno de ellos logra ver más allá de unos centímetros de su naríz, pero se comunican perfectamente entre ellos, y trabajan bajo la optimización de enjambres. Poco a poco ubican el objeto, y logran llevarlo hacia su objetivo. Realmente alucinante!!

(gracias Gregorio por comentarme sobre este tema y pasarme el video!)