Grammatical Evolution in Dynamic Environments
University College Dublin, Ireland, (2007)Abstract
Many real-world problems are anchored in dynamic
environments, where some element of the problem domain
changes with time. The application of Evolutionary
Computation (EC) to dynamic environments creates
challenges different to those encountered in static
environments. Foremost among these, are issues of
premature convergence, and the evolution of overfit
solutions. This study aims to identify mechanisms that
address these problems. A recent powerful addition to
the stable of EC methodologies is Grammatical Evolution
(GE). GE uses BNF grammars for the evolution of
variable length programs. Thus far, there has been
little study of the utility of GE in dynamic
environments. A comprehensive analysis of prior work in
EC and GE in the context of dynamic environments is
presented. From this, it is seen that GE offers
substantial potential due to the flexibility provided
by the BNF grammar and the many-to-one
genotype-to-phenotype mapping. Subsequently novel
methods of constant creation are introduced that
incorporate greater levels of latent evolvability
through the use of BNF grammars. These methods are
demonstrated to be more accurate and adaptable than the
standard methods adopted. Through placing GE in the
context of a dynamic real-world problem, the trading of
financial indices, phenotypic diversity is demonstrated
to be a function of the fitness landscape. That is,
phenotypic entropy fluctuates with the universe of
potentially fit solutions. Evidence is also presented
of the evolution of robust solutions that provide
superior out-of-sample performance over a statically
trained population. The findings in this study
highlight the importance of the genotype-to-phenotype
mapping for evolution in dynamic environments and
uncover some of the potential benefits of the
incorporation of BNF grammars in GE.