Combining local search and fitness function adaptation in a GA for solving binary constraint satisfaction problems
Bart G. W. Craenen, Agoston Endre Eiben, Elena Marchiori, Adri Steenbeek · 2000
this paper we investigate the eectiveness of GAs that combine these two methods, more speci - cally, whether the use of a more involved tness function improves the performance of GLS algorithms for random BCSPs. GLS has been recently used in a hybrid GA [3]; at each generation, the osprings produced by the application of genetic operators are improved by means of a local search procedure. Next, we replace the tness function with the tness function from SAW-ing [2] and de ne an adaptive cost function (resulting in GLS+SAW). We conduct extensive experiments on a large set of standard benchmark instances of random BCSPs. Binary constraint satisfaction problems are de ned by having a set of variables, where each variable has a domain of values, and a set of constraints acting between pairs of variables. A solution of a BCSP is an assignment of values to the variables in such a way that all restrictions imposed by the constraints are satis ed. In this paper we use randomly generated BCSPs that can be de ned by four parameters: the number of variables n, the (uniform) domainsize m, the probability of a constraint between two variables d (density), and the probablity of a con- ict between two values of a constraint t (tightness). The results indicate that the addition of the SAW-ing method does not deteriorate the succes rate (percentage of runs that nd a solution, SR) of GLS, while it decreases the average number of tness evaluations (AES) for some classes of problems. When comparing GLS+SAW with one of the best GA based algorithms, Microgenetic Iterative Descent Method Genetic Algorithm (MIDA) [1], we found that GLS+SAW is slightly better in both SR and AES