Information Technology Reference
In-Depth Information
Representation in Evolutionary Algorithms
The way in which a candidate solution is recorded is called its representation.
For a particular problem domain there may be many ways of recording a so-
lution. Choosing an appropriate representation is akin to the decision made by
a programmer when deciding how to record a certain piece of information in
memory. There may be a selection of representations available, such as arrays,
linked lists, hash tables, and trees, and each of these will have different advan-
tages and disadvantages depending on how the information will be accessed
and used. The programmer must trade off the various pros and cons and select
the one that is most effective or efficient. On many occasions this will not be
the most natural or understandable representation.
In an EA, a representation is accessed and used in two different ways. Dur-
ing evaluation, the effectiveness of the solution is measured to gauge its fitness.
During evolution, the solution is modified by variational operators such as mu-
tation and crossover. This introduces two sets of demands upon a representation:
generative and variational [2]. Generative demands depend on the domain, but
in general it is required that the representation makes solutions easy to measure.
Variational demands require that the representation is evolvable.
Evolvability is the ability of a representation, when subject to variational
operators, to generate solutions of increasing fitness on a regular basis. The
role of artificial evolution is to search within a space of possible solutions and
find a solution that is optimal with respect to the fitness-measuring function.
The manner, and hence the effectiveness, with which this space is searched is
decided by the action of the variational operators upon current solutions within
the population. The way in which the variational operators transform existing
solutions determines the form and fitness of future solutions. Moreover, the way
in which the variational operators transform existing solutions is determined
by the degrees of freedom presented by the representation. Consequently, the
representation determines which paths are available through the search space.
An evolvable representation promotes paths that lead to better solutions and
ultimately to optimal solutions.
Unfortunately, it is not easy to predetermine what constitutes a fitness-
increasing transformation during evolution. It is, however, possible to identify
what constitutes a bad transformation. Consequently, the incidence of fitness-
increasing transformations can be increased by reducing the incidence of fitness-
decreasing transformations.
The easiest way to enact a bad transformation is to make a large change to
an existing solution. This is because a search space usually contains many more
bad solutions than it does good solutions, and making a large change to a fitter-
than-average solution will most likely move it to a lower fitness location in the
search space. In fact, most changes to a fitter-than-average solution will lead to
