Particle Swarm Optimization (PSO)

class pagmo::pso

Particle Swarm Optimization.

../../../_images/pso.png

Particle swarm optimization (PSO) is a population based algorithm inspired by the foraging behaviour of swarms. In PSO each point has memory of the position where it achieved the best performance \(\mathbf x^l_i\) (local memory) and of the best decision vector \( \mathbf x^g \) in a certain neighbourhood, and uses this information to update its position using the equations (constriction coefficient):

\[\begin{split} \begin{array}{l} \mathbf v_{i+1} = \omega \left( \mathbf v_i + \eta_1 \mathbf r_1 \cdot \left( \mathbf x_i - \mathbf x^l_i \right) + \eta_2 \mathbf r_2 \cdot \left( \mathbf x_i - \mathbf x^g \right) \right) \\ \mathbf x_{i+1} = \mathbf x_i + \mathbf v_i \end{array} \end{split}\]
or (inertia weight):
\[\begin{split} \begin{array}{l} \mathbf v_{i+1} = \omega \mathbf v_i + \eta_1 \mathbf r_1 \cdot \left( \mathbf x_i - \mathbf x^l_i \right) + \eta_2 \mathbf r_2 \cdot \left( \mathbf x_i - \mathbf x^g \right) \\ \mathbf x_{i+1} = \mathbf x_i + \mathbf v_i \end{array} \end{split}\]

The user can specify the values for \(\omega, \eta_1, \eta_2\) and the magnitude of the maximum velocity allowed (normalized with respect ot the bounds). The user can specify one of five variants where the velocity update rule differs on the definition of the random vectors \(r_1\) and \(r_2\):

  • Variant 1: \(\mathbf r_1 = [r_{11}, r_{12}, ..., r_{1n}]\), \(\mathbf r_2 = [r_{21}, r_{21}, ..., r_{2n}]\) … (inertia weight)

  • Variant 2: \(\mathbf r_1 = [r_{11}, r_{12}, ..., r_{1n}]\), \(\mathbf r_2 = [r_{11}, r_{11}, ..., r_{1n}]\) … (inertia weight)

  • Variant 3: \(\mathbf r_1 = [r_1, r_1, ..., r_1]\), \(\mathbf r_2 = [r_2, r_2, ..., r_2]\) … (inertia weight)

  • Variant 4: \(\mathbf r_1 = [r_1, r_1, ..., r_1]\), \(\mathbf r_2 = [r_1, r_1, ..., r_1]\) … (inertia weight)

  • Variant 5: \(\mathbf r_1 = [r_{11}, r_{12}, ..., r_{1n}]\), \(\mathbf r_2 = [r_{21}, r_{21}, ..., r_{2n}]\) … (constriction coefficient)

  • Variant 6: Fully Informed Particle Swarm (FIPS)

Note

The default variant in PaGMO is n. 5 corresponding to the canonical PSO and thus using the constriction coefficient velocity update formula

Warning

The algorithm is not suitable for multi-objective problems, nor for constrained or stochastic optimization

See also

http://www.particleswarm.info/ for a repository of information related to PSO

Public Types

typedef std::tuple<unsigned, unsigned long long, double, double, double, double> log_line_type

Single entry of the log (Gen, Fevals, gbest, Mean Vel., Mean lbest, Avg. Dist.)

typedef std::vector<log_line_type> log_type

The log.

Public Functions

pso(unsigned gen = 1u, double omega = 0.7298, double eta1 = 2.05, double eta2 = 2.05, double max_vel = 0.5, unsigned variant = 5u, unsigned neighb_type = 2u, unsigned neighb_param = 4u, bool memory = false, unsigned seed = pagmo::random_device::next())

Constructor.

Allows to specify in detail all the parameters of the algorithm.

