Constraint Satisfaction Using a Hybrid Evolutionary Hill-Climbing Algorithm that Performs Opportunistic Arc and Path Revision

AAAI 1996

TL;DR

This paper introduces AGSAP, a novel hybrid evolutionary algorithm that significantly speeds up solving complex constraint satisfaction problems (CSPs). By cleverly combining evolutionary search with opportunistic constraint checking (arc and path revision), AGSAP not only finds solutions faster but also more reliably identifies impossible problems, outperforming existing methods on challenging benchmarks.

What Problem Does This Paper Address?

Constraint Satisfaction Problems (CSPs) are ubiquitous in computer science, appearing in areas like scheduling, planning, and resource allocation. The core challenge is finding an assignment of values to variables that satisfies a set of constraints. Many real-world CSPs are computationally expensive to solve, meaning the time required can grow exponentially with the problem size. Traditional methods like hill-climbing can get stuck in "local optima" (suboptimal solutions) and struggle to determine if a problem is fundamentally unsolvable. Evolutionary Algorithms (EAs) offer a robust way to explore large search spaces and escape local optima, but they can be slow and don't inherently identify unsolvable problems. This paper aims to bridge this gap by creating a hybrid EA that leverages the strengths of both evolutionary search and constraint processing techniques to solve CSPs more efficiently and effectively.

Methods

The paper presents AGSAP (A Genetic/Systematic Arc and Path revising hybrid), a sophisticated evolutionary algorithm. Here's a breakdown of its key components:

  • Hybrid Evolutionary Approach: AGSAP uses a population of candidate solutions (chromosomes), where each chromosome represents a potential assignment of values to variables in the CSP.
  • Heuristic Mutation: A "pivot" mechanism guides the mutation operator, focusing changes on specific variables to explore the search space more intelligently.
  • Opportunistic Arc Revision: This is a core innovation. As the EA explores solutions, it uses information about constraint violations to proactively prune values from variable domains that are unlikely to lead to a solution. This is done "opportunistically," meaning it's integrated into the evolutionary process rather than being a separate, expensive step.
  • Opportunistic Path Revision: Building on arc revision, this technique looks at relationships between three variables. If a combination of values for two variables is inconsistent with all possible values of a third variable, it can simplify the constraint between those two variables. This is also performed opportunistically.
  • Family Table: A data structure that tracks relationships between individuals in the population, helping to avoid redundant evaluations and manage the evolutionary process.
  • Linear Rank Selection: A method for choosing parents for the next generation based on their fitness rank, promoting diversity and preventing premature convergence.
  • Breakout Mechanism (Implicit): While not explicitly detailed as a separate component, the hybrid nature and the ability to detect unsolvable problems suggest an implicit mechanism for handling situations where no solution exists, similar to how break-out methods work in pure hill-climbing.

The novelty lies in the interleaving of these constraint processing techniques (arc and path revision) directly within the evolutionary search loop, rather than applying them as a pre-processing step or a separate post-processing phase.

Datasets

The authors evaluated their algorithm on a test suite of 750 randomly generated Constraint Satisfaction Problems (CSPs). These CSPs were generated based on a triple (n, d, t):

  • n: Number of objects (variables) in the CSP (randomly selected between 10 and 20).
  • d: Network density (ratio of constraints to possible constraints).
  • t: Average constraint tightness (ratio of disallowed tuples to total possible tuples).

The density (d) and tightness (t) values were varied across five levels: {0.1, 0.3, 0.5, 0.7, 0.9}. For each of the 25 (d, t) combinations, 30 instances were generated, totaling 750 CSPs. This systematic generation allows for a thorough comparison across different problem characteristics.

Key Insights and Ideas

  • The Power of Opportunism: The most significant insight is that integrating constraint revision techniques opportunistically within an evolutionary search is far more effective than applying them separately or not at all. This "just-in-time" approach significantly prunes the search space without incurring the high computational cost of traditional systematic methods.
  • Detecting Inconsistency is Key: AGSAP's ability to recognize when a CSP is fundamentally unsolvable (arc or path inconsistent) is a major advantage. This prevents wasted computation on problems that have no solution, a common pitfall for pure evolutionary or hill-climbing methods.
  • Synergy Between Arc and Path Revision: While arc revision alone provides substantial benefits, the addition of opportunistic path revision further enhances performance, especially on more complex problems with higher constraint tightness.
  • "Mushy Region" Challenges: The paper highlights that the most difficult CSPs often lie in a "mushy region" or "phase transition" area, where problems are neither trivially solvable nor completely impossible. AGSAP shows particular strength in navigating these challenging instances.

Key Results

AGSAP demonstrated superior performance compared to other algorithms tested:

  • Best Performance: AGSAP achieved the best performance (defined by finding solutions most often and with fewest evaluations) on 11 out of 25 problem classes.
  • Outperforming Others:
    • It consistently outperformed the pure evolutionary algorithm AGS (which only does arc revision) and the Iterative Descent Method (IDM), a well-known hill-climbing algorithm.
  • The impact of opportunistic arc revision was evident when comparing AGS to AGSA (which includes arc revision).
  • The addition of opportunistic path revision in AGSAP further boosted performance over AGSA, especially for CSPs with higher density and tightness.
  • High Success Rate: On CSPs with the highest tightness (t=0.9), AGSAP found solutions 100% of the time for most classes, and 99.6% for the most difficult class.
  • Efficiency: AGSAP often required significantly fewer evaluations to find solutions compared to other methods, particularly as problem difficulty increased.

Limitations and Future Work

  • Limitations:
    • While AGSAP outperforms IDM, IDM sometimes performed fewer evaluations on easier problems, though this difference was often statistical rather than practical.
  • The paper notes that AGSA marginally outperforms AGSAP on certain classes of CSPs where opportunistic path revision plays a less significant role.
  • Future Work: The authors mention ongoing work to integrate other beneficial aspects of systematic search into hybrid EAs and to provide systematic search techniques with insights gained from hybridizing evolutionary search. This suggests a continued effort to find the optimal balance between exploration (evolutionary) and exploitation/deduction (systematic/constraint-based) methods.

Summary updated

BibTeX
@inproceedings{1996constraint,
  title = {{Constraint Satisfaction Using a Hybrid Evolutionary Hill-Climbing Algorithm that Performs Opportunistic Arc and Path Revision}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure