Genetic Algorithms use an emulation of the process of evolution to seek out an optimal solution to a problem.
The GA uses the operators called
Selection and Crossover
to simulate the evolutionary process along with Mutation.
John H. Holland
first developed genetic algorithms in the early 1970's.
They utilize a survival of the fittest strategy similar the Darwinian model of evolution.
Within a GA each individual represents a particular solution to the problem that must be solved.
Each individual of the population within a GA is represented by a string of binary digits that obeys the schema theorem posed by
One of the best aspects of Genetic Algorithms is that the problem does not have to be explicitly
defined to the GA, only the fitness must be evaluated.
Although, design of the fitness algorithm may be as much or more computationally expensive than
just solving the problem in a traditional way,
there are some problems for which a traditional solution
would take thousands if not millions of years of computer time if they could be solved at all.
Genetic Algorithms excel at these problems because their parallel nature combined with the
properties of the evolutionary model defined within the GA rapidly converges to the optimum solution.
discussion of the problems encountered in designing an effective genetic algorithm
GA Router Analysis.
Most problems can be solved using traditional techniques such as the following.
Calculus Gradient Theory
This algorithm is a type of serial search for the best solution (also called Hill Climbing) where we get a partial solution and proceed in the direction where the answer is a better approximation.
An analogy of this would to find the highest peak in a range of mountains, but using only the ability to climb and not to descent. The result of this search would be highly dependent on the initial starting point. If we started at the base of a sub-ordinate peak we would reach the top but it would not be the global maximum peak.
These algorithms are used for hash searches such as fingerprint analysis reduction, and random sampling.
Here the solution is guided to its global optimum by first using a highly disordered random set of values and slowly decreasing the magnitude of a noise disruption operator so that the solution can emerge from the chaos.
This algorithms is based on the phenomena of crystal growth in slowly cooled metals, the analogy here is that the optimum crystal is one that has the structure with the least fractures.
Example Implementation: Genetic Algorithm Circuitry Router.
Genetic Algorithms exist as a conglomerate of these three, like hill-climbing the GA searches out better solutions, but in a parallel fashion on all individuals of a large population.
Each member of the population represents a particular solution to the problem, and by selecting the fittest and recombining them the fitness of the population, as a whole should rise.
The result of this implicit parallelism is that the GA should arrive at the global optimum and not at some local optimum value as in the above serial algorithms. The ability of the Genetic Algorithm to succeed is highly dependent on its fitness function and how it is specifically implemented; Koza: "we get exactly what we ask for".
The following are definitions of biological function in the context of genetic algorithms.
Chromosome: A string representation of an individual of a population
Fitness: The relative performance or correctness of the individual, or the mapping of the genotype-representation (usually a real positive value) to the phenotype-problem spaces.
Genotype: The complete genetic structure of an individual composed of 1 or more chromosomes
Mutation: The single point random flip of a bit within the chromosome that in biology occurs usually in the presence of radiation or during errors in duplication of the DNA into RNA strands.
Phenotype: The expression of the genotype when within its environment or solution space.
The following operators or phenomena are not usually applicable to genetic algorithms.
Recessive genes: Genes that are only expressed when their dominant pairs are not present.
Epistasis: The process in which a gene is expressed or suppressed due to the interaction between genes in the expression of the genotype. An example of this is when a certain gene can turn off or on the expression in the phenotype of other genes.
Example: The Golem Project at Brandeis U.
This project is very interesting in that it requires minimal human assistance.
These robots are
, and robotically fabricated, but
Humans are still required to hook up the motors
Note: golem might come from the name of the philosopher computer Golem XIV in Stanislav Lem's 1981 story about a computer that had no interest in performing its duties as a nuclear war waging machine.