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. Image File history File links Portal. ... // Hondas intelligent humanoid robot AI redirects here. ... EA, Ea, or ea can signify several things. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, a set A is a subset of a set B, if A is contained inside B. The relationship of one set being a subset of another is called inclusion. ... In computer science evolutionary computation is a subfield of artificial intelligence (more particularly computational intelligence) involving combinatorial optimization problems. ... A metaheuristic is a heuristic method for solving a very general class of computational problems by combining user given black-box procedures — usually heuristics themselves — in a hopefully efficient way. ... It has been suggested that Loop optimization be merged into this article or section. ... Flowcharts are often used to graphically represent algorithms. ... This article is about biological evolution. ... For other uses, see Reproduction (disambiguation) Reproduction is the biological process by which new individual organisms are produced. ... In biology, mutations are changes to the genetic material (either DNA or RNA). ... Recombination usually denotes a genetic event that occurs during the formation of sperm and egg cells (especially in areas of study of biology topics). ... Natural selection is the process by which individual organisms with favorable traits are more likely to survive and reproduce. ... Herbert Spencer coined the phrase survival of the fittest Survival of the fittest is a phrase which is a shorthand for a concept relating to competition for survival or predominance. ... In optimization (a branch of mathematics), a candidate solution is a member of a set of possible solutions to a given problem. ... Optimization is a branch of mathematics which is concerned with finding maxima and minima of real-valued functions. ... A fitness function is a particular type of objective function that quantifies the optimality of a solution (that is, a chromosome) in a genetic algorithm so that that particular chromosome may be ranked against all the other chromosomes. ... A phylogenetic tree of all extant organisms, based on 16S rRNA gene sequence data, showing the evolutionary history of the three domains of life, bacteria, archaea and eukaryotes. ... The form Æ or æ is also a letter and ligature in the Latin alphabet. ...

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. In evolutionary biology, fitness landscapes or adaptive landscapes are used to visualize the relationship between genotypes (or phenotypes) and replicatory success. ... Engineering is the application of scientific and technical knowledge to solve human problems. ... The Bath, a painting by Mary Cassatt (1891-1892). ... Biology (from Greek βίος λόγος, see below) is the branch of science dealing with the study of life. ... Face-to-face trading interactions among on the New York Stock Exchange trading floor Economics, as a social science, studies human choice behavior and how it effects the production, distribution, and consumption of scarce resources. ... Genetics (from the Greek genno γεννώ= give birth) is the science of genes, heredity, and the variation of organisms. ... Operations Research, or simply OR is an interdisciplinary science which deploys scientific methods like mathematical modeling, statistics, and algorithms to decision making in complex real-world problems which are concerned with coordination and execution of the operations within an organization. ... This article is in need of attention from an expert on the subject. ... The social sciences are groups of academic disciplines that study the human aspects of the world. ... The first few hydrogen atom electron orbitals shown as cross-sections with color-coded probability density. ... Chemistry (from Greek χημεία khemeia meaning alchemy, see below for possible origins of this word) is the science of matter at the atomic to molecular scale, dealing primarily with collections of atoms (such as molecules, crystals, and metals). ... An illustration of the No Free Lunch Theorem, showing the performance of a highly specialized algorithm (red) and a general-purpose one (blue). ...

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. This article is about biological evolution. ... Natural selection is the process by which individual organisms with favorable traits are more likely to survive and reproduce. ... Artificial life, also known as alife or a-life, is the study of life through the use of human-made analogs of living systems. ... Microevolution is the occurrence of small-scale changes in allele frequencies in a population, over a few generations, also known as change at or below the species level. ... Tierra is a computer simulation developed by ecologist Thomas S. Ray in the early 1990s in which computer programs compete for central processor unit (CPU) time and access to main memory. ... Avida is an artificial life software platform to study the evolutionary biology of self-replicating and evolving computer programs (digital organisms). ... Macroevolution refers to evolution that occurs above the level of species. ...

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. The genotype-phenotype distinction refers to the fact that while genotype and phenotype of an organism are related, they do not necessarily coincide. ... Embryogenesis is the process by which the embryo is formed and develops. ... The word encoding has a number of meanings. ... Evolvability is a concept in that relates ability of a particular phenotype to be robust to mutations. ...

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;
• Differential evolution - generalized autoadaptable evolution strategies
• 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.

