A GA Approach To Constraint Satisfaction Problems
Terry Warwick · 1995
Genetic algorithms (GAs) are generally considered to be unsuitable for constraint based problems, particularly those with tight constraints. Some researchers have developed specialised techniques for solving specific groups of problems. In this research we contribute to this work by developing a flexible generic GA which can exploit problem constraints. The GA has been designed to tackle and exploit an important class of optimisable constraint based problems, namely partial constraint satisfaction problems (PCSPs). This new GA is a strategy which incorporates an adaptive template type crossover and hill-climbing component (HC). This GA strategy which we call GAcSP, combines the robust global power of the GA with the specialist power of the HC to form a powerful combination the GA finds the hills and the HC climbs them. A crossover operator has been developed which has a learning capacity which can exploit problem constraints. The ability of GAcSP is demonstrated by tackling two distinct problems, namely the processors configuration problem and the car sequencing problem. Both problems are NP-hard, and represent a serious challenge to GAcSP. Results from these experiments show that GAcSP can out-perform specialised approaches, is not deterred by problem size, and not limited to tackling solvable problems only. The GAcSP strategy provides an effective tool for tackling a class of PCSPs. The power of GAcSP is due to the optimal balance of work between GA and HC by exploiting the abilities of both components. This synergistic combination between GA and HC gives the GAcSP flexible powers in tackling larger problems.