Diversity in Multipopulation Genetic Programming
Genetic and Evolutionary Computation -- GECCO-2003, volume 2724 of LNCS, page 1812--1813. Chicago, Springer-Verlag, (12-16 July 2003)Abstract
In the past few years, we have done a systematic
experimental investigation of the behavior of
multipopulation GP 2 and we have empirically observed
that distributing the individuals among several loosely
connected islands allows not only to save computation
time, due to the fact that the system runs on multiple
machines, but also to find better solution quality.
These results have often been attributed to better
diversity maintenance due to the periodic migration of
groups of "good" individuals among the
subpopulations. We also believe that this might be the
case and we study the evolution of diversity in
multi-island GP. All the diversity measures that we use
in this paper are based on the concept of entropy of a
population , defined as . If we are considering
phenotypic diversity, we define Fj as the fraction of
individuals in having a certain fitness , where is the
total number of fitness values in . In this case, the
entropy measure will be indicated as or simply Hp. To
define genotypic diversity, we use two different
techniques. The first one consists in partitioning
individuals in such a way that only identical
individuals belong to the same group. In this case, we
have considered Fj as the fraction of trees in the
population having a certain genotype , where is the
total number of genotypes in and the entropy measure
will be indicated as or simply HG. The second technique
consists in defining a distance measure, able to
quantify the genotypic diversity between two trees. In
this case, Fj is the fraction of individuals having a
given distance from a fixed tree (called origin), where
is the total number of distance values from the origin
appearing in and the entropy measure will be indicated
as or simply Hg. The tree distance used is Ekart's and
Nemeth's definition 1.