Investigating the Effectiveness of Shallow and Deep Learning Techniques on Predicting the Quality of a Policy Matrix

The Original Bin Packing problem is a classic one where a finite number of items varying in size are packed into bins of fixed capacity. This is an easy problem to solve and there are many simple algorithms to provide near optimal packing. Larger instances of the problem however require slightly more complex algorithms but are still possible to provide exact solutions. A classic and effective heuristic for example is the first fit algorithm which provides fast placement of items into the first bin which it fits in. Although this in itself is an interesting problem, one which carries more importance is the Online bin packing problem. This is the same as the original bin packing problem but with one variant. We are not aware of the number of items in the stream that arrive, and so are left with important decisions to make in order to minimise the total number of bins used. A proposed solution is through a heuristic representation in the form of a Policy Matrix which can be thought of as a 2-dimensional rule book for packing incoming items. A way to discover high performance policies is using genetic algorithms to create generations of heuristics improving in performance over iterations. However, this takes time to complete as poor performance policies take time to evaluate. To solve this problem, it was suggested to create a Fitness Approxima-tor that would approximate the performance of a policy before candidate selection during each iteration of the genetic algorithm. The steps taken towards accomplishing this involved generating large data sets of packing policies, designing and implementing neural networks to extract patterns from the structure of a policy matrix. The 2 sub-categories of neural network used are Multi-Layer Perceptron and Convolutional Neu-ral Networks, both of these function as feature extractors that can predict under-lying patterns in data. Results show that it is possible to classify and distinguish high performance policy matrices from low performance matrices, both multi-layer perceptron and convolutional neural networks displayed similarly high levels of accuracy suggesting there are patterns within the heuristics that can be identified and related to performance in packing. Further research could still be done on improving the accuracy of prediction, however the huge takeaway from this is that heuristics represented as a policy matrix can have their features define performance in their given task