PSO: Particle Swarm Optimization

Contents

PSO: Particle Swarm Optimization#

Particle Swarm Optimization was proposed in 1995 by Kennedy and Eberhart [15] based on the simulation of social behavior. The algorithm uses a swarm of particles to guide its search. Each particle has a velocity and is influenced by locally and globally best-found solutions. Many different implementations have been proposed in the past and, therefore, it is quite difficult to refer to THE correct implementation of PSO. However, the general concepts shall be explained in the following.

Given the following variables:

  • \(X_{d}^{(i)}\) d-th coordinate of i-th particle’s position

  • \(V_{d}^{(i)}\) d-th coordinate of i-th particle’s velocity

  • \(\omega\) Inertia weight

  • \(P_{d}^{(i)}\) d-th coordinate of i-th particle’s personal best

  • \(G_{d}^{(i)}\) d-th coordinate of the globally (sometimes also only locally) best solution found

  • \(c_1\) and \(c_2\) Two weight values to balance exploiting the particle’s best \(P_{d}^{(i)}\) and swarm’s best \(G_{d}^{(i)}\)

  • \(r_1\) and \(r_2\) Two random values being created for the velocity update

The velocity update is given by:

\begin{equation} V_{d}^{(i)} = \omega \, V_{d}^{(i)} \;+\; c_1 \, r_1 \, \left(P_{d}^{(i)} - X_{d}^{(i)}\right) \;+\; c_2 \, r_2 \, \left(G_{d}^{(i)} - X_{d}^{(i)}\right) \end{equation}

The corresponding position value is then updated by:

\begin{equation} X_{d}^{(i)} = X_{d}^{(i)} + V_{d}^{(i)} \end{equation}

The social behavior is incorporated by using the globally (or locally) best-found solution in the swarm for the velocity update. Besides the social behavior, the swarm’s cognitive behavior is determined by the particle’s personal best solution found. The cognitive and social components need to be well balanced to ensure that the algorithm performs well on a variety of optimization problems. Thus, some effort has been made to determine suitable values for \(c_1\) and \(c_2\). In pymoo both values are updated as proposed in [16]. Our implementation deviates in some implementation details (e.g. fuzzy state change) but follows the general principles proposed in the paper.

[1]:

from pymoo.algorithms.soo.nonconvex.pso import PSO
from pymoo.problems.single import Rastrigin
from pymoo.optimize import minimize

problem = Rastrigin()

algorithm = PSO()

res = minimize(problem,
               algorithm,
               seed=1,
               verbose=False)

print("Best solution found: \nX = %s\nF = %s" % (res.X, res.F))

Best solution found:
X = [4.45302738e-07 2.64409844e-08]
F = [3.94777544e-11]

API#

class pymoo.algorithms.soo.nonconvex.pso.PSO(self, pop_size=25, sampling=LHS(), w=0.9, c1=2.0, c2=2.0, adaptive=True, initial_velocity='random', max_velocity_rate=0.20, pertube_best=True, repair=NoRepair(), output=PSOFuzzyOutput(), **kwargs)[source]

Particle Swarm Optimization algorithm.

Parameters:

  • pop_size – The size of the swarm being used.

  • sampling – Sampling strategy.

  • adaptive – Whether w, c1, and c2 are changed dynamically over time.

  • w – Inertia weight for velocity update.

  • c1 – Cognitive impact (personal best) during velocity update.

  • c2 – Social impact (global best) during velocity update.

  • initial_velocity – How to initialize particle velocities (‘random’ or ‘zero’).

  • max_velocity_rate – Maximum velocity rate normalized by problem bounds.

  • pertube_best – Whether to mutate the global best solution.

  • repair – Repair strategy for handling constraints.

  • output – Output display strategy.

  • **kwargs – Additional algorithm parameters.

Contents