Buy the Book

  GEP Biblio

  Visit Gepsoft


© C. FERREIRA, 2002 (Terms of Use) ISBN: 9729589054

Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence

Replication and selection
Although vital, replication is the most uninteresting operator of all: by itself, it contributes nothing to genetic variation. Together with selection, it creates genetic drift, changing the proportions of the particular kinds of individuals with time. But, together with selection and modification, it allows adaptation and evolution.

The selection operator selects individuals according to fitness and the luck of the roulette. The fitter the individual the higher the probability of leaving more offspring. If selection is done by roulette-wheel sampling, the roulette is spun as many times as there are individuals in the population, continuously maintaining the same population size. So, the replication operator copies exactly the chromosomes of the individuals picked up by the selection operator. And the copied chromosomes consist of the chromosomes of the individuals of the next generation. But reproduction is not yet completed. Before that, the replicated chromosomes must be modified. This modification is done by the genetic operators of mutation, transposition and recombination (the search operators). But for now let us concentrate on selection and replication.

Figure 3.9 shows how the selected individuals are replicated (the search operators and elitism were switched off in order to better understand replication and selection). For instance, chromosome 0, one of the best of generation 0, left two daughters (chromosomes 1 and 3 of generation 1); chromosome 1, also one of the best of this generation, left only one descendant (chromosome 9 of generation 1); chromosome 7, also one of the best, left two daughters (chromosomes 2 and 4 of generation 1); but chromosome 8, also one of the best, died without leaving offspring; the second best (chromosome 3) also left two daughters (chromosomes 7 and 8 of generation 1); and although the most unfit of generation 0 (chromosomes 2, 4, and 5) did not reproduce, chromosome 6, a mediocre individual, left the biggest progeny (chromosomes 0, 5, and 6 of generation 1).

Generation N: 0            Generation N: 1
01234560123456             01234560123456
OOOaaabAAAcabb-[0] = 6
     OONbcaaAaAaacc-[0] = 4
AAcbbabNONaaac-[1] = 6
     OOOaaabAAAcabb-[1] = 6
ANaccbcNAAcbbc-[2] = 2
     AcOaccbAbNbabc-[2] = 6
OAOccbaAOAbcab-[3] = 5
     OOOaaabAAAcabb-[3] = 6
AAAbbabNcObcca-[4] = 3
     AcOaccbAbNbabc-[4] = 6
NbacabbNbccbbc-[5] = 2
     OONbcaaAaAaacc-[5] = 4
OONbcaaAaAaacc-[6] = 4
     OONbcaaAaAaacc-[6] = 4
AcOaccbAbNbabc-[7] = 6
     OAOccbaAOAbcab-[7] = 5
AaOacccAbbbaca-[8] = 6
     OAOccbaAOAbcab-[8] = 5
AOAcaaaNaNbaab-[9] = 4
     AAcbbabNONaaac-[9] = 6

Figure 3.9. Illustration of replication and selection. Only replication and roulette-wheel selection are switched on so that these operators could be better understood. Note, for instance, that chromosome 8 of generation 0 (one of the best) did not leave descendants, whereas chromosome 6 (a mediocre individual) left the biggest progeny.

The outcome of such an “evolutionary” process is shown in Figure 3.10, where we can see that by generation 13 all the individuals are descendants of only one individual: in this case, chromosome 0 of generation 0. Indeed, replication, together with selection, is only capable of causing genetic drift. And, although useful for searching the fitness landscape, genetic drift by itself cannot create genetic diversity. Only the search operators have that power.

Generation N: 13
OOOaaabAAAcabb-[0] = 6
OOOaaabAAAcabb-[1] = 6
OOOaaabAAAcabb-[2] = 6
OOOaaabAAAcabb-[3] = 6
OOOaaabAAAcabb-[4] = 6
OOOaaabAAAcabb-[5] = 6
OOOaaabAAAcabb-[6] = 6
OOOaaabAAAcabb-[7] = 6
OOOaaabAAAcabb-[8] = 6
OOOaaabAAAcabb-[9] = 6

Figure 3.10. Illustration of genetic drift. In this extreme case, after 13 generations the population loses all genetic diversity, and all its members are descendants of one chromosome, in this case, chromosome 0 of generation 0 (see Figure 3.9).

Home | Contents | Previous | Next