El templado o cocido o temple o recocido simulado es una metaheurística inspirada en el templado (o cocido o temple…) de metales (en algunos sitios hablan de espadas samuráis para hacerlo parecer más interesante. Como si una metaheurística necesitara algo más para parecer interesante…mejor no respondáis). La idea es que durante el templado los átomos van colocándose en las posiciones de menor energía aunque a veces pueden moverse a una de mayor energía. Este caso depende de la temperatura a la que esté en el material y a mayor temperatura más probable es que ocurra. Tampoco todos los saltos son igual de probables, a mayor diferencia de energía también es menos probable que ocurra.

Sonará ridículo, pero uno de los problemas que he encontrado con este algoritmo es que se suelen usar términos químicos para describirlo lo cual resulta confuso para los pobres programadores que no estamos acostumbrados a ellos. Así que dejando de lado el modelo real en que se inspira, el algoritmo es similar a la búsqueda aleatoria con el añadido de que tiene cierta probabilidad de aceptar una solución cuyo valor sea peor que la actual. Es decir, que las soluciones peores que la actual no se descartan siempre, se deja al azar si se conserva la actual (la mayoría de las veces) o se remplaza por la nueva solución. Esto le permite escapar de óptimos locales explorando zonas que de otra forma no visitaría. Eso sí, para evitar ir saltando de un lado a otro a lo loco y lograr converger en un máximo la diferencia entre los valores de la función fitness no puede superar un límite que se reduce con cada iteración con lo que es menos probable que se elija una solución peor que la actual. La formula que se aplica es que una solución de fitness f’ peor que f se acepta siempre y cuando:

e ^ (f-f’/ Ti ) > rnd(0,1)

Podemos ver que se usa e ^ x para calcular la posibilidad de que se elija esa solución. Para ello calculamos la diferencia entre ambas soluciones y la dividimos entre la temperatura actual. Hay que tener en cuente que este caso solo sirve cuando busquemos el mínimo (f’ es peor si f’ > f) pero si buscamos el máximo debería de ser f’-f  ( f’ es peor si f’ < f). con esto debería de darnos siempre un resultado negativo ya que si f’ es mejor que f se elegiría directamente y no llegaríamos a este punto.

if(newFitness  Math.random()){
    this.cords = newCords;
    this.fitness = newFitness;
}

Si nos fijamos en la gráfica de la función e ^ x entre -5 y 0 vemos que su valor decrece según aumenta la diferencia entre ambos valores. También podemos ver, que al estar dividida por la temperatura, cuanto mayor sea la misma más «tolerante» es con la diferencia. Como según se itera el algoritmo la temperatura se reduce cada vez es menos probable elegir una solución peor que la actual. Según disminuye la temperatura y el comportamiento del algoritmo se asemeja más a una búsqueda aleatoria.

Gráfica de e^x para x < 0

Función de enfriamiento

La función de enfriamiento es la operación que se ocupa de reducir el valor de la temperatura cada iteración. Es más importante de lo que parece ya que es la temperatura la que permite saltar a soluciones peores y explorar el espacio de soluciones. Las dos más habituales son:

Restar un valor que sea muy pequeño «casi cero»

Ti = To – k * i     =     Ti = T_i-1 – k

Tiene la ventaja de que se puede calcular muy rápidamente. El problema es que es demasiado lineal y no suele dar tan buen resultado.

Multiplicar por un valor menor que uno pero cercano a él. O sea que sea «casi 1».

Ti = T0 * k ^ i    =   Ti = T_i-1 * k

Es rápida de calcular y da buen resultado. Variando el valor de k variamos «el comportamiento» alargando o acortando el rápido descenso inicial o lo «exploradora» que sea la metaheurística.

Algunas más complejas:

Ti = T0*k*i

Ti = (To/imax) * i

Ti = To/(1+k*ln(1+i))

La temperatura controla el umbral de aceptación de una variable. Si es alta es más fácil que una solución peor «pase el filtro». Así que lo ideal sería poder adaptarla según lo necesite el algoritmo. Acelerar su descenso, retrasarlo e incluso invertirlo. Para que el algoritmo converja en una solución es necesario que la tendencia general de la temperatura sea descender pero puede sufrir momentos puntuales de aumento. En concreto lo ideal sería que la temperatura aumente cuando esté intentando «escapar» de un óptimo local. ¿Como sabemos cuándo es eso? Sencillo, ocurre cada vez que se elige una solución peor que la actual. Nos podemos imaginar que la solución

