A Stochastic Minimum Cross-Entropy Method for Combinatorial Optimization and Rare-event Estimation* |
| |
Authors: | Email author" target="_blank">R?Y?RubinsteinEmail author |
| |
Institution: | (1) Faculty of Industrial Engineering and Management, Technion, Haifa, Israel |
| |
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-backs 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.AMS 2000 Subject Classification: 65C05, 60C05, 68W20, 90C59*This reseach was supported by the Israel Science Foundation (grant no 191-565). |
| |
Keywords: | combinatorial optimization cross-entropy rare-event estimation Monte Carlo simulation stochastic optimization |
本文献已被 SpringerLink 等数据库收录! |
|