Аннотация
We investigate in detail what happens as genetic
programming (GP) populations evolve. Since we shall use
the populations which showed GP can evolve stack data
structures as examples, we start in Section 1 by
briefly describing the stack experiment
Langdon:1995:GPdata. In Section 2 we show
Price's Covariance and Selection Theorem can be applied
to Genetic Algorithms (GAs) and GP to predict changes
in gene frequencies. We follow the proof of the theorem
with experimental justification using the GP runs from
the stack problem. Section 3 briefly describes Fisher's
Fundamental Theorem of Natural Selection and shows in
its normal interpretation it does not apply to
practical GAs.
An analysis of the stack populations, in Section 4,
explains that the difficulty of the stack problem is
due to the presence of ``deceptive'' high scoring
partial solutions in the population. These cause a
negative correlation between necessary primitives and
fitness. As Price's Theorem predicts, the frequency of
necessary primitives falls, eventually leading to their
extinction and so to the impossibility of finding
solutions like those that are evolved in successful
runs.
Section 4 investigates the evolution of variety in GP
populations. Detailed measurements of the evolution of
variety in stack populations reveal loss of diversity
causing crossover to produce offspring which are copies
of their parents. Section 5 concludes with measurements
that show in the stack population crossover readily
produces improvements in performance initially but
later no improvements at all are made by
crossover.
Section 6 discusses the importance of these results to
GP in general.
Пользователи данного ресурса
Пожалуйста,
войдите в систему, чтобы принять участие в дискуссии (добавить собственные рецензию, или комментарий)