Buy the Book

  Home
  News
  Author
  Q&A
  Tutorials
  Downloads
  GEP Biblio
  Contacts

  Visit Gepsoft

 

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

Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence

Gene recombination
 
In the third kind of GEP recombination, entire genes are exchanged between two parent chromosomes, forming two daughter chromosomes containing genes from both parents.

The last two populations shown in Figure 3.24 are the outcome of an evolutionary process in which the only source of variation was gene recombination at a rate pgr = 0.8. For this simple problem, again the majority function problem, it was possible to find a correct solution only by shuffling the genes already present in the initial population. Obviously, we would not have been that lucky with a more complex problem, unless huge populations had been used. Note also that, with this operator, genes never trade places in the chromosome, always occupying the same position.


Generation N: 0
012345678012345678012345678
OAOcaacacAOaAcbbcbAaAAbabbb-[0] = 6
NNcaabbabONbcbacacOAOObccbb-[1] = 4
NcaacaaacNcAaaccbcOcaaacbbb-[2] = 4
OcbaacbccAOaccbccbNONNbcbbb-[3] = 6
ONAObcbcaNANccacabNAbObacab-[4] = 4
AOaaaabacAbbObcabaNcbAacacb-[5] = 5
NONOabaaaNaObccbbbNccabcbba-[6] = 2
NAaAaacbbNANbcbacaAAONacbaa-[7] = 3
NaAAbcbbaNaOAcbacbNcAaababb-[8] = 2
AcaabbcabNAcacaacbNNOAcbbbc-[9] = 4

Generation N: 1
012345678012345678012345678
OcbaacbccAOaccbccbNONNbcbbb-[0] = 6
OcbaacbccAOaccbccbNcbAacacb-[1] = 4
NONOabaaaAOaccbccbNONNbcbbb-[2] = 7
AcaabbcabNaObccbbbNccabcbba-[3] = 4
AcaabbcabAOaAcbbcbNNOAcbbbc-[4] = 6
NONOabaaaNaObccbbbNccabcbba-[5] = 2
OAOcaacacNAcacaacbAaAAbabbb-[6] = 4
NONOabaaaNAcacaacbNNOAcbbbc-[7] = 4
AOaaaabacAbbObcabaNONNbcbbb-[8] = 6
OAOcaacacAOaAcbbcbAaAAbabbb-[9] = 6

Generation N: 2
012345678012345678012345678
NONOabaaaAOaccbccbNONNbcbbb-[0] = 7
OAOcaacacAOaAcbbcbAaAAbabbb-[1] = 6
AOaaaabacAbbObcabaNONNbcbbb-[2] = 6
AcaabbcabAOaAcbbcbNONNbcbbb-[3] = 8
NONOabaaaAOaccbccbAaAAbabbb-[4] = 7
AOaaaabacAbbObcabaNNOAcbbbc-[5] = 5
OAOcaacacAOaAcbbcbNccabcbba-[6] = 4
NONOabaaaNaObccbbbAaAAbabbb-[7] = 4
NONOabaaaNaObccbbbNONNbcbbb-[8] = 3
NONOabaaaAOaccbccbNccabcbba-[9] = 4

Figure 3.24. An initial population and its immediate descendants created, via gene recombination, to solve the Majority (a, b, c) function problem. The chromosomes encode sub-ETs linked by OR. The perfect solution found in generation 2 (chromosome 3) is a daughter of chromosomes 4 and 8 of the previous generation (also shown in blue). Their other daughter (chromosome 5) is also shown in blue. Note that chromosome 5 is less fit than its parents whereas chromosome 3 surpasses them greatly. In fact, it codes for a perfect solution to the majority problem.


Figure 3.25 shows the gene recombination event that led to the perfect solution shown in Figure 3.24. In this case, gene 3 was exchanged between chromosomes 4 and 8 of generation 1, obtaining two new daughter chromosomes (chromosomes 3 and 5 of generation 2). Note that chromosome 5 is less fit than its parents, whereas chromosome 3 surpasses them greatly. Indeed, this chromosome has maximum fitness and therefore codes for a perfect solution to the majority function problem.



Figure 3.25. Illustration of gene recombination and its effects. a) An event of gene recombination. In this case, the parent chromosomes exchanged gene 3, forming two new daughter chromosomes. Note that both the parents and the offspring differ among themselves. b) The sub-ETs encoded by the parents (before recombination). c) The sub-ETs encoded by the daughter chromosomes (after recombination).


It is worth emphasizing that this operator is unable to create new genes: the individuals created by gene recombination are different arrangements of existing genes. Obviously, if gene recombination was used as the unique source of genetic variation, more complex problems could only be solved using very large initial populations in order to provide for the necessary diversity of genes (see chapter 7 for a discussion). However, GEP evolvability is based not only in the shuffling of genes (achieved by gene recombination and gene transposition), but also in the constant creation of new genetic material which is carried out essentially by mutation and transposition (both IS and RIS transposition) and, to a lesser extent, by recombination (both one-point and two-point recombination).

Home | Contents | Previous | Next