A New Hyper-Heuristic Based on a Restless Multi-armed Bandit for Multi-objective Optimization
Richard A. Gonçalves, Carolina Paula de Almeida, Sandra M. Venske, Myriam Delgado, Aurora Pozo · 2017
Hyper-Heuristic is a high-level methodology that automates the selection or generation of other heuristics. Despite their success, there are only a few hyper-heuristics developed for multi-objective optimization. Our approach, namely MOEA/DRMAB, is a multi-objective selection hyper-heuristic that expands the MOEA/D framework. It uses an innovative Restless Multi- Armed Bandit (MAB) to determine the low level heuristic (Differential Evolution mutation strategy) that should be applied to each individual during a MOEA/D execution. The advantage of using a Restless MAB is that it is able to better model and tackle the operators dynamic behavior. We tested MOEA/D-RMAB in a well established set of 10 instances from the CEC 2009 MOEA Competition. Pareto compliant indicators and Mann- Whitney statistical tests are applied to evaluate the algorithm performances. Results show that MOEA/D-RMAB outperforms some important multi-objective optimization algorithms, including MOEA/D-FRRMAB (a prominent MOEA/D variation which uses a classical MAB operator selection), becoming a promising multi-objective Hyper-Heuristic.