Dr Kevin Sim K.Sim@napier.ac.uk
Lecturer
Learning to solve bin packing problems with an immune inspired hyper-heuristic.
Sim, Kevin; Hart, Emma; Paechter, Ben
Authors
Prof Emma Hart E.Hart@napier.ac.uk
Professor
Prof Ben Paechter B.Paechter@napier.ac.uk
Professor
Contributors
Pietro Li�
Editor
Orazio Miglino
Editor
Giuseppe Nicosia
Editor
Stefano Nolfi
Editor
Mario Pavone
Editor
Abstract
Motivated by the natural immune system's ability to defend the body by generating and maintaining a repertoire of antibodies that collectively cover the potential pathogen space, we describe an artificial system that discovers and maintains a repertoire of heuristics that collectively provide methods for solving problems within a problem space. Using bin-packing as an example domain, the system continuously generates novel heuristics represented using a tree-structure. An novel affinity measure provides stimulation between heuristics that cooperate by solving problems in different parts of the space. Using a test suite comprising of 1370 problem instances, we show that the system self-organises to a minimal repertoire of heuristics that provide equivalent performance on the test set to state-of-the art methods in hyper-heuristics. Moreover, the system is shown to be highly responsive and adaptive: it rapidly incorporates new heuristics both when entirely new sets of problem instances are introduced or when the problems presented change gradually over time.
Citation
Sim, K., Hart, E., & Paechter, B. (2013, September). Learning to solve bin packing problems with an immune inspired hyper-heuristic
Start Date | Sep 2, 2013 |
---|---|
End Date | Sep 6, 2013 |
Publication Date | 2013 |
Deposit Date | Aug 26, 2013 |
Publicly Available Date | Dec 31, 2013 |
Peer Reviewed | Peer Reviewed |
Pages | 856-863 |
Book Title | Advances in Artificial Life, ECAL 2013 |
DOI | https://doi.org/10.7551/978-0-262-31709-2-ch126 |
Keywords | Hyper-heuristics; artificial systems; problem solving; novel affinity measure; |
Public URL | http://researchrepository.napier.ac.uk/id/eprint/6251 |
Publisher URL | http://dx.doi.org/10.7551/978-0-262-31709-2-ch126 |
Contract Date | Aug 26, 2013 |
Files
ecal2013_submission_219.pdf
(559 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc/4.0/
You might also like
A hyper-heuristic ensemble method for static job-shop scheduling.
(2016)
Journal Article
Roll Project Bin Packing Benchmark Problems.
(2015)
Data
A Novel Heuristic Generator for JSSP Using a Tree-Based Representation of Dispatching Rules
(2015)
Presentation / Conference Contribution
A research agenda for metaheuristic standardization.
(2015)
Presentation / Conference Contribution
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