A multilevel hyper-heuristic for solving Max-SAT. (2017)

• Record Type: Journal Article
• Authors: Lassouaoui, Mourad; Boughaci, Dalila; Benhamou, Belaid
• Is Part Of: International journal of metaheuristics. Volume 6:Number 3(2017)
• Page Start: 133
• Page End: 159
• Publication Date: 2017
• Subjects: hyper-heuristic -- Max-SAT -- multilevel paradigm; Heuristic algorithms -- Periodicals; 006.3105
• Languages: English
• ISSNs: 1755-2176

Abstract

A hyper-heuristic is a high-level method that manages a set of low-level heuristics to solve various problems in a problem-independent manner. In this paper, we propose a new selection hyper-heuristic with the multilevel paradigm. The multilevel paradigm refers to the process of dividing large problems into sub-problems. Each sub-problem is being solved to reach an optimal solution by using the resulting solution from a previous level as a starting solution at the next level. The selection strategy chooses the adequate low-level heuristic at any iteration during the search. For analysis purposes, several variants of hyper-heuristics are implemented and Max-SAT is used as the test bed. The experimental results revealed that the multilevel paradigm together with a new hybrid-heuristic selection mechanism provides a substantial performance improvement. A comparison with two known state of the art algorithms that are GSAT and WALKSAT is given to further show the efficiency of our method.