Adding co-evolution component - Questions and Ideas
Itamar K.
We are trying to add a Co-evolution described in previous post (here:
http://groups.google.com/group/heuristiclab/browse_thread/thread/e133017ab169aaeb)
(we work with Achiya).
We want the Co-Evolution to support the following features:
1. It has 2 different populations that might use different algorithms.
For example GA and GP, or any other algorithm, based on population and
iteration.
2. The evolution of the two populations might not be in the same
phase: sometimes we want that population A will evolve every single
generation, but population B will evolve every 5 generations (or any
other ratio).
3. The evaluation function of each algorithm evaluates an individual
against individual(s) from the other population.
We have some questions about the implementation:
1. This is the structure we thought about for the Co-Evolution:
Init Co-Evolution --> Init alg1 --> Init alg2 --> while terminating
condition had not met:
Iterate alg1 or alg2 once, according to the evaluation ratio.
Do you think this model is appropriate?
In addition, we should notice that the evaluation function of each
algorithm must know the population of the other algorithm.
2. To implement that, every algorithm must implement an interface that
guarantees:
a. It has a method "iterate once".
b. It has a method "initialize".
c. Its population can be accessed from the outside.
(Suggested name: IpopulationIterationAlgorithm)
What do you think about this idea of the interface?
3. Implementing that requires changes in the operator graph of
algorithms in HeuristicLab. In GA, for example, the "iterate once"
operation is currently embedded inside the "GA main loop" operator, so
iterating it once is not possible. In our opinion, it makes more sense
to create the operator graph like this:
https://picasaweb.google.com/itamar.kiesler/HeuristicLab1#5690404628047431650
In main loop we will have:
https://picasaweb.google.com/itamar.kiesler/HeuristicLab1#5690404686767737234
And in iterate once we will have:
https://picasaweb.google.com/itamar.kiesler/HeuristicLab1#5690404690950635042
In addition we will have the initialize component:
https://picasaweb.google.com/itamar.kiesler/HeuristicLab1#5690404688548886882
In the Co-Evolution operator graph it would appear like this:
https://picasaweb.google.com/itamar.kiesler/HeuristicLab1#5690404694625745602
And in the main loop of the Co-Evolution:
https://picasaweb.google.com/itamar.kiesler/HeuristicLab1#5690404696868935442
What do you think about this change?
4. As Stefan Wagner suggested in previous conversation, the 2
algorithms will be in 2 sub-scopes. In order to iterate one algorithm
and not the other, we need an operator that can apply operator on one
sub-scope and not the other. We understand that such operator does not
exist, and needs to be implemented from scratch.
5. We have another question, partially related:
What is the operator "Initialize EvaluatedSolutions" in GA operator
graph? We couldn't find it in the operators list.
Thank you very much,
Best regards,
(and merry Christmas to those of you who celebrate Christmas)
Tomer and Itamar
Stefan Wagner
using the graphical algorithm designer in HeuristicLab, I created a
user-defined algorithm which should fulfill your needs. I attached two
versions of this algorithm to this e-mail. The file "Co-Evolution
(Template).hl" contains the algorithm without any problem-specific operators
and data. Therefore it cannot be executed and shows only the structure of
the co-evolution algorithm. You can use it as a template and add the
operators and data of your problem. The second file "Co-Evolution.hl"
contains the same algorithm but additionally I added the required operators
and problem data to evolve two populations of TSP ch130 solutions with two
differently parameterized GAs. Of course this is not a reasonable
application of co-evolution, but it should simply demonstrate that the
operator graph of the algorithm is valid and that the algorithm can be
executed. Both files can be opened in HeuristicLab 3.3.6. Please note that I
did not implement anything for modeling the co-evolution algorithm. All the
operators which are required to model this algorithm are already included in
HeuristicLab.
Let's have a detailed look at the operator graph of the co-evolution
algorithm:
* The first operator (RandomCreator) initializes the PRNG and adds it to the
global scope.
* The second operator (SubScopesCreator) creates two new and empty
sub-scopes which are the parent scopes of the two populations.
* The third operator (SubScopesProcessor) applies its two sub-operators on
these two sub-scopes (the first sub-operator on the first sub-scope and the
second sub-operator on the second sub-scope). The two sub-operators are
combined operators which contain the operators required to initialize both
populations. First a result collection is created and collected in the main
result collection of the co-evolution algorithm. Then the new and empty
sub-scopes for the solutions are created and a solution creator is applied
on each of the sub-scopes.
* The fourth operator is again a SubScopesProcessor which applies two
combined operators which are responsible for evaluating the newly created
populations. Solution creation and evaluation are separated into two steps,
as both populations have to be fully created before you can evaluate them
(according to your requirements). Inside the combined operators, an
evaluator is applied on each solution and the variable for counting the
number of evaluated solutions is created and collected in the individual
result collection of algorithm A or algorithm B. Then an analyzer is applied
to analyze the initial population.
* The fifth operator (VariableCreator) creates a variable for counting the
number of iterations of the co-evolution algorithm.
* The sixth operator (ResultsCollector) collects this variable in the main
results of the co-evolution algorithm.
* The seventh operator (SubScopesProcessor) applies the main loops of the
two algorithms on the corresponding population. Please note that the two
sub-operators are placeholders. These placeholders retrieve the operator
which should be executed from the parameters of the co-evolution algorithm
(the two parameters are named AlgorithmA and AlgorithmB). By this means you
can simply exchange the algorithms to evolve the populations by changing the
parameter values in the parameters tab of the co-evolution algorithm.
* The eighth operator (IntCounter) increments the Iterations variable by 1.
* The ninth operator (Comperator) checks, if the Iterations variable is
larger or equal to MaximumIterations and adds a boolean variable with the
result of the comparison.
* The tenth operator (ConditionalBranch) checks the result of the previous
comparison and starts the next iteration of the co-evolution algorithm, if
necessary.
The next topic we should discuss are the parameters of the problem, the
algorithm and the operators:
* In the problem tab page and the parameters tab page of the co-evolution
algorithm you can see that there is an A and a B version of most of the
parameters. All "A" parameters correspond to algorithm A and to the first
population, all "B" parameters correspond to algorithm B and therefore to
the second population. The parameters of the operators in the operator graph
are configured correctly, so that they use the right parameter. For example,
the SubScopesCreator inside the initialization step of population A contains
a parameter named "NumberOfSubScopes" and this parameter is redirected to
the parameter "PopulationSizeA" of the algorithm.
* You can now simply parameterize the co-evolution algorithm by setting the
parameters on the problem and on the parameters tab page. You do not have to
modify the parameters of the operators in the operator graph, as they should
be configured correctly.
* When changing the population size of algorithm A or of algorithm B, you
must not forget to change the parameter "NumberOfSelectedSubScopes" in the
selectors as well. Otherwise the selectors will not select the right number
of parents. NumberOfSelectedSubScopes has to have the value (population size
- elites) * 2, as two parents are used by the crossover operator to create
one child.
* The two parameters "AlgorithmA" and "AlgorithmB" are set to the
GeneticAlgorithmMainLoopOperator. Therefore two GAs (but with different
parameters) are used to evolve the two populations. If you want to apply
another algorithm for evolving one of the populations, just replace the
GeneticAlgorithmMainLoop with the main loop operator of any other algorithm
and set the parameters of the operator correctly (for example redirect the
parameter "Crossover" to "CrossoverA", etc.).
* In general you have to be a bit careful when you parameterize the
algorithm or the problem with new operators (for example if you want to use
another selector). The parameters of the new operator have to be set
correctly so that the operator is ably to find all values it needs.
Ok, I think that was the most important information regarding the structure
of the co-evolution algorithm. Please have a look at it and test if, if it
is suitable for you.
Now let's concentrate on your questions:
1., 3. and 4.: The structure of the co-evolution algorithm I built is a bit
different from the structure you suggested. The main reason is that this
structure can be realized with the operators already included in
HeuristicLab. Of course you can also model the algorithm in the way you
suggested, but this would require some new operators.
2.: As I modeled the co-evolution algorithm, I noticed that a new interface
is not really required. You can use any existing main loop operator for
evolving the populations. The interface will only be required, if we
integrate the co-evolution algorithm as a standard algorithm in
HeuristicLab. As long as it is a user-defined algorithm, the interface is
not required, as you can choose an appropriate main loop operator manually.
5.: The operator "Initialize EvaluatedSolutions" is a SubScopesCounter.
Because of your question, we noticed that the operator types are not shown
in the operator graph. So it is very hard to identify the type of an
operator, after the name of the operator has been changed. We fixed this
issue in HeuristicLab 3.3.6 (ticket #1715 [1]). Now the type name of an
operator is also shown, if the name of the operator is not the same. Thanks
for this feedback.
As the co-evolution algorithm is defined now, the next step is to implement
the problem-specific operators (solution creator, evaluator). If the
existing solution encodings are not sufficient for your needs, you have to
implement a new encoding and corresponding solution creation and
manipulation operators.
The evaluation operator is a bit special in your case, as you have to access
the other population. You can access the scope tree in every operator with
this.ExecutionContext.Scope. Therefore you can implement an evaluation
operator which goes up in the scope tree (Scope.Parent) and then goes down
to the scopes of the other population (Scope.SubScopes) to retrieve the
corresponding solutions.
I hope that this information and the attached algorithms are helpful for
you. If you have any further questions, please let us know.
Best regards,
Stefan
[1] http://dev.heuristiclab.com/trac/hl/core/ticket/1715
-----Ursprüngliche Nachricht-----
Von: heuris...@googlegroups.com [mailto:heuris...@googlegroups.com] Im
Auftrag von Itamar K.
Gesendet: Montag, 26. Dezember 2011 13:02
An: HeuristicLab
Betreff: Adding co-evolution component - Questions and Ideas
Itamar K.
Thank you for the extensive response.
We would learn the new algorithm and respond later on with further
questions.
Tomer and Itamar
>
> read more »
>
> Co-Evolution (Template).hl
> 65KViewDownload
>
> Co-Evolution.hl
> 74KViewDownload
Itamar K.
We try to use this template to solve a problem with co-evolution. For now we try to solve the 15-puzzle, and in the future we will approach more complicated problems. However, evaluating takes long time, and we would like to parallel it.
How can we do it, when using the above template?
Thanks,
Tomer and Itamar
> Von: heuris...@googlegroups.com [mailto:heuristiclab@googlegroups.com] Im
Stefan Wagner
Dear Itamar and Tomer,
if parallel solution evaluation is supported by the inner algorithms which you use to evolve both populations (AlgorithmA and AlgorithmB), you can simply switch the execution engine from “Sequential Engine” to “Parallel Engine” on the “Engine” tab to use multiple cores. This is the case for the GeneticAlgorithmMainLoop which I used in the example I sent you. But also most of the other main loop operators support parallel solution evaluation.
If you also want to parallelize solution evaluation in the initialization of the algorithm, you have to open the combined operators “Evaluate Population A” and “Evaluate Population B” and to set the “Parallel” parameter of the “Evaluate Solutions” operator to true.
Best regards,
Stefan
From: heuris...@googlegroups.com [mailto:heuris...@googlegroups.com] On Behalf Of Itamar K.
Sent: Dienstag, 17. Juli 2012 15:43
To: heuris...@googlegroups.com
Subject: Re: Adding co-evolution component - Questions and Ideas
Dear HeuristicLab crew,
> Von: heuris...@googlegroups.com [mailto:heuris...@googlegroups.com] Im
Achiya Elyasaf
For some reason there is a bug in the algorithm you sent us when we change the engine to parallel
We don't understand why.
Best,
Achiya
On Wednesday, July 18, 2012 2:00:36 AM UTC+3, Stefan Wagner wrote:
Dear Itamar and Tomer,
if parallel solution evaluation is supported by the inner algorithms which you use to evolve both populations (AlgorithmA and AlgorithmB), you can simply switch the execution engine from “Sequential Engine” to “Parallel Engine” on the “Engine” tab to use multiple cores. This is the case for the GeneticAlgorithmMainLoop which I used in the example I sent you. But also most of the other main loop operators support parallel solution evaluation.
> Von: heuris...@googlegroups.com [mailto:heuristiclab@googlegroups.com] Im
swa...@heuristiclab.com
Dear Achiya,
I tested the file I sent you (Co-Evolution.hl) in HeuristicLab 3.3.6 and HeuristicLab 3.3.7 once more and found no problems. Can you describe your problem in more detail?
Best regards,
Stefan
From: heuris...@googlegroups.com [mailto:heuris...@googlegroups.com] On Behalf Of Achiya Elyasaf
Sent: Donnerstag, 26. Juli 2012 08:36
To: heuris...@googlegroups.com
Subject: Re: Adding co-evolution component - Questions and Ideas
Dear Stefan
> Von: heuris...@googlegroups.com [mailto:heuris...@googlegroups.com] Im