Cross-Entropy Method (CEM)

class pypop7.optimizers.cem.cem.CEM(problem, options)[source]

Cross-Entropy Method (CEM).

This is the abstract class for all CEM classes. Please use any of its instantiated subclasses to optimize the black-box problem at hand.

Note

CEM is a class of principled population-based optimizers, proposed originally by Rubinstein,

whose core idea is based on Kullback–Leibler (or Cross-Entropy) minimization.

“CEM is not only based on fundamental principles (cross-entropy distance, maximum likelihood, etc.), but is also very easy to program (with far fewer parameters than many other global optimization heuristics), and gives consistently accurate results, and is therefore worth considering when faced with a difficult optimization problem.”—[Kroese et al., 2006, MCAP]

Parameters:

  • problem (dict) –

    problem arguments with the following common settings (keys):

    • ’fitness_function’ - objective function to be minimized (func),

    • ’ndim_problem’ - number of dimensionality (int),

    • ’upper_boundary’ - upper boundary of search range (array_like),

    • ’lower_boundary’ - lower boundary of search range (array_like).

  • options (dict) –

    optimizer options with the following common settings (keys):

    • ’max_function_evaluations’ - maximum of function evaluations (int, default: np.inf),

    • ’max_runtime’ - maximal runtime to be allowed (float, default: np.inf),

    • ’seed_rng’ - seed for random number generation needed to be explicitly set (int);

    and with the following particular settings (keys):

    • ’sigma’ - initial global step-size, aka mutation strength (float),

    • ’mean’ - initial (starting) point, aka mean of Gaussian search distribution (array_like),

      • if not given, it will draw a random sample from the uniform distribution whose search range is bounded by problem[‘lower_boundary’] and problem[‘upper_boundary’].

    • ’n_individuals’ - number of individuals/samples (int, default: 1000),

    • ’n_parents’ - number of elitists (int, default: 200).

mean

initial (starting) point, aka mean of Gaussian search (mutation/sampling) distribution.

Type:

array_like

n_individuals

number of individuals/samples.

Type:

int

n_parents

number of elitists.

Type:

int

sigma

initial global step-size, aka mutation strength.

Type:

float

References

Amos, B. and Yarats, D., 2020, November. The differentiable cross-entropy method. In International Conference on Machine Learning (pp. 291-302). PMLR. http://proceedings.mlr.press/v119/amos20a.html

Rubinstein, R.Y. and Kroese, D.P., 2016. Simulation and the Monte Carlo method (Third Edition). John Wiley & Sons. https://onlinelibrary.wiley.com/doi/book/10.1002/9781118631980

Hu, J., Fu, M.C. and Marcus, S.I., 2007. A model reference adaptive search method for global optimization. Operations Research, 55(3), pp.549-568. https://pubsonline.informs.org/doi/abs/10.1287/opre.1060.0367

Kroese, D.P., Porotsky, S. and Rubinstein, R.Y., 2006. The cross-entropy method for continuous multi-extremal optimization. Methodology and Computing in Applied Probability, 8(3), pp.383-407. https://link.springer.com/article/10.1007/s11009-006-9753-0

De Boer, P.T., Kroese, D.P., Mannor, S. and Rubinstein, R.Y., 2005. A tutorial on the cross-entropy method. Annals of Operations Research, 134(1), pp.19-67. https://link.springer.com/article/10.1007/s10479-005-5724-z

Rubinstein, R.Y. and Kroese, D.P., 2004. The cross-entropy method: a unified approach to combinatorial optimization, Monte-Carlo simulation, and machine learning. New York: Springer. https://link.springer.com/book/10.1007/978-1-4757-4321-0

CEMs: