Evolving Solutions to Community-Structured Satisfiability Formulas


  • Frank Neumann The University of Adelaide
  • Andrew M. Sutton University of Minnesota Duluth




We study the ability of a simple mutation-only evolutionary algorithm to solve propositional satisfiability formulas with inherent community structure. We show that the community structure translates to good fitness-distance correlation properties, which implies that the objective function provides a strong signal in the search space for evolutionary algorithms to locate a satisfying assignment efficiently. We prove that when the formula clusters into communities of size sω(logn) ∩O(nε/(2ε+2)) for some constant 0 <ε< 1, and there is a nonuniform distribution over communities, a simple evolutionary algorithm called the (1+1) EA finds a satisfying assignment in polynomial time on a 1−o(1) fraction of formulas with at least constant constraint density. This is a significant improvement over recent results on uniform random formulas, on which the same algorithm has only been proven to be efficient on uniform formulas of at least logarithmic density.




How to Cite

Neumann, F., & Sutton, A. M. (2019). Evolving Solutions to Community-Structured Satisfiability Formulas. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 2346-2353. https://doi.org/10.1609/aaai.v33i01.33012346



AAAI Technical Track: Heuristic Search and Optimization