Three heuristic search methods, Genetic Algorithm, Simulated Annealing and Tabu Search are implemented to invert Rayleigh wave phase velocity for shallow S-wave velocity profiling in seismic surface wave surveying. Unlike linearized least-squares inversion, they do not require derivative calculation, or an initial model, only the forward modeling calculation. In this study, the performances of the three heuristic techniques are compared with numerical experiments. With common paramerization and search limits, the three algorithms can accurately reconstruct shallow S-wave profiles with and without a velocity reversal from the synthetic data without any specific initial models. The Genetic Algorithms and the Simulated Annealing show fast convergence. However, the Simulated Annealing can find models with the smallest misfits. It is also found that the decrease of the misfits is the most gradual in the Tabu Search.