Cross-Entropy Method

The cross-entropy method is a Monte Carlo method for importance sampling and optimization, applicable to both combinatorial and continuous problems with a static or noisy objective. It approximates the optimal importance-sampling estimator by repeatedly drawing a sample from a probability distribution and then minimizing the cross-entropy between that distribution and a target distribution to produce a better sample on the next iteration. Reuven Rubinstein developed the method for rare-event simulation, where very small probabilities must be estimated, such as in network reliability analysis, and it has since also been applied to combinatorial problems including the traveling salesman, quadratic assignment and max-cut problems.