Siendo

fbest la solución seleccionada hasta ese momento

f el valor de fitness para la solución elegida

Ti la temperatura calculada para la iteración i por alguno de los métodos anteriores

T’ = (1+(f-f_best/f))*Ti

Como f solo puede ser igual o mayor (es peor) a f_best. La formula actúa compensando la disminución de la temperatura cuando  la solución empeora. De tal forma que combina ciclos de descenso con otros de ascenso aunque en teoría tendencia general es que la temperatura disminuya. ¡Ojo! Que es en teoría. Puesto que al subir la temperatura aumenta la probabilidad de que seleccione soluciones peores y cada vez que selecciona una soluciones peor aumenta la temperatura puede llegar realimentarse hasta que el aumento de temperatura se dispara.

Al final yo he optado por:

T’ = (1+(f-f_best/f))*Kinc + Ti

Al ser una suma se frena el aumento de temperatura y el parámetro Kinc permite controlar esta variación.

Aunque con los parámetros iniciales adecuados puede encontrar una correcta aproximación al óptimo global su desempeño en espacios de búsqueda muy grandes o con muchas dimensiones no suele ser muy bueno. También se usa como optimizador local.

Puedes encontrar el código aquí.

Esta metaheurística tiene la ventaja de que es sencilla de entender y de aplicar. En su forma más simple consiste en partir de un punto aleatorio del espacio de soluciones, elegir aleatoriamente una solución cercana, si es peor se elige otra, si es mejor movernos a ella y volver a elegir otra solución desde ahí.

La implementación es fácil y su ejecución es rápida o al menos hasta donde lo permita el cálculo del fitness de la solución elegida.

var newCords = this.newSolution(this.cords.slice(0));
var newFitness = this.model.calculateFitness(newCords);
if(newFitness > this.fitness){
  this.cords = newCords;
  this.fitness = newFitness;
}

Por desgracia su desempeño solo es bueno en espacios de búsqueda sencillos. Es fácil que se quede atrapada en un óptimo local. Todo depende del tamaño del área en que se busca la nueva solución. Un tamaño muy grande hace que le cueste mucho más converger, uno muy pequeño causa que se quede atrapada en máximos locales. Y no hay una buena solución para todos los problemas, los valores dependen del espacio de búsqueda. Ahora es cuando estaréis pensando: «¿Y si hacemos el tamaño del área de selección variable?». Mala suerte, llegáis unas cuantas décadas tarde. Hay varios algoritmos que usan esta táctica.

Primero un detalle, el «Tamaño del área de selección» se le llama también «tamaño del paso» ya que sería el símil a lo que puede avanzar en cada iteración por el espacio de búsqueda (generalmente hay tendencia a representar el espacio de búsqueda como montañas y a nuestro algoritmo caminando por ahí).

Volviendo a las búsquedas aleatorias con «paso de tamaño variable». Hay varias estrategias, unas intentan calcular el tamaño del paso analizando la función a optimizar, otros van ajustando el valor de forma dinámica. La forma más sencilla de hacerlo es simplemente ir aumentando el tamaño del paso cada vez que compruebas un vecino y es peor que la solución actual. Una vez encuentras una solución mejor vuelves al tamaño de paso inicial. Con cuidado de no superar un tamaño máximo de paso para evitarnos problemas como superar el espacio de búsqueda.

var newCords = this.newSolution(this.cords.slice(0));
var newFitness = this.model.calculateFitness(newCords);
if(newFitness > this.fitness){
  this.cords = newCords;
  this.fitness = newFitness;
  this.step = this.parameters.step;
} else { //variamos tamaño del paso
  this.step.map(function(step){return step*this.parameters.increaseStep}, this);
}

Aunque se puede usar como optimizador global suele tener mejor desempeño como optimizador local que parte de los resultados obtenidos por un optimizador global.

Hay algunas modificaciones interesantes que mejoran algunos aspectos.

Por ejemplo, al ser el punto de origen aleatorio solo explora una pequeña parte del espacio de búsqueda. La forma más fácil de resolverlo es ejecutarlo varias veces con puntos de inicio diferentes y quedarse con la mejor. Esto permite su uso como optimizador global. Además lo hace fácilmente paralelizable. A este algoritmo se le denomina «con reinicio».

