The graph coloring problem is an NP-hard problem. Currently, the most effective method to solve the problem is the hybrid algorithm. This paper proposes a hybrid evolutionary algorithm NERS_HEAD with a new elite replacement strategy. In NERS_HEAD, a method to detect the local optimal state is proposed so that the evolutionary process can jump out of the local optimal by introducing diversity on time. A new elite structure and replacement strategy are designed to increase the diversity of the evolutionary population so that the evolution process can not only converge quickly but also jump out of the local optimum in time. Experiments based on 34 instances of the DIMACS benchmark show that compared with the current excellent graph coloring algorithm, NERS_HEAD can reduce the evolutionary generation by an average of 28.3% and the calculation time by 22.11%. Especially in the instance dsjc500.1, Nere_HEAD can reduce 56% of evolution generations and 40% of computing time; On the r1000.1c instance, it can reduce the evolution generations by 82.30% and the calculation time by 73.45%.