|
CSP format : variables, associated (finite) domains and constraints on the variables. Many solvers already exist for the CSP over finite domains, like GNU-Prolog (Codognet and Diaz, 2001) or ILOG Solver (Puget, 1994). Departing from classical constraint solving techniques, adaptive search is a heuristic algorithm, based on the the local search family (Aarts and Lenstra, 1997). These algorithms have already proven their efficiency on combinatorial problems such as the boolean satisfaction (SAT), the travelling salesman problem (TSP), job-shops, vehicule routing, etc. They basically rely on the idea of collecting information on the quality of the current configuration (assignment of variables to values of their domains), exploring a neighbourhood of slightly modified configurations and moving to the most promising one. Simulated annealing, genetic algorithms, Tabu method or the Greedy SAT algorithm are well-known instances of methods based on the local search paradigm. In adaptive search, every constraint is represented by an error function on the variables, which gives a measure of >how much< the constraint is violated. For instance, if the constraint is To avoid being trapped in local minima, the algorithm includes an adaptive memory, such as in Tabu Search : if a variable leads to a local minimum, it is marked Tabu and left out of the search for a fixed number of iterations. This number, the Tabu length, is an important parameter for the algorithm, intuitively it measures the stubbornness of the algorithm. A high value (the highest value being the number of variable) means that all the paths will be explored as long as it is possible. A low value means that the algorithm leaves quickly the paths that seem not promising. The user can fix the Tabu length according to his own needs : for instance, when his CSP has no solution, the Tabu length should be high. Local minima for all the variables can also be met. All the variables will then successively be marked Tabu. In this case the algorithm is re-started randomly. There are many ways to reset : one can start again from nothing, all the variables at random. Another possibility is to reset only some variables (as suggested Gomes et al., 2000). Experimentally, a good compromise is to reset the Tabu variables randomly.
4.2 Algorithm
|
, we could choose as a cost function 
for variables 
and 
, and 
for the other variables. Combining these functions in a global cost function (for instance by summing them), we can tell both the quality of the current variable-value configuration, and the cost of each variable regarding the constraints. Starting from a random assignment, the iterative process computes the costs of each variable, finds the worst variable (i.e. the most expensive one), searches its domain to find a better value that minimizes global cost, replaces it.