The present paper considers the derivative-free optimization of expensive non-smooth functions. One of the most efficient algorithms for this class of problems is the surrogate-based optimization framework by Booker et al, 1999. Searches performed using this algorithm are restricted to points lying on an underlying grid to keep function evaluations far apart until convergence is approached. Once convergence on this discrete grid is obtained, the grid is refined and the process repeated. All previous implementations of this algorithm have been based on a Cartesian grid. However, Cartesian grids are not nearly as uniform at packing, covering, and quantizing parameter space as several alternatives that are well known in coding theory, referred to as "n-dimensional sphere packings" or "lattices". Also, the distribution of nearest-neighbor lattice points turns out to be far superior in these alternative lattices, further increasing the efficiency of the optimization algorithm. The present study illustrates how such lattices may be incorporated into the surrogate-based optimization framework.