TY - GEN
T1 - An enhanced fuzzy-genetic algorithm to solve satisfiability problems
AU - Villamizar, José Francisco Saray
AU - Badr, Youakim
AU - Abraham, Ajith
PY - 2009
Y1 - 2009
N2 - 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 [1] 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.
AB - 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 [1] 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.
UR - http://www.scopus.com/inward/record.url?scp=69649092586&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=69649092586&partnerID=8YFLogxK
U2 - 10.1109/UKSIM.2009.106
DO - 10.1109/UKSIM.2009.106
M3 - Conference contribution
AN - SCOPUS:69649092586
SN - 9780769535937
T3 - 11th International Conference on Computer Modelling and Simulation, UKSim 2009
SP - 77
EP - 82
BT - 11th International Conference on Computer Modelling and Simulation, UKSim 2009
T2 - 11th International Conference on Computer Modelling and Simulation, UKSim 2009
Y2 - 25 March 2009 through 27 March 2009
ER -