Combining finite learning automata with GSAT for the satisfiability problem
A large number of problems that occur in knowledge-representation, learning, very large scale integration technology (VLSI-design), and other areas of artificial intelligence, are essentially satisfiability problems. The satisfiability problem refers to the task of finding a satisfying assignment that makes a Boolean expression evaluate to True. The growing need for more efficient and scalable algorithms has led to the development of a large number of SAT solvers. This paper reports the first approach that combines finite learning automata with the greedy satisfiability algorithm (GSAT). In brief, we introduce a new algorithm that integrates finite learning automata and traditional GSAT used with random walk. Furthermore, we present a detailed comparative analysis of the new algorithm's performance, using a benchmark set containing randomized and structured problems from various domains.
learning automata gsat satisfiability problem random walk combinatorial optimization