Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Cross-entropy method
open-in-new
<p>The cross-entropy (CE) method is a <a href="/facts/Monte_Carlo_method/AkHjY7jc">Monte Carlo</a> method for <a href="/facts/Importance_sampling/jrbUnMXa">importance sampling</a> and <a href="/facts/Optimization_(mathematics)/oRn8Iv5I">optimization</a>. It is applicable to both <a href="/facts/Combinatorial_optimization/PTcloS79">combinatorial</a> and <a href="/facts/Continuous_optimization/F8HupoHR">continuous</a> problems, with either a static or noisy objective. </p><p>The method approximates the optimal importance sampling estimator by repeating two phases: </p> <ol><li>Draw a sample from a <a href="/facts/Probability_distribution/EpsKKVRu">probability distribution</a>.</li> <li>Minimize the <i><a href="/facts/Cross-entropy/IG1WD4jb">cross-entropy</a></i> between this distribution and a target distribution to produce a better sample in the next iteration.</li></ol> <p><a href="/facts/Reuven_Rubinstein/nx0oyF1B">Reuven Rubinstein</a> developed the method in the context of <i>rare-event simulation</i>, 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 <a href="/facts/Traveling_salesman_problem/2WEKVLnV">traveling salesman</a>, <a href="/facts/Quadratic_assignment_problem/kQ5KJSb2">quadratic assignment</a>, <a href="/facts/Sequence_alignment/p8GQfF7b">DNA sequence alignment</a>, <a href="/facts/Maxcut/9rulcdeW">max-cut</a> and buffer allocation problems. </p>