Human derived heuristic enhancement of an evolutionary algorithm for the 2D Bin Packing Problem
Ross, N; Keedwell, E; Savic, D
Date: 2 September 2020
Journal
Lecture Notes in Computer Science
Publisher
Springer Verlag
Publisher DOI
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 ...
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.
Computer Science
Faculty of Environment, Science and Economy
Item views 0
Full item downloads 0