GEP Book

  Home
  News
  Author
  Q&A
  Tutorials
  Downloads
  GEP Biblio
  Contacts

  Visit Gepsoft

 

C. FERREIRA Invited Tutorial Presented at WSC6, 2001

Gene Expression Programming in Problem Solving

Selection and Replication
 

All artificial systems use a scheme to select individuals more or less according to fitness. Some schemes are totally deterministic, whereas others include a touch of unpredictability. For GEP, I chose one of the latter, namely, a fitness proportionate roulette-wheel scheme (Goldberg 1989) coupled with the cloning of the best individual (simple elitism) as it pretty accurately mimics nature and produces very good results.

According to fitness and the luck of the roulette, individuals are selected to be replicated. Although vital, replication is the most uninteresting operator. During replication, chromosomes are dully copied into the next generation. The fitter the individual the higher the probability of leaving more offspring. Thus, during replication, the genomes of the selected individuals are copied as many times as the outcome of the roulette. The roulette is spun as many times as there are individuals in the population, maintaining always the same population size.

Figure 4 shows how selected individuals are replicated (the other operators and elitism were switched off in order to better understand replication and roulette-wheel selection). For instance, chromosome 3, the best individual of generation 0, left only one daughter (chromosome 4 of generation 1); chromosome 1, the second best of generation 0, left two descendants (chromosomes 1 and 9 of generation 1); chromosome 0, a medium individual, died without leaving offspring; and, although one of the most unfit of generation 0, chromosome 6, didn’t reproduce, a mediocre individual, chromosome 9, left one of the biggest progeny (chromosomes 5 and 6 of generation 1). The outcome of such an ‘evolutionary’ process is shown in Figure 5, where we can see that by generation 8 all the individuals are descendants of only one individual: in this case, chromosome 1 of the initial population (see Figure 4). Indeed, replication and selection alone are only capable of causing genetic drift.


Generation N: 0
01234567890120123456789012
*+-/a*aaaaaaa//+*aaaaaaaaa-[0] = 10.64033
/-/a//aaaaaaa+*+a/+aaaaaaa-[1] = 16.2117
*+a-+aaaaaaaa---///aaaaaaa-[2] = 13.81953
+a*/-aaaaaaaa**+a*aaaaaaaa-[3] = 18.32701
*-+a/-aaaaaaa/aa+a/aaaaaaa-[4] = 11.13926
+*//a/aaaaaaa---aa-aaaaaaa-[5] = 13.88255
*-*-*aaaaaaaa/-a///aaaaaaa-[6] = 7.777691
/++a-*aaaaaaa/+a*+-aaaaaaa-[7] = 13.14786
//+*aaaaaaaaa*+-/--aaaaaaa-[8] = 7.713599
-**+-/aaaaaaa*//aa/aaaaaaa-[9] = 8.73985

Generation N: 1
01234567890120123456789012
*+a-+aaaaaaaa---///aaaaaaa-[0] = 13.81953
/-/a//aaaaaaa+*+a/+aaaaaaa-[1] = 16.2117
*-+a/-aaaaaaa/aa+a/aaaaaaa-[2] = 11.13926
+*//a/aaaaaaa---aa-aaaaaaa-[3] = 13.88255
+a*/-aaaaaaaa**+a*aaaaaaaa-[4] = 18.32701
-**+-/aaaaaaa*//aa/aaaaaaa-[5] = 8.73985
-**+-/aaaaaaa*//aa/aaaaaaa-[6] = 8.73985
//+*aaaaaaaaa*+-/--aaaaaaa-[7] = 7.713599
/++a-*aaaaaaa/+a*+-aaaaaaa-[8] = 13.14786
/-/a//aaaaaaa+*+a/+aaaaaaa-[9] = 16.2117 

Figure 4. An initial population (generation 0) and their immediate descendants (generation 1). The value after each chromosome indicates the fitness.


Generation N: 8
01234567890120123456789012
/-/a//aaaaaaa+*+a/+aaaaaaa-[0] = 16.2117
/-/a//aaaaaaa+*+a/+aaaaaaa-[1] = 16.2117
/-/a//aaaaaaa+*+a/+aaaaaaa-[2] = 16.2117
/-/a//aaaaaaa+*+a/+aaaaaaa-[3] = 16.2117
/-/a//aaaaaaa+*+a/+aaaaaaa-[4] = 16.2117
/-/a//aaaaaaa+*+a/+aaaaaaa-[5] = 16.2117
/-/a//aaaaaaa+*+a/+aaaaaaa-[6] = 16.2117
/-/a//aaaaaaa+*+a/+aaaaaaa-[7] = 16.2117
/-/a//aaaaaaa+*+a/+aaaaaaa-[8] = 16.2117
/-/a//aaaaaaa+*+a/+aaaaaaa-[9] = 16.2117

Figure 5. Illustration of genetic drift. After 8 generations, the population loses all diversity, and all its members are descendants of chromosome 1 of the initial population (see Figure 4).

Home | Contents | Previous | Next