Cross-entropy Method

Cross-entropy Method

The cross-entropy (CE) method attributed to Reuven Rubinstein is a general Monte Carlo approach to combinatorial and continuous multi-extremal optimization and importance sampling. The method originated from the field of rare event simulation, where very small probabilities need to be accurately estimated, for example in network reliability analysis, queueing models, or performance analysis of telecommunication systems. The CE method can be applied to static and noisy combinatorial optimization problems such as the traveling salesman problem, the quadratic assignment problem, DNA sequence alignment, the max-cut problem and the buffer allocation problem, as well as continuous global optimization problems with many local extrema.

In a nutshell the CE method consists of two phases:

  1. Generate a random data sample (trajectories, vectors, etc.) according to a specified mechanism.
  2. Update the parameters of the random mechanism based on the data to produce a "better" sample in the next iteration. This step involves minimizing the cross-entropy or Kullback-Leibler divergence.

Read more about Cross-entropy Method:  Estimation Via Importance Sampling, Generic CE Algorithm, Continuous Optimization—example, Related Methods

Famous quotes containing the word method:

    Government by average opinion is merely a circuitous method of going to the devil; those who profess to lead but in fact slavishly follow this average opinion are simply the fastest runners and the loudest squeakers of the herd which is rushing blindly down to its destruction.
    Thomas Henry Huxley (1825–95)