Particle swarm optimization (analysis)

Analysis title

Particle swarm optimization

Provider

Institute of Systems Biology

Multi-objective particle swarm optimization (MOPSO)

The particle swarm optimization (PSO) algorithm, initially proposed by Kennedy and Eberhart¹, is a direct search algorithm based on the simulation of the social behavior of birds within a flock. The swarm is typically modeled by particles in the multidimensional space that have a position and a velocity. These particles fly through hyperspace and have two essential reasoning capabilities: their memory of their own best position and knowledge of the global or their neighborhood's best.

Let x_i(t) denote the position of particle p_i at time step t. The position of p_i is then changed by adding a velocity v_i(t) to its current position, i.e.

xi(t) = xi(t − 1) + vi(t).

Let gbest is the position of the best particle from the entire swarm and pbest is the position of the neighborhood best that the particle obtained by communicating with a subset of the swarm. In this case, velocity equation is given by

vi(t) = W·vi(t − 1) + C1r1(xpbest − xi(t)) + C2r2(xgbest − xi(t)),

where W is the inertia weight, C₁ and C₂ are the learning factors (usually defined as constants), and r₁, r₂ ∈ [0,1] are random values.

Here we used a multiple-objective particle swarm optimizers based on the paper of Sierra and Coello². This optimizer allows to take into account parametric constraints and uses a crowding factor for the leaders selection as well as the following mutation operators: an uniform mutation operator, where the variability range allowed for each decision variable is constant over generations, and a non-uniform mutation operator, where such range decreases over time. These operators modify the values of the particle decision variables with a certain probability.

References

1. J Kennedy, RC Eberhart. "Particle Swarm Optimization". Proceedings of the 1995 IEEE International Conference on Neural Networks, Piscataway, New Jersey, IEEE Service Center, 1995, 1942-1948.
2. MR Sierra and CA Coello Coello "Improving PSO-Based Multi-objective Optimization Using Crowding, Mutation and e-Dominance." Evolutionary Multi-Criterion Optimization, 3410/2005: 505-519, Springer Berlin/Heidelberg.