A polynomial time computation of the exact correlation structure of k-satisfiability landscapes

Andrew M. Sutton, L. Darrell Whitley, Adele E. Howe

Research output: Chapter in Book/Report/Conference proceedingConference contribution

27 Scopus citations

Abstract

The autocorrelation function and related correlation length are statistical quantities that capture the ruggedness of the fitness landscape: a measure that is directly related to the hardness of a problem for certain heuristic search algorithms. Typically, these quantities are estimated empirically by sampling along a random walk. In this paper, we show that a polynomial-time Walsh decomposition of the k-satisfiability evaluation function allows us to compute the exact autocorrelation function and correlation length for any given k-satisfiability instance. We also use the decomposition to compute a theoretical expectation for the autocorrelation function and correlation length over the ensemble of instances generated uniformly at random. We find that this expectation is invariant to the constrainedness of the problem as measured by the ratio of clauses to variables. However, we show that filtered problems, which are typically used in local search studies, have a bias that causes a significant deviation from the expected correlation structure of unfiltered, uniformly generated problems.

Original languageEnglish (US)
Title of host publicationProceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009
Pages365-372
Number of pages8
DOIs
StatePublished - Dec 31 2009
Event11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009 - Montreal, QC, Canada
Duration: Jul 8 2009Jul 12 2009

Publication series

NameProceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009

Other

Other11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009
CountryCanada
CityMontreal, QC
Period7/8/097/12/09

Keywords

  • Combinatorial optimization
  • Fitness landscapes

Fingerprint Dive into the research topics of 'A polynomial time computation of the exact correlation structure of k-satisfiability landscapes'. Together they form a unique fingerprint.

Cite this