This paper proposes an optimal over-frequency generator tripping strategy aiming at implementing the least amount of generator tripping for the regional power grid with high penetration level of wind/photovoltaic (PV), to handle the over-frequency problem in the sending-end power grid under large disturbances. A steady-state frequency abnormal index is defined to measure the degrees of generator over-tripping and under-tripping, and a transient frequency abnormal index is presented to assess the system abnormal frequency effect during the transient process, which reflects the frequency security margin during the generator tripping process. The scenario-based analysis method combined with the non-parametric kernel density estimation method is applied to model the uncertainty of the outgoing power caused by the stochastic fluctuations of wind/PV power and loads. Furthermore, an improved fireworks algorithm is utilized for the solution of the proposed optimization model. Finally, the simulations are performed on a real-sized regional power grid in Southern China to verify the effectiveness and adaptability of the proposed model and method.