Hyper-heuristics using multi-armed bandit models for multi-objective optimization

In this work, we explore different multi-armed bandit-based hyper-heuristics applied to the multi-objective permutation flow shop problem. It is a scheduling problem which has been extensively studied due to its relevance for industrial engineering. Three multi-armed bandit basic formulations are used in the hyper-heuristic selection mechanism: (i) classic, (ii) restless, and (iii) contextual. All the three approaches are considered online selection perturbative hyper-heuristics as they are designed to choose the low level heuristic (crossover and mutation operators) that should be applied to modify each solution during the search process. Performances of the proposed approaches combined with MOEA/DD (Multi-objective Evolutionary Algorithm based on Dominance and Decomposition) are evaluated using the hypervolume indicator and nonparametric statistical tests on a set of 220 problem instances with two and three objectives. The best proposed approach (contextual with a linear realizability assumption) is compared with a stand-alone version of MOEA/DD using the best considered crossover and mutation operator. It is also compared with three state-of-the-art multi-objective algorithms. Results show that this best approach is able to outperform MOEA/DD in scenarios with two and three objectives and by encompassing both, Pareto and decomposition strategies, is competitive with the state of the art in those scenarios. (C) 2020 Elsevier B.V. All rights reserved.