Introduction
Particle Swarm Optimization(PSO) is a swarm intelligence based meta-heuristic, used for finding optimal solutions in large search-spaces; such as the infamous Genetic Algorithm. PSO outperforms most optimization algorithms in terms of speed and convergence in the continuous-space domain of numbers (Real Numbers); making it better suited for applications such as training neural networks and solving equations.
PSO has a higher resilience toward idling in local-optimum positions. The founders of PSO (James Kennedy and Russell Eberhart) originally intended to digitally simulate the flocking behavior of birds - later realizing its practical uses in optimization.
w - Velocity decay constant
Pvel - The Particle Velocity vector
R1, R2 - Random numbers 0 to 1
C1, C2 - Maximum Jump(interpolation) Constants
Pbest - Particle-Best-Position recorded
Ppos - Particles current position
Sbest - Global-Best-Position recorded
(Pbest - Ppos) Distance and direction toward the Particles-Best-Position recorded. C1 determines the maximum jump constant; where a value of 2 would indicate twice the vector length. R1 is a random number from 0 to 1 - determining how far it will jump along the vector length. C1 defaults to 1.5 to 2 for search space exploration reasons.
(Sbest - Ppos) Distance and direction toward the Global-Best-Position, C2 determines the maximum jump constant, C2 is the same as C1 in most cases. R2 is a random number from 0 to 1 - determining how far it will jump along the vector length. R2 is not the same as R1.
w*Pvel keep particles heading in a direction, improving resilience to local optimums. w is the inertia factor; that dictates how easily particles are influenced by position updates. w is usually a number in the range of 0 to 1, where 1 is no decay; the default is 0.72.
PSO has a higher resilience toward idling in local-optimum positions. The founders of PSO (James Kennedy and Russell Eberhart) originally intended to digitally simulate the flocking behavior of birds - later realizing its practical uses in optimization.
Mechanics
Particles are placed randomly into the search space and evaluated on performance via the Evaluation Function. Particle positions are updated according to the best position the particle has recorded, and toward the best position recorded by the swarm as a whole - known respectively as Local-Best-Position and Global-Best-Position.The Algorithm Flow
Prerequisite Vocabulary
A particles position-vector represents the parameters of the Evaluation Function being optimized. The velocity-vector represents the change of position on each update. The search-space represents the minimum and maximum bounds of the parameters.Initialize Particle Population
A population of particles known as the Swarm are created and distributed randomly within the search-space, population size ranges from 20 to 150 particles depending on the search-space size and runtime resources required for the evaluation function to execute. The Swarm serves as a container and controller for keeping track of best position found and managing the updates and data-structures of the algorithm.Evaluate Particles
The Evaluation Function, also known as the Objective Function is the function who's parameters we wish to optimize. Particle positions represent the parameters of the function, and the return value is what we wish to maximize/minimize.Update Particles Position
Particles update their velocity toward the Global-Best-Position and Particles-Best-Position by random jumping factors; in turn aiding in the exploration of the search-space, and idling in local optimum positions. Here's the equation:w - Velocity decay constant
Pvel - The Particle Velocity vector
R1, R2 - Random numbers 0 to 1
C1, C2 - Maximum Jump(interpolation) Constants
Pbest - Particle-Best-Position recorded
Ppos - Particles current position
Sbest - Global-Best-Position recorded
(Pbest - Ppos) Distance and direction toward the Particles-Best-Position recorded. C1 determines the maximum jump constant; where a value of 2 would indicate twice the vector length. R1 is a random number from 0 to 1 - determining how far it will jump along the vector length. C1 defaults to 1.5 to 2 for search space exploration reasons.
(Sbest - Ppos) Distance and direction toward the Global-Best-Position, C2 determines the maximum jump constant, C2 is the same as C1 in most cases. R2 is a random number from 0 to 1 - determining how far it will jump along the vector length. R2 is not the same as R1.
w*Pvel keep particles heading in a direction, improving resilience to local optimums. w is the inertia factor; that dictates how easily particles are influenced by position updates. w is usually a number in the range of 0 to 1, where 1 is no decay; the default is 0.72.
PSO Equation for coders
P.vel[i] = w*P.vel[i] + rand()*c1*(P.best[i] - P.pos[i]) + rand()*c2*(S.best[i] - P.pos[i])
P.pos[i] = P.pos[i] + P.vel[i]
P.pos[i] = P.pos[i] + P.vel[i]
Done - When to stop
When the Global-Best-Position reaches a satisfactory Fitness Score - or when the rate of change becomes permissible.Quick Code!
class Particle { constructor(searchSpaceSize, searchSpaceMaximum) { // position and velocity vectors sized according to search space this.position = Array(50).fill(searchSpaceSize); this.velocity = Array(50).fill(searchSpaceSize); // Search Space bounds this.searchSpaceMaximum = searchSpaceMaximum; //memory of the best positition found so far this.bestPosition = Array(50).fill(0); //score/fitness value this.score = 0; } // can be an array of bounds for each element placeRandomlyInSearchSpace() { for (let i = 0; i < this.position.length; i++) { this.position[i] = Math.random() * this.searchSpaceMaximum; } } updatePosition(swarmBestPosition) { // Decay and distance constants const w = 0.72; const C1 = 2; const C2 = 2; // for the random numbers let R1 = 0; let R2 = 0; for (let i = 0; i < this.position.length; i++) { //Generate Random Numbers R1 = Math.random(); R2 = Math.random(); // Update Velocity this.velocity[i] = w * this.velocity[i] + R1 * C1 * (this.bestPosition[i] - this.position[i]) + R2 * C2 * (swarmBestPosition[i] - this.position[i]); // Update Position this.position[i] = this.position + this.velocity[i]; } } evaluatePosition(evaluationFunction) { // Evaluate the current position and get score this.score = evaluationFunction(this.position); // Check if it's the best position found so far by particle if (this.score > this.bestScore) { this.bestScore = this.score; this.bestPosition = [...this.position]; } return this.score; } } class Swarm { constructor( evalFunc, numberOfParticles, searchSpaceSize, searchSpaceMaximum ) { // Evaluation Function as a callback this.evaluationFunction = evalFunc; this.particles = Array(numberOfParticles); // Best position found in history of object this.bestPosition = []; this.bestScore = 0; // Some params defining the search space this.searchSpaceSize = searchSpaceSize; this.searchSpaceMaximum = searchSpaceMaximum; } // Creates Particles and passes search space info to particles initializeParticles() { for (let i = 0; i < this.particles.length; i++) { this.particles[i] = new Particle( this.searchSpaceSize, this.searchSpaceMaximum ); this.particles[i].placeRandomlyInSearchSpace(50); } } run() { this.initializeParticles(); let running = true; while (running) { for (let i = 0; i < this.particles.length; i++) { this.particles[i].updatePosition(this.bestPosition); score = this.particles[i].evaluatePosition(this.evaluationFunction); // Check if Particle Score better than ever found // If so save if (this.particles[i].score > this.bestScore) { this.bestPosition = this.particles[i].position; this.bestScore = this.particles[i].score; } } } } }