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 $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 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 patriclesinverse_retraction_method
- (default_inverse_retraction_method(M, eltype(x))
) aninverse_retraction(M,x,y)
to use.swarm_size
- (100
) number of random initial positions of x0retraction_method
– (default_retraction_method(M, eltype(x))
) aretraction(M,x,ξ)
to use.social_weight
– (1.4
) a social weight factorstopping_criterion
– (StopWhenAny
(
StopAfterIteration
(500)
,StopWhenChangeLess
(10^{-4})))
a functor inheriting fromStoppingCriterion
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 typeAbstractVector{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
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
whichis 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
x
– a set of points (of typeAbstractVector{P}
) on a manifold as initial particle positionsvelocity
– a set of tangent vectors (of typeAbstractVector{T}
) representing the velocities of the particlesinertia
– (0.65
) the inertia of the patriclessocial_weight
– (1.4
) a social weight factorcognitive_weight
– (1.4
) a cognitive weight factorp_temp
– temporary storage for a point to avoid allocations during a step of the algorithmsocial_vec
- temporary storage for a tangent vector related tosocial_weight
cognitive_vector
- temporary storage for a tangent vector related tocognitive_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 useinverse_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
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, editors, 13–23. Springer Berlin Heidelberg (2010).