 |
    |
ERA: An Algorithm for Reducing the Epistasis of SAT Problems
Eduardo Rodriguez-Tello and Jose Torres-Jimenez
ITESM Campus Cuernavaca
Computer Science Department
Av. Paseo de la Reforma 182-A. Lomas de Cuernavaca
62589 Temixco Morelos, Mexico
{ertello,jtj}@itesm.mx
Abstract. A novel method, for solving satisfiability (SAT) instances is presented. It is based on two components: a) An Epistasis Reducer Algorithm (ERA) that produces a more suited representation (with lower epistasis) for a Genetic Algorithm (GA) by preprocessing the original SAT problem; and b) A Genetic Algorithm that solves the preprocesed instances.
ERA is implemented by a simulated annealing algorithm (SA), which transforms the original SAT problem by rearranging the variables to satisfy the condition that the most related ones are in closer positions inside the chromosome.
Results of experimentation demonstrated that the proposed combined approach outperforms GA in all the tests accomplished.
LNCS 2724, p. 1283 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003