El código completo esta en este repositorio de github.

Tanto imaginarnos que el espacio de soluciones es un pasaje con colinas y depresiones que antes o después el nombre alguna metaheurística tenía que hacer referencia a subir colinas. Su desarrollo es sencillo. Situado en un punto, revisa todos sus vecinos o, si son demasiados, una muestra aleatoria de ellos. Tras ello se mueve al vecino cuyo valor es mayor que el actual, allí repite el proceso. El algoritmo continua hasta que no se pueda encontrar un vecino mejor o se haya realizado un número de iteraciones prefijado.

Como optimizador local funciona bastante bien por lo que muchas veces se usa para «mejorar» el resultado de un optimizador global. Existe una versión para optimización global que consiste en lanzarlo varias veces desde puntos de origen distintos, a esta versión se le denomina «con reinicio» ya que una vez que deja de mejorar o se alcanza un número determinado de iteraciones se reinicia el algoritmo desde un nuevo origen.

Su funcionamiento es muy parecido a de random search, con la diferencia de que consulta todos (o al menos una muestra) sus vecinos para seleccionar el mejor. Hay otra forma de implementarlo. En lugar de visitar N vecinos se van comprobando vecinos de uno en uno hasta encontrar uno que mejore el resultado actual en por lo menos un valor umbral fijado, todos cuya mejora sea inferior a ese umbral son descartados. Si ese umbral es muy pequeño el comportamiento es similar al de random search.

Para que el código no sea muy parecido al de random search vamos a incluir una mejora. En lugar de mirar solo el fitness de los vecinos para compararlos vamos a usar la pendiente que sería igual a la variación del fitness dividido por la distancia a entre las coordenadas de la solución actual y el vecino que se compara. Es decir vamos a elegir el camino que más rápido sube. Por lo tanto el nuevo valor que usaremos para comparar vecinos es:

fdist(Ni) = f(Ni) – f(S) / dist(Ni, S)

Siendo Ni el vecino que se evalua y S el punto donde se encuentra ahora la búsqueda. Ojo y no confundir está pendiente calculada grosso modo con la pendiente de una función en un punto.

var newCords = this.newSolution(this.cords.slice(0));
var newFitness = this.model.calculateFitness(newCords);
var newVarition = (auxFitness-this.fitness)/this.distance(newCords, this.cords); //dif_fitness/distance

También se incluye un algoritmo para la variación del tamaño del paso de búsqueda en caso de que no se encuentre una solución mejor.

step = step*increaseStep

Para evitar que el tamaños del paso se dispare a valores absurdos se permite fijar un limite de veces que se multiplicara por el incremento. Cada vez que se encuentre una buena solución se volverá al tamaño de paso original.

if(newFitness > this.fitness){
  this.cords = newCords;
  this.fitness = newFitness;
  this.step = this.parameters.step;
  this.numberIncreaseSteps = 0;
} else {
  this.numberIncreaseSteps++;
  if(this.numberIncreaseSteps < this.parameters.maxTimesIncreaseStep){
    for(var i = 0; i < this.parameters.dimensions; ++i){
      this.step[i] *= this.parameters.increaseStep[i];
    }
  }
}

El código se puede encontrar en github.

Seamos sinceros, el discurso de que la inteligencia artificial es para lograr crear una mente artificial que imite la inteligencia humana suena muy bonito e inspirador, pero uno de los principales motivos para los que queremos la inteligencia artificial es que nos solucione problemas. Y a ser posible problemas que nosotros no seamos capaces de resolver fácilmente. Hay problemas que son irresolubles matemáticamente e inabordables por la fuerza bruta con la potencia de cálculo actual. Una de las herramientas que tenemos para resolver estos problemas son las heurísticas y metaheurísticas. Estos algoritmos exploran el espacio de soluciones (el conjunto de todas las posibles soluciones para un problema) usando información sobre la calidad de cada solución para guiarse en la búsqueda de la mejor solución. Estos algoritmos permiten resolver en un tiempo aceptable problemas demasiado costosos como para ser abordados de manera exhaustiva (comprobando todas las posibles soluciones). Pero nada es gratis en esta vida, a cambio
Su principal diferencia es que las heurísticas suelen estar orientadas a un tipo de problema mientras que las metaheurísticas son más genéricas y se pueden aplicar a multitud de problemas.

