Improve the Evolutionary Algorithm Search Efficiency with SAT Problem
Rasha Abdelkawy, Walid E. Gomaa · 2012
Since the 1990s, the use of incomplete algorithm for solving the SAT problem has grown quickly. Even though the incomplete algorithm is unable to prove unsatisfiability, but it may find solutions for a satisfying problem quickly. In this paper, the improvement of GA Performance in solving the 3-SAT Problem was our main objective and it is shown that the GA can be more efficient if SAT problem-knowledge is oriented in the GA encoding phase, and the GA operators is tuned according to the encoding phase gained knowledge. In this aspect, a novel evolutionary local search algorithm is developed. In this paper the first Part of our research will be presented, that Part of improve the EAs search Performance with the SAT Problem, that was integrated later in evolutionary local search algorithm. The EAs Enhancement was assessed using a set of well-known benchmarks that includes instances with different sizes, and compared with blind EAs algorithm.