TY - GEN
T1 - An evolutionary local search algorithm for the satisfiability problem
AU - Aksoy, Levent
AU - Gunes, Ece Olcay
PY - 2006
Y1 - 2006
N2 - Satisfiability problem is an NP-complete problem that finds itself or its variants in many combinatorial problems. There exist many complete algorithms that give successful results on hard problems, but they may be timeconsuming because of their branch and bound structures. In this manner, many successful incomplete algorithms are introduced. In this paper, the improvement of incomplete algorithms is of interest and it is shown that the incomplete algorithms can be more efficient if they are equipped with the problem specific knowledge, goal-oriented operators, and knowledge-based methods. In this aspect, an evolutionary local search algorithm is implemented, tested on a randomly generated benchmark that includes test instances with different sizes, and compared with prominent incomplete algorithms. Also, effects of goaloriented genetic operators and knowledge-based methods used in the evolutionary local search algorithm are examined by making comparisons with blind operators and random methods.
AB - Satisfiability problem is an NP-complete problem that finds itself or its variants in many combinatorial problems. There exist many complete algorithms that give successful results on hard problems, but they may be timeconsuming because of their branch and bound structures. In this manner, many successful incomplete algorithms are introduced. In this paper, the improvement of incomplete algorithms is of interest and it is shown that the incomplete algorithms can be more efficient if they are equipped with the problem specific knowledge, goal-oriented operators, and knowledge-based methods. In this aspect, an evolutionary local search algorithm is implemented, tested on a randomly generated benchmark that includes test instances with different sizes, and compared with prominent incomplete algorithms. Also, effects of goaloriented genetic operators and knowledge-based methods used in the evolutionary local search algorithm are examined by making comparisons with blind operators and random methods.
UR - http://www.scopus.com/inward/record.url?scp=33746708723&partnerID=8YFLogxK
U2 - 10.1007/11803089_22
DO - 10.1007/11803089_22
M3 - Conference contribution
AN - SCOPUS:33746708723
SN - 3540367136
SN - 9783540367130
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 185
EP - 193
BT - Artificial Intelligence and Neural Networks - 14th Turkish Symposium, TAINN 2005, Revised Selected Papers
PB - Springer Verlag
T2 - 14th Turkish Symposium on Artificial Intelligence and Neural Networks, TAINN 2005
Y2 - 16 June 2005 through 17 June 2005
ER -