Memetic Algorithm for Real-Time Combinatorial Stochastic Simulation Optimization Problems With Performance Analysis

Abstract

A three-phase memetic algorithm (MA) is proposed to find a suboptimal solution for real-time combinatorial stochastic simulation optimization (CSSO) problems with large discrete solution space. In phase 1, a genetic algorithm assisted by an offline global surrogate model is applied to find N good diversified solutions. In phase 2, a probabilistic local search method integrated with an online surrogate model is used to search for the approximate corresponding local optimum of each of the N solutions resulted from phase 1. In phase 3, the optimal computing budget allocation technique is employed to simulate and identify the best solution among the N local optima from phase 2. The proposed MA is applied to an assemble-to-order problem, which is a real-world CSSO problem. Extensive simulations were performed to demonstrate its superior performance, and results showed that the obtained solution is within 1% of the true optimum with a probability of 99%. We also provide a rigorous analysis to evaluate the performance of the proposed MA.