Schemata bandits for MAXSAT

Abstract

In this paper, we propose the use of schemata bandits for optimization. This technique is a subclass of hierarchical bandits where the bandits are schemata. We investigate its use on a benchmark of binary combinatorial optimization problems, the Maximum Satisfiability (MAXSAT) problem. We compare performance with hierarchical Bayesian Opti- mization Algorithms (hBOAs) namely GSAT and WALK- SAT. Results suggest that using a bandit strategy enhances solver performance