Efficient Ranking and Selection for Stochastic Simulation Model Based on Hypothesis Test

This paper proposes an efficient ranking and selection algorithm for a stochastic simulation model. The proposed algorithm evaluates an uncertainty to assess whether the observed best design is truly optimal, based on hypothesis test. Then, it conservatively allocates additional simulation resources to reduce uncertainty with an intuitive allocation rule in each iteration of a sequential procedure. This conservative allocation provides a high robustness to noise for the algorithm. The results of several experiments demonstrated its improved performance compared to the other algorithms in the literature. The algorithm can be an efficient way to solve optimization problems in real-world systems where significant noise exists.

I. Introduction

Simulation-based optimization (SBO) has been widely used to solve many problems in real-world systems [1], [2], such as project scheduling problems [3], discrete-event air combat systems [4], multicriteria decision-making problems [5], supply chain management [6], etc. However, the efficiency of SBO is still a concern: numerous repeating simulations are required to obtain an accurate result due to significant noise in such systems [7], [8]. As the number of computing resources for simulation is limited in practice, the problem of accurately finding the best solution with the constraint of limited resources has been drawing attention. If a search space is continuous and sufficiently large, classical metaheuristic search algorithms, such as simulated annealing [9], genetic algorithm [10], and tabu search [11], can be an effective way to solve the problem. Otherwise, if the space is discrete and relatively small (specifically, every design in the space can be simulated more than five times), this problem falls into the well-known ranking and selection (R&S) in statistics [12]–[16].