Grammatical Evolution Hyper-Heuristic for Combinatorial Optimization Problems

Created by W.Langdon from gp-bibliography.bib Revision:1.3872

  author =       "Nasser R. Sabar and Masri Ayob and Graham Kendall and 
                 Rong Qu",
  title =        "Grammatical Evolution Hyper-Heuristic for
                 Combinatorial Optimization Problems",
  journal =      "IEEE Transactions on Evolutionary Computation",
  year =         "2013",
  volume =       "17",
  number =       "6",
  pages =        "840--861",
  month =        dec,
  keywords =     "genetic algorithms, genetic programming, Grammatical
  ISSN =         "1089-778X",
  DOI =          "doi:10.1109/TEVC.2013.2281527",
  size =         "22 pages",
  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 using 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 neighbourhood 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 optimisation 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 use 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.",
  notes =        "also known as \cite{6595625}",

Genetic Programming entries for Nasser R Sabar Masri Ayob Graham Kendall Rong Qu