Parameters
  • gen – number of generations

  • omega – particles’ inertia weight, or alternatively, the constriction coefficient (definition depends on the variant used)

  • eta1 – magnitude of the force, applied to the particle’s velocity, in the direction of its previous best position

  • eta2 – magnitude of the force, applied to the particle’s velocity, in the direction of the best position in its neighborhood

  • max_vel – maximum allowed particle velocity (as a fraction of the box bounds)

  • variant – algorithm variant to use (one of 1 .. 6)

  • neighb_type – swarm topology to use (one of 1 .. 4) [gbest, lbest, Von Neumann, adaptive random]

  • neighb_param – the neighbourhood parameter. If the lbest topology is selected (neighb_type=2), it represents each particle’s indegree (also outdegree) in the swarm topology. Particles have neighbours up to a radius of k = neighb_param / 2 in the ring. If the Randomly-varying neighbourhood topology is selected (neighb_type=4), it represents each particle’s maximum outdegree in the swarm topology. The minimum outdegree is 1 (the particle always connects back to itself). If neighb_type is 1 or 3 this parameter is ignored.

  • memory – when true the particle velocities are not reset between successive calls to evolve

  • seed – seed used by the internal random number generator (default is random)

Throws

std::invalid_argument – if omega is not in the [0,1] interval, eta1, eta2 are not in the [0,4] interval, vcoeff is not in ]0,1], variant is not one of 1 .. 6, neighb_type is not one of 1 .. 4, neighb_param is zero

population evolve(population) const

Algorithm evolve method.

Parameters

pop – population to be evolved

Throws

std::invalid_argument – if the problem is multi-objective or constrained

Returns

evolved population

inline void set_verbosity(unsigned level)

Sets the algorithm verbosity.

Sets the verbosity level of the screen output and of the log returned by get_log(). level can be:

  • 0u: no verbosity

  • >=1u: will print and log one line each level generations

Example (verbosity 50u):

Gen:        Fevals:         gbest:     Mean Vel.:    Mean lbest:    Avg. Dist.:
   1             40        2.01917       0.298551        1855.03       0.394038
   51           1040     0.00436298      0.0407766         1.0704         0.1288
  101           2040    0.000228898      0.0110884       0.282699      0.0488969
  151           3040    5.53426e-05     0.00231688       0.106807      0.0167147
  201           4040    3.88181e-06    0.000972132      0.0315856     0.00988859
  251           5040    1.25676e-06    0.000330553     0.00146805     0.00397989
  301           6040    3.76784e-08    0.000118192    0.000738972      0.0018789
  351           7040    2.35193e-09    5.39387e-05    0.000532189     0.00253805
  401           8040    3.24364e-10     2.2936e-05    9.02879e-06    0.000178279
  451           9040    2.31237e-10    5.01558e-06    8.12575e-07    9.77163e-05

Gen is the generation number, Fevals the number of fitness evaluation made, gbest the global best, Mean Vel. the average mean normalized velocity of particles, Mean lbest the average of the local best fitness of particles and Avg. Dist. the average normalized distance among particles. Normalization is made with respect to the problem bounds.

Parameters

level – verbosity level

inline unsigned get_verbosity() const

Gets the verbosity level.

Returns

the verbosity level

void set_seed(unsigned)

Sets the seed.

Parameters

seed – the seed controlling the algorithm stochastic behaviour

inline unsigned get_seed() const

Gets the seed.

Returns

the seed controlling the algorithm stochastic behaviour

inline std::string get_name() const

Algorithm name.

One of the optional methods of any user-defined algorithm (UDA).

Returns

a string containing the algorithm name

std::string get_extra_info() const

Extra info.

One of the optional methods of any user-defined algorithm (UDA).

Returns

a string containing extra info on the algorithm

inline const log_type &get_log() const

Get log.

A log containing relevant quantities monitoring the last call to evolve. Each element of the returned std::vector is a pso::log_line_type containing: Gen, Fevals, gbest, Mean Vel., Mean lbest, Avg. Dist. as described in pso::set_verbosity

Returns

an std::vector of pso::log_line_type containing the logged values