Cross-Entropy Elite Gaussian Update

The Cross-Entropy Method (CEM) for continuous optimization iteratively refines a search distribution. In this component, we observe one iteration of updating a Gaussian search distribution to maximize an objective function. By selecting only the highest-scoring "elite" samples, the method maps the best current parameters back into a new search distribution.

Worked Example

Let the objective be to maximize - (x - 2)² (which peaks at x = 2). We draw fixed samples [-3, -2, -1, 0, 1, 2, 3, 4] from an initial normal distribution N(0, 4). If we select the best k = 2 elite samples, and resolve ties by favoring smaller x, we obtain:

Evaluate samples: scores are [ -25, -16, -9, -4, -1, 0, -1, -4 ].
Sort by descending score: the best are x = 2 (score 0) and x = 1 (score -1). (Note: x = 3 also has score -1, but ties favor the smaller x = 1).
The elite set is { 2, 1 }.
Calculate Maximum Likelihood (MLE) elite mean: \mu_(elite) = (2 + 1)/2 = 1.5.
Calculate population variance of the elite set: σ^2_(elite) = ((2 - 1.5)² + (1 - 1.5)²)/2 = (0.25 + 0.25)/2 = 0.25.
With smoothing factor η = 1 (no reduction), the updated distribution is N(1.5, 0.25).

Experiment with Parameters

You can interact with the Cross-Entropy Elite Gaussian Update module to see how elite selection and smoothing parameters shape the updated distribution:

Set Target to 2 and Elite count to 2. Notice the updated distribution concentrates around the elite samples (2 and 1) with low variance.
Change Elite count to 1. The variance collapses entirely to exactly zero, resulting in a single point mass at the elite sample. The algorithm cannot explore further!
To prevent this premature collapse, set Smoothing to 0.5. The updated variance becomes a mixture of the old broad variance (4) and the new narrow elite variance (0), keeping the search space open for the next iteration.

Limitations and Edge Cases

This module shows only a single, frozen iteration on a fixed set of samples rather than continuous random sampling over multiple generations. True CEM iterates this process, drawing fresh samples from the updated distribution each time.

Additionally, if the elite count is 1, or if all elite samples happen to hold the identical value, the MLE population variance is strictly zero. Evaluating a zero-width continuous probability density function fails, effectively yielding a point mass that prevents any further exploration of the parameter space. Parameter smoothing (mixing the old and new parameters) is critical to avoiding this premature convergence.

References

For a comprehensive tutorial on the Cross-Entropy Method, including continuous optimization and Gaussian updates, see the foundational paper: A Tutorial on the Cross-Entropy Method by de Boer et al. (2005).

Cross-Entropy Elite Gaussian Update