Skip to main content
SpringerLink
Log in

A Tutorial on the Cross-Entropy Method

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

The cross-entropy (CE) method is a new generic approach to combinatorial and multi-extremal optimization and rare event simulation. The purpose of this tutorial is to give a gentle introduction to the CE method. We present the CE methodology, the basic algorithm and its modifications, and discuss applications in combinatorial optimization and machine learning.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

References

  • Aarts, E.H.L. and J.H.M Korst. (1989). Simulated Annealing and Boltzmann Machines. John Wiley & Sons.

  • Alon, G., D.P. Kroese, T. Raviv, and R.Y. Rubinstein. (2005). “Application of the Cross-Entropy Method to the Buffer Allocation Problem in a Simulation-Based Environment.” Annals of Operations Research 134, 19–67.

    Article  Google Scholar 

  • Asmussen, S., D.P. Kroese, and R.Y. Rubinstein. (2005). “Heavy Tails, Importance Sampling and Cross-Entropy.” Stochastic Models 21(1). To appear.

  • Barto, A., R. Sutton, and C. Anderson. (1983). “Neuron-Like Adaptive Elements that can Solve Difficult Learning Control Problems.” IEEE Transactions on Systems, Man, and Cybernetics 13, 834–846.

    Google Scholar 

  • Barto, A.G. and R.S. Sutton. (1998). Reinforcement Learning. MIT Press.

  • Baxter, J., P.L. Bartlett, and L. Weaver. (2001). Experiments with Infinite-Horizon, Policy-Gradient Estimation.” Journal of Artificial Intelligence Research 15, 351–381.

    Google Scholar 

  • Bertsekas, D.P. (1995). Dynamic Programming and Optimal Control. Athena Scientific.

  • Bertsekas, D.P. and J.N. Tsitsiklis. (1995). Neuro-Dynamic Programming. Athena Scientific.

  • Chepuri, K. and T. Homem-de-Mello. (2005). “Solving the Vehicle Routing Problem with Stochastic Demands using the Cross-Entropy Method.” Annals of Operations Research 134, 153–181.

    Article  Google Scholar 

  • Cohen, I., B. Golany, and A. Shtub. (2005). “Managing Stochastic Finite Capacity Multi-Project Systems Through the Cross-Entropy Method.” Annals of Operations Research 134, 183–199.

    Article  Google Scholar 

  • Colorni, A., M. Dorigo, F. Maffioli, V. Maniezzo, G. Righini, and M. Trubian. (1996). “Heuristics from Nature for Hard Combinatorial Problems.” International Transactions in Operational Research 3(1), 1—21.

    Article  Google Scholar 

  • Dayan, P. and C. Watkins (1992). “Q-Learning.” Machine Learning 8, 279–292.

    Google Scholar 

  • de Boer, P.T. (2000). “Analysis and Efficient Simulation of Queueing Models of Telecommunication Systems.” Ph.D. thesis, University of Twente.

  • de Boer, P.T., D.P. Kroese, and R.Y. Rubinstein. (2002).“Estimating Buffer Overflows in Three Stages using Cross-Entropy.” In Proceedings of the 2002 Winter Simulation Conference. San Diego, pp. 301–309.

  • de Boer, P.T., D.P. Kroese, and R.Y. Rubinstein. (2004). “A Fast Cross-Entropy Method for Estimating Buffer Overflows in Queueing Networks.” Management Science 50(7), 883–895.

    Article  Google Scholar 

  • Dorigo, M., G. Di Caro, and L.M. Gambardella. (1999). “Ant Algorithms for Discrete Optimization.” Artificial Life 5(2), 137–172.

    Article  Google Scholar 

  • Dubin, U. (2002). “Application of the Cross-Entropy Method to Neural Computation.” Master’s thesis, Technion, Electrical Engineering.

  • Dubin, U. (2004). “Application of the Cross-Entropy Method for Image Segmentation.”Unpublished.

  • Garey, M.R. and D.S. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W.H. Freeman and Company.

    Google Scholar 

  • Glover, F. and M. Laguna. (1993). Modern Heuristic Techniques for Combinatorial Optimization, chapter 3: Tabu search. Blackwell Scientific Publications.

  • Goldberg, D. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley.

  • Gutjahr, W.J. (2000). “A Graph-Based Ant System and Its Convergence.” Future Generations Computing 16, 873–888.

    Article  Google Scholar 

  • Helvik, B.E. and O. Wittner. (2001). “Using the Cross-Entropy Method to Guide/Govern Mobile Agent’s Path Finding in Networks.” In 3rd International Workshop on Mobile Agents for Telecommunication Applications—MATA’01.

  • Homem-de-Mello, T. and R.Y. Rubinstein. (2002). “Rare Event Estimation for Static Models via Cross-Entropy and Importance Sampling.” (submitted for publication).

  • Hui, K.-P., N. Bean, M. Kraetzl, and D.P. Kroese. (2005). “The Cross-Entropy Method for Network Reliability Estimation.”Annals of Operations Research 134, 101–118.

    Article  Google Scholar 

  • Kaelbling, L.P., M. Littman, and A.W. Moore. (1996). “Reinforcement Learning—A Survey.” Journal of Artificial Intelligence Research 4, 237–285.

    Google Scholar 

  • Keith, J. and D.P. Kroese. (2002). “SABRES: Sequence Alignment By Rare Event Simulation.” In Proceedings of the 2002 Winter Simulation Conference, San Diego, pp. 320–327.

  • Konda, V.R. and J.N. Tsitsiklis. (2003). “Actor-Critic Algorithms.” SIAM Journal on Control and Optimization 42(4), 1134–1166.

    Google Scholar 

  • Kroese, D.P. and R.Y. Rubinstein. (2004). “The Transform Likelihood Ratio Method for Rare Event Simulation with Heavy Tails.” Queueing Systems 46, 317–351.

    Article  Google Scholar 

  • Lieber, D. (1998). “Rare-Events Estimation via Cross-Entropy and Importance Sampling.” Ph.D. thesis, William Davidson Faculty of Industrial Engineering and Management, Technion, Haifa, Israel.

  • Mannor, S., R.Y. Rubinstein, and Y. Gat. (2003). “The Cross-Entropy Method for Fast Policy Search.” In Proceedings of the Twentieth International Conference on Machine Learning. Morgan Kaufmann, pp. 512–519.

  • Margolin, L. (2002). “Application of the Cross-Entropy Method to Scheduling Problems.” Master’s thesis, Technion, Industrial Engineering.

  • Margolin, L. (2004). “The Cross-Entropy Method for the Single Machine Total Weighted Tardiness Problem.” Unpublished.

  • Margolin, L. (2005).“On the Convergence of the Cross-Entropy Method.” Annals of Operations Research 134, 201–214.

    Article  Google Scholar 

  • Menache, I., S. Mannor, and N. Shimkin. (2005). “Basis Function Adaption in Temporal Difference Reinforcement Learning.”Annals of Operations Research 134, 215–238.

    Article  Google Scholar 

  • Papadimitriou, C.H. and M. Yannakakis. (1991). “Optimization, Approximation, and Complexity Classes.”J. Comput. System Sci. 43, 425–440.

    Article  Google Scholar 

  • Puterman, M. (1994). Markov Decision Processes. Wiley-Interscience.

  • Ridder, A. (2005). “Importance Sampling Simulations of Markovian Reliability Systems Using Cross-Entropy.”Annals of Operations Research 134, 119–136.

    Article  Google Scholar 

  • Rosenstein, M.T. and A.G. Barto. (2001). “Robot Weightlifting by Direct Policy Search.” In B. Nebel (ed.). Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Morgan Kaufmann, pp. 839–846.

  • Rubinstein, R.Y. (1997). “Optimization of Computer Simulation Models with Rare Events.”European Journal of Operations Research 99, 89–112.

    Article  Google Scholar 

  • Rubinstein, R.Y. (1999). “The Simulated Entropy Method for Combinatorial and Continuous Optimization.”Methodology and Computing in Applied Probability 2, 127–190.

    Article  Google Scholar 

  • Rubinstein, R.Y. (2001). “Combinatorial Optimization, Cross-Entropy, Ants and Rare Events.”In S. Uryasev and P.M. Pardalos (eds.). Stochastic Optimization: Algorithms and Applications. Kluwer, pp. 304–358.

  • Rubinstein, R.Y. (2002). “Cross-Entropy and Rare-Events for Maximal Cut and Bipartition Problems.”ACM Transactions on Modeling and Computer Simulation, 27–53.

  • Rubinstein, R.Y. and D.P. Kroese. (2004). The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation and Machine Learning. Springer-Verlag, New York.

    Google Scholar 

  • Rubinstein, R.Y. and B. Melamed. (1998). Modern Simulation and Modeling. Wiley series in probability and Statistics.

  • Rubinstein, R.Y. and A. Shapiro. (1993). Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization via the Score Function Method. Wiley.

  • Shi, L. and S. Olafsson. (2000). “Nested Partitioning Method for Global Optimization.” Operations Research 48(3), 390–407.

    Article  Google Scholar 

  • Sutton, R.S., D. McAllester, S. Singh, and Y. Mansour. (2000). “Policy Gradient Methods for Reinforcement Learning with Function Approximation.” In Advances in Neural Information Processing Systems 12. MIT Press, pp. 1057–1063.

  • Voudouris, C. (2003). “Guided Local Search—An Illustrative Example in Function Optimisation.”BT Technology Journal 16(3), 46–50.

    Article  Google Scholar 

  • Webb, A. (1999). Statistical Pattern Recognition. Arnold.

Download references

Author information

Authors and Affiliations

  1. Department of Electrical Engineering, Mathematics and Computer Science, University of Twente, Enschede, The Netherlands

    Pieter-Tjerk de Boer

  2. Department of Mathematics, The University of Queensland, Brisbane, 4072, Australia

    Dirk P. Kroese

  3. Department of Electrical and Computer Engineering, McGill University, 3480 University Street, Montreal, Quebec, Canada

    Shie Mannor

  4. Department of Industrial Engineering, Technion, Israel Institute of Technology, Haifa, 32000, Israel

    Reuven Y. Rubinstein

Authors
  1. Pieter-Tjerk de Boer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dirk P. Kroese
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shie Mannor
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Reuven Y. Rubinstein
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pieter-Tjerk de Boer.

Rights and permissions

Reprints and permissions

About this article

Cite this article

de Boer, PT., Kroese, D.P., Mannor, S. et al. A Tutorial on the Cross-Entropy Method. Ann Oper Res 134, 19–67 (2005). https://doi.org/10.1007/s10479-005-5724-z

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-005-5724-z

Key words

Search

Navigation