Particle swarm optimization

particle_swarm(M, f; kwargs...)
particle_swarm(M, f, swarm; kwargs...)
particle_swarm(M, mco::AbstractManifoldCostObjective; kwargs...)
particle_swarm(M, mco::AbstractManifoldCostObjective, swarm; kwargs...)
particle_swarm!(M, f, swarm; kwargs...)
particle_swarm!(M, mco::AbstractManifoldCostObjective, swarm; kwargs...)

perform the particle swarm optimization algorithm (PSO) to solve

\[\operatorname*{arg\,min}_{p ∈ \mathcal{M}} f(p)\]

PSO starts with an initial swarm [BIA10] of points on the manifold. If no swarm is provided, the swarm_size keyword is used to generate random points. The computation can be performed in-place of swarm.

To this end, a swarm $S = \{s_1,…, 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)} = ω \mathcal T_{s_k^{(i)}←s_k^{(i-1)}} X_k^{(i-1)} + c r_1 \operatorname{retr}^{-1}_{s_k^{(i)}}(p_k^{(i)}) + s r_2 \operatorname{retr}^{-1}_{s_k^{(i)}}(g^{(i)}),\]

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
• \mathcal T_{⋅←⋅} is a vector transport, and
• \operatorname{retr}^{-1} is an inverse retraction

Then the position of the particle is updated as

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

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^{(i)}),\\ g^{(i)}, & \text{else,} \end{cases}\]

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal{M}$
• f: a cost function $f: \mathcal{M}→ ℝ$ implemented as (M, p) -> v
• 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.

Keyword Arguments

• callbacks::D = Dict{Symbol,Function}(): provided callback functions given either as a single function (symbol, problem, state, k) called in every hook or as a (vector of) pairs :hook => function, which are processed by process_callbacks_arg. As key you can either pass single symbol or an array of symbols to indicate a callback should be added in multiple places
• cognitive_weight=1.4: a cognitive weight factor
• inertia=0.65: the inertia of the particles
• inverse_retraction_method::AbstractInverseRetractionMethod=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• social_weight=1.4: a social weight factor
• stopping_criterion::StoppingCriterion=StopAfterIteration(500)|StopWhenSwarmVelocityLess(1e-4): a functor indicating that the stopping criterion is fulfilled
• swarm_size=100: swarm size, if it should be generated randomly
• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• 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 state decorators or decorate_objective! for objective decorators, respectively. If you provide the objective directly, these decorations can still be specified

Output

The obtained approximate minimizer $p^*$. To obtain the whole final state of the solver, see get_solver_return for details, especially the return_state= keyword.

particle_swarm(M, f; kwargs...)
particle_swarm(M, f, swarm; kwargs...)
particle_swarm(M, mco::AbstractManifoldCostObjective; kwargs...)
particle_swarm(M, mco::AbstractManifoldCostObjective, swarm; kwargs...)
particle_swarm!(M, f, swarm; kwargs...)
particle_swarm!(M, mco::AbstractManifoldCostObjective, swarm; kwargs...)

perform the particle swarm optimization algorithm (PSO) to solve

\[\operatorname*{arg\,min}_{p ∈ \mathcal{M}} f(p)\]

PSO starts with an initial swarm [BIA10] of points on the manifold. If no swarm is provided, the swarm_size keyword is used to generate random points. The computation can be performed in-place of swarm.

To this end, a swarm $S = \{s_1,…, 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)} = ω \mathcal T_{s_k^{(i)}←s_k^{(i-1)}} X_k^{(i-1)} + c r_1 \operatorname{retr}^{-1}_{s_k^{(i)}}(p_k^{(i)}) + s r_2 \operatorname{retr}^{-1}_{s_k^{(i)}}(g^{(i)}),\]

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
• \mathcal T_{⋅←⋅} is a vector transport, and
• \operatorname{retr}^{-1} is an inverse retraction

Then the position of the particle is updated as

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

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^{(i)}),\\ g^{(i)}, & \text{else,} \end{cases}\]

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal{M}$
• f: a cost function $f: \mathcal{M}→ ℝ$ implemented as (M, p) -> v
• 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.

Keyword Arguments

• callbacks::D = Dict{Symbol,Function}(): provided callback functions given either as a single function (symbol, problem, state, k) called in every hook or as a (vector of) pairs :hook => function, which are processed by process_callbacks_arg. As key you can either pass single symbol or an array of symbols to indicate a callback should be added in multiple places
• cognitive_weight=1.4: a cognitive weight factor
• inertia=0.65: the inertia of the particles
• inverse_retraction_method::AbstractInverseRetractionMethod=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• social_weight=1.4: a social weight factor
• stopping_criterion::StoppingCriterion=StopAfterIteration(500)|StopWhenSwarmVelocityLess(1e-4): a functor indicating that the stopping criterion is fulfilled
• swarm_size=100: swarm size, if it should be generated randomly
• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• 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 state decorators or decorate_objective! for objective decorators, respectively. If you provide the objective directly, these decorations can still be specified

Output

The obtained approximate minimizer $p^*$. To obtain the whole final state of the solver, see get_solver_return for details, especially the return_state= keyword.

ParticleSwarmState{P,T} <: AbstractManoptSolverState

Describes a particle swarm optimizing algorithm, with

Fields

• callbacks::D: provided callback functions given as a dictionary with symbols as keys
• cognitive_weight: a cognitive weight factor
• inertia: the inertia of the particles
• inverse_retraction_method::AbstractInverseRetractionMethod: an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• retraction_method::AbstractRetractionMethod: a retraction $\operatorname{retr}$ to use, see the section on retractions
• social_weight: a social weight factor
• stop::StoppingCriterion: a functor indicating that the stopping criterion is fulfilled
• vector_transport_method::AbstractVectorTransportMethod: a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• 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::P: a point on the manifold $\mathcal{M}$ storing the best point visited by all particles
• positional_best: storing the best position $p_i$ every single swarm participant visited
• q::P: a point on the manifold $\mathcal{M}$ serving as temporary storage for interims results; avoids allocations
• social_vector: temporary storage for a tangent vector related to social_weight
• swarm: a set of points (of type AbstractVector{P}) on a manifold $\{s_k\}_{k=1}^{n}$

Constructor

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

construct a particle swarm solver state for the manifold M starting with the initial population initial_swarm with velocities velocity. The p used in the following defaults is the type of one point from the swarm.

Keyword arguments

• callbacks::D = Dict{Symbol,Function}(): provided callback functions given as a dictionary with symbols as keys
• cognitive_weight=1.4
• inertia=0.65
• inverse_retraction_method::AbstractInverseRetractionMethod=default_inverse_retraction_method(M, typeof(p)): an inverse retraction $\operatorname{retr}^{-1}$ to use, see the section on retractions and their inverses
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• social_weight=1.4
• stopping_criterion::StoppingCriterion=StopAfterIteration(500)|StopWhenChangeLess(1e-4): a functor indicating that the stopping criterion is fulfilled
• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports

See also

particle_swarm

StopWhenSwarmVelocityLess <: StoppingCriterion

Stopping 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
• velocity_norms: interim vector to store the norms of the velocities before computing its norm

Constructor

StopWhenSwarmVelocityLess(tolerance::Real)

initialize the stopping criterion to a certain tolerance.