Grammatical evolution hyper-heuristic for combinatorial optimization problems
Designing generic problem solvers that perform well across a diverse set of problems is a challenging task. In this work, we propose a hyper-heuristic framework to automatically generate an effective and generic solution method by utilizing grammatical evolution. In the proposed framework, grammatic...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Published: |
Institute of Electrical and Electronics Engineers
2013
|
| Online Access: | https://eprints.nottingham.ac.uk/28282/ |
| _version_ | 1848793542479052800 |
|---|---|
| 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 | Designing generic problem solvers that perform well across a diverse set of problems is a challenging task. In this work, we propose a hyper-heuristic framework to automatically generate an effective and generic solution method by utilizing grammatical evolution. In the proposed framework, grammatical evolution is used as an online solver builder, which takes several heuristic components (e.g., different acceptance criteria and different neighborhood structures) as inputs and evolves templates of perturbation heuristics. The evolved templates are improvement heuristics, which represent a complete search method to solve the problem at hand. To test the generality and the performance of the proposed method, we consider two well-known combinatorial optimization problems: exam timetabling (Carter and ITC 2007 instances) and the capacitated vehicle routing problem (Christofides and Golden instances). We demonstrate that the proposed method is competitive, if not superior, when compared to state-of-the-art hyper-heuristics, as well as bespoke methods for these different problem domains. In order to further improve the performance of the proposed framework we utilize an adaptive memory mechanism, which contains a collection of both high quality and diverse solutions and is updated during the problem solving process. Experimental results show that the grammatical evolution hyper-heuristic, with an adaptive memory, performs better than the grammatical evolution hyper-heuristic without a memory. The improved framework also outperforms some bespoke methodologies, which have reported best known results for some instances in both problem domains. |
| first_indexed | 2025-11-14T19:01:57Z |
| format | Article |
| id | nottingham-28282 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:01:57Z |
| publishDate | 2013 |
| publisher | Institute of Electrical and Electronics Engineers |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-282822020-05-04T16:38:55Z https://eprints.nottingham.ac.uk/28282/ Grammatical evolution hyper-heuristic for combinatorial optimization problems Sabar, Nasar Ayob, Masri Kendall, Graham Qu, Rong Designing generic problem solvers that perform well across a diverse set of problems is a challenging task. In this work, we propose a hyper-heuristic framework to automatically generate an effective and generic solution method by utilizing grammatical evolution. In the proposed framework, grammatical evolution is used as an online solver builder, which takes several heuristic components (e.g., different acceptance criteria and different neighborhood structures) as inputs and evolves templates of perturbation heuristics. The evolved templates are improvement heuristics, which represent a complete search method to solve the problem at hand. To test the generality and the performance of the proposed method, we consider two well-known combinatorial optimization problems: exam timetabling (Carter and ITC 2007 instances) and the capacitated vehicle routing problem (Christofides and Golden instances). We demonstrate that the proposed method is competitive, if not superior, when compared to state-of-the-art hyper-heuristics, as well as bespoke methods for these different problem domains. In order to further improve the performance of the proposed framework we utilize an adaptive memory mechanism, which contains a collection of both high quality and diverse solutions and is updated during the problem solving process. Experimental results show that the grammatical evolution hyper-heuristic, with an adaptive memory, performs better than the grammatical evolution hyper-heuristic without a memory. The improved framework also outperforms some bespoke methodologies, which have reported best known results for some instances in both problem domains. Institute of Electrical and Electronics Engineers 2013-09-11 Article PeerReviewed Sabar, Nasar, Ayob, Masri, Kendall, Graham and Qu, Rong (2013) Grammatical evolution hyper-heuristic for combinatorial optimization problems. IEEE Transactions on Evolutionary Computation, 17 (6). pp. 840-861. ISSN 1089-778X http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6595625 doi:10.1109/TEVC.2013.2281527 doi:10.1109/TEVC.2013.2281527 |
| spellingShingle | Sabar, Nasar Ayob, Masri Kendall, Graham Qu, Rong Grammatical evolution hyper-heuristic for combinatorial optimization problems |
| title | Grammatical evolution hyper-heuristic for combinatorial optimization problems |
| title_full | Grammatical evolution hyper-heuristic for combinatorial optimization problems |
| title_fullStr | Grammatical evolution hyper-heuristic for combinatorial optimization problems |
| title_full_unstemmed | Grammatical evolution hyper-heuristic for combinatorial optimization problems |
| title_short | Grammatical evolution hyper-heuristic for combinatorial optimization problems |
| title_sort | grammatical evolution hyper-heuristic for combinatorial optimization problems |
| url | https://eprints.nottingham.ac.uk/28282/ https://eprints.nottingham.ac.uk/28282/ https://eprints.nottingham.ac.uk/28282/ |