Skip to main content

Research Repository

Advanced Search

Grammatical evolution hyper-heuristic for combinatorial optimization problems

Sabar, Nasar; Ayob, Masri; Kendall, Graham; Qu, Rong

Authors

Nasar Sabar

Masri Ayob

Profile Image

RONG QU rong.qu@nottingham.ac.uk
Associate Professor



Abstract

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.

Citation

Sabar, N., Ayob, M., Kendall, G., & Qu, R. (2013). Grammatical evolution hyper-heuristic for combinatorial optimization problems. IEEE Transactions on Evolutionary Computation, 17(6), doi:10.1109/TEVC.2013.2281527

Journal Article Type Article
Publication Date Sep 11, 2013
Deposit Date Mar 18, 2015
Publicly Available Date Mar 18, 2015
Journal IEEE Transactions on Evolutionary Computation
Print ISSN 1089-778X
Electronic ISSN 1089-778X
Publisher Institute of Electrical and Electronics Engineers
Peer Reviewed Peer Reviewed
Volume 17
Issue 6
DOI https://doi.org/10.1109/TEVC.2013.2281527
Public URL http://eprints.nottingham.ac.uk/id/eprint/28282
Publisher URL http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6595625
Copyright Statement Copyright information regarding this work can be found at the following address: http://eprints.nottingh.../end_user_agreement.pdf
Additional Information © 2013 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Files

TEC13.pdf (1.5 Mb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf





You might also like



Downloadable Citations