Particle swarm optimization

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 ManifoldM. 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 AbstractManifoldCostObjectivemco.

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

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 AbstractManifoldCostObjectivemco.

For more details and optional arguments, see particle_swarm.

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

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.