In this paper we present a simple algorithm for global optimization. This algorithm combines random searches with efficient local minimization algorithms. The proposed algorithm begins with an initial "local minimizer." In each iteration, a search direction is generated randomly, along which some points are chosen as the initial points for the local optimization algorithm and several "local minimizers" are obtained. The next iteration is determined by comparing these localminimizers. We will discuss the expected number of iterations for finding a global minimizer with this algorithm. Several variants of the algorithm that take advantage of the partially separable structure are proposed for the Lennard-Jones cluster problem and tested on the IBM SP1 parallel computer. Our numerical results show that our algorithms are promising.