Skip to content

(GECCO 2022) CMA-ES with Margin: Lower-Bounding Marginal Probability for Mixed-Integer Black-Box Optimization

License

Notifications You must be signed in to change notification settings

EvoConJP/CMA-ES_with_Margin

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

17 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

CMA-ES with Margin

CMA-ES with Margin (CMA-ESwM) [1] is a CMA-ES variant proposed for mixed-integer black-box optimization, which introduces a lower bound on the marginal probability associated with integer variables.

Demonstration

Here we show optimizing SphereInt function with CMA-ES and CMA-ESwM. The SphereInt function is given as follows (This is a minimization problem).

$$ f(x) = x_0^2 + x_1^2 \text{ , where } x_0 \in \mathbb{R}, x_1 \in \mathbb{Z} \text{.} $$

CMA-ES CMA-ESwM
CMA-ES CMA-ESwM

The integer variable $x_1$ is obtained by rounding the continuous variable sampled from the multivariate normal distribution. The dashed ellipse represents the confidence ellipse of the multivariate normal distribution. The red star indicates the optimal solution position. The CMA-ES may not change the evaluation value because of the plateau caused by the discretization. On the other hand, the CMA-ESwM prevents this stagnation by keeping the probability of being sampled outside a plateau above a certain level.

Usage

Please see sample_script.py.

Details (click to expand)

Setting the objective function

Set the objective function, the number of dimensions, and the maximum number of evaluations. As an example, the SphereOneMax function is set here.

func = 'SphereOneMax'
dim = 40     # total number of dimensions
dim_bi = dim//2     # number of binary variables
max_evals = dim * 1e4
f = eval('f_mixed.' + func)(d=dim, bid=dim_bi, ind=0, max_eval=max_evals)

Setting the discrete space

Set the search space for discrete variables. If the number of the elements of the discrete variable is different in each dimension, align the number of array elements by filling the tail with nan. For example, a three-dimensional discrete variable [[1, 2], [1, 2, 3], [1, 2, 3, 4]] is set as follows:

import numpy as np

discrete_space = np.full((3, 4), np.nan)
discrete_space[0, :2] = np.array([1, 2])
discrete_space[1, :3] = np.array([1, 2, 3])
discrete_space[2, :4] = np.array([1, 2, 3, 4])
# discrete_space
# [[  1.   2.  nan  nan]
#  [  1.   2.   3.  nan]
#  [  1.   2.   3.   4.]]

This implementation also allows assignment of discrete variables that are not consecutive integers, such as [1, 2, 4] and [0.01, 0.1, 1].

Setting the hyperparameter

Set the population size, weight function, and margin parameter. The margin parameter represents $ \alpha $ in [1] and its recommended value is $ 1/(N \lambda)$, where $N$ is the number of dimensions and $\lambda$ is the population size. When the margin parameter is 0, the CMA-ESwM behaves equivalently to the CMA-ES in this implementation.

lam = cma.CMAParam.pop_size(dim)
w_func = weight.CMAWeightWithNegativeWeights(lam, dim, min_problem=f.minimization_problem)
margin = 1 / (dim * lam)

Initialization of mean vector and step size

Appropriate initial values can be set depending on the number of dimensions of the objective function. In this implementation, the initial values of the mean vectors corresponding to continuous and integer variables are sampled from a uniform distribution.

init_m, init_sigma = f_mixed.initial_setting_for_gaussian(f)

CSV data log

The log of the experiment can be output in CSV format.

result_folder = f'./output/'
path_name = result_folder + f'{func}/dim{dim}/'
output = logg.DataLogger(file_name='result.csv', path_name=path_name)

If you do not want the log to be output, set None to logger as follows at running the optimizer.

opt.run(samp, logger=None, verbose=True)

Setting and running the optimizer

You can use IPOP restart strategy. If you want to use the restart, set the maximum number of restarts to restart. Otherwise, set -1 to restart.

# optimizer
samp = sampler.Sampler(f, lam)
opt = cma.CMAESwM(dim, discrete_space, w_func, samp,
                       lam=lam, m=init_m, sigma=init_sigma,
                       margin=margin, restart=-1, minimal_eigenval=1e-30)

# run
result = opt.run(samp, logger=output, verbose=True)

References and related papers

  1. Ryoki Hamano, Shota Saito, Masahiro Nomura, and Shinichi Shirakawa, CMA-ES with Margin: Lower-Bounding Marginal Probability for Mixed-Integer Black-Box Optimization, In Genetic and Evolutionary Computation Conference (GECCO ’22), July 9–13, 2022, Boston, MA, USA. ACM, New York, NY, USA, 9 pages. https://doi.org/10.1145/3512290.3528827 [arXiv]
  2. Ryoki Hamano, Shota Saito, Masahiro Nomura, and Shinichi Shirakawa, Benchmarking CMA-ES with Margin on the bbob-mixint Testbed, In Genetic and Evolutionary Computation Conference Companion (GECCO ’22 Companion), July 9–13, 2022, Boston, MA, USA. ACM, New York, NY, USA, 9 pages. https://doi.org/10.1145/3520304.3534043

About

(GECCO 2022) CMA-ES with Margin: Lower-Bounding Marginal Probability for Mixed-Integer Black-Box Optimization

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages