About

This web site is a collection of information and links about the Cross-Entropy method.

Pioneered in 1997 by Reuven Rubinstein (1938-2012) as an efficient method for the estimation of rare-event probabilities, the cross-entropy (CE) method has rapidly developed into a powerful and versatile technique for both rare-event simulation and combinatorial optimisation. The method derives its name from the cross-entropy (or Kullback-Leibler) distance - a well known measure of "information", which has been successfully employed in diverse fields of engineering and science, and in particular in neural computation, for about half a century.

The CE method is an iterative method, which involves the following two phases:
  • Generation of a sample of random data (trajectories, vectors, etc.) according to a specified random mechanism.
  • Updating the parameters of the random mechanism, on the basis of the data, in order to produce a "better" sample in the next iteration.
The significance of the cross-entropy concept is that it defines a precise mathematical framework for deriving fast, and in some sense "optimal" updating/learning rules.

The CE method has been successfully applied to a number of difficult combinatorial optimization problems, including the maximal cut problem, the traveling salesman problem (TSP), the quadratic assignment problem, different types of scheduling problems, the clique problem, the buffer allocation problem (BAP) for production lines, and combinatorial optimization problems associated with the genome. It is important to note that the CE method deals successfully with both deterministic problems, such as the TSP, and noisy (i.e., simulation-based) problems, such as the BAP.

An approach closely related to CE is the Probability Collectives work of Dr. David Wolpert and his collaborators. This approach uses information theory as a bridge to relate game theory, statistical physics, and distributed optimization/control.

In the field of rare-event simulation, CE is used in conjunction with the importance sampling (IS) technique: the CE method iteratively optimizes parameters of the distributions used in the simulation. Applications include the efficient estimation of performance measures in telecommunication networks and reliability systems.