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 can be downloaded below. 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.

ZIPdata_per_study_and_instance.zip
ZIPMETA-ANALYSIS.ods

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:

  • R. Turkeš, K. Sörensen, L. M. Hvattum, E. Barrena, H. Chentli, L. Coelho, I. Dayarian, A. Grimault, A. Gullhav, Ç. Iris, M. Keskin, A. Kiefer, R. Lusby, G. Mauri, M. Monroy-Licht, S. Parragh, J. Riquelme-Rodríguez, A. Santini, G. M. Santos Vinicius, and C. Thomas, "Meta-analysis of metaheuristics: Quantifying the effect of adaptiveness in adaptive large neighborhood search," University of Antwerp, Working Paper D/2019/1169/002 , 2019.
    [DOI] [Bibtex]
    @techreport{turkevs2019meta,
    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 and Barrena, Eva and Chentli, Hayet and Coelho, Leandro and Dayarian, Iman and Grimault, Alex and Gullhav, Anders and Iris, {\c{C}}a{\u{g}}atay and Keskin, Merve and Kiefer, Alexander and Lusby, Richard and Mauri, Geraldo and Monroy-Licht, Marcela and Parragh, Sophie and Riquelme-Rodríguez, Juan-Pablo and Santini, Alberto and Santos Vinicius, Gandra Martins and Thomas, Charles},
    institution = {University of Antwerp},
    type={Working Paper D/2019/1169/002},
    year={2019},
    doi={https://hdl.handle.net/10067/1636090151162165141}
    }

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