In order to overcome the drawbacks of basic krill herd algorithms, such as low convergence rate and poor convergence ability, a novel co-evolutionary gravitational krill herd algorithm was proposed in consider of cooperative evolution and gravitational search algorithms. First, the whole population was divided into two cooperative competitive populations to promote the population competition, and then the population was divided into three parts including employed krill herd, onlookers and scout krill herd. The population evolved according to three phases in order to enhance the population local exploitation ability. Second, the affinity for foraging motion was viewed as the gravitation inspired by gravitational search algorithm, which can make sure the direction of the search. In the last, in order to evade evolution stagnation and trap into local optimum, the physical diffusion was modified as the huddling behavior and following behavior to promote the population diversity. The trait of convergence and drift were analyzed, and the evolution performance was also analyzed in the paper. Simulation results of same and different kinds of algorithms demonstrated that the algorithm performs better than other algorithms.