Particle swarm optimization

Manopt.particle_swarmFunction
patricle_swarm(M, f; kwargs...)
patricle_swarm(M, f, swarm; kwargs...)
patricle_swarm(M, mco::AbstractManifoldCostObjective; kwargs..)
patricle_swarm(M, mco::AbstractManifoldCostObjective, swarm; kwargs..)

perform the particle swarm optimization algorithm (PSO), starting with an initial swarm [BIA10]. If no swarm is provided, swarm_size many random points are used.

The aim of PSO is to find the particle position $p$ on the Manifold M that solves approximately

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

To this end, a swarm $S = \{s_1, \ldots, s_n\}$ of particles is moved around the manifold M in the following manner. For every particle $s_k^{(i)}$ the new particle velocities $X_k^{(i)}$ are computed in every step $i$ of the algorithm by

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

where

  • $s_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
  • $T$ denotes the vector transport and $\operatorname{retr}^{-1}$ the inverse retraction used

Then the position of the particle is updated as

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

where $\operatorname{retr}$ denotes a retraction on the Manifold M. Then the single particles best entries $p_k^{(i)}$ are updated as

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

and the global best position

\[g^{(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}\]

Input

  • M: a manifold $\mathcal M$
  • f: a cost function $F:\mathcal M→ℝ$ to minimize
  • swarm: ([rand(M) for _ in 1:swarm_size]) an initial swarm of points.

Instead of a cost function f you can also provide an AbstractManifoldCostObjective mco.

Optional

  • cognitive_weight: (1.4) a cognitive weight factor
  • inertia: (0.65) the inertia of the particles
  • inverse_retraction_method: (default_inverse_retraction_method(M, eltype(swarm))) an inverse retraction to use.
  • swarm_size: (100) swarm size, if it should be generated randomly
  • retraction_method: (default_retraction_method(M, eltype(swarm))) a retraction to use.
  • social_weight: (1.4) a social weight factor
  • stopping_criterion: (StopAfterIteration(500) |StopWhenChangeLess(1e-4)) a functor inheriting from StoppingCriterion indicating when to stop.
  • vector_transport_mthod: (default_vector_transport_method(M, eltype(swarm))) a vector transport method to use.
  • velocity: a set of tangent vectors (of type AbstractVector{T}) representing the velocities of the particles, per default a random tangent vector per initial position

All other keyword arguments are passed to decorate_state! for decorators or decorate_objective!, respectively. If you provide the ManifoldGradientObjective directly, these decorations can still be specified

Output

the obtained (approximate) minimizer $g$, see get_solver_return for details

source
Manopt.particle_swarm!Function
patricle_swarm!(M, f, swarm; kwargs...)
patricle_swarm!(M, mco::AbstractManifoldCostObjective, swarm; kwargs..)

perform the particle swarm optimization algorithm (PSO), starting with the initial swarm which is then modified in place.

Input

  • M: a manifold $\mathcal M$
  • f: a cost function $f:\mathcal M→ℝ$ to minimize
  • swarm: ([rand(M) for _ in 1:swarm_size]) an initial swarm of points.

Instead of a cost function f you can also provide an AbstractManifoldCostObjective mco.

For more details and optional arguments, see particle_swarm.

source

State

Manopt.ParticleSwarmStateType
ParticleSwarmState{P,T} <: AbstractManoptSolverState

Describes a particle swarm optimizing algorithm, with

Fields

  • cognitive_weight: (1.4) a cognitive weight factor
  • inertia: (0.65) the inertia of the particles
  • inverse_retraction_method: (default_inverse_retraction_method(M, eltype(swarm))) an inverse retraction to use.
  • retraction_method: (default_retraction_method(M, eltype(swarm))) the retraction to use
  • social_weight: (1.4) a social weight factor
  • stopping_criterion: ([StopAfterIteration](@ref)(500) | [StopWhenChangeLess](@ref)(1e-4)) a functor inheriting from [StoppingCriterion`](@ref) indicating when to stop.
  • vector_transport_method: (default_vector_transport_method(M, eltype(swarm))) a vector transport to use
  • velocity: a set of tangent vectors (of type AbstractVector{T}) representing the velocities of the particles

Internal and temporary fields

  • cognitive_vector: temporary storage for a tangent vector related to cognitive_weight
  • p: storage for the best point $p$ visited by all particles.
  • positional_best: storing the best position $p_i$ every single swarm participant visited
  • q: temporary storage for a point to avoid allocations during a step of the algorithm
  • social_vec: temporary storage for a tangent vector related to social_weight
  • swarm: a set of points (of type AbstractVector{P}) on a manifold $\{s_i\}_{i=1}^N$

Constructor

ParticleSwarmState(M, initial_swarm, velocity; kawrgs...)

construct a particle swarm solver state for the manifold M starting at initial population x0 with velocities, where the manifold is used within the defaults specified previously. All fields with defaults are keyword arguments here.

See also

particle_swarm

source

Stopping Criteria

Manopt.StopWhenSwarmVelocityLessType
StopWhenSwarmVelocityLess <: StoppingCriterion

Stoping criterion for particle_swarm, when the velocity of the swarm is less than a threshold.

Fields

  • threshold: the threshold
  • at_iteration: store the iteration the stopping criterion was (last) fulfilled
  • reason: store the reaason why the stopping criterion was filfilled, see get_reason
  • velocity_norms: interims vector to store the norms of the velocities before coputing its norm

Constructor

StopWhenSwarmVelocityLess(tolerance::Float64)

initialize the stopping criterion to a certain tolerance.

source

Technical details

The particle_swarm solver requires the following functions of a manifold to be available

  • A retract!(M, q, p, X); it is recommended to set the default_retraction_method to a favourite retraction. If this default is set, a retraction_method= does not have to be specified.
  • An inverse_retract!(M, X, p, q); it is recommended to set the default_inverse_retraction_method to a favourite retraction. If this default is set, a inverse_retraction_method= does not have to be specified.
  • A vector_transport_to!M, Y, p, X, q); it is recommended to set the default_vector_transport_method to a favourite retraction. If this default is set, a vector_transport_method= does not have to be specified.
  • By default the stopping criterion uses the norm as well, to stop when the norm of the gradient is small, but if you implemented inner, the norm is provided already.
  • Tangent vectors storing the social and cognitive vectors are initialized calling zero_vector(M,p).
  • A `copyto!(M, q, p) and copy(M,p) for points.
  • The distance(M, p, q) when using the default stopping criterion, which uses StopWhenChangeLess.

Literature

[BIA10]
P. B. Borckmans, M. Ishteva and P.-A. Absil. A Modified Particle Swarm Optimization Algorithm for the Best Low Multilinear Rank Approximation of Higher-Order Tensors. In: 7th International Conference on Swarm INtelligence (Springer Berlin Heidelberg, 2010); pp. 13–23.