Comparative analysis of selection hyper-heuristics for real-world multi-objective optimization problems

de Carvalho, Vinicius Renan; Özcan, Ender; Sichman, Jaime Simão

Abstract

As exact algorithms are unfeasible to solve real optimization problems, due to their computational complexity, meta-heuristics are usually used to solve them. However, choosing a meta-heuristic to solve a particular optimization problem is a non-trivial task, and often requires a time-consuming trial and error process. Hyper-heuristics, which are heuristics to choose heuristics, have been proposed as a means to both simplify and improve algorithm selection or configuration for optimization problems. This paper novel presents a novel cross-domain evaluation for multi-objective optimization: we investigate how four state-of-the-art online hyper-heuristics with different characteristics perform in order to find solutions for eighteen real-world multi-objective optimization problems. These hyperheuristics were designed in previous studies and tackle the algorithm selection problem from different perspectives: Election-Based, based on Reinforcement Learning and based on a mathematical function. All studied hyper-heuristics control a set of five Multi-Objective Evolutionary Algorithms (MOEAs) as Low-Level (meta-)Heuristics (LLHs) while finding solutions for the optimization problem. To our knowledge, this work is the first to deal conjointly with the following issues: (i) selection of meta-heuristics instead of simple operators (ii) focus on multi-objective optimization problems, (iii) experiments on real world problems and not just function benchmarks. In our experiments, we computed, for each algorithm execution, Hypervolume and IGD+ and compared the results considering the Kruskal–Wallis statistical test. Furthermore, we ranked all the tested algorithms considering three different Friedman Rankings to summarize the cross-domain analysis. Our results showed that hyper-heuristics have a better cross-domain performance than single meta-heuristics, which makes them excellent candidates for solving new multi-objective optimization problems.

Citation

de Carvalho, V. R., Özcan, E., & Sichman, J. S. (2021). Comparative analysis of selection hyper-heuristics for real-world multi-objective optimization problems. Applied Sciences, 11(19), Article 9153. https://doi.org/10.3390/app11199153

• Journal Article Type: Article
• Acceptance Date: Sep 20, 2021
• Online Publication Date: Oct 1, 2021
• Publication Date: Oct 1, 2021
• Deposit Date: Dec 2, 2021
• Publicly Available Date: Dec 7, 2021
• Journal: Applied Sciences (Switzerland)
• Electronic ISSN: 2076-3417
• Publisher: MDPI
• Peer Reviewed: Peer Reviewed
• Volume: 11
• Issue: 19
• Article Number: 9153
• DOI: https://doi.org/10.3390/app11199153
• Keywords: Fluid Flow and Transfer Processes; Computer Science Applications; Process Chemistry and Technology; General Engineering; Instrumentation; General Materials Science
• Public URL: https://nottingham-repository.worktribe.com/output/6847012
• Publisher URL: https://www.mdpi.com/2076-3417/11/19/9153