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] = Kinertia * v[i] + Ksocial * rand(0,1) * (cordsocial[i] – cord[i]) + Kown * rand(0,1) * (cordsown[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:
- Calculamos las velocidades en cada dimensión.
- Calculamos las nuevas coordenadas.
- Verificamos y corregimos las coordenadas.
- Calculamos la nueva inercia.
- Calculamos el fitness de las nuevas coordenadas.
- Si es necesario actualizamos la mejor solución propia.
- 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.
Construyendo a Chispas 