A genetic algorithm (abbreviated as GA) is a search technique used in computing (with applications in computer science, engineering, economics, physics, mathematics and other fields) to find true or approximate solutions to optimization and search problems. ... In mathematics, optimization is the discipline which is concerned with finding the maxima and minima of functions, possibly subject to constraints. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... It is a subset of Evolutionary algorithm. ... In computer science, Evolution strategy (ES, from German Evolutionsstrategie) is an optimization technique based on ideas of adaptation and evolution. ... Differential Evolution (DE) grew out of Kenneth Prices attempts to solve the Chebyshev polynomial fitting problem that had been posed to him by Rainer Storn. ... Genetic programming (GP) is an automated methodology inspired by biological evolution to find computer programs that best perform a user-defined task. ... A learning classifier system, or LCS, is a machine learning system with close links to reinforcement learning and genetic algorithms. ...

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.

Differential Evolution (DE) grew out of Kenneth Prices attempts to solve the Chebyshev polynomial fitting problem that had been posed to him by Rainer Storn. ... In mathematics, the term optimization refers to the study of problems that have the form Given: a function f : A R from some set A to the real numbers Sought: an element x0 in A such that f(x0) ≤ f(x) for all x in A (minimization) or such that... Particle swarm optimization (PSO) is a form of swarm intelligence. ... In mathematics, the term optimization refers to the study of problems that have the form Given: a function f : A R from some set A to the real numbers Sought: an element x0 in A such that f(x0) ≤ f(x) for all x in A (minimization) or such that... The ant colony optimization algorithm (ACO), introduced by Moyson and Manderick [MoMa88] and widely developped by Marco Dorigo [CMD91,Dor92,DoSt04], is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. ... Combinatorial optimization is a branch of optimization in applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory. ...

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.

See also

• Developmental biology
• Evolutionary computation
• Evolutionary robotics
• Fitness landscape
• Genetic operators
• Interactive evolutionary computation
• Program synthesis

Views of a Foetus in the Womb, Leonardo da Vinci, ca. ... In computer science evolutionary computation is a subfield of artificial intelligence (more particularly computational intelligence) involving combinatorial optimization problems. ... This article is in need of attention from an expert on the subject. ... In evolutionary biology, fitness landscapes or adaptive landscapes are used to visualize the relationship between genotypes (or phenotypes) and replicatory success. ... A genetic operator is a process used in genetic algorithms to maintain genetic diversity. ... Interactive evolutionary computation (IEC) or Aesthetic Selection is a general term for methods of evolutionary computation that use human evaluation. ... Program synthesis comprises a range of technologies for the automatic generation of executable computer programs from high-level specifications of their behaviour. ...

External links

• VitaSCIENCES Web-platform of global optimization and metaheuristics.
• International Society for Genetic and Evolutionary Computation - Home of the largest conference on the subject, GECCO (since January 1, 2005 reorganized to become Special Interest Group for Genetic and Evolutionary Computation of the ACM)
• Illinois Genetic Algorithms Laboratory (IlliGAL)
• Kanpur Genetic Algorithms Laboratory (KanGAL)
• Evolutionary Computation Repository
• Evolutionary Computing European Network Of Excellence
• Hitch-Hiker's Guide to Evolutionary Computation (FAQ for comp.ai.genetic)
• Evolutionary computation in manufacturing scheduling
• www.talkorigins.org: Genetic Algorithms and Evolutionary Computation
• Evolutionary Computation Lab at George Mason University (ECLab)
• CILib - GPLed computational intelligence simulation and research environment written in Java, includes various EC implementations
• Nanopond (Grey Thumb) - A very tiny (less than 1000 lines of C!) evolvable instruction set virtual machine that exhibits striking emergent behaviors.
• Evolving Objects - GPLed C++ framework for evolutionary computation
• DGPF - A Distributed Framework for GA/GP and other randomized search algorithms.