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
Algorithm Analysis
Problem Landscapes for EAs
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:
- NK-Landscapes
- N-Peak Landscapes
- OneMax
- Royal Road
- HIFF
- Long Path
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:
- Fitness Distance Correlation
- Separability/Decomposability
- Walsh Analysis
- Epistasis
- Deception
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:
- Analysis of Grey versus binary coding
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:
- Evolvability
- Operator Correlation/Correlation length
- Population Sizing
- Mutation Probability
- Convergence Velocity of Operators
- Fixed point sizes of variable length genomes
- Selection/Takeover analysis
- Selection Analysis in Spatially Embedded Populations
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.
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.
- Local Performance Measure
- Traditional Schema Theory
- Construction and Survival Theory
- Exact/Correct Schema Theory
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.
- Optimization/Runtime Analysis
- Analysis of Convergence
- Convergence Velocity
- Measuring Coevolutionary Progress/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:
- Dynamical Systems Models of the Simple GA
- Markov Models and Expected Behavior Analysis
- Evolutionary Game Theory
- Teaching/Test Set Analysis
- Statistical Mechanics
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:
- Messy GAs
- Linkage Learning
- Graphical Models
- Adaptive Rates of Mutation and the 1/5th Rule
- Partial Restart Theory
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.