This manuscript announces a novel hybrid optimization model comprising the gradient-based optimizer (GBO) and Linear population size reduction technique of Success-History-based Adaptive Differential Evolution (LSHADE) algorithm, so-called GB-LSHADE, for optimal relay coordination problem (ORCP). The ORCP is framed as a nonlinear constrained engineering problem that aims to optimize the time-dial, pickup current, and relay characteristics so that the relay clearance times are minimized. The proposed GB-LSHADE operates in two phases meanwhile the first phase starts with GBO to enrich the exploitative tendencies while the second phase is adopted to boost the local searching competence and avoid the premature convergence. To verify the efficacy of the proposed optimization method, a comprehensive simulation has been conducted on three test-systems (8-bus, 15-bus, and IEEE 30-bus) with different complexities. Many scenarios including fixed and varied relay curves as per IEC 60255 are demonstrated. At a final stage of this work, the computational complexity of the proposed approach is carried out and analyzed. It can be confirmed that the adapted optimal settings produced by the GB-LSHADE achieve the full co-ordination of the protection without any violations for the systems under study. In addition, the numerical simulated results show that the GB-LSHADE supersedes the other viable optimizers reported in specialized literature thru further validations and comprehensive comparisons.