Evolving Solutions to Community-Structured Satisfiability Formulas

AAAI 2019 pp. 2346-2353

doi:10.1609/AAAI.V33I01.33012346 /aaai/2019/neumann2019aaai-evolving/

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

PDF AAAI Semantic Scholar

Cite

Text

Neumann and Sutton. "Evolving Solutions to Community-Structured Satisfiability Formulas." AAAI Conference on Artificial Intelligence, 2019. doi:10.1609/AAAI.V33I01.33012346

Markdown

[Neumann and Sutton. "Evolving Solutions to Community-Structured Satisfiability Formulas." AAAI Conference on Artificial Intelligence, 2019.](https://mlanthology.org/aaai/2019/neumann2019aaai-evolving/) doi:10.1609/AAAI.V33I01.33012346

BibTeX

@inproceedings{neumann2019aaai-evolving,
  title     = {{Evolving Solutions to Community-Structured Satisfiability Formulas}},
  author    = {Neumann, Frank and Sutton, Andrew M.},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2019},
  pages     = {2346-2353},
  doi       = {10.1609/AAAI.V33I01.33012346},
  url       = {https://mlanthology.org/aaai/2019/neumann2019aaai-evolving/}
}