Article Preview
TopIntroduction
The constraint satisfaction problems (CSPs) formalism allow formulating and resolving many problems in artificial intelligence and operational research such as scheduling problems, resource allocation, frequency allocation, Vehicle routing problem etc.
A CSP is a triple (X, D, C) where.
To resolve a CSP, we need an instantiation of all variables with values from their respective domains. This instantiation should satisfy all constraints to get a good solution. To find a CSP solution is often a hard task. In fact, with some real life problems, the solution is either too expensive to get or even nonexistent. In addition, in some cases we need to express preferences and evolution of constraints in time. For such tasks, we should find an instantiation that maximizes the number of constraints. This CSP extension, said Max-CSPs, is the topic of this paper.
Max CSPs have been dealt with by complete or incomplete methods. Complete methods such as forward checking algorithm (Freuder & Wallace, 1992) and branch and bound algorithms (Meseguer, 1997; Wallace, 1996) are shown to be able to achieve an optimal solution. Nevertheless, the combinatorial explosion is an obstacle faced by theses systematic search methods. In fact, to ensure that the solution found is the optimal, systematic search algorithms would need to exhaust the entire problem space to establish that fact (Lau & Tsang, 2001).
However, incomplete ones are not able to guarantee that a solution can be found, and neither can they prove that a solution does not exist. They forgo completeness for efficiency. Many works such as (Langley, 1992) demonstrated on several large problems that what complete search algorithms fail to solve, incomplete ones efficiently conquer.
In fact, incomplete methods such as Simulated Annealing, Genetic Algorithms and Tabu Search allow escaping from local optima. Moreover, another incomplete but distributed method known as Distributed Simulated Annealing (DSA) has been shown to be efficiently applied to static Max-CSP, dynamic Max-CSP (Ghédira, 1994), Resource allocation problem (Bouamama & Ghedira, 2006). Distributing the centralized SA outperformed the solution's quality. Genetic Algorithm (GA) is a further well known incomplete method. It was frequently used in hard optimization problems (Tsang, EPK. 1993) solving multiprocessor scheduling problems (Bouamama & Ghedira, 2006). Similarly to distributing DSA, Centralized Genetic Algorithms (CGAs), known to be expensive, was also distributed to get better performances. The result was the Distributed Guided Genetic Algorithm (DGGA) (Jlifi & Ghédira, 2003). DGGA was enhanced by a new parameter called guidance operator. The latter allowed not only diversification but also an escaping from local optima. The result is referred to as Distributed Double Guided Genetic Algorithm (D2G2A) (Bouamama & Ghedira, 2008). Moreover, a further Improvement was performed through a Dynamic aspect in D3G2A (Bouamama & Ghedira, 2006; Zaier, Bouamama, & Ghédira, 2007).