Figure 3.5. The descendants of the initial population shown in Figure 3.3. Five of them are better than the best of the previous generation.

And the expression of one of the best individuals of this generation (chromosome 5) is shown in Figure 3.6. I only used mutation and one-point recombination as sources of genetic modification in order to simplify the analysis of the evolutionary history of the population.

Figure 3.6. Expression of one of the best individuals of generation 1. a) The chromosome composed of two genes. b) The program encoded in the chromosome. The linking function is shown in gray. This Boolean function solves correctly six out of eight fitness cases.

Note that chromosome 0 of generation 1 (Figure 3.5) is an exact copy of one of the best individuals of the initial population (chromosome 8 in Figure 3.3). Indeed, from generation to generation, the best individual (or one of the best) is replicated unchanged into the next generation. If the best fitness is shared by more than one individual in the population, the last one is chosen to become a clone. In the case of generation 1, chromosome 5 will be replicated without modification and will occupy the first place in the next generation (see Figure 3.7 below). When this happens, the individual occupying that position dies. This is important to keep in mind when we are analyzing the outcome of certain operators, like recombination, where one of the daughter chromosomes might not be present in the next generation. The cloning of the best, also called simple elitism, guarantees that at least one descendant will be viable (obviously, only in problems where the selection environment is kept the same from generation to generation), keeping at the same time the best trait during the process of adaptation. Elitism plays also another role: it allows the use of several genetic operators at relatively high rates without the risk of causing a mass extinction.

In nature, at least in periods of stasis, the rates of mutation are tightly controlled and usually very small, and adaptation and evolution occur very smoothly. In GEP, populations are always evolving at high creative rates in what Eldredge and Gould called creative periods in their theory of punctuated equilibrium (Eldredge and Gould 1972). So, in artificial evolutionary systems, evolution can be much faster and kept in constant turmoil, allowing the discovery of very good solutions in record time.

Figure 3.7 shows the next generation (generation 2) created in this evolutionary process. The best individual of this generation (chromosome 8) has maximum fitness and thus encodes a perfect solution to the majority function. In fact, as shown in Figure 3.8, this chromosome codes for one of the most parsimonious solutions to the majority function.

Figure 3.7. The next generation of computer programs evolved to solve the Majority (a, b, c) function problem. The individuals of this generation are the immediate descendants of the selected individuals of the previous generation. Note that a perfect program with maximum fitness was discovered (chromosome 8), thus considerably better than its ancestors.

It is worth noticing that, in this run, some individuals contain genes encoding one-element sub-ETs (chromosomes 1, 4, and 7 of generation 1; and chromosome 7 of generation 2) as they have a terminal at the start position of one of their genes. All these genes could only have evolved by mutation, for only mutation is capable of introducing a terminal at the root of a sub-ET (see section 3.3 for a detailed analysis of the genetic operators used in GEP).

Figure 3.8. A perfect, parsimonious solution to the Majority (a, b, c) function. a) The chromosome encoding two genes linked by OR. b) The perfect solution to the majority function encoded in the chromosome. The linking function is shown in gray.