Determining the optimal sampling set size for random search

Random search is a core component of many well known simulation optimization algorithms such as nested partition and COMPASS. Given a fixed computation budget, a critical decision is how many solutions to sample from a search area, which directly determines the number of simulation replications for each solution assuming that each solution receives the same number of simulation replications. This is another instance of the exploration vs. exploitation tradeoff in simulation optimization. Modeling the performance profile of all solutions in the search area as a normal distribution, we propose a method to (approximately) optimally determine the size of the sampling set and the number of simulation replications and use numerical experiments to demonstrate its performance.