Dynamic Learning in Hyper-Heuristics to Solve Flowshop Problems

• Lucas Marcondes Pavelski UTFPR https://orcid.org/0000-0002-5622-392X
• Marie-Éléonore Kessaci Univ. Lille https://orcid.org/0000-0002-4372-5162
• Myriam Delgado UTFPR https://orcid.org/0000-0002-2791-174X

Resumo

Hyper-heuristics (HHs) are algorithms suitable for designing heuristics. HHs perform the search divided in two levels: they look for heuristic components in the high level and the heuristic is used, in the low level, to solve a set of instances of one or more problems. Different from offline HHs, hyper-heuristics with dynamic learning select or generate heuristics during the search. This paper proposes a hyper-heuristic associated with a dynamic learning strategy for selecting Iterated Greedy (IG) components. The proposal is capable of selecting appropriate values for six IG components: local search, perturbation, destruction size, neighborhood size, destruction position and local search focus. The proposed HH is tested with six dynamic adaptation strategies: random, ϵ -greedy, probability matching, multi-armed bandit, LinUCB, and Thompson Sampling (TS). The hyper-parameters of each strategy are tuned by irace. As a testbed, we use several instances with four different sizes (20, 50, 100 and 200 jobs) of three different formulations of flowshop problems (permutation, no-wait, no-idle), two distinct objectives (makespan, flowtime), and four processing time distributions (uniform, exponential and job or machine correlated). The results show that different strategies are most suitable for adapting different IG components, TS performs quite well for all components and, except for local search, using adaptation is always beneficial when compared with the IG running with standard parameters.

Palavras-chave: Hyper-heuristic, Iterated Greedy algorithm, Adaptive Components, Flowshop Variants