Buy the Book

  Home
  News
  Author
  Q&A
  Tutorials
  Downloads
  GEP Biblio
  Contacts

  Visit Gepsoft

 

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

Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence

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 candidate solutions is left to evolve in order to find a good solution to the problem at hand. Populations, and therefore solutions, evolve because individual solutions (chromosomes) reproduce with modification. As we have seen, this is 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.

Genetic algorithms use only one kind of entity: the chromosomes. Therefore, GAs’ chromosomes are simple replicators. They consist of linear symbolic strings of fixed length and represent a possible solution to the problem at hand. For each problem, a representation scheme must be created and rigorously defined in order to evaluate the fitness of each chromosome. The creation of the representation scheme is, in fact, the most difficult aspect in the implementation of the algorithm but, once devised, the problem can be encoded in symbolic chromosomes. An initial population of these chromosomes (candidate solutions) is randomly generated and left to evolve for a certain number of generations or until a good solution to the problem has been found.

Like all simple replicators, GAs’ chromosomes function simultaneously as genotype and phenotype: they are both the object of selection and the guardians of the genetic information that must be replicated and transmitted with modification to the next generation. Whatever is done in the genome will affect fitness and selection. To make this important feature of GAs clearer, compare this situation with the current state of nature where individuals are selected by virtue of the properties of their bodies alone: only the body of the individual and the abilities it can perform are important to the selection process; the state of its genome is irrelevant.

The variety of functions GAs’ chromosomes are able to play is severely limited by this dual function they play (genotype and phenotype) and by their structural organization, especially the simple language of chromosomes and their fixed length. This very much resembles a simple RNA replicator, where the linear RNA genome is also capable of exhibiting limited structural and functional diversity. In both cases, the whole structure of the replicator determines the functionality and, therefore, the fitness of the individual. For instance, it would not be possible to use only a particular region of the replicator as a solution to a problem in such systems: the whole replicator is always the solution: nothing more, nothing less. As a result, these systems are severely constrained.

Home | Contents | Previous | Next