Cross-entropy method: Difference between revisions

Revision as of 14:45, 22 April 2020

Latest revision as of 19:50, 23 April 2025

(17 intermediate revisions by 10 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 52 ⟶ 53:

===Pseudocode===

''// Initialize parameters''

&mu; := −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==

Line 81 ⟶ 82:

* [[Tabu search]]

* [[Natural Evolution Strategy]]

* [[Ant colony optimization algorithms]]

==See also==

Line 89 ⟶ 91:

== Journal papers ==

* 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 implementations==

* [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==