A multilevel synergy Thompson sampling hyper-heuristic for solving Max-SAT

Abstract

Hyper-heuristics are high-level methods, used to solve various optimization problems. Some of them are capable of learning and adapting their behavior throughout the solving process. Selection hyper-heuristics evaluate low-level heuristics and determine which of them to be applied at a given point in the search process. However, it has been shown that the additive learning process becomes inefficient in hard problems where the probability of fitness improvement is less than $\frac{1}{2}$ . Other alternative learning mechanisms have been proposed however they don’t take into account the synergy between the low-level heuristics. Moreover they haven’t been tested on large NP-hard problems. In this work, we propose a new hyper-heuristic which we called the Multilevel Synergy Thompson Sampling Hyper-Heuristic. The proposed method includes both the probabilistic learning mechanism and the multilevel paradigm. The latter refers to the process of creating hierarchically smaller sub-problems from large problem instances. The proposed hyper-heuristic is applied on very large industrial Max-SAT instances from the latest Max-SAT competition. The numerical results are promising and demonstrate the benefits of our method. The proposed method outperforms the other four types of hyper-heuristics: Random, Choice Function, Stochastic Choice Function and the simple Thompson Sampling Hyper-Heuristics.