Evolutionary computation applies biologically inspired concepts from
natural selection (such as populations, mutation, reproduction, and
survival of the fittest) to generate increasingly better solutions to the
problem. Some of the most popular methods are evolutionary
programming, evolution strategies, and genetic algorithms. Evolutionary
computation has been successfully applied to a wide range of problems
including aircraft design, routing in communications networks, game
playing, robotics, air traffic control, machine learning, pattern recognition,
market forecasting, and data mining. Although evolutionary programming,
evolution strategies, and genetic algorithms are similar at the highest
level, each of these varieties implements evolutionary algorithms in a
different manner.
Evolutionary programming, originally conceived by Lawrence J. Fogel in
1960, emphasizes the relationship between parent solutions (the solutions
being analyzed) and their offspring (new solutions resulting from some
modification of the parent solutions). Fogel, Owens, and Walsh’s 1966
book Artificial Intelligence Through Simulated Evolution is the landmark
publication in this area of AI. In general, in evolutionary programming, the
problem to be solved is represented or encoded in a string of variables
that defines all the potential solutions to the problem. Each full set of
variables with its specific values is known as an individual or candidate
solution. To solve the problem, a population of “individuals” is created,
with each individual representing a random possible solution to the
problem. Each of the individuals (i.e., each candidate solution) is
evaluated and assigned a fitness value based on how effective the
candidate solution is to solving the problem. Based on this fitness value,
some individuals (usually the most successful) are selected to be parents,
and offspring are generated from these parents.
In the generation process, a mutation operator selects elements of the
parents’ representation of the solution and manipulates these elements
when they are transferred to the offspring. A mutation operator is a rule
that selects random variables and randomly alters the value of these
variables in some degree, generating new individuals or candidate
solutions from the selected parents. Thus, some characteristics of the
parent solutions are changed slightly and then transferred to the offspring
solution. In general, the degree of mutation is greater in the first
generations, and it is gradually decreased as generations evolve and get
closer to an optimal solution. The offspring candidate solutions are then
evaluated based on their fitness, just like their parents were, and the
process of generating offspring from the parents is repeated until an
individual with sufficient quality (an optimal solution to the problem) is
found or a previously determined computational limit is reached (e.g.,
after evolving for a given number of generations).
Evolution strategies (Bäck, Hoffmeister, & Schwefel, 1991; Rechenberg,
1973) and evolutionary programming share many similarities. The main
difference is that, in evolution strategies, offspring are generated from the
selected parents not only by using a mutation operator but also by
recombination of the code from selected parents through a crossover
operator. A crossover operator applies some rule to recombine the
elements of the selected parents to generate offspring. The recombination
operation simulates some reproduction mechanism to transfer elements
from the parents to their offspring.
The crossover operator can take many variants (e.g., interchange the first
half of the elements from one of the parents and the second half from the
other one for one offspring; the reverse for another offspring). The
crossover operator is inspired by the role of sexual reproduction in the
evolution of living things. The mutation operator is inspired by the role of
mutation in natural evolution. Generally, both mutation and reproduction
are used simultaneously. Recombination and mutation create the
necessary diversity and thereby facilitate novelty, while selection acts as
a force increasing quality.
Genetic algorithms, popularized by John Holland (1975), are similar to
evolution strategies in the general steps that the algorithm follows.
However, there are substantial differences in how the problem is
represented. One of the main differences is that the problem to be solved
is encoded in each individual of the population by having arrays of bits
(bit-strings), which represent chromosomes. Each bit in the bit-string is
analogous to a gene (i.e., an element that represents a variable or part of
a variable of the problem). In a genetic algorithm, each individual or
candidate solution is encoded at a genotype level, whereas in
evolutionary programming and evolution strategy, the problem is encoded
at a phenotype level, in which there is a one-to-one relationship between
each value encoded in the phenotype and the real value that it represents
in the problem. A genetic algorithm can differentiate between genotype
(the genes) and phenotype (the expression of a collection of genes). The
manipulation at the level of genotype allows for more elaborated
implementation of the crossover operator and the mutation operator.
Additionally, the focus on genetic algorithms when creating offspring in
successive generations is on reproduction (crossover) and no mutation,
which is often considered as a background operator or secondary process.