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

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

@MastersThesis{cleary:2005:EGEWAGAATKP,

• 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/Site/evoilp.html",
• 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 applicability.

  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 examined.",

• language = "en",

}

Genetic Programming entries for Robert Cleary

Citations