The set covering problem is a classical optimization benchmark that finds application in several real-world domains, particularly in line balancing production, crew scheduling, and service installation. The problem consists in finding a subset of columns in a zero-one matrix such that they cover all the rows of the matrix at a minimum cost. In this paper, we present two new approaches for efficiently solving this problem, the first one based on cuckoo search and the second one on black hole optimization. Both are relatively modern bio-inspired metaheuristics that have attracted much attention due to their rapid convergence, easy implementation, and encouraging obtained results. We integrate to the core of both metaheuristics an effective pre-processing phase as well as multiple transfer functions and discretization methods. Pre-processing is employed for filtering the values from domains leading to infeasible solutions, while transfers function and discretization methods are used for efficiently handling the binary nature of the problem. We illustrate interesting experimental results where the two proposed approaches are able to obtain various global optimums for a set of well-known set covering problem instances, outperforming also several recently reported techniques.