 |
    |
Improving the Performance of a Genetic Algorithm Using a Variable-Reordering Algorithm
Eduardo Rodriguez-Tello1 and Jose Torres-Jimenez2
1LERIA, Université d’Angers, 2 Boulevard Lavoisier, 49045 Angers, France
ertello@info.univ-angers.fr
2ITESM Campus Cuernavaca, Computer Science Department., Av. Paseo de la Reforma 182-A. 62589 Temixco Morelos, Mexico
jtj@itesm.mx
Abstract. Genetic algorithms have been successfully applied to many difficult problems but there have been some disappointing results as well. In these cases the choice of the internal representation and genetic operators greatly conditions the result.
In this paper a GA and a reordering algorithm were used for solve SAT instances. The reordering algorithm produces a more suitable encoding for a GA that enables a GA performance improvement. The attained improvement relies on the building-block hypothesis, which states that a GA works well when short, low-order, highly-fit schemata (building blocks) recombine to form even more highly fit higher-order schemata. The reordering algorithm delivers a representation which has the most related bits (i.e. Boolean variables) in closer positions inside the chromosome.
The results of experimentation demonstrated that the proposed approach improves the performance of a simple GA in all the tests accomplished. These experiments also allow us to observe the relation among the internal representation, the genetic operators and the performance of a GA.
LNCS 3103, p. 102 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004