# Particle Swarm Optimization from Scratch with Python

Particle swarm optimization (PSO) is one of those rare tools that’s comically simple to code and implement while producing bizarrely good results. Developed in 1995 by Eberhart and Kennedy, PSO is a biologically inspired optimization routine designed to mimic birds flocking or fish schooling. I’ll occasionally use PSO for CFD based aerodynamic shape optimization, but more often than not, it’s for a machine learning project. PSO is not guaranteed to find the global minimum, but it does a solid job in challenging, high dimensional, non-convex, non-continuous environments. In this short introductory tutorial, I’ll demonstrate PSO in its absolute simplest form. At a later date, I’ll create another PSO tutorial featuring a more advanced implementation.

Below, are the only two equations that make up a bare bones PSO algorithm. As a heads up, “k” references the current iteration, therefore “k+1″ implies the next iteration.

Particle position:

$$x_{k+1}^i = x_{k}^i + v_{k+1}^i$$

Particle velocity:

$$v_{k+1}^i = w_k v_k^i + c_1 r_1 \left(p_k^i - x_k^i\right) + c_2 r_2 \left(p_k^g - x_k^i\right)$$

Where:

$$x_k^i$$ = particle position
$$v_k^i$$ = particle velocity
$$p_k^i$$ = best individual particle position
$$p_k^g$$ = best swarm position
$$w_k$$ = constant inertia weight
$$c_1, c_2$$ = cognitive and social parameters respectively
$$r_1, r_2$$ = random numbers between 0 and 1

From the particle velocity equation, two important groups emerge:

1. social term: $$c_2 r_2 \left(p_k^g - x_k^i\right)$$
2. cognitive term: $$c_1 r_1 \left(p_k^i - x_k^i\right)$$

Using these two simple equations, the basic flow structure of a PSO routine is as follows:

A) Initialize

1. Set constants: $$k_{max}, w_k, c_1, c_2$$
2. Randomly initialize particle positions.
3. Randomly initialize particle velocities.
4. Set k=1 (iteration counter).

B) Optimize

1. Evaluate cost function $$f_k^i$$ at each particle position $$x_k^i$$
2. If $$f_k^i \le f_{best}^i$$ then $$f_{best}^i = f_k^i$$ and $$p_k^i = x_k^i$$.
3. If $$f_k^i \le f_{best}^g$$ then $$f_{best}^g = f_k^i$$ and $$p_k^g = x_k^i$$.
4. If stopping condition is satisfied, go to C.
5. Update all particle velocities.
6. Update all particle positions.
7. Increment k.
8. Go to B(1).

C) Terminate

That’s it! It’s really is that simple. The main concept behind PSO, which is evident from the particle velocity equation above, is that there is a constant balance between three distinct forces pulling on each particle:

1. The particles previous velocity (inertia)
2. Distance from the individual particles’ best known position (cognitive force)
3. Distance from the swarms best known position (social force)

These three forces are then weighted by $$w_k$$, $$c_1$$, $$c_2$$ and randomly perturbed by $$r_1$$ and $$r_2$$. Thus depending on the weighting, either the swarms best location $$p_k^g$$ or the particles own best position $$p_k^i$$ will pull harder on the particle and dictate the overall direction. That’s assuming the particles initial velocity (or inertia) won’t cause the particle to wonder around. Often times, if you notice that the convergence is taking longer it’s because the particle inertia is weighted to heavily and should be reduced to speed up convergence. Keep in mind, that particle inertia is a double edged sword. If you're dealing with a noisy, highly multimodal cost function, too little inertia could result in the particles getting trapped at a local minimum, unable to climb out.

The implementation of a simple PSO routine in python is fairly straightforward. We are going to utilize some object oriented programming and create a swarm of particles using a particle class. These particles will be monitored by a main optimization class. Below is the entire code:

I hope this was helpful! If you want, you can download the entire code from my GitHub (here). Check back later for my post on a more advanced particle swarm optimization routine.