Table 3.1
Majority function.

Thus, with the symbols from F and T, the chromosomes of the initial population are randomly generated. Obviously, the heads of the genes are created using the elements from both F and T, whereas the tails of the genes are created using only terminals. Figure 3.2 shows a small initial population (also called generation 0) of 10 individuals randomly created to solve the majority problem. The chromosomes are composed of two genes, each with a length of 7 (h = 3 and t = 4). The chromosomes encode sub-ETs which are posttranslationally linked by the Boolean function OR.

Figure 3.2. The chromosomes of a small initial population created to solve the Majority (a, b, c) function problem. The randomly generated chromosomes are composed of two genes, encoding sub-ETs linked by OR.

It is worth noticing how easily the initial populations of gene expression programming are created. The simple structures of the chromosomes are randomly created using the symbols of the function and terminal sets and nothing whatsoever needs to be done to monitor their structural soundness: we know for sure that, without exception, all of them encode valid programs. As a comparison, the random generation of trees in GP must be done with extreme care in order to guarantee the formation of syntactically correct programs. Not surprisingly, the generation of initial populations in GP is a complicated, time consuming process.

After the random generation of the chromosomes of the individuals of the initial population, the chromosomes are expressed, and the fitness of each individual is evaluated. Figure 3.3 shows the fitness of each individual at the majority task (for simplicity, only the chromosomes of the individuals are shown).

Figure 3.3. The chromosomes of the individuals of the initial population and their respective fitness (the value after the equal sign). The fitness corresponds to the number of fitness cases correctly solved by the program encoded in each chromosome.

Then, according to fitness, the individuals are selected to reproduce with modification. For instance, all the 10 individuals of the initial population shown in Figure 3.2 are viable and are therefore eligible to be selected to reproduce. These viable individuals, among themselves, create as many new individuals as there are individuals in the population. As such, throughout a run, the population size is kept unchanged. The descendants of the selected individuals consist of the new members of the next generation. The expression of one of the best of generation 0 (chromosome 8) is shown in Figure 3.4. This individual was able to solve correctly five fitness cases, and thus its fitness is equal to 5.

Figure 3.4. Expression of the best individual of generation 0. 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 five out of eight fitness cases.

You have probably noticed that all the genes created randomly in the initial population have a function at position 0. Although I have chosen to have all the genes in the initial population starting with a function, this is not very important in multigenic individuals. This feature of initial populations is a remnant of the evolutionary process of GEP itself, for the first GEP implementation used chromosomes composed of only one gene. In those systems, genes coding for one-element ETs were of little use and were excluded from the populations. When multigenic chromosomes were developed, I did not change this feature of initial populations because terminals can be inserted at the start site of a gene in future generations. And if this happens to be advantageous for a certain task, this kind of gene can certainly evolve. We will see later on in this chapter that point mutation allows the evolution of genes encoding one-element sub-ETs.

The problem with the random generation of initial populations is that, sometimes, especially if the number of individuals and the number of fitness cases are small, none of the chromosomes encodes viable individuals and the run is aborted (this is highly improbable for Boolean problems, though). A simple form of circumventing this problem, consists of introducing a start up control. This control is by default set to one viable chromosome, and was used in all the problems presented in this book. We will see that GEP populations can efficiently evolve even when all the individuals are descendants of a sole viable founder (see chapter 7 for a discussion). This control mechanism, together with the cloning of the best individual (see section 3.1.2), prevents the existence of failed runs in gene expression programming. So, if all the individuals of the initial population had fitness 0, another initial population would be randomly generated. This process is repeated until at least one viable individual is created.