Copyright ACM, 2000
Next: Introduction


An Adaptive Evolutionary Algorithm for the Satisfiability Problem (*)

Claudio Rossi (+)
Elena Marchiori
Joost N. kok
Dept. of Computer Science
Faculty of Science
LIACS
Ca' Foscari Univ. of Venice
Free University Amsterdam
Leiden University
Via Torino 155
De Boelelaan 1081a
P.O. Box 9512
30173 Mestre-Venezia
1081 HV Amsterdam
2300 RA Leiden
Italy
The Netherlands
The Netherlands
rossi@dsi.unive.it
elena@cs.vu.nl
joost@liacs.nl

Abstract:

This paper introduces an adaptive heuristic-based evolutionary algorithm for the Satisfiability problem (SAT). The algorithm uses information about the best solutions found in the recent past in order to dynamically adapt the search strategy. Extensive experiments on standard benchmark problems are performed in order to asses the effectiveness of the algorithm. The results of the experiments indicate that this technique is rather successful: it improves on previous approaches based on evolutionary computation and it is competitive with the best heuristic algorithms for SAT.

Categories and Subject Descriptors

G.1.6 [Mathematics of Computing]: Optimization-Global optimization; I.2.8 [Artificial Intelligence]: Problem Solving, Control Methods, and Search-Heuristic methods

General Terms

Algorithms, Experimentation



Notes

(+) This work has been done while the author was visiting LIACS.

(*) Copyright notice - Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy other wise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
SAC 2000 Como, Italy
Copyrigth 2000 ACM 0-89791-88-6/97/05 .. $5.00



Next: Introduction
Claudio Rossi
1999-11-30

Copyright 2000 ACM

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and or fee.
SAC 2000 March 19-21 Como, Italy
(c) 2000 ACM 1-58113-239-5/00/003>...>$5.00