Enhanced Walksat with Finite Learning Automata For MAX-SAT

Abstract

Researchers in artificial intelligence usually adopt the constraint satisfaction problem and the Satisfiability paradigms as their preferred methods when solving various real worlds decision making problems. Local search algorithms used to tackle different optimization problems that arise in various fields aim at finding a tactical interplay between diversification and intensification to overcome local optimality while the time consumption should remain acceptable.
The Walksat algorithm for the Maximum Satisfiability Problem (MAX-SAT) is considered to be the main skeleton underlying almost all local search algorithms for MAX-SAT. This paper introduces an enhanced variant of Walksat using Finite Learning Automata. A benchmark composed of industrial and random instances is used to compare the effectiveness of the proposed algorithm against state-of-the-art algorithms.