Title: A multilevel hyper-heuristic for solving Max-SAT

Authors: Mourad Lassouaoui; Dalila Boughaci; Belaid Benhamou

Addresses: LRIA, USTHB, BP 32 El-ALIA Beb-Ezzouar, Algiers 16111, Algeria ' LRIA, USTHB, BP 32 El-ALIA Beb-Ezzouar, Algiers 16111, Algeria ' LSIS, AIX-Marseille University, Marseille, France

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.

Keywords: hyper-heuristic; Max-SAT; multilevel paradigm.

DOI: 10.1504/IJMHEUR.2017.085123

International Journal of Metaheuristics, 2017 Vol.6 No.3, pp.133 - 159

Received: 14 Nov 2015
Accepted: 03 Sep 2016
Published online: 12 Jul 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article