The integration of distributed generators (DGs) into electrical networks has become more prevalent due to their operational benefits. However, switching the DG on or off changes the fault current’s magnitude and direction, making an adaptive protection scheme (APS) necessary. This paper proposes a novel APS that optimally coordinates overcurrent relays, including Distance and directional overcurrent relays (D&DOCRs), at each transmission line’s ending near and far. This coordination problem is highly constrained and complex, involving coordinating primary and backup relays between DOCRs pairs and D&DOCRs pairs. To solve this optimization problem, the paper implements a modified Honey Badger algorithm (HBA), called CLHBA, that uses chaotic initialization and leader-based mutation selection. The proposed scheme is adaptable to changes in the electrical network’s state caused by switching the DGs on or off. The paper tests the proposed scheme on IEEE 8-bus and 14-bus distribution systems to demonstrate its ability to solve coordination problems.