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 Borkmanns, Ishteva, Absil, 7th IC Swarm Intelligence, 2010. If no swarm is provided, swarm_size many random points are used. Note that since this method does not work in-place – these points are duplicated internally.

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
• 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 patricles
• inverse_retraction_method - (default_inverse_retraction_method(M, eltype(x))) an inverse_retraction(M,x,y) to use.
• swarm_size - (100) number of random initial positions of x0
• retraction_method – (default_retraction_method(M, eltype(x))) a retraction(M,x,ξ) to use.
• social_weight – (1.4) a social weight factor
• stopping_criterion – (StopWhenAny(StopAfterIteration(500), StopWhenChangeLess(10^{-4}))) a functor inheriting from StoppingCriterion indicating when to stop.
• vector_transport_mthod - (default_vector_transport_method(M, eltype(x))) 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 inital 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 whichis 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.

ParticleSwarmState{P,T} <: AbstractManoptSolverState

Describes a particle swarm optimizing algorithm, with

Fields

• x – 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
• p_temp – 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
• cognitive_vector - temporary storage for a tangent vector related to cognitive_weight
• stopping_criterion – ([StopAfterIteration](@ref)(500) | [StopWhenChangeLess](@ref)(1e-4)) a functor inheriting from [StoppingCriterion`](@ref) indicating when to stop.
• retraction_method – (default_retraction_method(M, eltype(x))) the rectraction to use
• inverse_retraction_method - (default_inverse_retraction_method(M, eltype(x))) an inverse retraction to use.
• vector_transport_method - (default_vector_transport_method(M, eltype(x))) a vector transport to use

Constructor

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

construct a particle swarm Option for the manifold M starting at initial population x0 with velocities x0, where the manifold is used within the defaults of the other fields mentioned above, which are keyword arguments here.

See also

particle_swarm