An efficient heuristic-based evolutionary algorithm for solving constraint satisfaction problems
Vincent W. L. Tam, Peter J. Stuckey · 2002
GENET and EGENET are artificial neural networks with remarkable success in solving hard constraint satisfaction problems (CSPs) such as car sequencing problems. (E)GENET uses the min-conflict heuristic in variable updating to find local minima, and then applies heuristic learning rule(s) to escape the local minima not representing solution(s). In this paper we describe a micro-genetic algorithm (MGA) which generalizes the (E)GENET approach for solving CSPs efficiently. Our proposed MGA integrates the min-conflict heuristic into mutation for reassigning allels (values) to genes (variables). In addition, we derive two methods, based on general principles from evolutionary algorithms, for escaping local minima: population based learning, and look forward. Our preliminary experimental results showed that this evolutionary approach improved on EGENET in solving certain hard instances of CSPs.