On Constructing Ensembles for Combinatorial Optimisation

Hart, Emma; Sim, Kevin

Abstract

Although the use of ensemble methods in machine-learning is ubiquitous due to their proven ability to outperform their constituent algorithms, ensembles of optimisation algorithms have received relatively little attention. Existing approaches lag behind machine-learning in both theory and practice, with no principled design guidelines available. In this paper, we address fundamental questions regarding ensemble composition in opti-misation using the domain of bin-packing as a example; in particular we investigate the trade-off between accuracy and diversity, and whether diversity metrics can be used as a proxy for constructing an ensemble, proposing a number of novel metrics for comparing algorithm diversity. We find that randomly composed ensembles can outperform ensembles of high-performing algorithms under certain conditions and that judicious choice of diversity metric is required to construct good ensembles. The method and findings can be generalised to any meta-heuristic ensemble, and lead to better understanding of how to undertake principled ensemble design.

Citation

Hart, E., & Sim, K. (2018). On Constructing Ensembles for Combinatorial Optimisation. Evolutionary Computation, 26(1), 67-87. https://doi.org/10.1162/evco_a_00203

• Journal Article Type: Article
• Acceptance Date: Nov 26, 2016
• Online Publication Date: Jan 10, 2017
• Publication Date: 2018-03
• Deposit Date: Nov 28, 2016
• Publicly Available Date: Nov 29, 2016
• Journal: Evolutionary Computation
• Print ISSN: 1063-6560
• Electronic ISSN: 1530-9304
• Publisher: MIT Press
• Peer Reviewed: Peer Reviewed
• Volume: 26
• Issue: 1
• Pages: 67-87
• DOI: https://doi.org/10.1162/evco_a_00203
• Keywords: optimisation, ensembles, heuristics
• Public URL: http://researchrepository.napier.ac.uk/Output/444826
• Contract Date: Nov 28, 2016