Covariance matrix adaptation evolutionary strategy

cma_es(M, f, p=rand(M); σ::Real=1.0, kwargs...)
cma_es(M, mco::AbstractManifoldCostObjective, p=rand(M); σ::Real=1.0, kwargs...)
cma_es!(M, f, p_m; σ::Real=1.0, kwargs...)
cma_es!(M, mco::AbstractManifoldCostObjective, p_m; σ::Real=1.0, kwargs...)

Perform covariance matrix adaptation evolutionary strategy search for global gradient-free randomized optimization. It is suitable for complicated non-convex functions. It can be reasonably expected to find global minimum within 3σ distance from p_m.

Implementation is based on [Han23] with basic adaptations to the Riemannian setting.

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal{M}$
• f: a cost function $f: \mathcal{M}→ ℝ$ implemented as (M, p) -> v
• p::P: a point on the manifold $\mathcal{M}$

Keyword arguments

• σ=1.0: initial standard deviation
• λ=4 + Int(floor(3 * log(manifold_dimension(M)))): population size (can be increased for a more thorough global search but decreasing is not recommended)
• tol_fun=1e-12: tolerance for the StopWhenPopulationCostConcentrated, similar to absolute difference between function values at subsequent points
• tol_x=1e-12: tolerance for the StopWhenPopulationStronglyConcentrated, similar to absolute difference between subsequent point but actually computed from distribution parameters.
• stopping_criterion::StoppingCriterion= default_cma_es_stopping_criterion(M, λ; tol_fun=tol_fun, tol_x=tol_x): a functor indicating that the stopping criterion is fulfilled
• callbacks::D = Dict{Symbol,Function}(): provided callback functions given as a dictionary with symbols as keys
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• basis=default_basis(M, typeof(p)): a basis used to represent the covariance matrix in coordinates
• rng=default_rng(): random number generator for generating new points on M

All other keyword arguments are passed to decorate_state! for state decorators or decorate_objective! for objective decorators, respectively.

Output

The obtained approximate minimizer $p^*$. To obtain the whole final state of the solver, see get_solver_return for details, especially the return_state= keyword.

cma_es(M, f, p=rand(M); σ::Real=1.0, kwargs...)
cma_es(M, mco::AbstractManifoldCostObjective, p=rand(M); σ::Real=1.0, kwargs...)
cma_es!(M, f, p_m; σ::Real=1.0, kwargs...)
cma_es!(M, mco::AbstractManifoldCostObjective, p_m; σ::Real=1.0, kwargs...)

Perform covariance matrix adaptation evolutionary strategy search for global gradient-free randomized optimization. It is suitable for complicated non-convex functions. It can be reasonably expected to find global minimum within 3σ distance from p_m.

Implementation is based on [Han23] with basic adaptations to the Riemannian setting.

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal{M}$
• f: a cost function $f: \mathcal{M}→ ℝ$ implemented as (M, p) -> v
• p::P: a point on the manifold $\mathcal{M}$

Keyword arguments

• σ=1.0: initial standard deviation
• λ=4 + Int(floor(3 * log(manifold_dimension(M)))): population size (can be increased for a more thorough global search but decreasing is not recommended)
• tol_fun=1e-12: tolerance for the StopWhenPopulationCostConcentrated, similar to absolute difference between function values at subsequent points
• tol_x=1e-12: tolerance for the StopWhenPopulationStronglyConcentrated, similar to absolute difference between subsequent point but actually computed from distribution parameters.
• stopping_criterion::StoppingCriterion= default_cma_es_stopping_criterion(M, λ; tol_fun=tol_fun, tol_x=tol_x): a functor indicating that the stopping criterion is fulfilled
• callbacks::D = Dict{Symbol,Function}(): provided callback functions given as a dictionary with symbols as keys
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• vector_transport_method::AbstractVectorTransportMethod=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• basis=default_basis(M, typeof(p)): a basis used to represent the covariance matrix in coordinates
• rng=default_rng(): random number generator for generating new points on M

All other keyword arguments are passed to decorate_state! for state decorators or decorate_objective! for objective decorators, respectively.

Output

The obtained approximate minimizer $p^*$. To obtain the whole final state of the solver, see get_solver_return for details, especially the return_state= keyword.

CMAESState{P,T} <: AbstractManoptSolverState

State of covariance matrix adaptation evolution strategy.

Fields

