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.
SivanandamSNDeepaSN. Introduction to genetic algorithms. Springer, 2007.
15.
TsutsuiSGhoshA. Genetic algorithms with a robust solution searching scheme. IEEE Trans Evol Comput1997; 1: 201–208.
16.
FitzpatrickMGreffenstetteJJ. Genetic algorithms in noisy environments. Mach Learn1988; 3: 101–120.
17.
BrankeJ. Creating robust solutions by means of evolutionary algorithms. Lect Notes Comput Sci1998; 1498: 119–128.
18.
SchmidtCBrankeJChickSE. Integrating techniques from statistical ranking into evolutionary algorithms. Lect Notes Comput Sci2006; 3907: 752–763.
19.
TamakiHAraiT. A genetic algorithm approach to optimization problems in an uncertain environment. In: Proceeding of the 1997 international conference on neural information processing and intelligent information systems, 1997, pp.436–439.
20.
TanookaKTamakiHAbeV. A continuous age model of genetic algorithms applicable to optimization problems with uncertainties. In: Proceedings of the 1999 IEEE international conference on systems, man and cybernetics, 1999, Vol. 1, pp.637–642.
21.
XuJNelsonBLHongLJ. Industrial strength COMPASS: a comprehensive algorithm and software for optimization via simulation. ACM Trans Model Comput Simul2010; 20(1): 3.1–3.29.
22.
ChenCHHeDFuM. Efficient simulation budget allocation for selecting an optimal subset. INFORMS J Comput2008; 20: 579–595.
23.
XiaoHLeeLH. Efficient simulation budget allocation for ranking the top m designs. Discrete Dyn Nat Soc2014: 195054.
24.
ChenCH. A lower bound for the correct subset-selection probability and its application to discrete event system simulations. IEEE Trans Autom Control1996; 41: 1227–1231.
25.
ChenCHLinJYücesanE. Simulation budget allocation for further enhancing the efficiency of ordinal optimization. Discrete Event Dyn Syst Theory Appl2000; 10: 251–270.
26.
KimSHNelsonBL, Selecting the best system. Handb Oper Res Manage Sci2006; 13: 501–534.
27.
ChickSInoueK. New two-stage and sequential procedures for selecting the best simulated system. Oper Res2001; 49: 1609–1624.
28.
ChickSInoueK. Inoue. New procedures to select the best simulated system using common random numbers. Manage Sci2001; 47: 1133–1149.
29.
JiaQSZhouEChenCH. Efficient computing budget allocation for finding simplest good design. IIE Trans2013; 45: 736–750.
30.
YanSZhouEChenCH. Efficient selection of a set of good enough designs with complexity preference. IEEE Trans Autom Sci Eng2012; 9: 596–606.
31.
JiaQS. Efficient computing budget allocation for simulation-based policy improvement. IEEE Trans Autom Sci Eng2012; 9: 342–352.
32.
JiaQSShenJXuZ. Simulation-based policy improvement for energy management in commercial office buildings. IEEE Trans Smart Grid2012; 3: 2211–2223.
33.
LeeLHChewEPTengS. Optimal computing budget allocation for multi-objective simulation models. ACM Proc Winter Simul Conf2004: 586–594.
34.
LeeLHChewEPTengS. Finding the non-dominated Pareto set for multi-objective simulation models. IIE Trans2010; 42: 656–674.
35.
XiaoHLeeLHNgKM. Optimal computing budget allocation for complete ranking. IEEE Trans Autom Sci Eng2014; 11: 516–524.
36.
LeeLHPujowidiantoNALiLW. Approximate simulation budget allocation for selecting the best design in the presence of stochastic constraints. IEEE Trans Autom Control2012; 57: 2940–2945.
37.
HunterSRPasupathyR. Optimal sampling laws for stochastically constrained simulation optimization on finite sets. INFORMS J Comput2013; 25: 527–542.
38.
ZhangSChenPLeeLH. Simulation optimization using the particle swarm optimization with optimal computing budget allocation. ACM Proc Winter Simul Conf2011: 4303–4314.
39.
HeDLeeLHChenCH. Simulation optimization using the cross-entropy method with optimal computing budget allocation. ACM Trans Model Comput Simul2010; 20(1): 4.
40.
ChenCHLeeLH. Stochastic simulation optimization: an optimal computing budget allocation. Singapore: World Scientific, 2010.
41.
DemboAZeitouniO. Large deviations techniques and applications. New York: Springer-Verlag, 1998.
42.
GlynnPJunejaS. A large deviations perspective on ordinal optimization. ACM Proc Winter Simul Conf2004: 577–585.
