Cross-entropy method: Difference between revisions

Revision as of 01:17, 14 April 2015

Revision as of 23:53, 21 March 2016

Line 1:

{{Multiple issues|

{{no footnotes|date=September 2013}}

{{ref improverefimprove|date=September 2013}}

}}

The '''cross-entropy (CE) method''' attributed to [[Reuven Rubinstein]] is a general [[Monte Carlo method|Monte Carlo]] approach to

[[Combinatorial optimization|combinatorial]] and [[Continuous optimization|continuous]] multi-extremal [[Optimization (mathematics)|optimization]] and [[importance sampling]].

The method originated from the field of ''rare event simulation'', where

very small probabilities need to be accurately estimated, for example in network reliability analysis, queueing models, or performance analysis of telecommunication systems.

The CE method can be applied to static and noisy combinatorial optimization problems such as the [[traveling salesman problem]], the [[quadratic assignment problem]], [[Sequence_alignmentSequence alignment|DNA sequence alignment]], the [[Maxcut|max-cut]] problem and the buffer allocation problem, as well as continuous [[global optimization]] problems with many local [[extremum|extrema]].

In a nutshell the CE method consists of two phases:

Line 18 ⟶ 21:

==Generic CE algorithm==

# 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></p>

# Solve for <math>\mathbf{v}^{(t)}</math>, where<br><math>\mathbf{v}^{(t)} = \mathop{\textrm{argmax}}_{\mathbf{v}} \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})</math>

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

In several cases, the solution to step 3 can be found ''analytically''. Situations in which this occurs are

* When <math>f\,</math> belongs to the [[Exponential_familyExponential family|natural exponential family]]

* When <math>f\,</math> is [[discrete space|discrete]] with finite [[Support (mathematics)|support]]

* When <math>H(\mathbf{X}) = \mathrm{I}_{\{\mathbf{x}\in A\}}</math> and <math>f(\mathbf{X}_i;\mathbf{u}) = f(\mathbf{X}_i;\mathbf{v}^{(t-1)})</math>, then <math>\mathbf{v}^{(t)}</math> corresponds to the [[Maximum likelihood|maximum likelihood estimator]] based on those <math>\mathbf{X}_k \in A</math>.

Line 75 ⟶ 79:

==External links==

*[http://www.cemethod.org Homepage for the CE method]

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

[[Category:Heuristics]]

[[Category:Optimization algorithms and methods]]