A Tractable Walsh Analysis of SAT and its Implications for Genetic Algorithms

AAAI 1998

TL;DR

This paper introduces a novel Walsh analysis for MAXSAT problems, demonstrating that the complex interactions within these problems are surprisingly structured and can be computed efficiently. This tractability reveals why standard genetic algorithms struggle with MAXSAT, as the inherent structure leads to misleading "schema averages" that don't effectively guide search towards optimal solutions.

What Problem Does This Paper Address?

Boolean Satisfiability (SAT) is a foundational NP-Complete problem. While solving SAT involves finding a satisfying assignment, many optimization techniques, including genetic algorithms (GAs), are better suited for problems with a graded objective function. MAXSAT, which aims to maximize the number of satisfied clauses, provides such a graded objective. However, understanding the underlying structure of MAXSAT functions to effectively guide optimization algorithms like GAs has been challenging. Specifically, GAs rely on "schema theory" to understand how to allocate search effort, but computing the fitness of these schemas (sub-partitions of the search space) is typically computationally intractable for large problems. This paper addresses the question of whether the structure of MAXSAT problems, when viewed through the lens of Walsh analysis, can explain the difficulties GAs face and offer a more efficient way to analyze these problems.

Methods

The core of this paper is the application of Walsh analysis to MAXSAT problems. Walsh transforms are a mathematical tool analogous to Fourier transforms, used to decompose a function into its constituent linear and nonlinear interactions, represented by Walsh coefficients.

  • Walsh Transform: The paper defines the Walsh transform and its coefficients ($w_j$), explaining that $w_j$ measures the contribution of the interaction corresponding to the set bits in index $j$.
  • Tractability for MAXSAT: The key innovation is showing that for MAXSAT problems, the number of nonzero Walsh coefficients is significantly restricted. This is achieved by analyzing the structure of individual clauses and then summing the Walsh coefficients of these clauses.
  • Clause Analysis (Lemma 1): For a single disjunctive clause over $K$ variables, the paper derives a formula for its Walsh coefficients. Crucially, it shows that only a specific set of coefficients are nonzero, directly related to the negated variables in the clause.
  • General MAXSAT (Theorem 1): This lemma is extended to handle MAXSAT problems with multiple clauses and extraneous variables. The theorem proves that nonzero Walsh coefficients for a clause only occur when the index $j$ is a subset of the mask $m_i$ representing the variables in that clause. This drastically limits the number of potentially nonzero coefficients.
  • Schema Averages: The paper connects Walsh coefficients to schema averages, showing that the average fitness of a schema can be computed as a sum of Walsh coefficients.

Datasets

Not discussed in the paper. The paper uses theoretical examples and discusses the properties of MAXSAT problems in general, rather than evaluating on specific datasets.

Key Insights and Ideas

  • Structured Nonlinearity in MAXSAT: The most surprising finding is that MAXSAT functions, despite being NP-Complete, possess a highly structured and tractable form of nonlinearity when analyzed with Walsh transforms. This structure is not random but directly tied to the clause composition.
  • Efficient Computation: The paper demonstrates that all Walsh coefficients for a MAXSAT problem can be computed in time linear to the number of clauses, which is a significant result given the NP-Completeness of MAXSAT. This implies that if P ≠ NP, simply knowing the exact interactions of a function is insufficient to find its global optimum efficiently.
  • GA Deception in MAXSAT: The structured, limited nature of Walsh coefficients in MAXSAT directly explains why GAs struggle. Schema averages, which GAs use to guide search, are formed by sums of these coefficients. When coefficients are limited and often small (compared to $w_0$, the average fitness), schema averages become very similar, making it difficult for GAs to distinguish between good and bad search directions.
  • $w_0$ Dominance: The average fitness ($w_0$) of a MAXSAT problem is often much larger than the magnitudes of the nonlinear Walsh coefficients. This means that low-order schema averages are heavily dominated by the overall average fitness, providing little discriminatory information for GAs.

Key Results

  • Tractable Walsh Coefficient Computation: All Walsh coefficients for an L-bit MAXSAT problem with C clauses can be computed in $O(C)$ time, assuming the maximum clause length $K$ is a bounded constant.
  • Limited Nonzero Coefficients: For a MAXSAT problem, the number of nonzero Walsh coefficients is bounded by $2KC$, where $K$ is the maximum number of variables in a clause. This is a significant reduction from the $2^L$ possible coefficients.
  • Order of Nonlinearity: The maximum order of bitwise nonlinearity in a MAXSAT problem is limited by the length of the longest clause.
  • Schema Average Similarity: Due to the limited and often small magnitudes of nonlinear Walsh coefficients, schema averages for MAXSAT problems tend to be very similar, especially for low-order schemata. This similarity makes them unreliable for guiding GA search.

Limitations and Future Work

  • Generalization: The authors caution that their findings are specific to MAXSAT problems and their standard evaluation function. Modifying the evaluation function could lead to different Walsh coefficient structures and potentially different GA performance.
  • P ≠ NP Implication: The tractability of computing Walsh coefficients for MAXSAT, while proving that this information alone isn't sufficient for polynomial-time optimization, reinforces the P ≠ NP conjecture.
  • Future Work: The paper suggests exploring the relationship between Walsh analysis and polynomial-time approximation algorithms for NP-Complete problems. Further investigation into how different evaluation functions affect GA performance through Walsh analysis is also implied. The authors also note that the limited information in low-order schemata might make MAXSAT unsuitable for traditional GAs, but this doesn't preclude GAs from being effective on other problem types.

Summary updated

BibTeX
@inproceedings{1998tractable,
  title = {{A Tractable Walsh Analysis of SAT and its Implications for Genetic Algorithms}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1998},
}

Loading related content...

Figure