GENET: A Connectionist Architecture for Solving Constraint Satisfaction Problems by Iterative Improvement

Andrew J. Davenport, Edward P. K. Tsang, Chang J. Wang, Kangmin ZhuAAAI 1994

Introduction

Constraint Satisfaction Problems (CSPs) are fundamental to artificial intelligence, encompassing diverse applications from scheduling to map coloring. While iterative improvement techniques like hill-climbing are effective for large, relatively unconstrained problems, they often struggle with "hard" CSPs where search spaces are riddled with local minima. This paper introduces GENET, a connectionist architecture designed to overcome these challenges by combining parallel iterative improvement with a dynamic learning rule to escape local optima.

The GENET Architecture

GENET represents a CSP as a network of nodes organized into clusters. Each cluster corresponds to a variable, and each node within a cluster represents a possible value (label). The network operates under the constraint that only one node per cluster can be active at any time.

Nodes are linked by inhibitory connections with negative weights if their respective values conflict. The system updates clusters in parallel using a "modulator" that selects the value receiving the minimum inhibition from other active nodes.

The core innovation of GENET is its learning rule. When the network reaches a local minimum—a state where no single change can reduce conflicts—it increases the weights of the violated constraints. This process effectively "fills in" the local minimum, flattening the energy landscape and forcing the search into new regions. Furthermore, GENET supports complex logic through "constraint nodes," allowing it to handle non-binary constraints like atmost(N, Variables, Value), which are critical for real-world industrial problems.

Experimental Evaluation

The authors evaluated GENET against several challenging benchmarks, including hard graph coloring instances and the car sequencing problem—a complex industrial benchmark involving assembly line scheduling with strict capacity constraints.

Results and Discussion

GENET demonstrated significant performance gains over traditional symbolic solvers. In graph coloring tasks, GENET outperformed GSAT in both time and the number of repairs required. For a 250-node, 29-color problem, GENET converged in 1.1 hours, whereas GSAT required 1.8 hours and significantly more repair operations.

Table 1: Performance of GENET on hard graph coloring instances.

The most notable results occurred in the car sequencing domain. While standard logic programming tools like CHIP struggled to solve many 200-car test cases within an hour, the GENET3 variant achieved a 100% success rate. This improvement was largely due to the introduction of a probability parameter ($p_{sw}$) for "sideways moves," which prevents the algorithm from stalling on cost plateaus.

Table 2: Comparison of GENET and GENET3 on the car sequencing benchmark across different utilization levels.

Key Insights

  • Efficient Landscapes: The learning rule acts as a mechanism to flatten the search space, ensuring the algorithm does not remain trapped in suboptimal states.
  • Local vs. Global Repairs: GENET’s focus on local repairs proves more computationally efficient for structured problems than the global search strategies employed by solvers like GSAT.
  • Hardware Potential: Designed for VLSI implementation, GENET’s parallel nature suggests that future hardware realizations could reduce search times from hours to seconds.

Conclusion and Future Work

GENET represents a powerful bridge between connectionist speed and the robustness required for hard CSPs. However, as an iterative improvement method, it remains "incomplete"—it cannot prove a problem is unsatisfiable. Future work involves refining parameter tuning for $p_{sw}$ across different problem types and moving from software simulations to dedicated hardware implementations to realize the architecture's full speed potential.

Summary updated

BibTeX
@inproceedings{davenport1994genet,
  author = {Andrew J. Davenport and Edward P. K. Tsang and Chang J. Wang and Kangmin Zhu},
  title = {{GENET: A Connectionist Architecture for Solving Constraint Satisfaction Problems by Iterative Improvement}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure