Particle Swarm Optimization

Manopt.particle_swarmFunction
patricle_swarm(M, F)

perform the particle swarm optimization algorithm (PSO), starting with the initial particle positions $x_0$[Borckmans2010]. The aim of PSO is to find the particle position $g$ on the Manifold M that solves

\[\min_{x ∈\mathcal{M}} F(x).\]

To this end, a swarm of particles is moved around the Manifold M in the following manner. For every particle $k$ we compute the new particle velocities $v_k^{(i)}$ in every step $i$ of the algorithm by

\[v_k^{(i)} = ω \, \operatorname{T}_{x_k^{(i)}\gets x_k^{(i-1)}}v_k^{(i-1)} + c \, r_1 \operatorname{retr}_{x_k^{(i)}}^{-1}(p_k^{(i)}) + s \, r_2 \operatorname{retr}_{x_k^{(i)}}^{-1}(g),\]

where $x_k^{(i)}$ is the current particle position, $ω$ denotes the inertia, $c$ and $s$ are a cognitive and a social weight, respectively, $r_j$, $j=1,2$ are random factors which are computed new for each particle and step, $\operatorname{retr}^{-1}$ denotes an inverse retraction on the Manifold M, and $\operatorname{T}$ is a vector transport.

Then the position of the particle is updated as

\[x_k^{(i+1)} = \operatorname{retr}_{x_k^{(i)}}(v_k^{(i)}),\]

where $\operatorname{retr}$ denotes a retraction on the Manifold M. At the end of each step for every particle, we set

\[p_k^{(i+1)} = \begin{cases} x_k^{(i+1)}, & \text{if } F(x_k^{(i+1)})<F(p_{k}^{(i)}),\\ p_{k}^{(i)}, & \text{else,} \end{cases}\]

and

\[g_k^{(i+1)} =\begin{cases} p_k^{(i+1)}, & \text{if } F(p_k^{(i+1)})<F(g_{k}^{(i)}),\\ g_{k}^{(i)}, & \text{else,} \end{cases}\]

i.e. $p_k^{(i)}$ is the best known position for the particle $k$ and $g^{(i)}$ is the global best known position ever visited up to step $i$.

Input

  • M – a manifold $\mathcal M$
  • F – a cost function $F:\mathcal M→ℝ$ to minimize

Optional

  • n - (100) number of random initial positions of x0
  • x0 – the initial positions of each particle in the swarm $x_k^{(0)} ∈ \mathcal M$ for $k = 1, \dots, n$, per default these are n random_points
  • velocity – a set of tangent vectors (of type AbstractVector{T}) representing the velocities of the particles, per default a random_tangent per inital position
  • inertia – (0.65) the inertia of the patricles
  • social_weight – (1.4) a social weight factor
  • cognitive_weight – (1.4) a cognitive weight factor
  • retraction_method – (ExponentialRetraction()) a retraction(M,x,ξ) to use.
  • inverse_retraction_method - (LogarithmicInverseRetraction()) an inverse_retraction(M,x,y) to use.
  • vector_transport_mthod - (ParallelTransport()) a vector transport method to use.
  • stopping_criterion – (StopWhenAny(StopAfterIteration(500), StopWhenChangeLess(10^{-4}))) a functor inheriting from StoppingCriterion indicating when to stop.
  • return_options – (false) – if activated, the extended result, i.e. the complete Options are returned. This can be used to access recorded values. If set to false (default) just the optimal value x_opt if returned

... and the ones that are passed to decorate_options for decorators.

Output

  • g – the resulting point of PSO

OR

  • options - the options returned by the solver (see return_options)
source
Manopt.particle_swarm!Function
patricle_swarm!(M, F; n=100, x0::AbstractVector=[random_point(M) for i in 1:n], kwargs...)

perform the particle swarm optimization algorithm (PSO), starting with the initial particle positions $x_0$[Borckmans2010] in place of x0.

Input

  • M – a manifold $\mathcal M$
  • F – a cost function $F:\mathcal M→ℝ$ to minimize

Optional

  • n - (100) number of random initial positions of x0
  • x0 – the initial positions of each particle in the swarm $x_k^{(0)} ∈ \mathcal M$ for $k = 1, \dots, n$, per default these are n random_points

for more optional arguments, see particle_swarm.

source

Options

Manopt.ParticleSwarmOptionsType
ParticleSwarmOptions{P,T} <: Options

Describes a particle swarm optimizing algorithm, with

Fields

a default value is given in brackets if a parameter can be left out in initialization.

  • x0 – a set of points (of type AbstractVector{P}) on a manifold as initial particle positions
  • velocity – a set of tangent vectors (of type AbstractVector{T}) representing the velocities of the particles
  • inertia – (0.65) the inertia of the patricles
  • social_weight – (1.4) a social weight factor
  • cognitive_weight – (1.4) a cognitive weight factor
  • stopping_criterion – (StopWhenAny(StopAfterIteration(500), StopWhenChangeLess(10^{-4}))) a functor inheriting from StoppingCriterion indicating when to stop.
  • retraction_method – (ExponentialRetraction) the rectraction to use
  • inverse_retraction_method - (LogarithmicInverseRetraction) an inverse retraction to use.

Constructor

ParticleSwarmOptions(x0, velocity, inertia, social_weight, cognitive_weight, stopping_criterion[, retraction_method=ExponentialRetraction(), inverse_retraction_method=LogarithmicInverseRetraction()])

construct a particle swarm Option with the fields and defaults as above.

See also

particle_swarm

source

Literature

  • Borckmans2010

    P. B. Borckmans, M. Ishteva, P.-A. Absil, A Modified Particle Swarm Optimization Algorithm for the Best Low Multilinear Rank Approximation of Higher-Order Tensors, In: Dorigo M. et al. (eds) Swarm Intelligence. ANTS 2010. Lecture Notes in Computer Science, vol 6234. Springer, Berlin, Heidelberg, doi 10.1007/978-3-642-15461-4_2