GEP Book

  Home
  News
  Author
  Q&A
  Tutorials
  Downloads
  GEP Biblio
  Contacts

  Visit Gepsoft

 

C. FERREIRA In Leandro N. de Castro and Fernando J. Von Zuben, eds., Recent Developments in Biologically Inspired Computing, pages 82-103, Idea Group Publishing, 2004.

Gene Expression Programming and the Evolution of Computer Programs

Genetic Operators and Evolution
 
Genetic operators are the core of all evolutionary algorithms, and two of them are common to all evolutionary systems: selection and replication. Indeed, all artificial systems use a scheme to select individuals more or less according to fitness. Some schemes are totally deterministic, whereas others include a touch of unpredictability. Gene expression programming uses one of the latter, namely, a fitness proportionate roulette-wheel scheme (see e.g. Goldberg 1989) coupled with the cloning of the best individual (simple elitism) as it mimics nature very faithfully and produces very good results.

Thus, according to fitness and the luck of the draw, individuals are selected to be replicated. Although crucial, replication is the most uninteresting operator. During replication, chromosomes are dully copied and passed on to the next generation. The fitter the individual the higher the probability of passing on its genes to the next generation. So, during replication, the genomes of the selected individuals are copied every time the roulette picks them up. And the roulette is spun as many times as there are individuals in the population so that the same population size is maintained from generation to generation.

Although the center of the storm, by themselves, selection and replication, do nothing in terms of adaptation. In fact, by themselves they can only cause genetic drift, making populations less and less diverse with time until all the individuals are exactly the same. So, the corner stone of all evolutionary systems is genetic modification. And different algorithms create this modification differently. For instance, genetic algorithms normally use mutation and recombination; genetic programming uses almost exclusively tree recombination; and gene expression programming uses mutation, inversion, transposition, and recombination.

With the exception of GP, which is severely constrained in terms of tools of genetic modification, in both GAs and GEP it is possible to implement easily a vast set of search operators because the search operators act on simple linear chromosomes. In fact, a varied set of search operators was implemented in gene expression programming in order to shed some light on the dynamics of evolutionary systems, but what is important is to provide for the necessary degree of genetic diversification in order to allow an efficient evolution. Nevertheless, mutation (by far the most efficient operator) by itself is capable of wonders. However, the interplay of mutation with other operators not only allows an efficient evolution but also allows the duplication of genes and their subsequent differentiation, the creation of small repetitive sequences, and so forth, making things really interesting.

In the remainder of this section we will see how the search operators work and how their implementation in gene expression programming is a child’s play due to the simple fact that the genome is completely autonomous and consequently is not tied up in the structural complexities of the computer programs encoded within.

Home | Contents | Previous | Next