Transcript coevolution

Coevolutionary Models
A/Prof. Xiaodong Li
School of Computer Science and IT, RMIT University
Melbourne, Australia
Email: [email protected]
April 2015
Coevolution



In biology, coevolution is "the change of a
biological object triggered by the change of a
related object”. In other words, when changes
in at least two species’ genetic compositions
reciprocally affect each other’s evolution,
coevolution has occurred.
There is evidence for coevolution at the level
of populations and species.
The above is cited from wikipedia.
11/04/2016
2
Predators and preys
11/04/2016
3
Predator-prey population dynamics
11/04/2016
4
The Red Queen Effect


The Red Queen Effect, is an evolutionary hypothesis
which proposes that organisms must constantly adapt,
evolve, and proliferate not merely to gain reproductive
advantage, but also simply to survive while pitted against
ever-evolving opposing organisms in an ever-changing
environment.
The Red Queen hypothesis intends to explain two different
phenomena: the constant extinction rates as observed in
the paleontological record caused by co-evolution between
competing species, and the advantage of sexual
reproduction (as opposed to asexual reproduction) at the
level of individuals (from Wikipedia).
11/04/2016
5
Competitive coevolution


In competitive coevolution, individual fitness is evaluated
through competition with other individuals in the population,
rather than through an absolute fitness measure.
In other words, fitness signifies only the relative strengths of
solutions; an increased fitness in one solution leads to a
decreased fitness for another. Ideally, competing solutions
will continually outdo one another, leading to an “arms race”
of increasingly better solutions.
11/04/2016
6
Coevolving sorting networks



A model of hosts and parasites to the evolution of sorting
networks using a GA (Hillis, 1991).
One species (the hosts) represents sorting networks, and
the other species (the parasites) represents test cases in
the form of sequences of numbers to be sorted.
The interaction between the two species takes the form of
complementary fitness functions. More specifically, a sorting
network is evaluated on how well it sorts test cases, while
the test cases are evaluated on how poorly they are sorted.
11/04/2016
7
Cooperative
coevolution
Modelling an ecosystem
consisting of two or more
species, collaborating
cooperatively with one and
another.
Fitness of an individual is
evaluated based on how
well it “cooperates” with the
best-fit individuals from
other species.
11/04/2016
8
Cooperative coevolutionary GA
1)
2)
3)
4)
5)
A species represents a subcomponent of a potential solution;
Complete solutions are obtained by assembling
representative members of each of the species present;
Credit assignment at the species level is defined in terms of
the fitness of the complete solutions in which the species
members participate;
When required, the number of species (subpopulations)
should itself evolve; and
The evolution of each species (subpopulation) is handled by
a standard GA.
11/04/2016
9
CCGA-1
11/04/2016
10
CCGA-1


CCGA-1 begins by initializing a separate population of
individuals for each function variable. The initial fitness of
each subpopulation member is computed by combining it
with a random individual from each of the other species
and applying the resulting vector of variable values to the
target function.
After the startup phase, each of the individual
subpopulations in CCGA-1 is coevolved in a round-robin
fashion using a traditional GA. The fitness of a
subpopulation member is obtained by combining it with
the current best subcomponents of the remaining
(temporarily frozen) subpopulations.
11/04/2016
11
CCGA-1 results on test functions
11/04/2016
12
CCGA-2


Interacting variable (e.g., product terms) may present
difficulties.
To overcome this, the simple credit assignment scheme
can be modified as follows: each individual in a
subpopulation is evaluated by combining it with the best
known individual from each of the other species and with
a random selection of individuals from each of the other
species. The two resulting vectors are then applied to
the target function and then the better of the two values
is returned as the offspring’s fitness.
11/04/2016
13
CCGA-1 and CCGA-2 results
11/04/2016
14
Evolving cascade networks
In cascade networks, all input units have direct connections to all hidden units and to all output
units, the hidden units are ordered, and each hidden unit sends its output to all downstream
hidden units and to all output units.
11/04/2016
15
Evolving cascade networks

1)
2)
3)
The network shown in Figure 8 (shown in the previous
slide) is constructed incrementally as follows:
When the evolution of the network begins, there is only one species in
the ecosystem, and its individuals represent alternatives for the output
connection weights denoted by the three black boxes.
Later in the network’s evolution, the first hidden unit is added, and a
second species is created to represent the new unit’s input connection
weights. In addition, a new connection weight is added to each
individual of the first species. All of these new weights are denoted by
gray boxes in the figure.
The species creation event is triggered by evolutionary stagnation as
described earlier. Later still, evolution again stagnates and the second
hidden unit is added, a third species is created to represent the unit’s
connection weights, and the individuals of the first species are further
lengthened. Further information refer to (Potter and De Jong, 2000).
11/04/2016
16
Further readings

Mitchell A. Potter and Kenneth De Jong. A cooperative
coevolutionary approach to function optimization. In
Yuval Davidor, Hans-Paul Schwefel, and Reinhard
Manner, editors, Parallel Problem Solving from Nature PPSN III, pages 249-257, Berlin, 1994. Springer.

Mitchell A. Potter and Kenneth De Jong. Cooperative
Coevolution: An Architecture for Evolving Coadapted
Subcomponents. Evolutionary Computation, 8(1): 1-29.
MIT Press.
11/04/2016
17