Particle Swarm Optimization

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 – (default_retraction_method(M)) a retraction(M,x,ξ) to use.
• inverse_retraction_method - (default_inverse_retraction_method(M)) an inverse_retraction(M,x,y) to use.
• vector_transport_mthod - (default_vector_transport_method(M)) a vector transport method to use.
• stopping_criterion – (StopWhenAny(StopAfterIteration(500), StopWhenChangeLess(10^{-4}))) a functor inheriting from StoppingCriterion indicating when to stop.

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

Output

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

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.

ParticleSwarmOptions{P,T} <: Options

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
• 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)) the rectraction to use
• inverse_retraction_method - (default_inverse_retraction_method(M)) an inverse retraction to use.
• vector_transport_method - (default_vector_transport_method(M)) a vector transport to use

Constructor

ParticleSwarmOptions(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