Evolutionary algorithm

From Wikipedia, the free encyclopedia

Artificial intelligence Portal

In artificial intelligence, an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses some mechanisms inspired by biological evolution: reproduction, mutation, recombination, natural selection and survival of the fittest. Candidate solutions to the optimization problem play the role of individuals in a population, and the cost function determines the environment within which the solutions "live" (see also fitness function). Evolution of the population then takes place after the repeated application of the above operators. Artificial evolution (AE) describes a process involving individual evolutionary algorithms; EAs are individual components that participate in an AE.

Evolutionary algorithms consistently perform well approximating solutions to all types of problems because they do not make any assumption about the underlying fitness landscape; this generality is shown by successes in fields as diverse as engineering, art, biology, economics, genetics, operations research, robotics, social sciences, physics, and chemistry. However, the no-free-lunch theorem shows that evolutionary algorithms can nonetheless be outperformed by more field-specific algorithms.

Apart from their use as mathematical optimizers, evolutionary computation and algorithms have also been used as an experimental framework within which to validate theories about biological evolution and natural selection, particularly through work in the field of artificial life. Techniques from evolutionary algorithms applied to the modelling of biological evolution are generally limited to explorations of microevolutionary processes, however some computer simulations, such as Tierra and Avida, attempt to model macroevolutionary dynamics.

A limitation of evolutionary algorithms is their lack of a clear genotype-phenotype distinction. In nature, the fertilized egg cell undergoes a complex process known as embryogenesis to become a mature phenotype. This indirect encoding is believed to make the genetic search more robust (i.e. reduce the probability of fatal mutations), and also may improve the evolvability of the organism. Recent work in the field of artificial embryogeny, or artificial developmental systems, seeks to address these concerns.

1 Evolutionary Algorithm techniques
2 Related techniques
3 Bibliography
4 See also
5 External links

[edit] Evolutionary Algorithm techniques

Similar techniques differ in the implementation details and the nature of the particular applied problem.

Genetic algorithm - This is the most popular type of EA. One seeks the solution of a problem in the form of strings of numbers (traditionally binary, although the best representations are usually those that reflect something about the problem being solved - these are not normally binary), virtually always applying recombination operators in addition to selection and mutation. This type of EA is often used in optimization problems. It is very important to note, however, that while evolution can be considered to approach an optimum in computer science terms, actual biological evolution does not seek an optimum; it works in the "here and now";
Evolutionary programming - Like genetic programming, only the structure of the program is fixed and its numerical parameters are allowed to evolve;
Evolution strategy - Works with vectors of real numbers as representations of solutions, and typically uses self-adaptive mutation rates;
Genetic programming - Here the solutions are in the form of computer programs, and their fitness is determined by their ability to solve a computational problem.
Learning classifier system - Instead of using a fitness function, rule utility is decided by a reinforcement learning technique.

[edit] Related techniques

Differential evolution - Based on vector differences and is therefore primarily suited for numerical optimization problems.
Particle swarm optimization - Based on the ideas of animal flocking behaviour. Also primarily suited for numerical optimization problems.
Ant colony optimization - Based on the ideas of ant foraging by pheromone communication to form path. Primarily suited for combinatorial optimization problems.
Invasive weed optimization algorithm - Based on the ideas of weed colony behavior in searching and finding a suitable place for growth and reproduction.

[edit] Bibliography

Bäck, T. (1996), Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms, Oxford Univ. Press.
Bäck, T., Fogel, D., Michalewicz, Z. (1997), Handbook of Evolutionary Computation, Oxford Univ. Press.
Eiben, A.E., Smith, J.E. (2003), Introduction to Evolutionary Computing, Springer.