Cross-entropy method: Difference between revisions

Revision as of 12:50, 27 November 2019

Revision as of 12:05, 25 December 2019

Line 51:

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 := 100

t := 0

Line 60:

Ne := 10

// While maxits not exceeded and not converged

'''while''' t < maxits '''and''' sigma2 > epsilon '''do'''

// Obtain N samples from current sampling distribution

X := SampleGaussian(mu, sigma2, 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

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

sigma2 := 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]]

==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 simulation Models with Rare Events, ''European Journal of Operational Research'', '''99''', 89–112.

==Software Implementationsimplementations==

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

==References==