Development of a Hybrid System for Solving CSP Problems

Abstract

In the theses, an alternative, hybrid CSP problem solver is presented which integrates a specialized, problem-independent genetic algorithm within the classical backtracking procedure, including the technique of variable domain pruning.
The task of the genetic algorithm is to rapidly bridge larger distances in search space, effectively exploiting analyzed dependences between the variables in the CSP problem. The algorithm is embedded in a backtracking framework that inserts control points in the course of the search process.
The purpose of the control points is to trigger pruning so as to periodically reduce the remaining search space and also to act as milestones to which can be returned if the continued search for a solution turns out to be in vain.
The difference with the classical backtracking procedure is that in each step of the backtracking algorithm not necessarily one, but a predefined number of value assignments is sought by the genetic algorithm, thus stepwise extending the partial solution already obtained. This results in a hybrid system which can be set to operate along a continuous axis between the purely backtracking and purely genetic approach.
The intention of this novel system is to combine the advantages of both approaches so as to attain a problem solver which is capable of seeking solutions non-deterministically in larger search spaces, expecting improvements in time requirements especially for under-constrained problems.

Jan De Beer
may 15th, 2003