Covariance matrix adaptation evolutionary strategy

cma_es(M, f, p_m=rand(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: a manifold $\mathcal M$
• f: a cost function $f: \mathcal M→ℝ$ to find a minimizer $p^*$ for

Keyword arguments

• p_m=rand(M): an initial point p
• σ=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=default_cma_es_stopping_criterion(M, λ; tol_fun=tol_fun, tol_x=tol_x): a functor indicating that the stopping criterion is fulfilled
• retraction_method=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• vector_transport_method=default_vector_transport_method(M, typeof(p)): a vector transport $\mathcal T_{⋅←⋅}$ to use, see the section on vector transports
• basis (DefaultOrthonormalBasis()) basis used to represent covariance in
• 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
• 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
• 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 for random number generation and wmean_y_c of length n_coords
• 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::AbstractVectorTransportMethodP: 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};
    retraction_method::TRetraction=default_retraction_method(M, typeof(p_m)),
    vector_transport_method::TVTM=default_vector_transport_method(M, typeof(p_m)),
    basis::TB=DefaultOrthonormalBasis(),
    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 20% but at least min_size and no more than max_size iterations. 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 maximum deviation increased by more than tol. 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 with iteration $i \geq 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_eig eigen decomposition when expanded in basis from point p to point q on M. Update matrix_eigen in-place.

(p, matrix_eig) belongs to the fiber bundle of $B = \mathcal M × 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.