The laws of gravity and mass interactions inspire the gravitational search algorithm (GSA), which finds optimal regions of complex search spaces through the interaction of individuals in a population of particles. Although GSA has proven effective in both science and engineering, it is still easy to suffer from premature convergence especially facing complex problems. In this paper, we proposed a new hybrid algorithm by integrating genetic algorithm (GA) and GSA (GA-GSA) to avoid premature convergence and to improve the search ability of GSA. In GA-GSA, crossover and mutation operators are introduced from GA to GSA for jumping out of the local optima. To demonstrate the search ability of the proposed GA-GSA, 23 complex benchmark test functions were employed, including unimodal and multimodal high-dimensional test functions as well as multimodal test functions with fixed dimensions. Wilcoxon signed-rank tests were also utilized to execute statistical analysis of the results obtained by PSO, GSA, and GA-GSA. Experimental results demonstrated that the proposed algorithm is both efficient and effective.