Attributed Grammatical Evolution with Lookahead for the Multiple Knapsack Problem

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

  author =       "Muhammad Rezaul Karim and Conor Ryan",
  title =        "Attributed Grammatical Evolution with Lookahead for
                 the Multiple Knapsack Problem",
  journal =      "Memetic Computing",
  year =         "2012",
  volume =       "4",
  number =       "4",
  pages =        "279--302",
  keywords =     "genetic algorithms, genetic programming, Grammatical
                 Evolution, Attribute Grammar, Multiple Knapsack
  ISSN =         "1865-9284",
  publisher =    "Springer-Verlag",
  language =     "English",
  DOI =          "doi:10.1007/s12293-012-0097-8",
  size =         "24 pages",
  abstract =     "This paper presents an Attribute Grammar with
                 Lookahead (AG+LA) approach, a technique to solve
                 heavily constrained Multiple Knapsack Problem. This
                 approach incorporates a form of look ahead into the
                 mapping process of Grammatical Evolution (GE) using
                 Attribute Grammar (AG) to focus only on feasible
                 solutions, thereby avoiding issues such as repeated
                 remapping and introns, both of which are limitations of
                 previous approaches based on AG. We also present AG+LAE
                 (AG+LA with an efficiency measure to bias the search
                 towards the most efficient, i.e., best value, objects),
                 the successor of AG+LA where a biasing process is
                 incorporated using problem specific knowledge to
                 significantly improve the performance of its
                 predecessor, both in terms of the number of evaluations
                 required and the quality of solutions obtained.
                 Degenerate code, as used in DNA, is code that uses
                 redundancy, so that different codons can represent the
                 same thing. Many developmental systems, such as GE, use
                 a degenerate encoding to help promote neutral
                 mutations, that is, minor genetic changes that do not
                 result in a phenotypic change. While early work in GE
                 suggested that some level of degeneracy was important,
                 it does come at the cost of increasing the size of the
                 search space. Duplicate Elimination techniques, as
                 opposed to degenerate encoding, are employed in
                 decoder-based Evolutionary Algorithms to ensure that
                 the newly generated solutions are not already contained
                 in the current population. The results and analysis
                 show that it is crucial to incorporate duplicate
                 elimination to improve the performance of both
                 approaches, while the reduced level of degeneracy is
                 crucial only for AG+LA.",
  notes =        "special issue on the NICSO 2011 workshop",

Genetic Programming entries for Muhammad Rezaul Karim Conor Ryan