@article{Neumann_Sutton_2019, title={Evolving Solutions to Community-Structured Satisfiability Formulas}, volume={33}, url={https://ojs.aaai.org/index.php/AAAI/article/view/4074}, DOI={10.1609/aaai.v33i01.33012346}, abstractNote={<p>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 <em>s</em> ∈ <em>ω</em>(log<em>n</em>) ∩<em>O</em>(<em>n</em><sup><em>ε/</em>(2<em>ε</em>+2)</sup>) for some constant 0 <em><ε<</em> 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−<em>o</em>(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.</p>}, number={01}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Neumann, Frank and Sutton, Andrew M.}, year={2019}, month={Jul.}, pages={2346-2353} }