Cross-entropy method

Cross-entropy method

Cross-entropy method was developed as an efficient estimation technique for rare event probabilities in discrete event simulation systems and has been adapted for use in optimization. The technique's name comes from the Kullback-Leibler cross-entropy method for measuring the amount of information (bits) needed to identify an event from a set of probabilities.

The information processing strategy of the algorithm is to sample the problem space and approximate the distribution of good solutions. This is achieved by assuming a distribution of the problem space (such as Gaussian), sampling the problem domain, generating candidate solutions using the distribution, and updating the distribution based on the best candidate solutions discovered. Samples are built in stages (one component at a time) based on the summarized distribution of good solutions. As the algorithm progresses, the distribution becomes more refined until it focuses on the domain or range of optimal solutions in the domain.

The following algorithm describes the cross-entropy method for minimizing a cost function.

The cross-entropy method has been adapted to combinatorial optimization problems, although it has been applied to continuous function optimization as well as simulation problems containing lots of noise.

A parameter alpha (a) or a learning rate in [0; 1] is usually set high, such as 0.7. A smoothing function can be used to further control updates to the sample distribution(s) of the definition space. For example, in the optimization of a continuous function, a parameter can replace (a) for the standard deviation update, calculated at time t as BB(1-1/t)^q, where B is initially set in [0,8; 0.99] and q is a small integer in [5; 10].