Determination of the long wavelength, or background, velocity structure is a critical step in prestack imaging. We have developed an efficient procedure for the solution of this non-linear inverse problem using a genetic algorithm (GA). In our approach velocities are described by splines; velocity values at spline nodes are the parameters in the inversion.