In hydraulic machinery, the surface of the blade can get damaged by the cavitation of the leading-edge. In order to improve the cavitation performance, the anti-cavitation optimization design of blade leading-edge is conducted. A heuristic-parallel locally-terminated improved hill-climbing algorithm, which is named as the global dynamic-criterion (GDC) algorithm was proposed in this study. The leading-edge shape of NACA 0009-mod foil profile was optimized by combining the GDC algorithm, CFD prediction, Diffusion-angle Integral (DI) design method and orthogonal test. Three different optimal foil geometries were obtained for specific incidence angles that 0, 3, and 6 degrees. According to the flow field analyses, it was found that the geometric variation of the optimized foil fits the incoming flow better at the respective optimal incidence angles due to a slighter leading-edge flow separation. The pressure drops become gentler so that the cavitation performance get improved. Results show that the GDC algorithm quickly and successfully fits the target condition by parallel running with the ability against falling into local-best tarps. The −Cpmin of the optimal foils was improved especially by +11.4% and +14.5% at 3 and 6 degrees comparing with the original foil. This study provided a reference for the anti-cavitation design of hydraulic machinery blades.