This example explores cooperative coevolution using DEAP. This tutorial is not as complete as previous examples concerning type creation and other basic stuff. Instead, we cover the concepts of coevolution as they would be applied in DEAP. Assume that if a function from the toolbox is used, it has been properly registered. This example makes a great template for implementing your own coevolutionary algorithm, it is based on the description of cooperative coevolution by [Potter2001].
Coevolution is, in fact, just an extension of how algorithms works in deap. Multiple populations are evolved in turn (or simultaneously on multiple processors) just like in traditional genetic algorithms. The implementation of the coevolution is thus straightforward. A first loop acts for iterating over the populations and a second loop iterates over the individuals of these population.
The first step is to create a bunch of species that will evolve in our population.
species = [toolbox.species() for _ in range(NUM_SPECIES)]
species_index = range(NUM_SPECIES)
last_index_added = species_index[-1]
Cooperative coevolution works by sending the best individual of each species (called representative) to help in the evaluation of the individuals of the other species. Since the individuals are not yet evaluated we select randomly the individuals that will be in the set of representatives.
representatives = [random.choice(species[i]) for i in range(NUM_SPECIES)]
The evaluation function takes a list of individuals to be evaluated including the representatives of the other species and possibly some other arguments. It is not presented in detail for scope reasons, the structure would be, as usual, something like this
def evaluate(individuals):
# Compute the collaboration fitness
return fitness,
The evolution can now begin.
g = 0
for i in range(len(schematas)):
while g < ngen:
# Initialize a container for the next generation representatives
next_repr = [None] * len(species)
for (i, s), j in zip(enumerate(species), species_index):
# Variate the species individuals
s = algorithms.varAnd(s, toolbox, 0.6, 1.0)
# Get the representatives excluding the current species
r = representatives[:i] + representatives[i+1:]
for ind in s:
# Evaluate and set the individual fitness
ind.fitness.values = toolbox.evaluate([ind] + r, target_set)
# Select the individuals
species[i] = toolbox.select(s, len(s)) # Tournament selection
next_repr[i] = toolbox.get_best(s)[0] # Best selection
g += 1
representatives = next_repr
The last lines evolve each species once before sharing their representatives. The common parts of an evolutionary algorithm all present, variation, evaluation and selection occurs for each species. The species index is simply a unique number identifying each species, it can be used to keep independent statistics on each new species added.
After evolving each species, steps described in [Potter2001] are achieved to add a species and remove useless species on stagnation. These steps are not covered in this example but are present in the complete source code of the coevolution examples.
| [Potter2001] | (1, 2) Potter, M. and De Jong, K., 2001, Cooperative Coevolution: An Architecture for Evolving Co-adapted Subcomponents. |