Novel Hyper-heuristics Applied to the Domain of Bin Packing

Sim, Kevin

Abstract

Principal to the ideology behind hyper-heuristic research is the desire to increase the level of generality of heuristic procedures so that they can be easily applied to a wide variety of problems to produce solutions of adequate quality within practical timescales.
This thesis examines hyper-heuristics within a single problem domain, that of Bin Packing where the benefits to be gained from selecting or generating heuristics for large problem sets with widely differing characteristics is considered. Novel implementations of both selective and generative hyper-heuristics are proposed. The former approach attempts to map the characteristics of a problem to the heuristic that best solves it while the latter uses Genetic Programming techniques to automate the heuristic design process. Results obtained using the selective approach show that solution quality was improved significantly when contrasted to the performance of the best single heuristic when applied to large sets of diverse problem instances. Although enforcing the benefits to be gained by selecting from a range of heuristics the study also highlighted the lack of diversity in human designed algorithms. Using Genetic Programming techniques to automate the heuristic design process allowed both single heuristics and collectives of heuristics to be generated that were shown to perform significantly better than their human designed counterparts. The thesis concludes by combining both selective and generative hyper-heuristic approaches into a novel immune inspired system where heuristics that cover distinct areas of the problem space are generated. The system is shown to have a number of advantages over similar cooperative approaches in terms of its plasticity, efficiency and long term memory. Extensive testing of all of the hyper-heuristics developed on large sets of both benchmark and newly generated problem instances enforces the utility of hyper-heuristics in their goal of producing fast understandable procedures that give good quality solutions for a range of problems with widely varying characteristics.

Citation

Sim, K. Novel Hyper-heuristics Applied to the Domain of Bin Packing. (Thesis). Edinburgh Napier University. http://researchrepository.napier.ac.uk/id/eprint/7563

• Thesis Type: Thesis
• Deposit Date: Feb 13, 2015
• Peer Reviewed: Not Peer Reviewed
• Keywords: hyper-heuristics; heuristic procedures; bin packing; Genetic Programming; problem solving
• Public URL: http://researchrepository.napier.ac.uk/id/eprint/7563
• Contract Date: Feb 13, 2015
• Award Date: 2014-10