This paper establishes the environmental economic dispatch model of power system considering operating costs and polluted emissions and proposes an improved gravity search algorithm (IGSA) to solve this problem. The algorithm applies Pareto sorting and crowded distance methods in the NSGA-II to the basic gravity search algorithm to process the individual partial order. In order to solve the problem of slow convergence caused by basic gravity search algorithm, this algorithm improves the location updating formula according to the particle swarm algorithm. In addition, elitist conversation strategy is adopted to guide the group to the region near the Pareto optimal solution set and guarantee that the solution set can be distributed evenly. Finally, fuzzy set theory is utilized to produce the best compromise solution which can provide scheduling solutions for decision makers. Cases studies demonstrate the feasibility and effectiveness of the proposed algorithm which will provide a new methods to balance the economy and environmental protection.