Tutorial on cross-entropy method

A Tutorial on theCross-Entropy MethodPieter-Tjerk de BoerElectrical Engineering, Mathematics and Computer Science departmentUniversity of Twente ptdeboer@cs.utwente.nlDirk P. KroeseDepartment of MathematicsThe University of QueenslandBrisbane 4072, Australiakroese@maths.uq.edu.auShie MannorLaboratory for Information and Decision SystemsMassachusetts Institute of TechnologyCambridge, MA 02139shie@mit.eduReuven Y. RubinsteinDepartment of Industrial EngineeringTechnion, Israel Institute of TechnologyHaifa 32000, Israelierrr01@ie.technion.ac.ilLast updated: September 2, 2003AbstractThe cross-entropy (CE) method is a new generic approach to combi-natorial and multi-extremal optimization and rare event simulation. Thepurpose of this tutorial is to give a gentle introduction to the CE method.We present the CE methodology, the basic algorithm and its modi ca-tions, and discuss applications in combinatorial optimization and machinelearning.11 IntroductionMany everyday tasks in operations research involve solving complicated op-timization problems. The travelling salesman problem (TSP), the quadraticassignment problem (QAP) and the max-cut are a representative sam-ple of combinatorial optimization problems (COP) where the problem beingstudied is completely known and static. In contrast, the bu er allocation prob-lem (BAP) is a noisy estimation problem where the objective function needs tobe estimated since it is unknown. Discrete event ...