Optimization of fuel cost function of large-scale thermal generating units under several constraints in smart power grid is a challenging problem. Because of these constraints, the fuel cost function becomes multimodal, discontinuous and non-convex. Although the global particle swarm optimization with inertia weight (GPSO-w) algorithm is a popular optimization technique, it is not capable of solving such complex problems satisfactory. In this paper, a novel multi-gradient PSO (MG-PSO) algorithm is proposed to solve such a challenging problem. In MG-PSO algorithm, two phases, called Exploration phase and Exploitation phase, are used. In the Exploration phase, the m particles are called Explorers and undergo multiple episodes. In each episode, the Explorers use a different negative gradient to explore new neighbourhood whereas in the Exploitation phase, the m particles are called Exploiters and they use one negative gradient that is less than that of the Exploration phase, to exploit a best neighborhood. This diversity in negative gradients provides a balance between global search and local search. The effectiveness of the MG-PSO algorithm is demonstrated using four (medium and large) power generation systems. Superior performance of the MG-PSO algorithm over several PSO variants in terms of several performance measures has been shown. (C) 2017 Elsevier Ltd. All rights reserved.