Provided by Cognitive Sciences ePrint Archive
Evidence of coevolution in multi-objective evolutionary
algorithms
James M. Whitacre
School of Information Technology and Electrical Engineering; University of New South Wales at the
Australian Defence Force Academy, Canberra, Australia
Abstract - This paper demonstrates that simple yet important
characteristics of coevolution can occur in evolutionary
algorithms when only a few conditions are met. We find that
interaction-based fitness measurements such as fitness (linear)
ranking allow for a form of coevolutionary dynamics that is
observed when 1) changes are made in what solutions are able
to interact during the ranking process and 2) evolution takes
place in a multi-objective environment. This research
contributes to the study of simulated evolution in a at least two
ways. First, it establishes a broader relationship between
coevolution and multi-objective optimization than has been
previously considered in the literature. Second, it
demonstrates that the preconditions for coevolutionary
behavior are weaker than previously thought. In particular,
our model indicates that direct cooperation or competition
between species is not required for coevolution to take place.
Moreover, our experiments provide evidence that
environmental perturbations can drive coevolutionary
processes; a conclusion that mirrors arguments put forth in
dual phase evolution theory. In the discussion, we briefly
consider how our results may shed light onto this and other
recent theories of evolution.
Keywords: coevolution, dual phase evolution, evolutionary
algorithms, multi-objective optimization, self-organized
criticality.
1 Introduction
In Evolutionary Algorithms (EAs), individuals (i.e. candidate
solutions to the problem) typically interact in two ways:
through selective and recombinative operators. Both forms of
interaction impact algorithm behavior by controlling how the
population moves through solution space. Recombinative
operators (or search operators in general) influence how the
population can sample new positions in solution space while
selective operators control how, and under what conditions,
solutions are added and removed from the population.
Although the two operators are quite distinct, the execution of
either operator requires some interaction between individuals in
order to determine which new solutions to sample and which to
keep. This fact can sometimes be obscured when
implementing globally defined selection schemes or when
using distribution based search techniques where these
interactions are not explicitly defined. Such interactions are
more clearly observed however in EAs using tournament
selection, EAs with more traditional crossover operators, and
in most spatially distributed EA designs such as the cellular
GA. In these latter cases, there are clearly pair-wise or small
group interactions which result in population-wide search
behaviors.
1.1 Coevolution
Under some conditions, fitness evaluations involving
interactions between individuals can result in a contextual or
subjective definition of fitness. By contextual fitness, we
mean that fitness can sometimes be sensitive to who the
individual interacts with during fitness evaluation. Simulation
studies have suggested that contextual fitness may influence
natural phenomena such as speciation [1], population diversity
[2], and cooperative behavior [3].
Contextual fitness is also a key defining feature of coevolution
where fitness is determined in part based on interactions
between individuals. Coevolution has been studied in a
number of computer models in the domain of artificial life
(e.g. NKC models [4] [5] and tangled nature models [6]),
evolutionary game theory [7] [8], and in optimization (e.g.
cooperative [9] and competitive coevolutionary algorithms
[10]). With coevolution, the evaluation of fitness can
sometimes be intransitive, meaning that changes to the
interaction topology (i.e. who interacts with who) can alter the
ordering of fitness rankings (e.g. likelihood of survival) of
individuals.
Coevolving Fitness Landscapes: Descriptions of coevolution
often focus entirely on contextual fitness. A similar but
broader view describes coevolution based on the contextual
dependence of fitness landscapes between interacting species
(e.g. see [4]). This latter perspective requires one to look
beyond current fitness evaluations and consider the contextual
dependence of future adaptive options for each species. In
particular, the mutations (to a species) that are deemed
adaptive will depend on the context in which mutations are
taking place. This paper studies coevolution by evaluating the
codependence of fitness landscapes. However, because this is
a direct consequence of contextual fitness, this should not
detract from any of the conclusions drawn here.