Meta-analysis of metaheuristics: Quantifying the effect of adaptiveness in adaptive large neighborhood search

Research on metaheuristics has focused on (novel) algorithmic development and on competitive testing, both of which have been frequently argued to yield little generalizable knowledge. The main goal of this paper is to promote meta-analysis - a systematic statistical examination that combines the results of several independent studies - as a more suitable way to obtain problem- and implementation-independent insights on metaheuristics. Meta-analysis is widely used in several scientific domains, most notably the medical sciences (e.g., to establish the efficacy of a certain treatment). To the best of our knowledge, this is the first meta-analysis in the field of metaheuristics. To illustrate the approach, we carry out a meta-analysis to gain insights into the importance of the adaptive layer in adaptive large neighborhood search (ALNS). Although ALNS has been widely used to solve a broad range of problems, it has not yet been established whether or not adaptiveness actually contributes to the performance of an ALNS algorithm. A total of 134 studies were identified through Google Scholar or personal e-mail correspondence with researchers in the domain, 63 of which fit our eligibility criteria. After sending requests for data to the authors of the eligible studies, we obtained results for 25 different implementations of ALNS, which were analysed using a random effects model. On average, the addition of an adaptive layer in an ALNS algorithm improves the objective function value by 0.14% (95% confidence interval 0.06-0.21%). Although the adaptive layer can (and in a limited number of studies does) have an added value, it also adds complexity and can therefore only be recommended in some specific situations. These findings underline the importance of evaluating the contribution of metaheuristic components. (C) 2020 Elsevier B.V. All rights reserved.

Automated summary

This paper promotes meta-analysis as a more suitable way to gain problem- and implementation-independent insights on metaheuristics. The research shows that adding an adaptive layer in adaptive large neighborhood search algorithms can improve objective function value slightly, but it also adds complexity and should therefore be recommended in specific situations only.