Research Output

On Constructing Ensembles for Combinatorial Optimisation

  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.

  • Type:

    Article

  • Date:

    10 January 2017

  • Publication Status:

    Published

  • DOI:

    10.1162/EVCO_a_00203

  • ISSN:

    1063-6560

  • Library of Congress:

    QA75 Electronic computers. Computer science

  • Dewey Decimal Classification:

    005 Computer programming, programs & data

Citation

Hart, E. & Sim, K. (2017). On Constructing Ensembles for Combinatorial Optimisation. Evolutionary Computation. , 1-21. doi:10.1162/EVCO_a_00203. ISSN 1063-6560

Authors

Copyright

This is the author accepted version of an article which has been accepted for publication in Evolutionary Computation.

Keywords

optimisation, ensembles, heuristics

Monthly Views:

Available Documents