Particle swarm optimization
Manopt.particle_swarm
— Functionpatricle_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 $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)}$ we compute the new particle velocities $X_k^{(i)}$ in every step $i$ of the algorithm by
\[begin{aligned*} 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, $\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
\[s_k^{(i+1)} = \operatorname{retr}_{s_k^{(i)}}(X_k^{(i)}),\]
where $\operatorname{retr}$ denotes a retraction on the Manifold
M
. Then we update the single every particles best entries $p_k^{(i)}$ 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 minimizeswarm
– ([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 factorinertia
– (0.65
) the inertia of the particlesinverse_retraction_method
- (default_inverse_retraction_method(M, eltype(swarm))
) an inverse retraction to use.swarm_size
- (100
) swarm size, if it should be generated randomlyretraction_method
– (default_retraction_method(M, eltype(swarm))
) a retraction to use.social_weight
– (1.4
) a social weight factorstopping_criterion
– (StopAfterIteration
(500) |
StopWhenChangeLess
(1e-4)
) a functor inheriting fromStoppingCriterion
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 typeAbstractVector{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
Manopt.particle_swarm!
— Functionpatricle_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 minimizeswarm
– ([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
.
State
Manopt.ParticleSwarmState
— TypeParticleSwarmState{P,T} <: AbstractManoptSolverState
Describes a particle swarm optimizing algorithm, with
Fields
cognitive_weight
– (1.4
) a cognitive weight factorinertia
– (0.65
) the inertia of the particlesinverse_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 usesocial_weight
– (1.4
) a social weight factorstopping_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 usevelocity
– a set of tangent vectors (of typeAbstractVector{T}
) representing the velocities of the particles
Internal and temporary fields
cognitive_vector
- temporary storage for a tangent vector related tocognitive_weight
positional_best
– storing the best position $p_i$ every single swarm participant visitedq
– temporary storage for a point to avoid allocations during a step of the algorithmsocial_vec
- temporary storage for a tangent vector related tosocial_weight
swarm
– a set of points (of typeAbstractVector{P}
) on a manifold $\{s_i\}_{i=1}^N$p
- storage for the best point $p$ visited by all particles.
Constructor
ParticleSwarmState(M, initial_swarm, velocity; kawrgs...)
construct a particle swarm solver state 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
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 thedefault_retraction_method
to a favourite retraction. If this default is set, aretraction_method=
does not have to be specified. - An
inverse_retract!
(M, X, p, q)
; it is recommended to set thedefault_inverse_retraction_method
to a favourite retraction. If this default is set, ainverse_retraction_method=
does not have to be specified. - A
vector_transport_to!
M, Y, p, X, q)
; it is recommended to set thedefault_vector_transport_method
to a favourite retraction. If this default is set, avector_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 implementedinner
, 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)
andcopy
(M,p)
for points. - The
distance
(M, p, q)
when using the default stopping criterion, which usesStopWhenChangeLess
.
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.