El origen de estos algoritmos es diverso, desde reglas descubiertas empíricamente, desarrollos matemáticos, prueba y error o claras inspiraciones en fenómenos de la naturaleza. Rara vez estos algoritmos son únicos. Generalmente existen familias basadas en variaciones del mismo algoritmo para mejorar su rendimiento con distintos tipos de problemas.

Pese a una descripción tan genérica estos algoritmos tienen ciertas características en común:

Fitness/distancia:

Todas poseen una función que evalúa una solución y le indica «lo buena que es».  Aunque hablare casi todo el rato de función de fitness realmente esta función puede adoptar dos formas:

Una función de fitness o bondad que indica lo correcta que es una solución. Su valor, aumenta cuanto más cerca se está del valor deseado.

Una función distancia que indica a qué distancia del valor buscado estamos. Esta función decrece según nos acercamos a la solución ideal.

Aunque nos pueda parecer que son muy distintas realmente hay dos maneras muy simples de convertir un tipo de función en la otra.

Dividir un numero K mayor de 0 por el valor de la función.  K/f(x)

Restarle a un valor K mayor que 0 el valor de la función. en este caso hay que asegurarse de el valor de la función nunca es mayor que K.  K-f(x) 

Esta función ha de ser una representación apropiada del problema real ya que es la aporta información sobre la solución al algoritmo y de su corrección dependerá que se puede encontrar una solución adecuada.

Máximo/mínimo:

Intenta maximizar o minimizar el valor la función de fitness. El punto deseado debe de ser siempre un máximo o un mínimo y hay que crear la función de fitnes para que cumpla ese requisito.

Una función no tiene porque tener un único punto máximo/mínimo de hecho puede tener máximos/mínimos locales que son puntos que son máximos/mínimos en su entorno pero no son el punto máximo/mínimo de la función. Hay que tener cuidado de no quedarse atascado en uno de estos puntos.

Exploración:

Como ya se ha comentado estos algoritmos basan su funcionamiento en explorar el espacio de soluciones guiándose por la función de fitness buscando sus valores máximos (o mínimos).

Podemos imaginarnos el espacio de soluciones como una amplia pradera llena de lomas, cada punto de este terreno es una solución y la altura de cada punto viene determinada por la función fitness.

Ejemplo de espacio de búsqueda – Imagen obtenida Wikipedia

Estos algoritmos al ver un punto alto se lanzan hacia él cual montañista o cabra que siempre tira al monte y en cuanto llegan a ese máximo puede quedarse «atrapados» en él negándose a seguir explorando el terreno. Para evitar esto se tiene que permitir que exploren soluciones que sean peores que las ya encontradas, sin embargo tampoco han de ser tan «exploradores» que ignoren los máximos o se convertirán en un algoritmo que se mueve aleatoriamente por el espacio de soluciones. Gran parte de la dificultad de hacer funcionar estos algoritmos es lograr el equilibrio entre ambas situaciones.

Coste vs mejor solución:

Generalmente estos algoritmos devuelven aproximaciones de cual es la mejor solución. Para mejorar estas aproximaciones es necesario realizar más iteraciones lo que supone mayor consumo de recursos y coste en tiempo. Hay que buscar un equilibrio entre la exactitud del resultado y el coste en tiempo y recursos del mismo.

Solución aproximada:

No hay seguridad de que lo que se vaya a obtener sea la mejor solución, posiblemente solo se obtenga una aproximación. Pero afortunadamente en el mundo real una buena aproximación puede ser tan validad como la solución ideal. Ademas que en muchos casos se necesita solo una buena solución, sin necesidad que sea la solución óptima.

Dada su variedad también es difícil clarificarlas. Pero vamos a ver algunas características por las que agruparlas:

Una única solución o múltiples soluciones: 

Algunas heurísticas/metaheurísticas usan varias soluciones las cuales van modificando, a veces combinándolas,  para obtener nuevas soluciones. En el caso de una única solución simplemente tiene una solución que van mejorando.

Búsqueda global o búsqueda local:

