Buy the Book

  GEP Biblio

  Visit Gepsoft


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

Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence

Two-point recombination
In two-point recombination the parent chromosomes are paired and two points are randomly chosen by which both chromosomes are split. The material between the recombination points is then exchanged between the two chromosomes, forming two new daughter chromosomes.

Figure 3.22 shows two-point recombination at work. An initial population and its immediate descendants obtained in a run are shown. In this experiment, the only source of genetic variation was a two-point recombination rate p2r of 0.8. Note that a perfect solution was obtained early in generation 1 (chromosome 3). Indeed, when recombination is the only source of genetic variation, most of the times, perfect solutions are either found early on in the run or are not found at all, as populations become less and less diverse with time (see chapter 7). Note that chromosomes 1 and 3 of generation 1 are the daughters of chromosomes 4 and 6 of the initial population.

Generation N: 0
ONOANbbcaaaNcONcaabccc-[0] = 4
ANANbaacbbcNANOAabbcbc-[1] = 5
NNNcOacbbabONcbacbbabb-[2] = 4
ANAcbbababcNcbNbabcaab-[3] = 2
AOaObbcccacObaNOacabab-[4] = 6
OOAcOaabccaAacbNcbaccb-[5] = 5
OcbbAcccbccAAOObacbaab-[6] = 6
NbAANccbacaAbNNNbbcbbc-[7] = 2
AaONbaababcAbNNAcacaaa-[8] = 6
NOAcObaccbaAObbObcacca-[9] = 4

Generation N: 1
AaONbaababcAbNNAcacaaa-[0] = 6
OcbbAccccacObaObacbaab-[1] = 5
AOaObaabccaAacbNacabab-[2] = 6
AOaObbccbccAAONOacabab-[3] = 8
ONOANbbcaaaNcONcaabccc-[4] = 4
OOAcOaabccaAaNONcbaccb-[5] = 5
OOAcObcccacObaNOcbaccb-[6] = 5
ANANbaacbbcNAcbAabbcbc-[7] = 3
ANANbaacbbcNANOAabbcbc-[8] = 5
OaOANbbcaaaNcONcaabccc-[9] = 5

Figure 3.22. An initial population and its immediate descendants created, via two-point recombination, to solve the Majority (a, b, c) function problem. The chromosomes encode sub-ETs linked by OR. The perfect solution found in generation 1 (chromosome 3) is a daughter of chromosomes 4 and 6 (shown in blue). Their other daughter (chromosome 1) is also highlighted. Note that chromosome 1 is less fit than both mothers whereas chromosome 3 surpasses them greatly.

The event that led to the creation of the perfect solution is shown in Figure 3.23. In this case, the parent chromosomes exchanged the genetic material between point 7 (between positions 6 and 7 of gene 1) and point 14 (between positions 2 and 3 of gene 2). Note that the first gene is, in both parents, split downstream of the termination point. Indeed, the non-coding regions of GEP chromosomes are ideal regions where chromosomes can be split to cross over without disrupting the ORFs. We have already seen that these regions are also ideal places where neutral mutations can accumulate. Note also that the second gene of chromosome 4 was also cut downstream of the termination point. However, gene 2 of chromosome 6 was split upstream of the termination point, changing profoundly the encoded sub-ET. Furthermore, when these chromosomes recombined, the non-coding region of chromosome 4 was activated, integrating the perfect solution found in generation 1 (chromosome 3).

Figure 3.23. Illustration of two-point recombination and its effects. a) An event of two-point recombination. The daughter chromosomes were obtained after crossing over points 7 (between positions 6 and 7 in gene 1) and 14 (between positions 2 and 3 in gene 2). Note that both parents and offspring are different. b) The sub-ETs encoded by the mother chromosomes (before recombination). c) The sub-ETs encoded by the daughter chromosomes (after recombination). Note that daughter dA is much better than its parents. In fact, it is a perfect solution to the majority function.

It is worth emphasizing that two-point recombination is more disruptive than one-point recombination in the sense that it recombines the genetic material more thoroughly, constantly destroying old building blocks and creating new ones (see chapter 7 for a comparison with the other recombinational operators). But like one-point recombination, two-point recombination has also a conservative side and is good at swapping entire genes and ORFs. And finally, two-point recombination can also give rise to duplicated genes if used together with gene transposition.

Notwithstanding, if the goal is to evolve good solutions, one-point or two-point recombination should never be used as the only source of genetic variation as they tend to homogenize populations (see chapter 7 for a discussion). However, together with mutation and transposition, these operators are an excellent source of genetic variation and are more than sufficient to evolve good solutions to virtually all problems.

Home | Contents | Previous | Next