• p::P: a point on the manifold $\mathcal{M}$ storing the best point found so far
• callbacks::D: provided callback functions given as a dictionary with symbols as keys
• p_obj objective value at p
• μ parent number
• λ population size
• μ_eff variance effective selection mass for the mean
• c_1 learning rate for the rank-one update
• c_c decay rate for cumulation path for the rank-one update
• c_μ learning rate for the rank-μ update
• c_σ decay rate for the cumulation path for the step-size control
• c_m learning rate for the mean
• d_σ damping parameter for step-size update
• population population of the current generation
• ys_c coordinates of random vectors for the current generation
• covariance_matrix coordinates of the covariance matrix
• last_variances eigenvalues of covariance_matrix from the previous iteration, used to replace nonpositive eigenvalues
• covariance_matrix_eigen eigen decomposition of covariance_matrix
• covariance_matrix_cond condition number of covariance_matrix, updated after eigen decomposition
• best_fitness_current_gen best fitness value of individuals in the current generation
• median_fitness_current_gen median fitness value of individuals in the current generation
• worst_fitness_current_gen worst fitness value of individuals in the current generation
• p_m point around which the search for new candidates is done
• σ step size
• p_σ coordinates of a vector in $T_{p_m}\mathcal{M}$
• p_c coordinates of a vector in $T_{p_m}\mathcal{M}$
• deviations standard deviations of coordinate RNG
• buffer buffer of length n_coords for random number generation and for the weighted mean $⟨y⟩_w$ of the selected steps
• e_mv_norm expected value of norm of the n_coords-variable standard normal distribution
• recombination_weights recombination weights used for updating covariance matrix
• retraction_method::AbstractRetractionMethod: a retraction $\operatorname{retr}$ to use, see the section on retractions
• stop::StoppingCriterion: a functor indicating that the stopping criterion is fulfilled
• vector_transport_method::AbstractVectorTransportMethod: a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• basis a real coefficient basis for covariance matrix
• rng RNG for generating new points

Constructor

CMAESState(    M::AbstractManifold,    p_m::P,    μ::Int,    λ::Int,    μ_eff::TParams,    c_1::TParams,    c_c::TParams,    c_μ::TParams,    c_σ::TParams,    c_m::TParams,    d_σ::TParams,    stop::TStopping,    covariance_matrix::Matrix{TParams},    σ::TParams,    recombination_weights::Vector{TParams};    callbacks=Dict{Symbol, Function}(),    retraction_method::TRetraction=default_retraction_method(M, typeof(p_m)),    vector_transport_method::TVTM=default_vector_transport_method(M, typeof(p_m)),    basis::TB=default_basis(M, typeof(p_m)),    rng::TRng=default_rng(),) where {    P,    TParams<:Real,    TStopping<:StoppingCriterion,    TRetraction<:AbstractRetractionMethod,    TVTM<:AbstractVectorTransportMethod,    TB<:AbstractBasis,    TRng<:AbstractRNG,}

See also

cma_es

StopWhenBestCostInGenerationConstant <: StoppingCriterion

Stop if the range of the best objective function values of the last iteration_range generations is zero. This corresponds to EqualFunValues condition from [Han23].

See also StopWhenPopulationCostConcentrated.

StopWhenCovarianceIllConditioned <: StoppingCriterion

Stop CMA-ES if condition number of covariance matrix exceeds threshold. This corresponds to ConditionCov condition from [Han23].

StopWhenEvolutionStagnates{TParam<:Real} <: StoppingCriterion

The best and median fitness in each iteration is tracked over the last (at most) max_size iterations, and the criterion is evaluated once at least min_size values have been recorded. Solver is stopped if in both histories the median of the most recent fraction of values is not better than the median of the oldest fraction.

StopWhenPopulationCostConcentrated{TParam<:Real} <: StoppingCriterion

Stop if the range of the best objective function value in the last max_size generations and all function values in the current generation is below tol. This corresponds to TolFun condition from [Han23].

Constructor

StopWhenPopulationCostConcentrated(tol::Real, max_size::Int)

StopWhenPopulationDiverges{TParam<:Real} <: StoppingCriterion

Stop if σ times the maximum deviation has grown by a factor larger than tol compared to its value at the start of the run. This usually indicates a far too small σ, or divergent behavior. This corresponds to TolXUp condition from [Han23].

StopWhenPopulationStronglyConcentrated{TParam<:Real} <: StoppingCriterion

Stop if the standard deviation in all coordinates is smaller than tol and norm of σ * p_c is smaller than tol. This corresponds to TolX condition from [Han23].

Fields

• tol the tolerance to verify against
• at_iteration an internal field to indicate at which iteration $k ≥ 0$ the tolerance was met.

Constructor

StopWhenPopulationStronglyConcentrated(tol::Real)

eigenvector_transport!(
    M::AbstractManifold, matrix_eigen::Eigen, p, q,
    basis::AbstractBasis, vtm::AbstractVectorTransportMethod,
)

Transport the matrix with matrix_eigen eigen decomposition when expanded in basis from point p to point q on M. Update matrix_eigen in-place.

(p, matrix_eigen) belongs to the fiber bundle of $B = \mathcal{M} × \mathrm{SPD}(n)$, where n is the (real) dimension of M. The function corresponds to the Ehresmann connection defined by vector transport vtm of eigenvectors of matrix_eigen.