EN
JavaScript - async loop based scattered Particle Swarm Optimization (PSO) algorithm example
4
points
In this article, we're going to have a look at how to implement PSO (Particle Swarm Optimization) algorithm that shedules tasks in groups to indicated servers in JavaScript.
This article is combination of following articles:
- JavaScript - Particle Swarm Optimization (PSO) algorithm example
- JavaScript - how to make buffered async loop class with next iteration confirmation?
Main idea of presented below aproach is to send requests for computation to backend/server, waint until it will be finished and do not let to make more than set number (threadsCount parameter) of computations in same time. When some computation is completed implementation shedules next one untill all will be completed and next epoch occurs.
Practical implementation example
In below code, backend/server computations are simulated by fake $.ajax() method that waits random time and retunrs infomration about completed job. Fake methos can be replaced by real AJAX method, WebSocket, or other technology if needed.
// ONLINE-RUNNER:browser;
// copied from https://dirask.com/q/x1RzR1
//
function AsyncLoop(index, count, buffer, onIteration, onFinished) {
var self = this;
var STOPPED = 0; // loop is stopped
var STARTED = 1; // loop is started
var AVAILABLE = 2; // loop is started and ready to execute next iterations
var ITERATING = 3; // loop is progressing iterations
var FINISHING = 4; // loop is finishing
var i, c, b; // executed indexes, confirmed indexs, free buffer
var state = STOPPED;
function shedule(i) {
var called = false;
var cover = function(action) {
return function() {
if (called) {
throw new Error('Only once callback function can be executed in iteration.');
}
called = true;
c -= 1;
b += 1;
if (state == ITERATING) {
state = AVAILABLE;
}
action();
};
};
var callback = function() {
if (state == FINISHING) {
return;
}
onIteration(i, cover(resume), cover(finish));
};
setTimeout(callback, 0);
}
function resume() {
if (state == STARTED || state == AVAILABLE) {
if (i < count) {
state = ITERATING;
while(i < count && b > 0) {
i += 1;
b -= 1;
shedule(i - 1);
}
} else {
if (c == 0) {
state = FINISHING;
var callback = function() {
state = STOPPED;
onFinished(true);
};
setTimeout(callback, 0);
}
}
}
}
function finish() {
if (state == STARTED || state == AVAILABLE || state == ITERATING) {
state = FINISHING;
var callback = function() {
state = STOPPED;
onFinished(false);
};
setTimeout(callback, 0);
}
}
self.run = function() {
if (state == STOPPED) {
i = index;
c = count - index;
b = buffer;
if (onIteration.length > 1) {
// for onIteration(index, resume, finish)
state = STARTED;
resume();
} else {
// for onIteration(index)
state = STARTED;
try {
while(i < count) {
i += 1;
onIteration(i - 1);
}
} finally {
state = STOPPED;
if (onFinished) {
onFinished(true);
}
}
}
}
};
}
// copied from https://dirask.com/q/9pYXwD
// some unnecessary variables and methods have been removed
// some methods have been changed to publish
//
function PsoAlgorithm(config) {
var self = this;
var positionRanges = config.positionRanges; // range array
var particleSpeed = config.particleSpeed || 0.1; // from 0.0 to 1.0
// removed unnecessary variables for this example...
self.createSolution = function() {
var buffer = [ ];
for (var i = 0; i < positionRanges.length; ++i) {
buffer.push(Math.random());
}
var result = {
buffer: buffer,
position: null,
error: Number.POSITIVE_INFINITY
};
return result;
};
self.correctPosition = function(position) {
if (position < 0.0) {
return 0.0;
}
if (position > 1.0) {
return 1.0;
}
return position;
};
self.denormalizePosition = function(position) {
var result = [ ];
for (var i = 0; i < positionRanges.length; ++i) {
var range = positionRanges[i];
var scope = range.maximum - range.minimum;
result.push(position[i] * scope + range.minimum);
}
return result;
};
self.createParticle = function() {
var actualBuffer = [ ];
var actualVelocity = [ ];
for (var i = 0; i < positionRanges.length; ++i) {
var position = Math.random();
var velocity = particleSpeed * Math.random();
actualVelocity.push(velocity);
actualBuffer.push(position);
}
var particle = {
bestSolution: self.createSolution(),
actualSolution: {
velocity: actualVelocity, // normalized particle velocity
buffer: actualBuffer, // normalized particle position
position: null,
error: Number.POSITIVE_INFINITY
}
};
return particle;
};
self.createParticles = function(particlesCount) {
var result = [ ];
for (var i = 0; i < particlesCount; ++i) {
result.push(self.createParticle());
}
return result;
};
// removed unnecessary methods for this example...
}
// extended PsoAlgorithm class
//
function AsyncPsoAlgorithm(config) {
var self = this;
var positionRanges = config.positionRanges; // range array
var calculateError = config.calculateError; // goal function
if (positionRanges == null) {
throw new Error('Input ranges array has not been defined.');
}
if (calculateError == null) {
throw new Error('Calculate error function has not been defined.');
}
var master = new PsoAlgorithm(config);
// 0.729 and 1.49445 come from literatire
var particleSpeed = config.particleSpeed || 0.1; // should be in range from 0.0 to 1.0
var particleInertia = config.particleInertia || 0.729;
var globalAcceleration = config.globalAcceleration || 1.49445;
var localAcceleration = config.localAcceleration || 1.49445;
var threadsCount = config.threadsCount || 1;
var onIterationStarted = config.onIterationStarted;
var onParticleComputed = config.onParticleComputed;
var onIterationFinished = config.onIterationFinished;
self.computeParticle = function(particle, globalBuffer, onFinished, onCanceled) {
var bestSolution = particle.bestSolution;
var bestBuffer = bestSolution.buffer;
var actualSolution = particle.actualSolution;
var actualBuffer = actualSolution.buffer;
var actualVelocity = actualSolution.velocity;
for (var i = 0; i < actualBuffer.length; ++i) {
var globalDifference = globalBuffer[i] - actualBuffer[i];
var localDifference = bestBuffer[i] - actualBuffer[i];
var globalInfluance = globalAcceleration * globalDifference * Math.random();
var localInfluance = localAcceleration * localDifference * Math.random();
actualVelocity[i] = particleInertia * actualVelocity[i]
+ globalInfluance + localInfluance;
actualBuffer[i] = master.correctPosition(actualBuffer[i] + actualVelocity[i]);
}
var computedPosition = master.denormalizePosition(actualBuffer);
function accept(computedError) {
actualSolution.error = computedError;
actualSolution.position = computedPosition;
if (computedError < bestSolution.error) {
bestSolution = particle.bestSolution = {
position: computedPosition,
buffer: actualBuffer.slice(),
error: computedError
};
}
onFinished(bestSolution);
}
function cancel() {
if(onCanceled) {
onCanceled();
}
}
calculateError(computedPosition, accept, cancel);
};
self.computeEpoch = function(particles, globalBuffer, onFinished, onCanceled) {
var epochSolution = {
error: Number.POSITIVE_INFINITY
};
function onIterationProxy(i, resume, finish) {
var particle = particles[i];
function onFinishedProxy(localSolution) {
if (localSolution.error < epochSolution.error) {
epochSolution = localSolution;
}
if (onParticleComputed) {
onParticleComputed(i, particle.actualSolution, localSolution);
}
resume();
}
function onCanceledProxy() {
finish();
if(onCanceled) {
onCanceled();
}
}
self.computeParticle(particle, globalBuffer, onFinishedProxy, onCanceledProxy);
}
function onFinishedProxy() {
onFinished(epochSolution);
}
var loop = new AsyncLoop(0, particles.length, threadsCount, onIterationProxy, onFinishedProxy);
loop.run();
};
self.computeEpoches$1 = function(toleratedError, epochesLimit, particles, onFinished, onCanceled) {
if (particles.length == 0) {
throw new Error("Particles have not been defined.");
}
var globalSolution = master.createSolution();
function onIterationProxy(i, resume, finish) {
if (onIterationStarted) {
onIterationStarted(i);
}
function onFinishedProxy(epochSolution) {
if (epochSolution.error < globalSolution.error) {
globalSolution = epochSolution;
}
if (onIterationFinished) {
onIterationFinished(i, globalSolution);
}
if (globalSolution.error < toleratedError) {
finish();
} else {
resume();
}
}
function onCanceledProxy() {
finish();
if(onCanceled) {
onCanceled();
}
}
self.computeEpoch(particles, globalSolution.buffer, onFinishedProxy, onCanceledProxy);
}
function onFinishedProxy() {
onFinished(globalSolution);
}
var loop = new AsyncLoop(0, epochesLimit, 1, onIterationProxy, onFinishedProxy);
loop.run();
};
self.computeEpoches$2 = function(toleratedError, epochesLimit, particlesCount, onFinished, onCanceled) {
var particles = master.createParticles(particlesCount);
return self.computeEpoches$1(toleratedError, epochesLimit, particles, onFinished, onCanceled);
};
}
// Helper methods:
// this function simulates request to server
window.$ = {
ajax: function(config) {
var url = config.url;
var onsuccess = config.onsuccess;
var onerror = config.onerror;
// y(x1, x2) = x1^2 + x2^2 computation
if (url == '/cluster/make-simulation') {
var data = config.data;
function callback() {
var x1 = data.x1;
var x2 = data.x2;
// this function can be replaced with any simulation
var y = x1 * x1 + x2 * x2; // y(x1, x2) = x1^2 + x2^2
var response = {
success: true,
result: y
};
onsuccess(response);
}
var timeout = Math.floor(100 * Math.random());
setTimeout(callback, timeout); // random time of computation only for exmaple
} else {
onerror('Incorrect url.');
}
}
};
// Usage example:
var algorithm = new AsyncPsoAlgorithm({
threadsCount: 5, // not like threads in cpp, rather like sheduled computations in same time
positionRanges: [
{
// x1 search range
minimum: -4, maximum: +4
},
{
// x2 search range
minimum: -4, maximum: +4
}
],
particleSpeed: 0.1,
particleInertia: 0.729,
globalAcceleration: 1.49445,
localAcceleration: 1.49445,
calculateError: function(position, accept, cancel) {
$.ajax({
url: '/cluster/make-simulation',
data: {
x1: position[0],
x2: position[1]
},
onsuccess: function(response) {
if (response.success) {
// we are looking for root points in the presented example so computed error will be:
var computedError = Math.abs(0 - response.result);
accept(computedError);
} else {
cancel();
}
},
onerror: function(message) {
cancel();
}
});
},
onIterationStarted: function(epochIndex) {
// nothing here...
},
onParticleComputed: function(epochIndex, actualSolution, localSolution) {
// nothing here...
},
onIterationFinished: function(epochIndex, globalSolution) {
var error = globalSolution.error;
var position = globalSolution.position;
console.log(epochIndex + '\t' + error + '\t[' + position + ']');
}
});
var toleratedError = 0.01; // samller or equal computation error stops algorithm
var epochesLimit = 100; // maximal number of executed iterations
var particlesCount = 10;
console.log('[epoch]\t[error]\t\t\t[position]\n');
function onFinished(solution) {
console.log('-------------------------------');
console.log('Optimal solution:');
console.log(' error: ' + solution.error);
console.log(' position: ' + solution.position);
}
algorithm.computeEpoches$2(toleratedError, epochesLimit, particlesCount, onFinished);