Information Technology Reference
In-Depth Information
evolvability of programs. Although it would be an advantage to have a famil-
iarity with both genetic programming and biological representations, concise
introductions to both these subjects are provided.
INTRODUCTION
Artificial Evolution and Evolutionary Computation
According to modern biological understanding, evolution is solely responsible
for the complexity we see in the structure and behavior of biological organisms.
Nevertheless, evolution itself is a simple process that can occur in any popula-
tion of imperfectly replicating entities where the right to replicate is determined
by a process of selection.
Consequently, given an appropriate model of such an environment, evolu-
tion can also occur within computers. This artificial evolution is the domain of
a discipline called
evolutionary computation
(EC), which uses the search and
optimization qualities of evolution to design, search for, and optimize any struc-
ture that can be represented on a computer. Programs that implement artificial
evolution are called
evolutionary algorithms
(EAs). There were three original
forms of EA: genetic algorithms [13, 14], evolution strategies [5, 33, 36], and
evolutionary programming [12]. Although contemporary algorithms now form
a continuum of approaches, these three terms are still commonly used as a basis
for classification.
The activity of an EA revolves around a fundamental data structure called
the
population
—a collection of individuals, each of which encodes a candidate
solution to a particular problem. It is common to use biological terminology in
EC. The value of a particular candidate solution, and a measure of how well it
solves the problem, is called fitness. The encoded form of a solution is known
as a genotype and the actual solution a phenotype.
The goal of an EA is to find an optimal solution to a problem. It does this
through the iterative replication of existing, fit genetic material to form new,
hopefully fitter, individuals that then replace less fit individuals within the popu-
lation. Good genetic material is promoted by a selection process that determines
which individuals contribute toward the genetic makeup of new individuals. To
prevent genetic stagnation, new genetic material is introduced by making oc-
casional random changes to the genotypes of new individuals, a process called
mutation.
In some EAs mutation is the only genetic operator and new individuals are
simply mutated versions of existing individuals. Other EAs, including genetic
algorithms (GAs), use a crossover operator that generates new individuals by
splicing together components from more than one existing solution. This re-
sembles biological recombination and is theorized to encourage the formation
and replication of high-fitness genetic components called building blocks.
