Prof Emma Hart E.Hart@napier.ac.uk
Professor
Prof Emma Hart E.Hart@napier.ac.uk
Professor
Dr Kevin Sim K.Sim@napier.ac.uk
Lecturer
Prof Ben Paechter B.Paechter@napier.ac.uk
Professor
We describe a novel Hyper-heuristic system which continuously learns over time to solve a combinatorial optimisation problem. The system continuously generates new heuristics and samples problems from its environment; representative problems and heuristics are incorporated into a self-sustaining network of interacting entities in- spired by methods in Artificial Immune Systems.The network is plastic in both its structure and content leading to the following properties: it exploits existing knowl- edge captured in the network to rapidly produce solutions; it can adapt to new prob- lems with widely differing characteristics; it is capable of generalising over the prob- lem space. The system is tested on a large corpus of 3968 new instances of 1D-bin packing problems as well as on 1370 existing problems from the literature; it shows excellent performance in terms of the quality of solutions obtained across the datasets and in adapting to dynamically changing sets of problem instances compared to pre- vious approaches. As the network self-adapts to sustain a minimal repertoire of both problems and heuristics that form a representative map of the problem space, the system is further shown to be computationally efficient and therefore scalable.
Hart, E., Sim, K., & Paechter, B. (2015). A Lifelong Learning Hyper-heuristic Method for Bin Packing. Evolutionary Computation, 23(1), 37-67. https://doi.org/10.1162/EVCO_a_00121
Journal Article Type | Article |
---|---|
Online Publication Date | Mar 13, 2015 |
Publication Date | Mar 13, 2015 |
Deposit Date | Apr 11, 2014 |
Publicly Available Date | May 15, 2017 |
Journal | Evolutionary Computation |
Print ISSN | 1063-6560 |
Electronic ISSN | 1530-9304 |
Publisher | MIT Press |
Peer Reviewed | Peer Reviewed |
Volume | 23 |
Issue | 1 |
Pages | 37-67 |
DOI | https://doi.org/10.1162/EVCO_a_00121 |
Keywords | novel Hyper-heuristic system; 1D-bin packing; scalable; |
Public URL | http://researchrepository.napier.ac.uk/id/eprint/6640 |
Publisher URL | http://dx.doi.org/10.1162/EVCO_a_00121 |
A lifelong learning hyper-heuristic method for bin packing
(<nobr>2.4 Mb</nobr>)
PDF
Evolutionary Approaches to Improving the Layouts of Instance-Spaces
(2022)
Conference Proceeding
Minimising line segments in linear diagrams is NP-hard
(2022)
Journal Article
A Neural Approach to Generation of Constructive Heuristics
(2021)
Conference Proceeding
Drawing Algorithms For Linear Diagrams (Supplementary)
(2020)
Dataset
Algorithm selection using deep learning without feature extraction
(2019)
Conference Proceeding
About Edinburgh Napier Research Repository
Administrator e-mail: repository@napier.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
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/)
Advanced Search