Solving Constraint Satisfaction Problems Using Neural Networks

this paper, we describe GENET, a generic neural network simulator, that can solve general CSPs with finite domains. GENET generates a sparsely connected network for a given CSP with constraints C specified as binary matrices, and simulates the network convergence procedure. In case the network falls into local minima, a heuristic learning rule will be applied to escape from them. The network model lends itself to massively parallel processing. The experimental results of applying GENET to randomly generated, including very tight constrained, CSPs and the real life problem of car sequencing will be reported and an analysis of the effectiveness of GENET will be given. NETWORK MODEL The network model is based on the Interactive Activation model (IA) with modifications to suit the natures of the CSPs as defined at the beginning of this paper. The IA model in its original form can be characterized as weak constraint satisfaction, in which the connections represent the coherence, or compatibility, between the connected nodes. This model was developed for associative information retrieval or pattern matching [11, 12]. However, it is not adequate for solving CSPs in general, for which all the constraints are absolute and none of them should be violated at all. For this purpose, the following modifications have been developed. 1. The nodes in the network are grouped into clusters with each cluster representing a variable in Z, and the nodes in each cluster represent the values that can be assigned to the variable. 2. Only inhibitory connections are allowed. The inhibitory connections represent the constraints that do not allow the connected nodes to be active (i.e. turned on) simultaneously. 3. The nodes in the same cluster compete with each other in convergence cycles. The node..