Theories of Evolutionary Computation

Thomas Jansen    R. Paul Wiegand

This document is an attempt to categorize different theoretical approaches to the field of Evolutionary Computation to help better understand evolutionary algorithms (EAs) and the problems to which they are applied. It should be noted that this is only one break down, and reflects only our own vision of the field. Clearly there are many other equally valid ways one might develop such a taxonomy.

We provide a high-level categorization of the theories, in which we believe most, if not all current work can be fitted. Short descriptions of what is meant by the categories in that hierarchy are also given. Within the hierarchy, we also elicit some specific example topics. This endeavor was not meant to be an exhaustive list of EC theories. Such a list would be quite difficult to assemble, due to the diverse nature of concentrations in the field. In certain cases we also cite specific articles that we feel are appropriate survey articles of a particular topic, provide a good introduction, or introduced the particular topic. The idea was to provide guideposts for people beginning their study of EC theory.

Categories of EC Theory

Problem Landscapes for EAs

Landscapes for Analysis

In the pursuit of developing analytical understandings of EAs, it is sometimes helpful to construct problems or landscapes for study. While there have been many problems constructed for the purposes of empirical verification of hypotheses, our focus here is on those problems which are constructed explicitly from theoretical understandings of the algorithm, the purpose of which is further formal analysis. Some examples include:

Analysis of Problems/Landscapes

A subject which has captured the interest of many EC researchers is the notion of attempting to identify the characteristics of problem landscapes. There are a variety of methods which have been employed to help gain a better formal understanding for what kinds of properties of problems make them easy or hard for certain EAs. Some examples include:

Problem Transformation

Since EAs must represent potential solutions to problems, in application there is almost always some process to encode and decode these solutions into some representation to which genetic operators can be applied. Sometimes this process is direct and obvious, and sometimes it is less so. There has been some theoretical work in gaining a better formal understanding for the affects of problem transformation. An example of this is:

Component Analysis

Like any model, EAs can be thought of as composites of internal components (selection, genetic operators, population structure, etc.). Much of EC theory has focused on the task of attempting to understand how these individual components operate, both in and out of an actual algorithm. We distinguish these from Algorithm Analysis because the main goal of these analytical methods has been to understand how individual pieces of the algorithm work, not in understanding the operation of the algorithm in its totality. Examples of component analysis include:

Algorithm Analysis

While understanding how components in an EA work is important, these algorithms are, by their very nature, non-linear systems. As such, many researchers have chosen to focus their efforts on analyzing the algorithms as complete entities. These can be grouped roughly into the following six categories.

Local Analysis

While there are a variety of ways to look at the analysis of EAs, one way common to a variety of methods is to look at what an algorithm does in one step. It does not matter whether the analysis is exact or asymptotic - it fits within this category as long as it is local either in time or in space.

Global Analysis

This category covers analyses which focus on an algorithm's run-time behavior, including (and perhaps particularly) the end result of how, when, and where an algorithm will arrive during a run. Again, the question of exact, approximated, or asymptotic is irrelevant for the question of membership.

Models of EA Dynamics

Some formalisms of EAs have attempted specifically to build more general models which are meant to capture the dynamics of the algorithm itself. While this category clearly includes dynamical systems, they also more broadly include methods in which the main point is to more directly, and perhaps more generally, model the behavior of the algorithm. Some examples include:

Algorithm Design

This group has been reserved for what we are calling theory-guided algorithm design. That is, algorithms (or augmentations to algorithms) which were constructed based on specific formal understandings for how EAs tend to solve problems. Some examples include:

No Free Lunch

Though there doesn't seem to be an appropriate spot in our hierarchy for NFL, we felt it had to be included. No Free Lunch concerns itself with when we can and cannot expect any given algorithm to do any better than other algorithms against all problems. Debates on the nature of the assumptions and ramifications of this theory belong here.