Automated design of population-based algorithms: a case study in vehicle routing
Metaheuristics have been extensively studied to solve constraint combinatorial optimisation problems such as vehicle routing problems. Most existing algorithms require considerable human effort and different kinds of expertise in algorithm design. These manually designed algorithms are discarded aft...
| Main Author: | |
|---|---|
| Format: | Thesis (University of Nottingham only) |
| Language: | English |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/73914/ |
| _version_ | 1848800824743952384 |
|---|---|
| author | Yi, Wenjie |
| author_facet | Yi, Wenjie |
| author_sort | Yi, Wenjie |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | Metaheuristics have been extensively studied to solve constraint combinatorial optimisation problems such as vehicle routing problems. Most existing algorithms require considerable human effort and different kinds of expertise in algorithm design. These manually designed algorithms are discarded after solving the specific instances. It is highly desirable to automate the design of search algorithms, thus to solve problem instances effectively with less human intervention.
This thesis develops a novel general search framework to formulate in a unified way a range of population-based algorithms. Within this framework, generic algorithmic components such as selection heuristics on the population and evolution operators are defined, and can be composed using machine learning to generate effective search algorithms automatically. This unified framework aims to serve as the basis to analyse algorithmic components,
generating effective search algorithms for complex combinatorial optimisation problems. Three key research issues within the general search framework are identified: automated design of evolution operators, of selection heuristics, and of both.
To accurately describe the search space of algorithm design as a new task for machine learning, this thesis identifies new key features, namely search-dependent and instance-dependent features. These features are identified to assist effective algorithm design. With these features, a set of state-of-the-art reinforcement learning techniques, such as deep Q-network based and proximal policy optimisation based models and maximum entropy mechanisms have been developed to intelligently select and combine appropriate evolution operators and selection heuristics during different stages of the optimisation process. The effectiveness and generality of these algorithms automatically designed within the proposed general search framework are validated comprehensively across different capacitated vehicle routing problem with time windows benchmark instances. This thesis contributes to making a key step towards automated algorithm design with a general framework supporting fundamental analysis by effective machine learning. |
| first_indexed | 2025-11-14T20:57:42Z |
| format | Thesis (University of Nottingham only) |
| id | nottingham-73914 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T20:57:42Z |
| publishDate | 2023 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-739142023-07-26T04:40:38Z https://eprints.nottingham.ac.uk/73914/ Automated design of population-based algorithms: a case study in vehicle routing Yi, Wenjie Metaheuristics have been extensively studied to solve constraint combinatorial optimisation problems such as vehicle routing problems. Most existing algorithms require considerable human effort and different kinds of expertise in algorithm design. These manually designed algorithms are discarded after solving the specific instances. It is highly desirable to automate the design of search algorithms, thus to solve problem instances effectively with less human intervention. This thesis develops a novel general search framework to formulate in a unified way a range of population-based algorithms. Within this framework, generic algorithmic components such as selection heuristics on the population and evolution operators are defined, and can be composed using machine learning to generate effective search algorithms automatically. This unified framework aims to serve as the basis to analyse algorithmic components, generating effective search algorithms for complex combinatorial optimisation problems. Three key research issues within the general search framework are identified: automated design of evolution operators, of selection heuristics, and of both. To accurately describe the search space of algorithm design as a new task for machine learning, this thesis identifies new key features, namely search-dependent and instance-dependent features. These features are identified to assist effective algorithm design. With these features, a set of state-of-the-art reinforcement learning techniques, such as deep Q-network based and proximal policy optimisation based models and maximum entropy mechanisms have been developed to intelligently select and combine appropriate evolution operators and selection heuristics during different stages of the optimisation process. The effectiveness and generality of these algorithms automatically designed within the proposed general search framework are validated comprehensively across different capacitated vehicle routing problem with time windows benchmark instances. This thesis contributes to making a key step towards automated algorithm design with a general framework supporting fundamental analysis by effective machine learning. 2023-07-26 Thesis (University of Nottingham only) NonPeerReviewed application/pdf en cc_by https://eprints.nottingham.ac.uk/73914/1/PhD%20thesis_Wenjie%20Yi.pdf Yi, Wenjie (2023) Automated design of population-based algorithms: a case study in vehicle routing. PhD thesis, University of Nottingham. Metaheuristics; Vehicle routing problems; Algorithm design; Population-based algorithms; Machine learning; Evolution operators; Selection heuristics |
| spellingShingle | Metaheuristics; Vehicle routing problems; Algorithm design; Population-based algorithms; Machine learning; Evolution operators; Selection heuristics Yi, Wenjie Automated design of population-based algorithms: a case study in vehicle routing |
| title | Automated design of population-based algorithms: a case study in vehicle routing |
| title_full | Automated design of population-based algorithms: a case study in vehicle routing |
| title_fullStr | Automated design of population-based algorithms: a case study in vehicle routing |
| title_full_unstemmed | Automated design of population-based algorithms: a case study in vehicle routing |
| title_short | Automated design of population-based algorithms: a case study in vehicle routing |
| title_sort | automated design of population-based algorithms: a case study in vehicle routing |
| topic | Metaheuristics; Vehicle routing problems; Algorithm design; Population-based algorithms; Machine learning; Evolution operators; Selection heuristics |
| url | https://eprints.nottingham.ac.uk/73914/ |