Cross-entropy method: Difference between revisions

Revision as of 09:39, 8 August 2023

Latest revision as of 19:50, 23 April 2025

(6 intermediate revisions by 4 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.

Line 6 ⟶ 7:

#Minimize the ''[[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 67 ⟶ 68:

''// Sort X by objective function values in descending order''

X := sort(X, S)

''// Update parameters of sampling distribution via elite samples''

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

σ2 := var(X(1:Ne))

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]