In this paper, we present a stochastic adaptive algorithm using radial basis function models for global optimization of costly black-box functions. The exploration radii in local searches are generated adaptively. Each iteration point is selected from some randomly generated trial points according to certain criteria. A restarting strategy is adopted to build the restarting version of the algorithm. The performance of the presented algorithm and its restarting version are tested on 13 standard numerical examples. The numerical results suggest that the algorithm and its restarting version are very effective.