A dynamic multiarmed bandit-gene expression programming hyper-heuristic for combinatorial optimization problems
Hyper-heuristics are search methodologies that aim to provide high-quality solutions across a wide variety of problem domains, rather than developing tailor-made methodologies for each problem instance/domain. A traditional hyper-heuristic framework has two levels, namely, the high level strategy (h...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Published: |
IEEE
2015
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/28275/ |
| _version_ | 1848793540463689728 |
|---|---|
| author | Sabar, Nasar R. Ayob, Masri Kendall, Graham Qu, Rong |
| author_facet | Sabar, Nasar R. Ayob, Masri Kendall, Graham Qu, Rong |
| author_sort | Sabar, Nasar R. |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | Hyper-heuristics are search methodologies that aim to provide high-quality solutions across a wide variety of problem domains, rather than developing tailor-made methodologies for each problem instance/domain. A traditional hyper-heuristic framework has two levels, namely, the high level strategy (heuristic selection mechanism and the acceptance criterion) and low level heuristics (a set of problem specific heuristics). Due to the different landscape structures of different problem instances, the high level strategy plays an important role in the design of a hyper-heuristic framework. In this paper, we propose a new high level strategy for a hyper-heuristic framework. The proposed high-level strategy utilizes a dynamic multiarmed bandit-extreme value-based reward as an online heuristic selection mechanism to select the appropriate heuristic to be applied at each iteration. In addition, we propose a gene expression programming framework to automatically generate the acceptance criterion for each problem instance, instead of using human-designed criteria. Two well-known, and very different, combinatorial optimization problems, one static (exam timetabling) and one dynamic (dynamic vehicle routing) are used to demonstrate the generality of the proposed framework. Compared with state-of-the-art hyper-heuristics and other bespoke methods, empirical results demonstrate that the proposed framework is able to generalize well across both domains. We obtain competitive, if not better results, when compared to the best known results obtained from other methods that have been presented in the scientific literature. We also compare our approach against the recently released hyper-heuristic competition test suite. We again demonstrate the generality of our approach when we compare against other methods that have utilized the same six benchmark datasets from this test suite. |
| first_indexed | 2025-11-14T19:01:55Z |
| format | Article |
| id | nottingham-28275 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:01:55Z |
| publishDate | 2015 |
| publisher | IEEE |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-282752020-05-04T17:01:52Z https://eprints.nottingham.ac.uk/28275/ A dynamic multiarmed bandit-gene expression programming hyper-heuristic for combinatorial optimization problems Sabar, Nasar R. Ayob, Masri Kendall, Graham Qu, Rong Hyper-heuristics are search methodologies that aim to provide high-quality solutions across a wide variety of problem domains, rather than developing tailor-made methodologies for each problem instance/domain. A traditional hyper-heuristic framework has two levels, namely, the high level strategy (heuristic selection mechanism and the acceptance criterion) and low level heuristics (a set of problem specific heuristics). Due to the different landscape structures of different problem instances, the high level strategy plays an important role in the design of a hyper-heuristic framework. In this paper, we propose a new high level strategy for a hyper-heuristic framework. The proposed high-level strategy utilizes a dynamic multiarmed bandit-extreme value-based reward as an online heuristic selection mechanism to select the appropriate heuristic to be applied at each iteration. In addition, we propose a gene expression programming framework to automatically generate the acceptance criterion for each problem instance, instead of using human-designed criteria. Two well-known, and very different, combinatorial optimization problems, one static (exam timetabling) and one dynamic (dynamic vehicle routing) are used to demonstrate the generality of the proposed framework. Compared with state-of-the-art hyper-heuristics and other bespoke methods, empirical results demonstrate that the proposed framework is able to generalize well across both domains. We obtain competitive, if not better results, when compared to the best known results obtained from other methods that have been presented in the scientific literature. We also compare our approach against the recently released hyper-heuristic competition test suite. We again demonstrate the generality of our approach when we compare against other methods that have utilized the same six benchmark datasets from this test suite. IEEE 2015-02-28 Article PeerReviewed Sabar, Nasar R., Ayob, Masri, Kendall, Graham and Qu, Rong (2015) A dynamic multiarmed bandit-gene expression programming hyper-heuristic for combinatorial optimization problems. IEEE Transactions on Cybernetics, 45 (2). pp. 217-228. ISSN 2168-2275 Gene Expression Programming Hyper-heuristic Timetabling Vehicle Routing Dynamic Optimization http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6824192 doi:10.1109/TCYB.2014.2323936 doi:10.1109/TCYB.2014.2323936 |
| spellingShingle | Gene Expression Programming Hyper-heuristic Timetabling Vehicle Routing Dynamic Optimization Sabar, Nasar R. Ayob, Masri Kendall, Graham Qu, Rong A dynamic multiarmed bandit-gene expression programming hyper-heuristic for combinatorial optimization problems |
| title | A dynamic multiarmed bandit-gene expression programming hyper-heuristic for combinatorial optimization problems |
| title_full | A dynamic multiarmed bandit-gene expression programming hyper-heuristic for combinatorial optimization problems |
| title_fullStr | A dynamic multiarmed bandit-gene expression programming hyper-heuristic for combinatorial optimization problems |
| title_full_unstemmed | A dynamic multiarmed bandit-gene expression programming hyper-heuristic for combinatorial optimization problems |
| title_short | A dynamic multiarmed bandit-gene expression programming hyper-heuristic for combinatorial optimization problems |
| title_sort | dynamic multiarmed bandit-gene expression programming hyper-heuristic for combinatorial optimization problems |
| topic | Gene Expression Programming Hyper-heuristic Timetabling Vehicle Routing Dynamic Optimization |
| url | https://eprints.nottingham.ac.uk/28275/ https://eprints.nottingham.ac.uk/28275/ https://eprints.nottingham.ac.uk/28275/ |