TITLE:
A Hybrid Genetic Algorithm with Wisdom of Artificial Crowds for the Boolean Satisfiability Problem—A Machine-Checked, Reproducible Empirical Study on Planted 3-SAT Instances
AUTHORS:
James Godwin
KEYWORDS:
Genetic Algorithm, Wisdom of Artificial Crowds, Boolean Satisfiability, 3-SAT, Planted Instances, Metaheuristics, Memetic Algorithms, Formal Verification, Lean 4, Phase Transition
JOURNAL NAME:
Journal of Applied Mathematics and Physics,
Vol.14 No.11,
November
13,
2026
ABSTRACT: Boolean satisfiability (SAT) is the canonical NP-complete problem and a standard proving ground for heuristic optimizers. This paper studies a hybrid metaheuristic for the 3-SAT variant that couples a Genetic Algorithm (GA) with the Wisdom of Artificial Crowds (WoC) post-processing technique of Yampolskiy and El-Barkouky. Multiple independent GA populations (“crowds”) evolve under diversified parameters and periodically exchange elite individuals through migration; a fitness-weighted consensus then aggregates their best solutions. We evaluate GA, WoC, and the hybrid on 3-SAT instances with 20, 40, and 60 variables, all at a fixed clause-to-variable ratio m/n = 4.0 and generated exclusively in guaranteed-satisfiable (“planted”) mode, so that every instance is satisfiable by construction and the planted assignment serves as a known-correct oracle. Across five runs per configuration, every method attains mean fitness ≥ 0.99 and a 100% success rate under a 0.95 threshold; the WoC consensus attains the highest observed mean fitness at the two larger sizes, though with only five runs per configuration these differences are descriptive rather than statistically tested. We additionally contribute a machine-checked correctness proof, formalized in the Lean 4 theorem prover, of the planted-assignment instance generator used in our harness: any formula the generator emits is satisfiable by construction, with an explicit witness, so its optimal fitness is provably 1. We situate the observed near-perfect results against the random-3-SAT satisfiability phase transition at αc ≈ 4.267 and discuss why planting, together with the chosen density regime, makes the tested instances comparatively easy. Because WoC and the hybrid each evolve five GA populations, they operate under roughly five times the single-population GA’s fitness-evaluation budget, so the GA results should be read as a lower-resource baseline rather than a compute-matched comparison. All code, data, and the verified proof are provided for reproducibility.