Evolutionary algorithms and hyper-heuristics for orthogonal packing problems
This thesis investigates two major classes of Evolutionary Algorithms, Genetic Algorithms (GAs) and Evolution Strategies (ESs), and their application to the Orthogonal Packing Problems (OPP). OPP are canonical models for NP-hard problems, the class of problems widely conceived to be unsolvable on a...
| Main Author: | |
|---|---|
| Format: | Thesis (University of Nottingham only) |
| Language: | English |
| Published: |
2011
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/29311/ |
| _version_ | 1848793758244536320 |
|---|---|
| author | Guo, Qiang |
| author_facet | Guo, Qiang |
| author_sort | Guo, Qiang |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | This thesis investigates two major classes of Evolutionary Algorithms, Genetic Algorithms (GAs) and Evolution Strategies (ESs), and their application to the Orthogonal Packing Problems (OPP). OPP are canonical models for NP-hard problems, the class of problems widely conceived to be unsolvable on a polynomial deterministic Turing machine, although they underlie many optimisation problems in the real world. With the increasing power of modern computers, GAs and ESs have been developed in the past decades to provide high quality solutions for a wide range of optimisation and learning problems. These algorithms are inspired by Darwinian nature selection mechanism that iteratively select better solutions in populations derived from recombining and mutating existing solutions. The algorithms have gained huge success in many areas, however, being stochastic processes, the algorithms' behaviour on different problems is still far from being fully understood. The work of this thesis provides insights to better understand both the algorithms and the problems.
The thesis begins with an investigation of hyper-heuristics as a more general search paradigm based on standard EAs. Hyper-heuristics are shown to be able to overcome the difficulty of many standard approaches which only search in partial solution space. The thesis also looks into the fundamental theory of GAs, the schemata theorem and the building block hypothesis, by developing the Grouping Genetic Algorithms (GGA) for high dimensional problems and providing supportive yet qualified empirical evidences for the hypothesis. Realising the difficulties of genetic encoding over combinatorial search domains, the thesis proposes a phenotype representation together with Evolution Strategies that operates on such representation. ESs were previously applied mainly to continuous numerical optimisation, therefore being less understood when searching in combinatorial domains. The work in this thesis develops highly competent ES algorithms for OPP and opens the door for future research in this area. |
| first_indexed | 2025-11-14T19:05:23Z |
| format | Thesis (University of Nottingham only) |
| id | nottingham-29311 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T19:05:23Z |
| publishDate | 2011 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-293112025-02-28T11:35:51Z https://eprints.nottingham.ac.uk/29311/ Evolutionary algorithms and hyper-heuristics for orthogonal packing problems Guo, Qiang This thesis investigates two major classes of Evolutionary Algorithms, Genetic Algorithms (GAs) and Evolution Strategies (ESs), and their application to the Orthogonal Packing Problems (OPP). OPP are canonical models for NP-hard problems, the class of problems widely conceived to be unsolvable on a polynomial deterministic Turing machine, although they underlie many optimisation problems in the real world. With the increasing power of modern computers, GAs and ESs have been developed in the past decades to provide high quality solutions for a wide range of optimisation and learning problems. These algorithms are inspired by Darwinian nature selection mechanism that iteratively select better solutions in populations derived from recombining and mutating existing solutions. The algorithms have gained huge success in many areas, however, being stochastic processes, the algorithms' behaviour on different problems is still far from being fully understood. The work of this thesis provides insights to better understand both the algorithms and the problems. The thesis begins with an investigation of hyper-heuristics as a more general search paradigm based on standard EAs. Hyper-heuristics are shown to be able to overcome the difficulty of many standard approaches which only search in partial solution space. The thesis also looks into the fundamental theory of GAs, the schemata theorem and the building block hypothesis, by developing the Grouping Genetic Algorithms (GGA) for high dimensional problems and providing supportive yet qualified empirical evidences for the hypothesis. Realising the difficulties of genetic encoding over combinatorial search domains, the thesis proposes a phenotype representation together with Evolution Strategies that operates on such representation. ESs were previously applied mainly to continuous numerical optimisation, therefore being less understood when searching in combinatorial domains. The work in this thesis develops highly competent ES algorithms for OPP and opens the door for future research in this area. 2011-12-14 Thesis (University of Nottingham only) NonPeerReviewed application/pdf en arr https://eprints.nottingham.ac.uk/29311/1/555394.pdf Guo, Qiang (2011) Evolutionary algorithms and hyper-heuristics for orthogonal packing problems. PhD thesis, University of Nottingham. genetic algorithms shipping packing business data processing |
| spellingShingle | genetic algorithms shipping packing business data processing Guo, Qiang Evolutionary algorithms and hyper-heuristics for orthogonal packing problems |
| title | Evolutionary algorithms and hyper-heuristics for orthogonal packing problems |
| title_full | Evolutionary algorithms and hyper-heuristics for orthogonal packing problems |
| title_fullStr | Evolutionary algorithms and hyper-heuristics for orthogonal packing problems |
| title_full_unstemmed | Evolutionary algorithms and hyper-heuristics for orthogonal packing problems |
| title_short | Evolutionary algorithms and hyper-heuristics for orthogonal packing problems |
| title_sort | evolutionary algorithms and hyper-heuristics for orthogonal packing problems |
| topic | genetic algorithms shipping packing business data processing |
| url | https://eprints.nottingham.ac.uk/29311/ |