GEP Book

  Home
  News
  Author
  Q&A
  Tutorials
  Downloads
  GEP Biblio
  Contacts

  Visit Gepsoft

 

C. FERREIRA Invited Tutorial Presented at WSC6, 2001

Gene Expression Programming in Problem Solving

Genetic Algorithms
 
Genetic algorithms, invented by J. Holland in the 1960s, applied biological evolution theory to computer systems (Holland 1975). Like all evolutionary computer systems, GAs are an oversimplification of biological evolution. In this case, solutions to a problem are encoded in character strings (usually 0’s and 1’s), and a population of these solutions is left to evolve in order to find a solution to the problem at hand. Populations, and therefore solutions, evolve because individual solutions (chromosomes) reproduce with modification. This is obviously the prerequisite for evolution to occur. Modification in the original GA was introduced by mutation, crossover, and inversion. In addition, for evolution to occur, individuals must pass the sieve of selection. They are selected according to fitness, being the fitness rigorously determined and its value used to reproduce them proportionately. The higher the fitness, the higher the probability of leaving more offspring.

The chromosomes of GAs are simple replicators (e.g., Dawkins 1995), and therefore they survive by virtue of their properties alone. This is equivalent to say that they function simultaneously as genome and phenome. So, the chromosomes are not only keepers of the genetic information that is replicated and transmitted with modification to the next generation, but are also the object of selection. The variety of functions GAs’ chromosomes are able to play is severely limited by this dual role and by their structural organization, especially the simple language of chromosomes and their fixed length. This very much resembles a simple RNA World, where the linear RNA genome is also capable of exhibiting structural diversity. In this case, the whole structure of the RNA molecule determines the functionality and, therefore, the fitness of the individual. For instance, it wouldn’t be possible in such systems to use only a particular region of the genome as a solution to the problem: the whole genome is always the solution. Obviously these systems are severely constrained.

Home | Contents | Previous | Next