Adding coevolution algorithm plugin
eggsterino
I want to create a coevolution algorithm plugin but i need some help
with planning the operators graph.
I'll try to give some information:
There are 2 different populations. Each one has its different
evaluation function, random generator, xo, mutation, etc.
The first population's fitness is in inverse proportion to the fitness
of the second population - I will explain it more later.
They are not necessarily evolve at the same time - meaning one of the
population can evolve each generation and the other one might evolve
only if one of the following conditions has become true: n generations
have passed since the last evolving or if the average fitness of the
first population is good enough (the idea is that we want the first
population to have enough time for improving before the second
population evolves and become harder).
I use coevolution in the following manner - the second population is a
population of problems (tsp, rubic-cube, tile-puzzle, etc.). The first
population is a population of solvers.
Each generation, each individual / solver is trying to solve k
problems from the second population and its fitness is the average
performance of the solver over these k problems.
So this is the evaluation function of the solvers.
About the problems fitness - if a problem in the second population is
being solved k times by different solvers - then its fitness will be
the "opposite" of the average performance of the solvers - the better
the solvers are - the lower the fitness of the problem is, and vice-
verse.
Therefore the second population need to know how the solvers solved.
What i did until now was simple - every time a solver tried to solve -
it passed its performance information to that problem which kept the
information till the end of all of the solvers evaluations. Then, all
the problems evaluated their fitness by averaging all the information
they have gathered. Now every individual in both population has
fitness and the evolutionary process can move on.
I know it's a bit complicated and i hope i made myself clear. if not i
can try explain a bit different.
Any ideas?
Thanks
Achiya
Stefan Wagner
I think the best way to build such a coevolutionary algorithm is to create
an operator graph which consists of two GA operator graphs. You can create a
custom algorithm and add the operators of the GA twice. You have to be a bit
careful with their parameter names to avoid name clashes and you have to add
an additional operator (SubScopesCreator) to create two new sub-scopes first
which will then serve as the root scopes of the two GAs. The evaluation
operator will be quite special in that case and has to be implemented from
scratch, as it has to fetch information from both populations. Additionally,
another operator will be necessary which handles the execution of the
iterations of the two GAs, as one GA (the one that evolves the problems) is
executed less often than the other.
However, before you start to create such a coevolutionary algorithm, I would
recommend you to implement the two problems (evolution of solvers, evolution
of problems) independently from each other first. When you have these two
problems and when you can execute a GA to solve them independently,
combining both problems in a coevolutionary algorithm should not be that
difficult. Of course we will be happy to assist you in the definition of the
operator graph of the coevolutionary algorithm, but the two problems and the
corresponding operators (xover, mutation, evaluation) have to be implemented
first. For some guidance to creating custom problems, please have a look at
the how tos [1].
If you have any further questions on how to implement these problems, please
let us know.
Best regards,
Stefan
[1] http://dev.heuristiclab.com/trac/hl/core/wiki/DevelopersHowtos
eggsterino
Although in my case both of the populations are GAs, coevolution is
not necessarily combined from 2 GA population. It might be that one of
the populations is GP or neural network.
Isn't it enough to assume that each of the population will implement
some population interface (and not necessarily GA)?
Best regards
Achiya
Stefan Wagner
yes, that would be enough. However, we have not yet defined such a common
interface for arbitrary population-based algorithms in HeuristicLab. Due to
the operator model of HeuristicLab such an interface was not necessary so
far, but it will not be a big deal to define it. Then you can create a
coevolutionary algorithm which is not restricted to GAs and allows to use
arbitrary algorithms (which implement this interface) for evolving the two
populations.
Best regards,
Stefan