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 12. 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.