La búsqueda global busca en todo el espacio de soluciones mientras que la local busca solamente en el espacio cercano a una solución propuesta. Lo mayoría de las heurísticas o metaheurísticas tratan de equilibrar ambos aspectos, sin embargo depende del problema a resolver necesitaremos decantarnos por uno de estos dos lados.

Deterministas o estocásticos:

En el primer caso si ejecutamos la heurística/metaheurística varias veces con los mismos parámetros iniciales e iteramos el mismo número de veces obtendremos siempre el mismo resultado. Mientras que en el segundo caso al entran en juego partes aleatorias la respuesta puede ser diferente, pese a que las condiciones iniciales sean idénticas. Eso significa también que puede ser necesario ejecutar el algoritmo varias veces para asegurarse de que la respuesta obtenida es la más adecuada.

Paralelizables:

Algunas heurística/metaheurística son fácilmente paralelizables. Esta característica puede ser importante si necesitamos resolver un problema con gran consumo de recursos ya que podríamos distribuir su calculo entre varias maquinas.

Inspiradas en la naturaleza:

Muchas metaheurísticas han aparecido de fijarse como en la naturaleza se soluciona el mismo problema. Los insectos, bandadas o los genes han sido inspiradores de varias de ellas. El problema es que este método puede llevar a encontrar metaheurísticas que funcionan sin saber muy bien el porque. sin embargo ha dado muy buenos resultados. Aunque últimamente da la sensación de que el proceso de creación de estas metaheurísticas ha dado la vuelta y parece en algunos casos primero se crea el algoritmo y luego se busca a que se parece ya que este tipo de algoritmos siempre despiertan interés independientemente de que no sean tan buenos o aporten nada a los ya existentes.

Podemos pensar que ya tenemos una solución mágica para todos nuestros problemas. Desgraciadamente no es tan sencillo. Suelen funcionar bien con problemas de optimización matemática, optimización combinatoria o satisfación de restricciones. Ejemplos hay muchos, el problema del viajante, el problema de la mochila, el problema de la ocho/n reinas, …

Sin embargo en casos cuando el espacio de soluciones no es fácil de explorar ya sea porque es enorme, hay muchas discontinuidades, muchos máximos locales o una combinación de todas.

Personalmente estos algoritmos me gustan, ya no solo por el interés que tiene de resolver este problemas, si no por fácil que puede resultar resolver alguno problemas irresolubles cambiando la forma de afrontar el problema. La mayoría de estas soluciones adoptan estrategias, que al menos a mi, me resultan curiosas.

Esta metahurística está inspirada en el comportamiento de en como los enjambres de insectos, bandadas de pájaros o de los bancos de peces se comportan buscando alimento.

Se basa en «liberar» un grupo de individuos en el espacio de soluciones. Estos se mueven explorándolo en busca de los puntos máximos (óptimos). En cada iteración se mueven condicionados por la dirección que llevan ahora, cuyo símil sería la inercia, la mejor solución que ellos han visitado, que sería su experiencia, y la mejor solución visitada por el grupo, que seria la tendencia social.

Cada individuo tiene memoria y recuerda cual a sido el mejor punto por el que ha pasado y su «bondad» (fitness) para compararlo con la calidad de otros puntos buscando otro mejor. A parte de eso tiene una lista de coordenadas con la posición actual y otra con la velocidad a la que se moverá en cada dimensión en la siguiente interacción. Las velocidades pueden ser positivas o negativas así que además de la cantidad de desplazamiento también indican la velocidad. A diferencia de los enjambres del mundo real que solo se mueven en 3 dimensiones (al menos los que hay aqui en la Tierra) en los virtuales los individuos se mueven en tantas dimensiones como hagan falta para explorar las soluciones del problema. Por ejemplo si queremos encontrar el máximo de una función que tiene 10 parámetros cada parámetro será una dimensión del espacio de soluciones. Enjambres virtuales que vuelan en un espacio de n dimensiones buscando sus puntos máximos. Hay que reconocer que suena mejor que «Optimización basada en enjambres».

El algoritmo funciona actualizando el vector de coordenadas sumándole el vector de velocidades cuyos valores se actualizan en cada interacción y representa la lucha interna entre las creencias propias del individuo y las que comparte la sociedad (no diréis que no lo vendo interesante). Esto matemáticamente se realiza calculando la distancia a la mejor solución propia y a la mejor solución de todo el enjambre y cada una se pondera multiplicándola por un  valor que indica su importancia (Ksocial, Kown) . Ademas se multiplica por un valor aleatorio entre 0 y 1. Para introducir cierta variación aleatoria en cuanta importancia da a cada creencia. Imagínate una mañana antes del café lo que te importa que piense la sociedad.

