Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
A generation perturbative hyper-heuristic for combinatorial optimization problems
Dissertation (MSc (Computer Science))--University of Pretoria, 2020.
Saved in:
| Other Authors: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
University of Pretoria
2020
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613565538533376 |
|---|---|
| access_status_str | Open Access |
| author2 | Pillay, Nelishia |
| author_browse | Pillay, Nelishia |
| author_facet | Pillay, Nelishia |
| collection | Thesis |
| dc_rights_str_mv | © 2019 University of Pretoria. All rights reserved. The copyright in this work vests in the University of Pretoria. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of the University of Pretoria. |
| description | Dissertation (MSc (Computer Science))--University of Pretoria, 2020. |
| format | Thesis |
| id | oai:repository.up.ac.za:2263/75932 |
| institution | University of Pretoria (South Africa) |
| language | English |
| last_indexed | 2026-06-10T12:38:09.710Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from UPSpace — University of Pretoria Institutional Repository |
| publishDate | 2020 |
| publishDateRange | 2020 |
| publishDateSort | 2020 |
| publisher | University of Pretoria |
| publisherStr | University of Pretoria |
| record_format | dspace |
| source_str | UPSpace — University of Pretoria Institutional Repository |
| spelling | oai:repository.up.ac.za:2263/75932 A generation perturbative hyper-heuristic for combinatorial optimization problems Pillay, Nelishia george.mweshi@tuks.co.za Mweshi, George Artificial intelligence (AI) Machine learning Grammatical evolution Examination timetabling Boolean satisfiability Vehicle routing Hyper-heuristics UCTD Engineering, built environment and information technology theses SDG-08 Engineering, built environment and information technology theses SDG-09 Engineering, built environment and information technology theses SDG-11 Dissertation (MSc (Computer Science))--University of Pretoria, 2020. Perturbative heuristics or move operators are problem dependent operators commonly used by search techniques to solve computationally hard problems such as combinatorial optimization problems. These operators are generally derived manually by problem domain experts but this process is extremely challenging and time consuming. Hence, some initiatives aimed at automating the derivation process using search methodologies such as hyper-heuristics have been proposed in recent years. However, most of the proposed hyper-heuristic approaches generate new perturbative heuristics by recombining already existing and human-derived perturbative heuristics or components with various move acceptance criteria instead of generating the heuristics from scratch. As a result, these approaches cannot be easily applied to other problem domains where the human-derived heuristics are not available. In addition, the few hyper-heuristic approaches that have been proposed to generate perturbative heuristics from scratch are either designed for a single problem domain or applicable only to specific types of problems such as those that can be represented as graphs. The research presented in this dissertation addresses these issues by proposing a novel approach that can be used to automatically generate perturbative heuristics for any combinatorial optimization problem. In the proposed approach, perturbative heuristics are defined in terms of a set of basic operations (e.g. move and swap) and components of the solution (e.g. exam, period and room for the examination timetabling problem). Grammatical evolution, a well-known Evolutionary Algorithm, is used to combine the basic operations and components of the solution into perturbative heuristics. The generality of the proposed approach is tested by applying it to benchmark sets from three different problem domains, namely examination timetabling, vehicle routing and Boolean satisfiability. In addition, the performance of the perturbative heuristics generated by the proposed approach on the benchmark sets is compared to that of the commonly-used human-derived perturbative heuristics as well as the perturbative heuristics generated by other hyper-heuristic approaches in the literature. The experimental results show that the perturbative heuristics evolved by the proposed approach, specifically the grammatical evolution extended approach, outperformed the human-derived perturbative heuristics on all benchmark sets from the three problem domains. When compared to existing hyper-heuristic approaches, the proposed approach obtained solutions that were superior to those obtained by most hyper-heuristic approaches on the examination timetabling problem and only slightly inferior to those obtained by the best performing hyper-heuristic approaches on the vehicle routing and Boolean satisfiability problems. This performance of the proposed approach can be attributed to the fact that the generated perturbative heuristics were applied as is with no optimization as is commonly done with most hyper-heuristic approaches. Overall, the experimental results demonstrated success in developing an approach that can be used to automatically generate perturbative heuristics from scratch. Future work will consider incorporating optimization techniques during problem solving as well as performing a fitness landscape analysis in order to further improve the quality of solutions and have a better understanding of the proposed approach. SELF/ NRF Masters bs2026 Computer Science MSc (Computer Science) Unrestricted SDG-08: Decent work and economic growth SDG-09: Industry, innovation and infrastructure SDG-11: Sustainable cities and communities 2020-08-27T11:30:13Z 2020-08-27T11:30:13Z 2020 2020 Dissertation Mweshi, George 2020, A generation perturbative hyper-heuristic for combinatorial optimization problems, MSc thesis, University of Pretoria, Pretoria, viewed yyyymmdd http://hdl.handle.net/2263/75932 S2020 http://hdl.handle.net/2263/75932 en © 2019 University of Pretoria. All rights reserved. The copyright in this work vests in the University of Pretoria. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of the University of Pretoria. application/pdf University of Pretoria |
| spellingShingle | Artificial intelligence (AI) Machine learning Grammatical evolution Examination timetabling Boolean satisfiability Vehicle routing Hyper-heuristics UCTD Engineering, built environment and information technology theses SDG-08 Engineering, built environment and information technology theses SDG-09 Engineering, built environment and information technology theses SDG-11 A generation perturbative hyper-heuristic for combinatorial optimization problems |
| title | A generation perturbative hyper-heuristic for combinatorial optimization problems |
| title_full | A generation perturbative hyper-heuristic for combinatorial optimization problems |
| title_fullStr | A generation perturbative hyper-heuristic for combinatorial optimization problems |
| title_full_unstemmed | A generation perturbative hyper-heuristic for combinatorial optimization problems |
| title_short | A generation perturbative hyper-heuristic for combinatorial optimization problems |
| title_sort | generation perturbative hyper heuristic for combinatorial optimization problems |
| topic | Artificial intelligence (AI) Machine learning Grammatical evolution Examination timetabling Boolean satisfiability Vehicle routing Hyper-heuristics UCTD Engineering, built environment and information technology theses SDG-08 Engineering, built environment and information technology theses SDG-09 Engineering, built environment and information technology theses SDG-11 |
| url | http://hdl.handle.net/2263/75932 |