Buy the Book

  GEP Biblio

  Visit Gepsoft


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

Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence

One-point recombination
In one-point recombination the parent chromosomes are paired and split up at exactly the same point. The material downstream of the recombination point is afterwards exchanged between the two chromosomes. In GEP, an event of recombination always involves two parent chromosomes and always results in two new individuals. Usually the new daughter chromosomes are as different from each other as they are from their mothers.

Figure 3.20 shows three populations an initial population and two later generations obtained in a run in order to show the workings of one-point recombination. In this experiment, the only source of genetic variation was one-point recombination at a rate of p1r = 0.8 so that the effects of this operator could be clearly analyzed. Chromosomes 1 and 6 of generation 13 are the result of a recombination event between chromosomes 6 and 7 of generation 12. In this case, the chromosomes crossed over point 1 (between positions 0 and 1) of gene 1, exchanging part of gene 1 and the entire gene 2 (Figure 3.21).

                  Generation N: 0
                  OccbccbacAOAccaaaa-[0] = 6
                  AcbcacabcAcAAcacac-[1] = 7
                  AbNNabbccOaacaacbc-[2] = 6
                  OcbObcacaAAObbabbc-[3] = 6
                  ONbNaabbcOaOaaaccb-[4] = 6
                  AcaccbcaaNNcAcabcb-[5] = 6
                  AOcNaabacONOcccaac-[6] = 4
                  NOacccacaOOONbbbcb-[7] = 4
                  AAcNaabbcAONOccaca-[8] = 4
                  ObcbcbacbNbObbbaaa-[9] = 4


Generation N: 12                   Generation N: 13
012345678012345678                 012345678012345678
AcbcacaccAcAAcacbc-[0] = 7         AcbcacacaAcAAcacbc-[0] = 7
AcbcacacaAAObbabbc-[1] = 6 
        AObcacacaAcAAcacbc-[1] = 8
AcbcacacaAcAAcacbc-[2] = 7 
        AcbcacaccAcAAcacbc-[2] = 7
AcbcacaccAcAAcacbc-[3] = 7
         AcbcacaccAcAAcacbc-[3] = 7
AcbcacacaAcAAbabbc-[4] = 6 
        AcbcacaccAcAAcacbc-[4] = 7
AcbcbcacaAcAAcacbc-[5] = 7 
        AcbcacaccAcAAbabbc-[5] = 6
NObcacacaAcAAcacbc-[6] = 4 
        NcacccacaAAOAcacbc-[6] = 4
AcacccacaAAOAcacbc-[7] = 7 
        AcbcacacaAAObbabbc-[7] = 6
AcbcacacaAAObcacbc-[8] = 6 
        AcbcacacaAcAAcacbc-[8] = 7
AcbcacacaAcAAcacbc-[9] = 7 
        AcbcacacaAAObbabbc-[9] = 6

Figure 3.20. An initial population and its later descendants created, via one-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 13 (chromosome 1) is a daughter of chromosomes 6 and 7 of the previous generation (also shown in blue). Their other daughter (chromosome 6) is also highlighted. Note that none of the later descendants resembles their ancestors of generation 0. The event of one-point recombination that led to the creation of the perfect solution is shown in Figure 3.21.

The expression of these four chromosomes (parents and progeny) shows how profound one-point recombination can be. In this case, the first gene was split immediately after the start position, drastically reshaping the sub-ETs, whereas the second gene was left undisturbed. One of the newly created individuals (chromosome 6) is as mediocre as the worse of its progenitors; the other (chromosome 1) is better than its parents and, in fact, is a perfect solution to the problem at hand.

Figure 3.21. Illustration of one-point recombination and its effects. a) An event of one-point recombination. The daughter chromosomes are the result of crossing over point 1 (between positions 0 and 1 in gene 1). Note that both mothers and daughters differ among themselves. 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 a perfect solution to the majority problem.

It is worth emphasizing that GEP chromosomes can cross over any point in the genome, continually disrupting old building blocks and continually forming new ones. Furthermore, due to both the multigenic nature of GEP chromosomes and the existence of non-coding regions in most genes, entire genes and intact ORFs can be swapped between parent chromosomes. Thus, the disruptive tendencies of one-point recombination (splitting of building blocks) coexist side by side with its more conservative tendencies (swapping of genes and ORFs), making one-point recombination (and of course two-point recombination) a very well balanced genetic operator. Furthermore, like all the other recombinational operators, when used together with gene transposition, one-point recombination is also capable of duplicating genes.

Home | Contents | Previous | Next