Comparative Analysis of Selection Hyper-Heuristics for Real-World Multi-Objective Optimization Problems

• Published in: Applied sciences 2021-10, Vol.11 (19), p.9153
• Main Authors: de Carvalho, Vinicius Renan, Özcan, Ender, Sichman, Jaime Simão
• Format: Article
• Language: English
• Subjects: Algorithms; artificial intelligence; Benchmarks; Comparative analysis; Computer applications; Distance learning; Domains; Evolutionary algorithms; Genetic algorithms; Heuristic; Immunoglobulin D; Mathematical functions; meta-heuristics; multi-objective optimization; Multiple objective analysis; Mutation; online algorithm selection; Operators (mathematics); Optimization; Problem solving; Statistical tests; World problems
• ISSN: 2076-3417; 2076-3417
• DOI: 10.3390/app11199153

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 hyper-heuristics 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.