Extending Grammatical Evolution with Attribute Grammars: An Application to Knapsack Problems

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

  title =        "Extending Grammatical Evolution with Attribute
                 Grammars: An Application to Knapsack Problems",
  author =       "Robert Cleary",
  school =       "University of Limerick",
  year =         "2005",
  type =         "Master of Science in Computer Science",
  address =      "University of Limerick, Ireland",
  keywords =     "genetic algorithms, genetic programming, grammatical
                 evolution, grammatical swarm, attribute grammars",
  URL =          "http://ncra.ucd.ie/downloads/pub/thesisExtGEwithAGs-CRC.pdf",
  size =         "197 pages",
  abstract =     "Research extending the capabilities of the well-known
                 evolutionary-algorithm (EA) of Grammatical Evolution
                 (GE) is presented. GE essentially describes a software
                 component for (potentially) any search algorithm (more
                 prominently an EA) - whereby it serves to facilitate
                 the generation of viable solutions to the problem at
                 hand. In this way, GE can be thought of as a generally
                 applicable, robust and pluggable component to any
                 search-algorithm. Facilitating this plug- ability - is
                 the ability to hand-describe the structure of solutions
                 to a particular problem; this, under the guise of the
                 concise and effective notation of a grammar definition.
                 This grammar may be thought of, as the rules for the
                 generation of solutions to a problem. Recent research
                 has shown, that for static-problems - (problems whose
                 optimum-solution resides within a finitely-describable
                 set, for the set of all possible solutions), the
                 ability to focus the search (for the optimum) on the
                 more promising regions of this set, has provided the
                 best-performing approaches to-date. As such, it is
                 suggested that search be biased toward more promising
                 areas of the set of all possible solutions.

                 In it's use of a grammar, GE provides such a bias (as a
                 language-bias), yet remains unable, to effectively bias
                 the search for problems of constrained optimisation. As
                 such, and as detailed in this thesis - the mechanism of
                 an attribute grammar is proposed to maintain GE as a
                 pluggable component for problems of this type also;
                 thus extending it's robustness and general

                 A family of academically recognised (hard) knapsack
                 problems, are used as a testing-ground for the
                 extended-system and the results presented are
                 encouraging. As a side-effect of this study (and
                 possibly more importantly) we observe some interesting
                 behavioural findings about the GE system itself.

                 The standard GE one-point crossover operator, emerges
                 as exhibiting a mid evolutionary change-of-role from a
                 constructive to destructive operator; GE's
                 ripple-crossover is found to be heavily dependent on
                 the presence of a GE-tail (of residual-introns) in
                 order to function effectively; and the propagation of
                 individuals - characterised by large-proportions of
                 such residual-introns - is found to be an evolutionary
                 self- adaptive response to the destructive change of
                 role found in the one-point crossover: all of these
                 findings are found with respect to the problems
  language =     "en",

Genetic Programming entries for Robert Cleary