Languages
[Edit]
EN

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

1 points
Created by:
Root-ssh
68600

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:

  1. JavaScript - Particle Swarm Optimization (PSO) algorithm example
  2. 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, 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.

1. Practical implementation example

In below code, backend 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 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 self = this;

    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);

    var particleSpeed = config.particleSpeed || 0.1; // from 0.0 to 1.0
    var particleInertia = config.particleInertia || 0.729; // 0.729 from literatire
    var globalAcceleration = config.globalAcceleration || 1.49445; // 1.49445 from literatire
    var localAcceleration = config.localAcceleration || 1.49445; // 1.49445 from literatire

    var threadsCount = config.threadsCount || 1;
    
    var onIterationStarted = config.onIterationStarted;
    var onParticleComputed = config.onParticleComputed;
    var onIterationFinished = config.onIterationFinished;
  
    self.computeParticle = function(particle, bestGlobalBuffer, onFinished, onCanceled) {
        var bestSolution = particle.bestSolution;
        var actualSolution = particle.actualSolution;

        var bestLocalBuffer = bestSolution.buffer;

        var actualVelocity = actualSolution.velocity;
        var actualBuffer = actualSolution.buffer;

        for (var i = 0; i < actualBuffer.length; ++i) {
            var globalDifference = bestGlobalBuffer[i] - actualBuffer[i];
            var globalInfluance = globalAcceleration * globalDifference * Math.random();

            var localDifference = bestLocalBuffer[i] - actualBuffer[i];
            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, bestGlobalBuffer, onFinished, onCanceled) {
        var bestEpochSolution = {
            error: Number.POSITIVE_INFINITY
        };

        function onIterationProxy(i, resume, finish) {
          	var particle = particles[i];

          	function onFinishedProxy(bestLocalSolution) {
                if (bestLocalSolution.error < bestEpochSolution.error) {
                    bestEpochSolution = bestLocalSolution;
                }

                if (onParticleComputed) {
                    onParticleComputed(i, particle.actualSolution, bestLocalSolution);
                }

                resume();
            }

            function onCanceledProxy() {
                finish();

                if(onCanceled) {
                   onCanceled();
                }
            }
          
            self.computeParticle(particle, bestGlobalBuffer, onFinishedProxy, onCanceledProxy);
        }
      
      	function onFinishedProxy() {
        	onFinished(bestEpochSolution);
        }

        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 bestGlobalSolution = master.createSolution();

      	function onIterationProxy(i, resume, finish) {
          	if (onIterationStarted) {
                onIterationStarted(i);
            }

          	function onFinishedProxy(bestEpochSolution) {
            	if (bestEpochSolution.error < bestGlobalSolution.error) {
                    bestGlobalSolution = bestEpochSolution;
                }

                if (onIterationFinished) {
                    onIterationFinished(i, bestGlobalSolution);
                }

                if (bestGlobalSolution.error < toleratedError) {
                    finish();
                } else {
                    resume();
            	}
            }

            function onCanceledProxy() {
                finish();

                if(onCanceled) {
                   onCanceled();
                }
            }
          
            self.computeEpoch(particles, bestGlobalSolution.buffer, onFinishedProxy, onCanceledProxy);
        }
      
      	function onFinishedProxy() {
            onFinished(bestGlobalSolution);
        }

        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()); // random time of computation only for exmaple

            setTimeout(callback, timeout);
        } else {
        	onerror('Incorrect url.');
        }
    }
};

// Usage example:

var algorithm = new AsyncPsoAlgorithm({
    threadsCount: 5, // this is not like threads in cpp, rather number of 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 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, bestLocalSolution) {
        // nothing here...
    },
    onIterationFinished: function(epochIndex, bestGlobalSolution) {
        var error = bestGlobalSolution.error;
        var position = bestGlobalSolution.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('Solution:');
    console.log('  error: ' + solution.error);
    console.log('  position: ' + solution.position);
}

algorithm.computeEpoches$2(toleratedError, epochesLimit, particlesCount, onFinished);

 

Native Advertising
50 000 ad impressions - 449$
🚀
Get your tech brand or product in front of software developers.
For more information contact us:
Red dot
Dirask - friendly IT community for everyone.

❤️💻 🙂

Join