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.
International Journal of Metaheuristics, 2017 Vol.6 No.3, pp.133 - 159
Received: 14 Nov 2015
Accepted: 03 Sep 2016
Published online: 15 Jun 2017 *