Top community members
All Wiki Articles Create Wiki Article

Welcome to Dirask IT community! ❤ 💻
We are community of people that helps each other.

If you think you have some skills to help others

help someone and become a part of our community - List Q & A

JavaScript - Particle Swarm Optimization (PSO) algorithm example

0 contributions
8 points

Using JavaScript it is possible to write own PSO algorithm implementation in following way.

1. PSO example

// ONLINE-RUNNER:browser;

function PsoAlgorithm(config) {

    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 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 onIterationStarted = config.onIterationStarted;
    var onParticleComputed = config.onParticleComputed;
    var onIterationFinished = config.onIterationFinished;

    function createSolution() {
        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;
    }

    function correctPosition(position) {
        if (position < 0.0) {
            return 0.0;
        }

        if (position > 1.0) {
            return 1.0;
        }

        return position;
    }

    function denormalizePosition(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;
    }

    this.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: createSolution(),
            actualSolution: {
                velocity: actualVelocity, // normalized particle velocity
                buffer: actualBuffer, // normalized particle position
                position: null,
                error: Number.POSITIVE_INFINITY
            }
        };

        return particle;
    };

    this.createParticles = function(particlesCount) {
        var result = [ ];

        for (var i = 0; i < particlesCount; ++i) {
            result.push(this.createParticle());
        }

        return result;
    };

    this.computeParticle = function(particle, bestGlobalBuffer) {
        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] = correctPosition(actualBuffer[i] + actualVelocity[i]);
        }

        var computedPosition = denormalizePosition(actualBuffer);
        var computedError = calculateError(computedPosition);

        actualSolution.error = computedError;
        actualSolution.position = computedPosition;

        if (computedError < bestSolution.error) {
            bestSolution = particle.bestSolution = {
                position: computedPosition,
                buffer: actualBuffer.slice(),
                error: computedError
            };
        }

        return bestSolution;
    };

    this.computeEpoch = function(particles, bestGlobalBuffer) {
        var bestEpochSolution = {
            error: Number.POSITIVE_INFINITY
        };

        for (var i = 0; i < particles.length; ++i) {
            var particle = particles[i];

            var bestLocalSolution = this.computeParticle(particle, bestGlobalBuffer);

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

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

        return bestEpochSolution;
    };

    this.computeEpoches$1 = function(toleratedError, epochesLimit, particles) {
        if (particles.length == 0) {
            throw new Error("Particles have not been defined.");
        }

        var bestGlobalSolution = createSolution();

        for (var i = 0; i < epochesLimit; ++i) {
            if (onIterationStarted) {
                onIterationStarted(i);
            }

            var bestEpochSolution = this.computeEpoch(particles, bestGlobalSolution.buffer);

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

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

            if (bestGlobalSolution.error < toleratedError) {
                break;
            }
        }

        return bestGlobalSolution;
    };

    this.computeEpoches$2 = function(toleratedError, epochesLimit, particlesCount) {
        var particles = this.createParticles(particlesCount);

        return this.computeEpoches$1(toleratedError, epochesLimit, particles);
    };
}

// Usage example:

var algorithm = new PsoAlgorithm({
    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) {
        var x1 = position[0];
        var x2 = position[1];

        // we are working with this function
        var y = x1 * x1 + x2 * x2; // y(x1, x2) = x1^2 + x2^2

        // we are looking for global minimum, so function value is treat as error
        // actual solution is better if actual value is smaller than best one known before
        // (negative values are accepted too)
        return y;
    },
    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');

var solution = algorithm.computeEpoches$2(toleratedError, epochesLimit, particlesCount);

console.log('-------------------------------');
console.log('Solution:');
console.log('  error: ' + solution.error);
console.log('  position: ' + solution.position);

References

  1. Particle swarm optimization - Wikipedia
0 contributions

Checkout latest Findings & News:

Checkout latest questions:

Checkout latest wiki articles:

Hey 👋
Would you like to know what we do?
  • Dirask is IT community, where we share coding knowledge and help each other to solve coding problems.
  • We welcome everyone,
    no matter what the experience,
    no matter how basic the question is,
    this community will help you.
Read more