Extending Grammatical Evolution with Attribute Grammars: An Application to Knapsack Problems
Robert Cleary pursued an MSc by Research in this area, graduating in September 2005. His thesis is available here.

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 who's optimum-solution resides within a finitely-describable set, for the set of allpossible 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 its 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 utilised 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 behavioral findings about the GE system itself. The standard GE one-point crossover operator, emerges as exhibiting a midevolutionary change-of-role from a constructive to destructive operator; GEs 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 propogation 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.

EvoILP: Evolving Constraints for ILP
In collaboration with the University of Limerick (Dr. Nikola Nikolov and Alex Tarrasov) we investigated the use of Evolutionary Algorithms to generate constraints for Integer Linear Programming Problems. This research was supported under an Enterprise Ireland Basic Research award.