Recently, several environmental problems are beginning to affect all aspects of life. For this reason, many governments and international agencies have expressed great interest in using more renewable energy sources (RESs). However, integrating more RESs with distribution networks resulted in several critical problems vis-à-vis the frequency stability, which might lead to a complete blackout if not properly treated. Therefore, this paper proposed a new Under Frequency Load Shedding (UFLS) scheme for islanding distribution network. This scheme uses three meta-heuristics techniques, binary evolutionary programming (BEP), Binary genetic algorithm (BGA), and Binary particle swarm optimization (BPSO), to determine the optimal combination of loads that needs to be shed from the islanded distribution network. Compared with existing UFLS schemes using fixed priority loads, the proposed scheme has the ability to restore the network frequency without any overshooting. Furthermore, in terms of execution time, the simulation results show that the BEP technique is fast enough to shed the optimal combination of loads compared with BGA and BPSO techniques.