An Enhanced Fuzzy-Genetic Algorithm to Solve Satisfiability Problems

摘要

The satisfiability is a decision problem that belongs to NP-complete class and has significant applications in various areas of computer science. Several works have proposed high-performance algorithms and solvers to explore the space of variables and look for satisfying assignments. Pedrycz, Succi and Shai (2002) have studied a fuzzy-genetic approach which demonstrates that a formula of variables can be satisfiable by assigning Boolean variables to partial true values between 0 and 1. In this paper we improve this approach by proposing an improved fuzzy-genetic algorithm to avoid undesired convergence of variables to 0.5. The algorithm includes a repairing function that eliminates the recursion and maintains a reasonable computational convergence and adaptable population generation.Implementation and experimental results demonstrate the enhancement of solving satisfiability problems.