Simulation optimization using genetic algorithms with optimal computing budget allocation

摘要

A method is proposed to improve the efficiency of simulation optimization by integrating the notion of optimal computing budget allocation into the genetic algorithm, which is a global optimization search method that iteratively generates new solutions using elite candidate solutions. When applying genetic algorithms in a stochastic setting, each solution must be simulated a large number of times. Hence, the computing budget allocation can make a significant difference to the performance of the genetic algorithm. An easily implementable closed-form computing budget allocation rule of ranking the best m solutions out of total k solutions is proposed. The proposed budget allocation rule can perform better than the existing asymptotically optimal allocation rule for ranking the best m solutions. By integrating the proposed budget allocation rule, the search efficiency of genetic algorithms has significantly improved, as shown in the numerical examples.