Ólafsson and Kim’s work is a good introduction to this paper:
Simulation optimization is the process of finding the best values of some decision variables [that is, continuous or discrete] for a system where the performance is evaluated based on the output of a simulation model of this system. ... Techniques for simulation optimization vary greatly, depending on the exact problem setting. [1]
In this area, and in a continuous and noisy search-space setting, He et al. face an open issue: the development of an effective approach that can both optimize the simulation budget allocation and improve the efficiency of the cross-entropy (CE) search method.
The first difficulty is the stochastic nature of evaluating such an objective function. Indeed, previous approaches are heavily hampered by noise, due to the kind of evaluation methods employed (such as stochastic simulation). One plausible workaround is to focus on how to best allocate simulation replications among candidate solutions, namely: “how much of [the] simulation budget should be allocated to additional replications at already visited points and how much to allocate for replications at newly generated points.” Optimizing this tradeoff is beneficial to computational efficiency.
With this in mind, the authors apply some efficient ranking and selection procedures, in order to enhance the computational efficiency of the CE algorithm. Instead of equally simulating all solutions, some distribution-based algorithms--ranging from deterministic global optimization to simulation optimization--try to allocate a larger portion of the computing budget to those candidate solutions that play a more important role. Toward this goal, He at al. investigate a different computing budget allocation approach. Using CE as the sampling method, they consider an objective designed for the performance of the CE method, intending to find an efficient computing budget allocation so that this objective can be optimized. Specifically, they derive an asymptotically optimal allocation--CE with optimal computing budget allocation (CEOCBA)--to be used just prior to the parameter updating step, at each iteration of the CE method, which minimizes the expected mean-squared error of the CE weight function (suggested in this paper).
The authors apply numerical tests to four algorithms: standard CE with equal allocation, a standard version of the CEOCBA procedure, extended CE with equal allocation, and an extended version of the CEOCBA procedure. The results show that the integrated procedure can lead to significant computational efficiency gains for both CE methods, when compared to cases that do not have smarter computing budget allocation.
In conclusion, even though the paper’s approach was developed for the CE method, CEOCBA has the potential to be extended to other population-based evolutionary algorithms and distribution-based algorithms. The authors’ proposal is well presented and clearly explained.