A Hybrid Genetic Algorithm for the Satisfiability Problem

摘要

This paper introduces a hybrid genetic algorithm for the satisfiability problem (SAT). This algorithm, called GASAT, incorporates local search within the genetic framework. GASAT relays on a problem specific crossover operator to create new solutions, that are improved by a tabu search procedure. The performance of GASAT is assessed using a set of well-known benchmarks. Comparisons with state-of-the-art SAT algorithms show that GASAT gives competitive results.