Jugando con las constantes Ksocial, Kown puedes obtener individuos que se vean influenciados de distinta forma por la experiencia social y personal. Por ejemplo si ambos son cero el individuo no se verá influenciado por ninguna experiencia. Si poniendo cualquiera de ellos a cero nuestro individuo no tendrá en cuenta esa experiencia para guiarse. Por lo general el valor que se da ambas es 2.

El calculo de las velocidades para cada coordenada seria:

v[i] = K_inertia * v[i] + K_social * rand(0,1) * (cord_social[i] – cord[i]) + K_own * rand(0,1) * (cords_own[i] – cord[i])

this.updateVelocities = function(){
  var ownExperienceVelocities = this.ownExperience.velocities(this.cords);
  var socialExperienceVelocities = this.socialExperience.velocities(this.cords);
  for(var i = 0; i < this.cords.length; ++i){
    this.velocities[i] = this.inertia.value * this.velocities[i] + ownExperienceVelocities[i] + socialExperienceVelocities[i];
  }
};

La cordenadas se actualizarian con una simple suma:

Cords[i] = cords[i] + v[i]

//Update cords
this.move = function(){
  for(var i = 0; i < this.cords.length; ++i){
    this.cords[i] += this.velocities[i];
  }
};

Finalmente nos queda la la inercia. La inercia se multiplica por el valor actual de la velocidad en cada dimensión Si el valor es muy grande los individuos se moverán más rápido y menor será el efecto de los otros parámetros basados en la experiencia. La función de la inercia es evitar que los individuos converjan demasiado pronto obligándoles a recorrer el terreno. Un valor de inercia elevado es útil al principio cuando interesa explorar lugares nuevos del espacio de soluciones pero dificulta la aproximación final al resultado óptimo una vez encontrada la región donde está. Es buena idea ir reduciéndola con el tiempo. Para ello se fija una inercia inicial y una final y se reduce cada interacción hasta alcanzar la inercia final. Al ir decreciendo los movimientos son cada vez más pequeños aproximándose a la solución final.

var Inertia = function(inertiaMin, inertiaMax, inertiaChange){
this.inertiaMin = inertiaMin || 0;
this.inertiaMax =  inertiaMax || 1;
this.inertiaChange = inertiaChange || 0.01;
this.value = 1;

this.update = function(){
  if(this.value >= this.inertiaMin){}
    this.value -= this.inertiaChange;
  }
  if(this.value < this.inertiaMin){
    this.value = this.inertiaMin;
  }
}
}

Cada interacción del algoritmo consta de los siguientes pasos:

1.  Calculamos las velocidades en cada dimensión.
2. Calculamos las nuevas coordenadas.
3. Verificamos y corregimos las coordenadas.
4. Calculamos la nueva inercia.
5. Calculamos el fitness de las nuevas coordenadas.
6. Si es necesario actualizamos la mejor solución propia.
7. Si es necesario actualizamos la mejor solución social.

this.fly = function(){
  this.updateVelocities();
  this.move();
  this.cords = this.modelFitness.validateCords(this.cords);
  this.inertia.update();
  this.fitness = this.modelFitness.calculateFitness(this.cords);
  this.ownExperience.updateFitness(this.fitness, this.cords);
  this.socialExperience.updateFitness(this.fitness, this.cords);
}

Con el paso de las iteraciones los individuos iran convergiendo sobre el punto óptimo que hayan encontrado.

Vamos a modelar este sistema. Lo primero es ver que parámetros nos hacen falta:

La inercia simplemente almacena el valor inicial, el final, la cantidad que cambia y el valor actual. Cada vez que se indica que se actualice se resta al valor actual el valor de cambio hasta alcanzar el mínimo.

Almacenaremos la experiencia como un objeto que almacena las mejores coordenadas, su valor de fitness, la importancia (peso) que se da a la misma en la formula del cálculo de velocidades y una función para actualizarla y otra para calcular el valor correspondiente a la formula de actualización de velocidades.

