A friend asked me just what it is that I study. This is an extended version of my answer to him. It motivates the idea of heuristics by describing computationally hard problems, describes evolutionary computation as a category of heuristic algorithms, summarizes the origins of evolutionary computation, and indicates the kinds of investigations that researchers in evolutionary computation pursue.
Some problems are computationally easy. Algorithms that solve these problems exactly require times that grow only as polynomial functions of the sizes of problem instances. Examples of such problems include sorting an array of values; finding a minimum spanning tree in a connected, weighted, undirected graph; finding the convex hull of a collection of points in the plane; and multiplying matrices.
However, many interesting and useful problems are computationally hard. All known exact algorithms for these problems require times that grow exponentially with the sizes of problem instances, so for large instances, these algorithms are infeasible. That is, we know how to get a solution to a large instance of such a problem, but it would take so long that we'd all be dead (and the sun burned down to a cinder) before even the fastest computer could finish the necessary computation.
An example is the Traveling Salesman Problem (TSP), in which we have a collection of cities (points in the plane) and we know all the distances between every pair of them. In a tour of the cities, we visit each city exactly once, then return to the start city. We want a tour that does this in the shortest possible total distance. Any algorithm (program) guaranteed to find an optimal solution to this problem will, for larger numbers of cities, eventually take so long that we can't wait for the answer.
Other examples include:
These problems are NP-hard. For such problems, and there are lots of them with important applications, we turn to heuristics: algorithms that return approximate solutions reasonably quickly. In general, we don't know if a heuristic solution is optimal. Evolutionary computation (EC) is one category of heuristics.
The inspiration for EC comes from the mechanisms of biological evolution: reproduction with variation, selection according to fitness, and repetition. Evolution will occur in any system that exhibits these features. An evolutionary algorithm (EA) maintains a collection of strings of symbols, called its population. The strings are called chromosomes, and they represent candidate solutions to the target problem. An EA's population initially consists of random chromosomes, representing random solutions to the problem.
For example, in an EA for the traveling salesman problem, we can number the cities, and a chromosome is a permutation of the city numbers: a list in which each number appears once. The tour such a chromosome represents visits the cities in the listed order and returns to the first city. The permutations in the initial population are random.
Attached to each chromosome is a number that represents how good the chromosome's solution is. (In our TSP example, that number is the total length of the tour the chromosome represents.) This number is called the chromosome's fitness, and depending on the problem, either larger or smaller values might represent better solutions. (For TSP, smaller is better.) Determining a chromosome's fitness is called evaluating it.
In nature, organisms of better fitness are in general more successful at survival and reproduction; the same is true here. An EA selects chromosomes to survive or to reproduce so that the more fit ones---the ones that represent better solutions---are more likely to be chosen.
An EA generates new candidate solutions, called offspring, through mechanisms that imitate the genetic processes of biological reproduction. Crossover builds a new chromosome from two chromosomes, its parents, by combining some of their symbols, thus the information they contain; this operation is also called recombination. Mutation modifies a single parent chromosome, usually in some small, random way. In nature, mutation is rare, but EAs mutate their chromosomes more often, to speed the search for good solutions to the target problem. (For the TSP, crossover will build the representation of a new tour that has connections between cities from both parent tours, and mutation will change a few edges in a tour.)
After enough offspring have been built using crossover and mutation, they replace their parents' generation---that is, they become the population---and the process continues. As the generations succeed each other, better chromosomes, representing better solutions, evolve. When enough generations have passed, or the algorithm finds a solution that is good enough, the EA stops and reports the best solution it has found.
There are several kinds of evolutionary algorithms. They differ in the representations by which their chromosomes represent candidate solutions, the details of their usual selection, crossover, and mutation operators, whether selection is used to determine which chromosomes survive into the next generation or which chromosomes get to reproduce (via crossover and mutation), and the kinds of problems they are usually applied to. The following sketch summarizes one version of a kind of EA called a genetic algorithm (GA). The sketch assumes some problem to which we're trying to find a good approximate solution, a coding by which the GA's chromosomes represent candidate solutions to the problem, and crossover and mutation operators that act on the coding.
initialize the population with random chromosomes;
evaluate all the chromosomes;
repeat
{
for i from 1 to the population size
{
decide whether to use crossover or mutation;
if crossover
select two parents;
cross them to produce an offspring;
else
select one parent;
mutate it to produce an offspring;
evaluate the offspring;
record the offspring in the next generation;
}
offspring replace parents;
} until enough generations have passed;
report the best solution the best chromosome represents;
A common and useful extension of such an algorithm is elitism: copy the best chromosome from the current generation into the next generation. That way, the search for a good solution never goes backwards.
Although researchers started simulating features of evolution as soon as adequate computers were available (in the 1950's), consideration of evolution as a model for optimization has three later, independent origins. In the early 1960's, Rechenberg and Schwefel evolved good solutions to some engineering design problems; their work produced Evolution Strategies (ES). In ES, chromosomes are usually strings of real values and selection determines which chromosomes survive into the next generation.
In the mid-1960's, Lawrence Fogel and others developed another evolutionary approach called Evolutionary Programming (EP). Originally, it was used to search spaces of finite-state machines but is now used with chromosomes of various types, including strings of real values. In general, EP does not use crossover.
In 1975, John Holland published a book entitled Adaptation in Natural and Artificial Systems that started Genetic Algorithms (GAs). Originally, chromosomes in genetic algorithms were strings of binary symbols---0's and 1's---but other representations are now common: strings over larger alphabets, permutations (as in the TSP example above), and specialized codings for particular kinds of problems, such as lists of edges in GAs that search spaces of spanning trees. GAs select chromosomes to reproduce---that is, to participate in crossover and mutation---as in the sketch above.
A related field is Genetic Programming (GP), which applies mechanisms inspired by evolution to generate not solutions to individual problem instances but programs that solve specified problems in general. The seminal work in this area is John Koza's 1992 book Genetic Programming.
For a while, people in these areas held their own conferences, but over the last ten or fifteen years, they've discovered each other. Now the distinctions between the various flavors of EC are fading; it's all Evolutionary Computation (EC) or Evolutionary Algorithms (EAs).
So what kinds of questions do researchers in evolutionary computation investigate? The following list indicates---in no particular order---some lines of inquiry.