dc.contributor.author | Ross, N | |
dc.contributor.author | Keedwell, E | |
dc.contributor.author | Savic, D | |
dc.date.accessioned | 2020-06-25T16:01:01Z | |
dc.date.issued | 2020-09-02 | |
dc.description.abstract | The 2D Bin-Packing Problem (2DBPP) is an NP-Hard combinatorial
optimisation problem with many real-world analogues. Fully deterministic
methods such as the well-known Best Fit and First Fit heuristics, stochastic
methods such as Evolutionary Algorithms (EAs), and hybrid EAs that combine
the deterministic and stochastic approaches have all been applied to the problem. Combining derived human expertise with a hybrid EA offers another potential approach. In this work, the moves of humans playing a gamified version
of the 2DBPP were recorded and four different Human-Derived Heuristics
(HDHs) were created by learning the underlying heuristics employed by those
players. Each HDH used a decision tree in place of the mutation operator in the
EA. To test their effectiveness, these were compared against hybrid EAs utilising Best Fit or First Fit heuristics as well as a standard EA using a random swap
mutation modified with a Next Fit heuristic if the mutation was infeasible. The
HDHs were shown to outperform the standard EA and were faster to converge
than – but ultimately outperformed by – the First Fit and Best Fit heuristics.
This shows that humans can create competitive heuristics through gameplay
and helps to understand the role that heuristics can play in stochastic search. | en_GB |
dc.description.sponsorship | Engineering and Physical Sciences Research Council (EPSRC) | en_GB |
dc.identifier.citation | Vol. 12270, pp. pp 413-427 | en_GB |
dc.identifier.doi | 10.1007/978-3-030-58115-2_29 | |
dc.identifier.grantnumber | 714478 | en_GB |
dc.identifier.grantnumber | EP/P009441/1 | en_GB |
dc.identifier.uri | http://hdl.handle.net/10871/121666 | |
dc.language.iso | en | en_GB |
dc.publisher | Springer Verlag | en_GB |
dc.rights | © Springer Nature Switzerland AG 2020 | |
dc.subject | Genetic algorithms | en_GB |
dc.subject | Heuristics | en_GB |
dc.subject | Hybridization | en_GB |
dc.title | Human derived heuristic enhancement of an evolutionary algorithm for the 2D Bin Packing Problem | en_GB |
dc.type | Article | en_GB |
dc.date.available | 2020-06-25T16:01:01Z | |
dc.identifier.issn | 0302-9743 | |
dc.description | Parallel Problem Solving from Nature – PPSN XVI. 16th International Conference, PPSN 2020, Leiden, The Netherlands, 5 - 9 September 2020 | en_GB |
dc.description | This is the author accepted manuscript. The final version is available from Springer Verlag via the DOI in this record | |
dc.identifier.journal | Lecture Notes in Computer Science | en_GB |
dc.rights.uri | http://www.rioxx.net/licenses/all-rights-reserved | en_GB |
pubs.funder-ackownledgement | Yes | en_GB |
dcterms.dateAccepted | 2020-05-27 | |
exeter.funder | ::Engineering and Physical Sciences Research Council (EPSRC) | en_GB |
rioxxterms.version | AM | en_GB |
rioxxterms.licenseref.startdate | 2020-05-27 | |
rioxxterms.type | Journal Article/Review | en_GB |
refterms.dateFCD | 2020-06-25T15:58:18Z | |
refterms.versionFCD | AM | |
refterms.dateFOA | 2021-03-10T15:50:22Z | |
refterms.panel | B | en_GB |