Springer
Table of ContentsAuthor IndexSearch

Diversity in Multipopulation Genetic Programming

Marco Tomassini1, Leonardo Vanneschi1, Francisco Fernández2, and Germán Galeano2

1Computer Science Institute
University of Lausanne
Lausanne, Switzerland

2Computer Science Institute
University of Extremadura
Spain

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 $P$, defined as $H(P)=-\sum _{j=1}^{N}F_j \log (F_j)$. If we are considering phenotypic diversity, we define Fj as the fraction ${n_j}/ {N}$ of individuals in $P$ having a certain fitness $j$, where $N$ is the total number of fitness values in $P$. In this case, the entropy measure will be indicated as $H_p(P)$ 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 $P$ having a certain genotype $j$, where $N$ is the total number of genotypes in $P$ and the entropy measure will be indicated as $H_G(P)$ 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 $j$ from a fixed tree (called origin), where $N$ is the total number of distance values from the origin appearing in $P$ and the entropy measure will be indicated as $H_g(P)$ or simply Hg. The tree distance used is Ekárt's and Németh's definition [1].

LNCS 2724, p. 1812 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003