var Experience = function(K){
  this.fitness = 0;
  this.cords = [];
  this.K = K || 2;

  this.updateFitness = function(fitness, cords){
    if(fitness < this.fitness){
      this.fitness = fitness;
      this.cords = cords.slice();
    }
  }

  this.velocities = function(birdCords){
    var velocities = [];
    for(var i = 0; i < this.cords.length; ++i){
      velocities[i] = (this.cords[i]-birdCords[i]) * this.K * Math.random();
    }
    return velocities;
  }
};

Cada individuo tendrá su propia experiencia y compartira la experiencia social con el resto de individuos. De esta forma tan sencilla se comunican entre ellos.

Los individuos son sencillos, simplemente se componen de la experiencia propia y social, el fitness actual, las coordenadas actuales, el vector de velocidades y la inercia.

var Bird = function(inertia, socialExperience, ownExperience, modelFitness, parameters){
  this.socialExperience = socialExperience;
  this.ownExperience = ownExperience;
  this.parameters = parameters;
  this.modelFitness = modelFitness;
  this.fitness = 0;
  this.cords = [];
  this.velocities = [];
  this.inertia = inertia;

  this.fly = function(){
  ...
  }

  this.move = function(){
  ...
  };

  this.updateVelocities = function(){
  ...
  };

  this.initialize = function(){
  ...
  };
};

La bandada/enjambre/nube es simplemente un array de individuos que cada iteracción se les pide que actualicen sus posiciones y fitness.

Las iteracciones se repiten hasta alcanzar la condición de finalización deseada. La mejor solución estará almacenada en la experiencia social.

Vamos a ver un ejemplo calculando el valor mínimo de la función similar a la que define una esfera.

f(x, y) = x²+y²

Pero para n dimensiones, el valor de la misma en cada punto es la suma de todas las coordenadas del punto elevada al cuadrado. Siento desvelaros el asesino pero el resultado se encuentra en punto que tenga todas sus coordenadas a 0. Realizaremos la búsqueda en el espacio comprendido entre 10 y -10 para cada una de sus coordenadas

Como buscamos el mínimo de la función pero este algoritmo funciona buscando máximos hemos de buscar una forma de solucionarlo. La búsqueda es en el espacio comprendido entre 10 y -10 asi que el valor máximo que puede tomar la función, que recordemos es la suma del cuadrado del valor de cada coordenada, es 100 por el numero de coordenadas. Solo hemos de restar a ese valor el valor del punto actual y tenemos una función de fitness que devuelve el valor máximo cuando nuestro punto corresponde con el mínimo.

La función de validar coordenadas es tan secilla como asegurarse de que nunca son menores de -10 ni mayores de 10.

Debajo esta el ejemplo para 5 dimensiones:

var test = require('../test/sphere.js');
var mrWolf = require('./flock.js');

var sphere = new test.TestSphere();
var model = {
  calculateFitness: sphere.calculateFitnessMaximize.bind(sphere),
  validateCords: sphere.validateCords.bind(sphere)
}
var parameters = new mrWolf.FlockParameters();
parameters.dimensions = 5;
parameters.cordsMin = [-10, -10, -10, -10, -10];
parameters.cordsMax = [10, 10, 10, 10, 10];
parameters.velocityMin = [-1, -1, -1, -1, -1];
parameters.velocityMax = [1, 1, 1, 1, 1];
parameters.inertiaChange = 0.05;

var flock = new mrWolf.Flock(parameters, model)
for(var i = 0; i < 1000; ++i){
  flock.search();
  console.log("Iteration "+i+" : "+flock.birds[0].socialExperience.fitness)
}
console.log("Best solution:")
console.log(flock.birds[0].socialExperience.fitness);
for(var i = 0; i < flock.birds[0].socialExperience.cords.length; ++i){
  console.log(flock.birds[0].socialExperience.cords[i]);
}

Aquí puedes encontrar el código en GitHub.

Una variante interesante de esta metaheurística es modificar el alcance de la experiencia social de cada individuo. En lugar de compartir una experiencia común para todos se comparte solo entre un grupo de individuos. Este grupo de individuos se puede fijar en la creación del mismo o por proximidad, calculando la distancia entre ellos y seleccionando la mejor experiencia solo entre aquellos cuya distancia sea menor de un valor fijado. Es importante que entre los grupos haya intercambio de información o no aportará nada tener varios grupos.