Evolutionary computation
Encyclopedia
In computer science
, evolutionary computation is a subfield of artificial intelligence
(more particularly computational intelligence
) that involves combinatorial optimization
problems.
Evolutionary computation uses iterative progress, such as growth or development in a population
. This population is then selected
in a guided random search using parallel processing
to achieve the desired end. Such processes are often inspired by biological mechanisms of evolution
.
As evolution can produce highly optimised processes and networks, it has many applications in computer science
. Here, simulations of evolution using evolutionary algorithm
s and artificial life
started with the work of Nils Aall Barricelli in the 1960s, and was extended by Alex Fraser
, who published a series of papers on simulation of artificial selection
. Artificial evolution
became a widely recognised optimisation method as a result of the work of Ingo Rechenberg
in the 1960s and early 1970s, who used evolution strategies
to solve complex engineering problems. Genetic algorithm
s in particular became popular through the writing of John Holland
. As academic interest grew, dramatic increases in the power of computers allowed practical applications, including the automatic evolution of computer programs. Evolutionary algorithms are now used to solve multi-dimensional problems more efficiently than software produced by human designers, and also to optimise the design of systems.
principles for automated problem solving originated in the fifties
. It was not until the sixties
that three distinct interpretations of this idea started to be developed in three different places.
Evolutionary programming
was introduced by Lawrence J. Fogel
in the USA
, while John Henry Holland
called his method a genetic algorithm
. In Germany
Ingo Rechenberg
and Hans-Paul Schwefel
introduced evolution strategies
. These areas developed separately for about 15 years. From the early nineties
on they are unified as different representatives (“dialects”) of one technology, called evolutionary computing. Also in the early nineties, a fourth stream following the general ideas had emerged – genetic programming
. Since the 1990s, evolutionary computation has largely become swarm-based computation, and nature-inspired algorithms are becoming an increasingly significant part.
These terminologies denote the field of evolutionary computing and consider evolutionary programming, evolution strategies, genetic algorithms, and genetic programming as sub-areas.
optimization
algorithm
s. Broadly speaking, the field includes:
Evolutionary algorithm
s
and in a lesser extent also:
, 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.
In this process, there are two main forces that form the basis of evolutionary systems: Recombination and mutation create the necessary diversity and thereby facilitate novelty, while selection acts as a force increasing quality.
Many aspects of such an evolutionary process are stochastic
. Changed pieces of information due to recombination and mutation are randomly chosen. On the other hand, selection operators can be either deterministic, or stochastic. In the latter case, individuals with a higher fitness
have a higher chance to be selected than individuals with a lower fitness
, but typically even the weak individuals have a chance to become a parent or to survive.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, evolutionary computation is a subfield of artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
(more particularly computational intelligence
Computational intelligence
Computational intelligence is a set of Nature-inspired computational methodologies and approaches to address complex problems of the real world applications to which traditional methodologies and approaches are ineffective or infeasible. It primarily includes Fuzzy logic systems, Neural Networks...
) that involves combinatorial optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
problems.
Evolutionary computation uses iterative progress, such as growth or development in a population
Population
A population is all the organisms that both belong to the same group or species and live in the same geographical area. The area that is used to define a sexual population is such that inter-breeding is possible between any pair within the area and more probable than cross-breeding with individuals...
. This population is then selected
Artificial selection
Artificial selection describes intentional breeding for certain traits, or combination of traits. The term was utilized by Charles Darwin in contrast to natural selection, in which the differential reproduction of organisms with certain traits is attributed to improved survival or reproductive...
in a guided random search using parallel processing
Parallel processing
Parallel processing is the ability to carry out multiple operations or tasks simultaneously. The term is used in the contexts of both human cognition, particularly in the ability of the brain to simultaneously process incoming stimuli, and in parallel computing by machines.-Parallel processing by...
to achieve the desired end. Such processes are often inspired by biological mechanisms of evolution
Evolution
Evolution is any change across successive generations in the heritable characteristics of biological populations. Evolutionary processes give rise to diversity at every level of biological organisation, including species, individual organisms and molecules such as DNA and proteins.Life on Earth...
.
As evolution can produce highly optimised processes and networks, it has many applications in computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
. Here, simulations of evolution using evolutionary algorithm
Evolutionary algorithm
In artificial intelligence, an evolutionary algorithm 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, and selection...
s and artificial life
Artificial life
Artificial life is a field of study and an associated art form which examine systems related to life, its processes, and its evolution through simulations using computer models, robotics, and biochemistry. The discipline was named by Christopher Langton, an American computer scientist, in 1986...
started with the work of Nils Aall Barricelli in the 1960s, and was extended by Alex Fraser
Alex Fraser (scientist)
Alex Fraser was a major innovator in the development of the computer modeling of population genetics and his work has stimulated many advances in genetic research over the past decades....
, who published a series of papers on simulation of artificial selection
Artificial selection
Artificial selection describes intentional breeding for certain traits, or combination of traits. The term was utilized by Charles Darwin in contrast to natural selection, in which the differential reproduction of organisms with certain traits is attributed to improved survival or reproductive...
. Artificial evolution
Evolutionary algorithm
In artificial intelligence, an evolutionary algorithm 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, and selection...
became a widely recognised optimisation method as a result of the work of Ingo Rechenberg
Ingo Rechenberg
Ingo Rechenberg is a German computer scientist and professor. Rechenberg is a pioneer of the fields of evolutionary computation and artificial evolution. In the 1960s and 1970s he invented a highly influential set of optimization methods known as evolution strategies...
in the 1960s and early 1970s, who used evolution strategies
Evolution strategy
In computer science, evolution strategy is an optimization technique based on ideas of adaptation and evolution. It belongs to the general class of evolutionary computation or artificial evolution methodologies.-History:...
to solve complex engineering problems. Genetic algorithm
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
s in particular became popular through the writing of John Holland
John Henry Holland
John Henry Holland is an American scientist and Professor of Psychology and Professor of Electrical Engineering and Computer Science at the University of Michigan, Ann Arbor. He is a pioneer in complex systems and nonlinear science. He is known as the father of genetic algorithms. He was awarded...
. As academic interest grew, dramatic increases in the power of computers allowed practical applications, including the automatic evolution of computer programs. Evolutionary algorithms are now used to solve multi-dimensional problems more efficiently than software produced by human designers, and also to optimise the design of systems.
History
The use of DarwinianDarwinism
Darwinism is a set of movements and concepts related to ideas of transmutation of species or of evolution, including some ideas with no connection to the work of Charles Darwin....
principles for automated problem solving originated in the fifties
1950s
The 1950s or The Fifties was the decade that began on January 1, 1950 and ended on December 31, 1959. The decade was the sixth decade of the 20th century...
. It was not until the sixties
1960s
The 1960s was the decade that started on January 1, 1960, and ended on December 31, 1969. It was the seventh decade of the 20th century.The 1960s term also refers to an era more often called The Sixties, denoting the complex of inter-related cultural and political trends across the globe...
that three distinct interpretations of this idea started to be developed in three different places.
Evolutionary programming
Evolutionary programming
Evolutionary programming is one of the four major evolutionary algorithm paradigms. It is similar to genetic programming, but the structure of the program to be optimized is fixed, while its numerical parameters are allowed to evolve....
was introduced by Lawrence J. Fogel
Lawrence J. Fogel
Dr. Lawrence J. Fogel , was a pioneer in evolutionary computation and human factors analysis. He is known as the father of evolutionary programming. Born in Brooklyn, New York, he earned his B.E.E. from New York University in 1948, M.S. from Rutgers University in 1952 and Ph.D...
in the USA
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
, while John Henry Holland
John Henry Holland
John Henry Holland is an American scientist and Professor of Psychology and Professor of Electrical Engineering and Computer Science at the University of Michigan, Ann Arbor. He is a pioneer in complex systems and nonlinear science. He is known as the father of genetic algorithms. He was awarded...
called his method a genetic algorithm
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
. In Germany
Germany
Germany , officially the Federal Republic of Germany , is a federal parliamentary republic in Europe. The country consists of 16 states while the capital and largest city is Berlin. Germany covers an area of 357,021 km2 and has a largely temperate seasonal climate...
Ingo Rechenberg
Ingo Rechenberg
Ingo Rechenberg is a German computer scientist and professor. Rechenberg is a pioneer of the fields of evolutionary computation and artificial evolution. In the 1960s and 1970s he invented a highly influential set of optimization methods known as evolution strategies...
and Hans-Paul Schwefel
Hans-Paul Schwefel
Hans-Paul Schwefel is a German computer scientist and professor emeritus at University of Dortmund , where he held the chair of systems analysis from 1985 until 2006. He is one of the pioneers in evolutionary computation and one of the authors responsible for the evolution strategies...
introduced evolution strategies
Evolution strategy
In computer science, evolution strategy is an optimization technique based on ideas of adaptation and evolution. It belongs to the general class of evolutionary computation or artificial evolution methodologies.-History:...
. These areas developed separately for about 15 years. From the early nineties
1990s
File:1990s decade montage.png|From left, clockwise: The Hubble Space Telescope floats in space after it was taken up in 1990; American F-16s and F-15s fly over burning oil fields and the USA Lexie in Operation Desert Storm, also known as the 1991 Gulf War; The signing of the Oslo Accords on...
on they are unified as different representatives (“dialects”) of one technology, called evolutionary computing. Also in the early nineties, a fourth stream following the general ideas had emerged – genetic programming
Genetic programming
In artificial intelligence, genetic programming is an evolutionary algorithm-based methodology inspired by biological evolution to find computer programs that perform a user-defined task. It is a specialization of genetic algorithms where each individual is a computer program...
. Since the 1990s, evolutionary computation has largely become swarm-based computation, and nature-inspired algorithms are becoming an increasingly significant part.
These terminologies denote the field of evolutionary computing and consider evolutionary programming, evolution strategies, genetic algorithms, and genetic programming as sub-areas.
Techniques
Evolutionary computing techniques mostly involve metaheuristicMetaheuristic
In computer science, metaheuristic designates a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Metaheuristics make few or no assumptions about the problem being optimized and can search very large spaces...
optimization
Optimization (computer science)
In computer science, program optimization or software optimization is the process of modifying a software system to make some aspect of it work more efficiently or use fewer resources...
algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s. Broadly speaking, the field includes:
Evolutionary algorithm
Evolutionary algorithm
In artificial intelligence, an evolutionary algorithm 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, and selection...
s
- Genetic algorithmGenetic algorithmA genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
s - Evolutionary programmingEvolutionary programmingEvolutionary programming is one of the four major evolutionary algorithm paradigms. It is similar to genetic programming, but the structure of the program to be optimized is fixed, while its numerical parameters are allowed to evolve....
- Evolution strategyEvolution strategyIn computer science, evolution strategy is an optimization technique based on ideas of adaptation and evolution. It belongs to the general class of evolutionary computation or artificial evolution methodologies.-History:...
- Swarm intelligenceSwarm intelligenceSwarm intelligence is the collective behaviour of decentralized, self-organized systems, natural or artificial. The concept is employed in work on artificial intelligence...
- Ant colony optimizationAnt colony optimizationIn computer science and operations research, the ant colony optimization algorithm ' is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs....
- Particle swarm optimizationParticle swarm optimizationIn computer science, particle swarm optimization is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality...
and in a lesser extent also:
- Artificial lifeArtificial lifeArtificial life is a field of study and an associated art form which examine systems related to life, its processes, and its evolution through simulations using computer models, robotics, and biochemistry. The discipline was named by Christopher Langton, an American computer scientist, in 1986...
(also see digital organismDigital organismA digital organism is a self-replicating computer program that mutates and evolves. Digital organisms are used as a tool to study the dynamics of Darwinian evolution, and to test or verify specific hypotheses or mathematical models of evolution...
) - Artificial immune systemArtificial immune systemIn computer science, Artificial immune systems are a class of computationally intelligent systems inspired by the principles and processes of the vertebrate immune system...
s - Cuckoo searchCuckoo searchCuckoo search is an optimization algorithm developed by Xin-she Yang and Suash Debin 2009. It was inspired by the obligate brood parasitism of some cuckoo species by laying their eggs in the nests of other host birds . Some host birds can engage direct conflict with the intruding cuckoos...
- Cultural algorithmCultural algorithmCultural algorithms are a branch of evolutionary computation where there is a knowledge component that is called the belief space in addition to the population component. In this sense, cultural algorithms can be seen as an extension to a conventional genetic algorithm. Cultural algorithms were...
s - Differential evolutionDifferential evolutionIn computer science, differential evolution is a method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Such methods are commonly known as metaheuristics as they make few or no assumptions about the problem being optimized...
- Firefly algorithmFirefly algorithmThe firefly algorithm is a metaheuristic algorithm, inspired by the flashing behaviour of fireflies. The primary purpose for a firefly's flash is to act as a signal system to attract other fireflies...
- Harmony searchHarmony searchIn computer science and operations research, harmony search is a phenomenon-mimicking algorithm inspired by the improvisation process of musicians...
- Learning classifier systemLearning classifier systemA learning classifier system, or LCS, is a machine learning system with close links to reinforcement learning and genetic algorithms. First described by John Holland, his LCS consisted of a population of binary rules on which a genetic algorithm altered and selected the best rules.Rule fitness...
s - Learnable Evolution ModelLearnable Evolution ModelThe Learnable Evolution Model is a novel, non-Darwinian methodology for evolutionary computation that employs machine learning to guide the generation of new individuals...
- Parallel simulated annealing
- Self-organizationSelf-organizationSelf-organization is the process where a structure or pattern appears in a system without a central authority or external element imposing it through planning...
such as self-organizing mapSelf-organizing mapA self-organizing map or self-organizing feature map is a type of artificial neural network that is trained using unsupervised learning to produce a low-dimensional , discretized representation of the input space of the training samples, called a map...
s, competitive learningCompetitive learningCompetitive learning is a form of unsupervised learning in artificial neural networks, in which nodes compete for the right to respond to a subset of the input data. A variant of Hebbian learning, competitive learning works by increasing the specialization of each node in the network... - Self-Organizing Migrating Genetic Algorithm
- Swarm-based computing
Evolutionary algorithms
Evolutionary algorithms form a subset of evolutionary computation in that they generally only involve techniques implementing mechanisms inspired by biological evolution such as reproduction, mutationMutation
In molecular biology and genetics, mutations are changes in a genomic sequence: the DNA sequence of a cell's genome or the DNA or RNA sequence of a virus. They can be defined as sudden and spontaneous changes in the cell. Mutations are caused by radiation, viruses, transposons and mutagenic...
, recombination
Genetic recombination
Genetic recombination is a process by which a molecule of nucleic acid is broken and then joined to a different one. Recombination can occur between similar molecules of DNA, as in homologous recombination, or dissimilar molecules, as in non-homologous end joining. Recombination is a common method...
, natural selection
Natural selection
Natural selection is the nonrandom process by which biologic traits become either more or less common in a population as a function of differential reproduction of their bearers. It is a key mechanism of evolution....
and survival of the fittest
Survival of the fittest
"Survival of the fittest" is a phrase originating in evolutionary theory, as an alternative description of Natural selection. The phrase is today commonly used in contexts that are incompatible with the original meaning as intended by its first two proponents: British polymath philosopher Herbert...
. 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
Fitness function
A fitness function is a particular type of objective function that is used to summarise, as a single figure of merit, how close a given design solution is to achieving the set aims....
). Evolution
Evolution
Evolution is any change across successive generations in the heritable characteristics of biological populations. Evolutionary processes give rise to diversity at every level of biological organisation, including species, individual organisms and molecules such as DNA and proteins.Life on Earth...
of the population then takes place after the repeated application of the above operators.
In this process, there are two main forces that form the basis of evolutionary systems: Recombination and mutation create the necessary diversity and thereby facilitate novelty, while selection acts as a force increasing quality.
Many aspects of such an evolutionary process are stochastic
Stochastic
Stochastic refers to systems whose behaviour is intrinsically non-deterministic. A stochastic process is one whose behavior is non-deterministic, in that a system's subsequent state is determined both by the process's predictable actions and by a random element. However, according to M. Kac and E...
. Changed pieces of information due to recombination and mutation are randomly chosen. On the other hand, selection operators can be either deterministic, or stochastic. In the latter case, individuals with a higher fitness
Physical fitness
Physical fitness comprises two related concepts: general fitness , and specific fitness...
have a higher chance to be selected than individuals with a lower fitness
Physical fitness
Physical fitness comprises two related concepts: general fitness , and specific fitness...
, but typically even the weak individuals have a chance to become a parent or to survive.
Evolutionary computation practitioners
- Kalyanmoy DebKalyanmoy debKalyanmoy Deb is a professor of mechanical engineering at IIT Kanpur. His research lab is one of the premier places for evolutionary algorithms research in the world. Deb's book 'Multi-Objective Optimization using Evolutionary Algorithms' has become one of the most popular and highly cited books...
- David E. GoldbergDavid E. GoldbergDavid Edward Goldberg is an American computer scientist, and professor at the department of Industrial and Enterprise Systems Engineering at the University of Illinois at Urbana-Champaign and is most noted for his seminal works in the field of genetic algorithms...
- John Henry HollandJohn Henry HollandJohn Henry Holland is an American scientist and Professor of Psychology and Professor of Electrical Engineering and Computer Science at the University of Michigan, Ann Arbor. He is a pioneer in complex systems and nonlinear science. He is known as the father of genetic algorithms. He was awarded...
- John KozaJohn KozaJohn R. Koza is a computer scientist and a former consulting professor at Stanford University, most notable for his work in pioneering the use of genetic programming for the optimization of complex problems. He was a cofounder of Scientific Games Corporation, a company which built computer systems...
- Peter NordinPeter NordinPeter Nordin is a Swedish computer scientist, entrepreneur and author who has contributed to artificial intelligence, automatic programming, machine learning, and evolutionary robotics.- Studies and early career :...
- Ingo RechenbergIngo RechenbergIngo Rechenberg is a German computer scientist and professor. Rechenberg is a pioneer of the fields of evolutionary computation and artificial evolution. In the 1960s and 1970s he invented a highly influential set of optimization methods known as evolution strategies...
- Hans-Paul SchwefelHans-Paul SchwefelHans-Paul Schwefel is a German computer scientist and professor emeritus at University of Dortmund , where he held the chair of systems analysis from 1985 until 2006. He is one of the pioneers in evolutionary computation and one of the authors responsible for the evolution strategies...
- Peter J. Fleming http://www.shef.ac.uk/acse/staff/peter_fleming
- Carlos M. Fonseca http://eden.dei.uc.pt/~cmfonsec/
- Lee Graham3D Virtual Creature Evolution3D Virtual Creature Evolution, abbreviated to 3DVCE, is an artificial evolution simulation program created by Lee Graham. Its purpose is to visualize and research common themes in body plans and strategies to achieve a fitness function of the artificial organisms generated and maintained by the...
Major conferences and workshops
- IEEE Congress on Evolutionary ComputationIEEE Congress on Evolutionary ComputationThe IEEE Congress on Evolutionary Computation is one of the largest and most important conferences within Evolutionary computation , the other conferences of similar importance being Genetic and Evolutionary Computation Conference and Parallel Problem Solving from Nature .CEC, which is organized...
(CEC) - Genetic and Evolutionary Computation Conference (GECCO)
See also
- Estimation of distribution algorithm
- Evolutionary roboticsEvolutionary roboticsEvolutionary robotics is a methodology that uses evolutionary computation to develop controllers for autonomous robots. Algorithms in ER frequently operate on populations of candidate controllers, initially selected from some distribution. This population is then repeatedly modified according to...
- Fitness approximationFitness approximationIn function optimization, fitness approximation is a method for decreasing the number of fitness function evaluations to reach a target solution...
- Grammatical evolutionGrammatical evolutionGrammatical evolution is a relatively new evolutionary computation technique pioneered by Conor Ryan, JJ Collins and Michael O'Neill in 1998 at the in the University of Limerick....
- Human-based evolutionary computationHuman-based evolutionary computationHuman-based evolutionary computation is a set of evolutionary computation techniques that rely on human innovation. Human-based evolutionary computation techniques can be classified into three more specific classes analogous to ones in evolutionary computation. There are three basic types of...
- Inferential programmingInferential programmingIn ordinary computer programming, the programmer keeps the program's intended results in mind and painstakingly constructs a computer program to achieve those results. Inferential programming refers to techniques and technologies enabling the inverse...
- Interactive evolutionary computationInteractive evolutionary computationInteractive evolutionary computation or aesthetic selection is a general term for methods of evolutionary computation that use human evaluation...
- Mutation testing
- No free lunch in search and optimization
- Universal DarwinismUniversal darwinismUniversal Darwinism refers to a variety of approaches that extend the theory of Darwinism beyond its original domain of biological evolution on Earth...