【Abstract】Random search is an important category of algorithms to solve continuous optimization via simulation problems. To design an efficient random search algorithm, the handling of the triple E (i.e., exploration, exploitation and estimation) is critical. The first two E's refer to the design of sampling distribution to balance explorative and exploitative searches, whereas the third E refers to the estimation of objective function values based on noisy simulation observations. In this paper, we propose a class of Gaussian process-based random search (GPRS) algorithms, which provide a new framework to handle the triple E. In each iteration, algorithms under the framework build a Gaussian process surrogate model to estimate the objective function based on single observation of each sampled solution and randomly sample solutions from a lower-bounded sampling distribution. Under the assumption of heteroscedastic and known simulation noise, we prove the global convergence of GPRS algorithms. Moreover, for Gaussian processes having continuously differentiable sample paths, we show that the rate of convergence of GPRS algorithms can be no slower than Op(n �1=(d+2)). Then, we introduce a specific GPRS algorithm to show how to design an integrated GPRS algorithm with adaptive sampling distributions and how to implement the algorithm efficiently. Numerical experiments show that the algorithm has good performances, even for problems where the variances of simulation noises are unknown.