The cross-entropy (CE) method is a Monte Carlo method for importance sampling and optimization. It is applicable to both combinatorial and continuous problems, with either a static or noisy objective.

The method approximates the optimal importance sampling estimator by repeating two phases:

  1. Draw a sample from a probability distribution.
  2. Minimize the cross-entropy between this distribution and a target distribution to produce a better sample in the next iteration.

Reuven Rubinstein developed the method in the context of rare event simulation, where tiny probabilities must be estimated, for example in network reliability analysis, queueing models, or performance analysis of telecommunication systems. The method has also been applied to the traveling salesman, quadratic assignment, DNA sequence alignment, max-cut and buffer allocation problems.

Estimation via importance sampling

Consider the general problem of estimating the quantity

,

where is some performance function and is a member of some parametric family of distributions. Using importance sampling this quantity can be estimated as

,

where is a random sample from . For positive , the theoretically optimal importance sampling density (PDF) is given by

.

This, however, depends on the unknown . The CE method aims to approximate the optimal PDF by adaptively selecting members of the parametric family that are closest (in the Kullback–Leibler sense) to the optimal PDF .

Generic CE algorithm

  1. Choose initial parameter vector ; set t = 1.
  2. Generate a random sample from
  3. Solve for , where
  4. If convergence is reached then stop; otherwise, increase t by 1 and reiterate from step 2.

In several cases, the solution to step 3 can be found analytically. Situations in which this occurs are

  • When belongs to the natural exponential family
  • When is discrete with finite support
  • When and , then corresponds to the maximum likelihood estimator based on those .

Pseudo-code

// Initialize parameters
mu:=-6
sigma2:=100
t:=0
maxits:=100
N:=100
Ne:=10
// While maxits not exceeded and not converged
while t < maxits and sigma2 > epsilon
  // Obtain N samples from current sampling distribution
  X:=SampleGaussian(mu,sigma2,N)
  // Evaluate objective function at sampled points
  S:=exp(-(X-2)^2) + 0.8 exp(-(X+2)^2)
  // Sort X by objective function values in descending order
  X:=sort(X,S)
  // Update parameters of sampling distribution                  
  mu:=mean(X(1:Ne))
  sigma2:=var(X(1:Ne))
  t:=t+1
// Return mean of final sampling distribution as solution
return mu

Related methods

  • Simulated annealing
  • Genetic algorithms
  • Harmony search
  • Estimation of distribution algorithm
  • Tabu search
  • Natural Evolution Strategy

Journal Papers

  • Rubinstein, R.Y. (1997). Optimization of Computer simulation Models with Rare Events, European Journal of Operational Research, 99, 89–112.

Software Implementations


    This article uses material from the Wikipedia article Cross-entropy method, which is released under the Creative Commons Attribution-Share-Alike License 3.0.