[Edit]
JavaScript - async loop based scattered Particle Swarm Optimization (PSO) algorithm example

1 contributors
2 contributions
0 discussions
4 points
Created by:
Root-ssh
178180
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:
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

Edit
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.
xxxxxxxxxx
 
// 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);
Auto running
Show discussions ...
JavaScript - async loop based scattered Particle Swarm Optimization (PSO) algorithm example

Practical implementation example

Native Advertising

🚀

Dirask - we help you to

solve coding problems.

Ask question.

❤️💻 🙂
