Metaheuristic Approaches for the Satisfiability Problem (SAT): A Systematic Review and Comparative Study with Modern SAT Solvers

The Boolean Satisfiability Problem is a central challenge in artificial intelligence and combinatorial optimization, with applications in circuit verification, planning, and bioinformatics. This study makes two main contributions: a systematic review of metaheuristic approaches conducted under the Preferred Reporting Items for Systematic Reviews and Meta-Analyses (PRISMA) protocol, and a comparative evaluation of 11 algorithms. The considered methods include genetic algorithms, genetic algorithms with stepwise adaptation of weights, hybrid grey wolf genetic algorithms, genetic-based local search, population-based simulated annealing, dynamic clause weighting local search, stochastic local search, phase transition-based local search, random walk with local (1 + 1) evolutionary algorithm, improved adaptive genetic algorithm, and artificial bee colony. The evaluation relies on multiple criteria, including solution quality, robustness, success rate with confidence intervals, computational efficiency, and scalability across the benchmark families UF20 to UF250, complemented by additional benchmarks from the SAT Challenge Random Track (2018) and newly generated random 3-SAT instances. The results show that Genetic Algorithm, phase transition-based local search, dynamic clause weighting local search, genetic-based local search, random walk with local (1+1) Evolutionary Algorithm, and Artificial Bee Colony provide the most robust performance, maintaining a balance between exploration and exploitation. Beyond comparisons within metaheuristics, the study also examines how bio-inspired approaches compare with modern SAT solvers based on conflict-driven clause learning and stochastic local search across different problem scales. By contrast, highly specialized variants, such as genetic algorithms with stepwise adaptation of weights, population-based simulated annealing, hybrid grey wolf genetic algorithms, and improved adaptive genetic algorithms, degrade significantly on larger benchmarks. Overall, this study consolidates the strengths and weaknesses of metaheuristics and outlines future directions for adaptability, hybridization with machine learning, and scalable computations.