The automatic design of hyper-heuristic framework with gene expression programming for combinatorial optimization problems
Hyper-heuristic approaches aim to automate heuristic design in order to solve multiple problems instead of designing tailor-made methodologies for individual problems. Hyper-heuristics accomplish this through a high level heuristic (heuristic selection mechanism and an acceptance criterion). This au...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Published: |
Institute of Electrical and Electronics Engineers
2014
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/28274/ |
| _version_ | 1848793540145971200 |
|---|---|
| author | Sabar, Nasar Ayob, Masri Kendall, Graham Qu, Rong |
| author_facet | Sabar, Nasar Ayob, Masri Kendall, Graham Qu, Rong |
| author_sort | Sabar, Nasar |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | Hyper-heuristic approaches aim to automate heuristic design in order to solve multiple problems instead of designing tailor-made methodologies for individual problems. Hyper-heuristics accomplish this through a high level heuristic (heuristic selection mechanism and an acceptance criterion). This automates heuristic selection, deciding whether to accept or reject the returned solution. The fact that different problems or even instances, have different landscape structures and complexity, the design of efficient high level heuristics can have a dramatic impact on hyper-heuristic performance. In this work, instead of using human knowledge to design the high level heuristic, we propose a gene expression programming algorithm to automatically generate, during the instance solving process, the high level heuristic of the hyper-heuristic framework. The generated heuristic takes information (such as the quality of the generated solution and the improvement made) from the current problem state as input and decides which low level heuristic should be selected and the acceptance or rejection of the resultant solution. The benefit of this framework is the ability to generate, for each instance, different high level heuristics during the problem solving process. Furthermore, in order to maintain solution diversity, we utilize a memory mechanism which contains a population of both high quality and diverse solutions that is updated during the problem solving process. The generality of the proposed hyper-heuristic is validated against six well known combinatorial optimization problem, with very different landscapes, provided by the HyFlex software. Empirical results comparing the proposed hyper-heuristic with state of the art hyper-heuristics, conclude that the proposed hyper-heuristic generalizes well across all domains and achieves competitive, if not superior, results for several instances on all domains. |
| first_indexed | 2025-11-14T19:01:55Z |
| format | Article |
| id | nottingham-28274 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:01:55Z |
| publishDate | 2014 |
| publisher | Institute of Electrical and Electronics Engineers |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-282742020-05-04T20:17:45Z https://eprints.nottingham.ac.uk/28274/ The automatic design of hyper-heuristic framework with gene expression programming for combinatorial optimization problems Sabar, Nasar Ayob, Masri Kendall, Graham Qu, Rong Hyper-heuristic approaches aim to automate heuristic design in order to solve multiple problems instead of designing tailor-made methodologies for individual problems. Hyper-heuristics accomplish this through a high level heuristic (heuristic selection mechanism and an acceptance criterion). This automates heuristic selection, deciding whether to accept or reject the returned solution. The fact that different problems or even instances, have different landscape structures and complexity, the design of efficient high level heuristics can have a dramatic impact on hyper-heuristic performance. In this work, instead of using human knowledge to design the high level heuristic, we propose a gene expression programming algorithm to automatically generate, during the instance solving process, the high level heuristic of the hyper-heuristic framework. The generated heuristic takes information (such as the quality of the generated solution and the improvement made) from the current problem state as input and decides which low level heuristic should be selected and the acceptance or rejection of the resultant solution. The benefit of this framework is the ability to generate, for each instance, different high level heuristics during the problem solving process. Furthermore, in order to maintain solution diversity, we utilize a memory mechanism which contains a population of both high quality and diverse solutions that is updated during the problem solving process. The generality of the proposed hyper-heuristic is validated against six well known combinatorial optimization problem, with very different landscapes, provided by the HyFlex software. Empirical results comparing the proposed hyper-heuristic with state of the art hyper-heuristics, conclude that the proposed hyper-heuristic generalizes well across all domains and achieves competitive, if not superior, results for several instances on all domains. Institute of Electrical and Electronics Engineers 2014 Article PeerReviewed Sabar, Nasar, Ayob, Masri, Kendall, Graham and Qu, Rong (2014) The automatic design of hyper-heuristic framework with gene expression programming for combinatorial optimization problems. IEEE Transactions on Evolutionary Computation . ISSN 1089-778X (In Press) Hyper-heuristics Gene Expression Programming Timetabling Vehicle Routing Dynamic Optimization http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6805577 doi:10.1109/TEVC.2014.2319051 doi:10.1109/TEVC.2014.2319051 |
| spellingShingle | Hyper-heuristics Gene Expression Programming Timetabling Vehicle Routing Dynamic Optimization Sabar, Nasar Ayob, Masri Kendall, Graham Qu, Rong The automatic design of hyper-heuristic framework with gene expression programming for combinatorial optimization problems |
| title | The automatic design of hyper-heuristic framework with gene expression programming for combinatorial optimization problems |
| title_full | The automatic design of hyper-heuristic framework with gene expression programming for combinatorial optimization problems |
| title_fullStr | The automatic design of hyper-heuristic framework with gene expression programming for combinatorial optimization problems |
| title_full_unstemmed | The automatic design of hyper-heuristic framework with gene expression programming for combinatorial optimization problems |
| title_short | The automatic design of hyper-heuristic framework with gene expression programming for combinatorial optimization problems |
| title_sort | automatic design of hyper-heuristic framework with gene expression programming for combinatorial optimization problems |
| topic | Hyper-heuristics Gene Expression Programming Timetabling Vehicle Routing Dynamic Optimization |
| url | https://eprints.nottingham.ac.uk/28274/ https://eprints.nottingham.ac.uk/28274/ https://eprints.nottingham.ac.uk/28274/ |