Meta-analysis of metaheuristics: A path to generalizable knowledge

Research on metaheuristics has focused almost exclusively on (novel) algorithmic development and on competitive testing, both of which have been frequently argued to yield very little generalizable knowledge. One way to obtain problem- and implementation-independent insights about metaheuristics is meta-analysis, a systematic statistical examination that combines the results of several independent studies. Meta-analysis is widely used in several scientific domains, most notably the medical sciences (e.g., to establish the efficacy of a certain treatment), but has not yet been applied in operations research.

In order to demonstrate its potential in learning about algorithms, we carried out a meta-analysis 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 a set of predefined eligibility criteria. After sending requests for data to the authors of the eligible studies, results for 25 different implementations of ALNS were collected and analysed using a random-effects model.

The detailed comparison of ALNS with the non-adaptive variant per study and per instance, together with the meta-analysis summary results is publicly available on Mendeley. The data allows to replicate the analysis, to evaluate the algorithms using other metrics, to revisit the importance of ALNS adaptive layer if results from more studies become available, or to simply consult the ready-to-use formulas in META-ANALYSIS.ods to carry out a meta-analysis of any research question.

On average, the addition of an adaptive layer in an ALNS algorithm improves the objective function value by 0.14% (95% confidence interval 0.07 to 0.22%). Although the adaptive layer can (and in a limited number of studies does) have an added value, it also adds considerable complexity and can therefore only be recommended in some very specific situations. A detailed description of the process of identification and selection of studies, the statistical analysis, and the insights gained can be found in:

  • [DOI] R. Turkeš, K. Sörensen, and L. M. Hvattum, “Meta-analysis of metaheuristics: Quantifying the effect of adaptiveness in adaptive large neighborhood search,” European Journal of Operational Research, 2020.
    title={Meta-analysis of metaheuristics: {Q}uantifying the effect of adaptiveness in adaptive large neighborhood search},
    author={Turke{\v{s}}, Renata and S{\"o}rensen, Kenneth and Hvattum, Lars Magnus},
    journal={{European Journal of Operational Research}},

The findings of this meta-analysis underline the importance of evaluating the contribution of metaheuristic components, and of knowledge over competitive testing. Our goal with the aforementioned paper was to promote meta-analysis as a methodology of obtaining knowledge and understanding of metahueristics frameworks, and we hope to see an increase in its popularity in the domain of operations research.

Meta-analysis of metaheuristics: A path to generalizable knowledge