This study investigates the combination of binarization methods and chaotic maps within the Reptile Search Algorithm to address binary combinatorial optimization challenges, specifically concentrating on the Set Covering Problem. Binarization in metaheuristics is critical for transforming continuous search spaces into discrete ones, which is essential for efficiently solving binary problems. We investigate the impact of chaotic maps, precisely the chaotic map type “sine”, to enhance the stochastic components of metaheuristics, facilitating robust broadening and refinement of the search space. Our experimental analysis compares the performance of the Reptile Search Algorithm, enhanced with different binarization strategies, in comparison to established metaheuristics like the well-known Particle Swarm Optimization and the popular Grey Wolf Optimizer. The results demonstrate that the Reptile Search Algorithm with elitist binarization strategies, particularly when integrated with chaotic maps, significantly outperforms other algorithms to achieve near-optimal solutions with minimal variance. These findings highlight the effectiveness of sophisticated binarization strategies and the potential of chaotic maps to refine the search capabilities of metaheuristics in complex optimization scenarios.