Hyper-Heuristic Based NSGA-III for the Many-Objective Quadratic Assignment Problem

• Bianca N. K. Senzaki UNICENTRO https://orcid.org/0000-0001-6256-1872
• Sandra M. Venske UNICENTRO https://orcid.org/0000-0001-8602-3008
• Carolina P. Almeida UNICENTRO https://orcid.org/0000-0003-4939-6432

Resumo

The Quadratic Assignment Problem (QAP) can be subdivided into different versions, being present in several real-world applications. In this work, it is used a version that considers many objectives. QAP is an NP-hard problem, so approximate algorithms are used to address it. This work analyzes a Hyper-Heuristic (HH) that selects genetic operators to be applied during the evolutionary process. HH is based on the NSGA-III framework and on the Thompson Sampling approach. Our main contribution is the analysis of the use of a many objective algorithm using HH for QAP, as this problem was still under-explored in the context of many objective optimization. Furthermore, we analyze the behavior of operators forward the changes related to HH (TS). The proposal was tested considering 42 instances with 5, 7 and 10 objectives. The results, interpreted using the Friedman statistical test, were satisfactory when compared to the original algorithm (without HH), as well as when compared to algorithms in the literature: MOEA/DD, MOEA/D, SPEA2, NSGA-II and MOEA/D-DRA.

Palavras-chave: NSGA-III, Hyper-Heuristic, Thompson sampling, MaQAP