Research Output

Novel Hyper-heuristics Applied to the Domain of Bin Packing.

  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.

  • Type:

    Thesis

  • Date:

    30 September 2014

  • Publication Status:

    Unpublished

  • Library of Congress:

    QA76 Computer software

  • Dewey Decimal Classification:

    006.3 Artificial intelligence

Citation

Sim, K. Novel Hyper-heuristics Applied to the Domain of Bin Packing. (Thesis)

Authors

Keywords

hyper-heuristics; heuristic procedures; bin packing; Genetic Programming; problem solving;

Monthly Views:

Available Documents