# About

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

Pioneered in **1997** by Reuven Rubinstein as an efficient method for the estimation of rare-event probabilities, the

**has rapidly developed into a powerful and versatile technique for both**

*cross-entropy (CE) method**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.

- 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 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.

**Our visitors map** (click the map to enlarge):