The ever increasing presence of renewable distributed generation (DG) in microgrids is imposing new challenges in protection coordination. The high penetration of renewable DG enables microgrids to operate under different topologies, giving rise to bidirectional power flows and in consequence, rendering traditional coordination approaches inappropriate to guarantee network security. This paper proposes an approach for the optimal coordination of directional over-current relays (OCRs) in microgrids that integrate renewable DG and feature several operational modes. As a main contribution, the characteristic curves of directional OCRs are considered to be decision variables, instead of fixing a single type of curve for all relays as considered in previous works. The proposed approach allows for the selection of several IEC and IEEE curves which combination results in the best protection coordination. Several tests were carried out on an IEC benchmark microgrid in order to show the applicability of the proposed approach. Furthermore, a comparison with other coordination approaches evidenced that the proposed approach is able to find lower operation times and, at the same time, guarantee the suitable operation of protections under different condition faults and operational modes.