This study introduces two novel algorithms to address the minimum identifying code problem. The first algorithm integrates the population-based local search (PB-LS) with a repair mechanism into the Rank Genetic Algorithm (Rank GA), enhancing solution quality through localized adjustments. The second algorithm uses the Rank GA with a penalty mechanism to guide the search for feasible solutions. The Rank GA’s ability to escape local optima and refine solutions is a significant advantage, achieved by evaluating and ranking the population before applying genetic operators. This ensures that each genetic operator is uniquely applied based on the individual’s rank, thereby enhancing the search for optimal solutions. We compare the performance of these algorithms against previously published methods, demonstrating their superiority in solution quality and diversity. The results indicate that while Rank GA with PB-LS excels in quickly improving solutions, Rank GA with the penalty mechanism offers a broader search, capturing diverse solutions. The experimental results on various grid sizes highlight the strengths and trade-offs of each approach. This paper provides a comprehensive analysis of the methodologies, experimental results, and comparative performance, concluding with insights into the potential future research directions for larger problem instances with increased computational budgets.