Prof Emma Hart E.Hart@napier.ac.uk
Professor
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 |
Files
On Constructing Ensembles for Combinatorial Optimisation
(436 Kb)
PDF
Copyright Statement
This is the author accepted version of an article which has been accepted for publication in Evolutionary Computation.
You might also like
Evolving Behavior Allocations in Robot Swarms
(2024)
Conference Proceeding
Towards optimisers that `Keep Learning'
(2023)
Conference Proceeding
A Feature-Free Approach to Automated Algorithm Selection
(2023)
Conference Proceeding
Downloadable Citations
About Edinburgh Napier Research Repository
Administrator e-mail: repository@napier.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search