Abstract:

When the Optimized Genetic Algorithm based on clustering and ranking selection is  used for the SAT problem, a crossover factor and a mutation factor are imported. Moreover, according to the fitness function and the characteristics of the related issue, threshold δ is adjusted, in order to produce a new population clustering. The algorithm has the effective suppression of delayed convergence, so the satisfiability of formula can be assigned rapidly. Meanwhile,we introduce the DPLL algorithm into the genetic algorithm. It performs the resolution to the variables, and raises the algorithm’s solution efficiency. According to the related experimental data, the performance of the algorithm is obviously better than other algorithms alike, and it has a high reliability.

Key words: 3-SAT problem, genetic algorithm, clustering and ranking selection