TY - GEN

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

AU - Sutton, Andrew M.

AU - Whitley, L. Darrell

AU - Howe, Adele E.

PY - 2009/12/31

Y1 - 2009/12/31

N2 - 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.

AB - 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.

KW - Combinatorial optimization

KW - Fitness landscapes

UR - http://www.scopus.com/inward/record.url?scp=72749093323&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=72749093323&partnerID=8YFLogxK

U2 - 10.1145/1569901.1569952

DO - 10.1145/1569901.1569952

M3 - Conference contribution

AN - SCOPUS:72749093323

SN - 9781605583259

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

SP - 365

EP - 372

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

T2 - 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009

Y2 - 8 July 2009 through 12 July 2009

ER -