GASAT: A Genetic Local Search Algorithm for the Satisfiability Problem
- 1 June 2006
- journal article
- Published by MIT Press in Evolutionary Computation
- Vol. 14 (2) , 223-253
Abstract
This paper presents GASAT, a hybrid algorithm for the satisfiability problem (SAT). The main feature of GASAT is that it includes a recombination stage based on a specific crossover and a tabu search stage. We have conducted experiments to evaluate the different components of GASAT and to compare its overall performance with state-of-the-art SAT algorithms. These experiments show that GASAT provides very competitive results.Keywords
This publication has 7 references indexed in Scilit:
- Evolutionary Algorithms for the Satisfiability ProblemEvolutionary Computation, 2002
- Hybrid Evolutionary Algorithms for Graph ColoringJournal of Combinatorial Optimization, 1999
- Determining computational complexity from characteristic ‘phase transitions’Nature, 1999
- Asynchronous circuit synthesis with Boolean satisfiabilityIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1995
- Algorithms for the maximum satisfiability problemComputing, 1990
- A Chessboard Coloring ProblemThe College Mathematics Journal, 1989
- A machine program for theorem-provingCommunications of the ACM, 1962