Cross-entropy method: Difference between revisions

Revision as of 13:02, 1 April 2019

Latest revision as of 19:50, 23 April 2025

(20 intermediate revisions by 12 users not shown)

Line 1:

{{Short description|Monte Carlo method for importance sampling and optimization}}

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

The method approximates the optimal importance sampling estimator by repeating two phases:<ref>Rubinstein, R.Y. and Kroese, D.P. (2004), The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Machine Learning, Springer-Verlag, New York {{ISBN|978-0-387-21240-1}}.</ref>

#Draw a sample from a [[probability distribution]].

#Minimize the ''[[cross entropy|''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 problem|traveling salesman]], [[quadratic assignment problem|quadratic assignment]], [[Sequence alignment|DNA sequence alignment]], [[Maxcut|max-cut]] and buffer allocation problems.

==Estimation via importance sampling==

Line 26 ⟶ 27:

# Choose initial parameter vector <math>\mathbf{v}^{(0)}</math>; set t = 1.

# Generate a random sample <math>\mathbf{X}_1,\dots,\mathbf{X}_N</math> from <math>f(\cdot;\mathbf{v}^{(t-1)})</math>

# Solve for <math>\mathbf{v}^{(t)}</math>, where<br><math>\mathbf{v}^{(t)} = \mathop{\textrm{argmax}}_{\mathbf{uv}} \frac{1}{N} \sum_{i=1}^N H(\mathbf{X}_i)\frac{f(\mathbf{X}_i;\mathbf{u})}{f(\mathbf{X}_i;\mathbf{v}^{(t-1)})} \log f(\mathbf{X}_i;\mathbf{v}^{(t-1)})</math>

# If convergence is reached then '''stop'''; otherwise, increase t by 1 and reiterate from step 2.

Line 36 ⟶ 37:

== Continuous optimization&mdash;example==

The same CE algorithm can be used for optimization, rather than estimation.

Suppose the problem is to maximize some function <math>S(x)</math>, for example,

<math>S(x) = \textrm{e}^{-(x-2)^2} + 0.8\,\textrm{e}^{-(x+2)^2}</math>.

To apply CE, one considers first the ''associated stochastic problem'' of estimating

Line 51 ⟶ 52:

This yields the following randomized algorithm that happens to coincide with the so-called Estimation of Multivariate Normal Algorithm (EMNA), an [[estimation of distribution algorithm]].

===Pseudo-codePseudocode===

''// Initialize parameters''

&mu; :=-6 −6

sigma2&sigma;2 := 100

t := 0

maxits := 100

N := 100

Ne := 10

''// While maxits not exceeded and not converged''

'''while''' t < maxits '''and''' sigma2&sigma;2 > &epsilon; '''do'''

''// Obtain N samples from current sampling distribution''

X := SampleGaussian(&mu;,sigma2 &sigma;2, 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 via elite samples''

&mu; := mean(X(1:Ne))

sigma2 &sigma;2 := 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]]

* [[Ant colony optimization algorithms]]

==See also==

* [[Cross entropy]]

* [[Kullback–Leibler divergence]]

* [[Randomized algorithm]]

* [[Importance sampling]]

== Journal Paperspapers ==

* De Boer, P.-T., Kroese, D.P., Mannor, S. and Rubinstein, R.Y. (2005). A Tutorial on the Cross-Entropy Method. ''Annals of Operations Research'', '''134''' (1), 19–67.[http://www.maths.uq.edu.au/~kroese/ps/aortut.pdf]

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

==Software Implementationsimplementations==

* [https://ceopt.org '''CEopt''' Matlab package]
* [https://cran.r-project.org/web/packages/CEoptim/index.html '''CEoptim''' R package]

* [https://www.nuget.org/packages/Novacta.Analytics '''Novacta.Analytics''' .NET library]

==References==