Extending Grammatical Evolution with Attribute
Grammars: An Application to Knapsack Problems
University of Limerick, University of Limerick, Ireland, Master of Science in Computer Science, (2005)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 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
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.