We discuss desirable features that optimization algorithms need to possess to exhibit good empirical performance when applied to solve simulation optimization problems possessing little known structure. Our approach emphasizes maintaining an appropriate balance between exploration, exploitation, and estimation. Exploration refers to searching the entire feasible region for promising solutions, exploitation refers to the search of improved solutions in promising subregions, and estimation refers to obtaining enhanced estimates of the objective function values at promising solutions. We also present two new random search methods that possess these desirable features, show their almost sure global convergence, and provide numerical results that show the attractive empirical behavior of the proposed methods.