A multilevel learning automata for MAX-SAT

The need to solve optimization problems of unprecedented sizes is becoming a challenging task. Utilizing classical methods of Operations Research often fail due to the exponentially growing computational effort. It is commonly accepted that these methods might be heavily penalized by the NP-Hard nature of the problems and consequently will then be unable to solve large size instances of a problem. Lacking the theoretical basis and guided by intuition, meta-heuristics are the techniques commonly used even if they are unable to guarantee an optimal solution. Meta-heuristics search techniques tend to spend most of the time exploring a restricted area of the search space preventing the search to visit more promising areas thereby leading to solutions of poor quality. In this paper, a multilevel learning automata and a multilevel WalkSAT algorithm are proposed as a paradigm for finding a tactical interplay between diversification and intensification for large scale optimization problems. The multilevel paradigm involves recursive coarsening to create a hierarchy of increasingly smaller and coarser versions of the original problem. This phase is repeated until the size of the smallest problem falls below a specified reduction threshold. A solution for the problem at the coarsest level is generated, and then successively projected back onto each of the intermediate levels in reverse order. The solution at each child level is improved before moving to the parent level. Benchmark including large MAX-SAT test cases are used to compare the effectiveness of the multilevel approach against its single counter part.