Evolving Solutions to Community-Structured Satisfiability Formulas

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

Abstract

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.

Published
2019-07-17
Section
AAAI Technical Track: Heuristic Search and Optimization