Back to Search
Start Over
A Stochastic Minimum Cross-Entropy Method for Combinatorial Optimization and Rare-event Estimation*.
- Source :
- Methodology & Computing in Applied Probability; Mar2005, Vol. 7 Issue 1, p5-50, 46p
- Publication Year :
- 2005
-
Abstract
- We present a new method, called the minimum cross-entropy (MCE) method for approximating the optimal solution of NP-hard combinatorial optimization problems and rare-event probability estimation, which can be viewed as an alternative to the standard cross entropy (CE) method. The MCE method presents a generic adaptive stochastic version of Kull-back’s classic MinxEnt method. We discuss its similarities and differences with the standard cross-entropy (CE) method and prove its convergence. We show numerically that MCE is a little more accurate than CE, but at the same time a little slower than CE. We also present a new method for trajectory generation for TSP and some related problems. We finally give some numerical results using MCE for rare-events probability estimation for simple static models, the maximal cut problem and the TSP, and point out some new areas of possible applications. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 13875841
- Volume :
- 7
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- Methodology & Computing in Applied Probability
- Publication Type :
- Academic Journal
- Accession number :
- 16527129
- Full Text :
- https://doi.org/10.1007/s11009-005-6653-7