Different ways to call the evolve method

[sowuy]

Hi,

I am using NSGA2 for my multi-objective problem and I am confused at some level on the terminology used in PyGMO.
What is the difference of setting the number of evolutions or generations ?

Below, you will find 3 cases which for me does the same job. But I would like to use the most efficient.

First, here is the intial structure of my code:

prob = pg.problem(multiObjProblem) # Create UDP
pop = pg.population(prob, size=200)  # Create population 
algo = pg.algorithm(pg.nsga2(gen=nGen)) # Set algorithm
archi = pg.archipelago() # Initialize empty archipelago
islands = [pg.island(algo=algo, pop=pop) for i in range(nIsl)]
for i in islands:
  archi.push_back(i)
archi.set_topology(pg.fully_connected(len(archi))) # Set topology of archipelago

Now, i list the three cases:

1. Evolving 10 times 20 generations of a population of 200 individuals => Fevals = 10x20x200 = 40 000

nGen = 20
nEvol = 10
for i in range(nEvol):
  archi.evolve(1) 

2. Same as one but using n argument of .evolve

nGen = 20
nEvol = 10
archi.evolve(nEvol) 

3. Evolving 200 time 1 generation of a population of 200 individuals => Fevals = 1x200x200 = 40 000

nGen = 1
nEvol = 10 * 20 = 200
archi.evolve(nEvol) 

Other questions are:

• If i don't define a topology (=islands evolve indepently), is the archipelago still useful ?
• I thought that I was using an archipelago with connected topology, I would solve my problem way faster (less generations or indivuals needed per island). But it does not seem to be the case. Why ?
• At which moment do the islands communicate and exchange individuals ? Is it at end of an evolution in the loop ?
• When should we use the archi.wait() ? In the loop after each evolution ? Or at the end of the evolution ?

Thank you.

[darioizzo]

Thanks for the question, it is always a bit confusing indeed, let me try to answer as clearly as I can:

All UDAs shipped with pagmo are guaranteed to make:

for i in range(10):
    pop = algorithm(uda(gen=1)).evolve(pop)

equivalent to

pop = algorithm(uda(gen=10)).evolve(pop)

The exception are those algorithms with a memory argument, for example CMAES. When that argument is not set to true, the above equivalence is broken as the algorithm resets its internal state at each call to the method evolve and the following call will have no memory of the previous. In those cases setting memory to true recovers the above equivalence.

Now, with this in mind lets go to your case where you have an archipelago and nsgaii. nsgaii does not have a memory argument, so the above equivalence is guaranteed. But your code is making use of the archipelago, hence migration happens between connected islands. Migration happens at the end of each call to island.evolve. archi.evolve(1) calls one evolve for each island in the archipelago (and the island.evolve calls the algo.evolve on a thread/process/node)). Migration happens asynchronously.

So we are now ready to answer your questions. You have 3 code snippets labelled with (1,2,3), they all do slightly different things and hence will have slightly different results.

1,2 do very similar things, As no wait is called no synchronization point is forced and evolutions will be started asynchronously in different threads/processes/nodes as soon as a thread/process/node is available (as regulated by the UDI type). The only difference is really technical and hidden in the exact timing sequence the various island.evolve will be called and hence started on each available resource. I would not bother understanding this, just note that you will get numerically different results and that the two are though equivalent from any higher level point of view.

3 Does a very different thing instead. Since nsgaii is memory less, in an unconnected archipelago the computation would actually be the same. But you have a fully connected topology, hence the migrations will occur and differently since nEvol will be many more in 3 than they are in 1 and 2

As per your other questions:
Q: If i don't define a topology (=islands evolve indepently), is the archipelago still useful ?
A: Yes it will perform the evolutions in parallel hence the result will be the same, but parallel (linear scaling) speed achieved.
Q: I thought that I was using an archipelago with connected topology, I would solve my problem way faster (less generations or indivuals needed per island). But it does not seem to be the case. Why ?
A: It usually is the case. You may have a strange UDP or just not able to see clearly the statistical difference. Another option is that you have too many migrations and thus exploitation is too high you should consider using a ring topology or less chance of mograting. Inspect the migration log to determine this.
A: At which moment do the islands communicate and exchange individuals ? Is it at end of an evolution in the loop ?
Q: Hopefully answered above. At the end of evolution on each island.
Q: When should we use the archi.wait() ? In the loop after each evolution ? Or at the end of the evolution ?
A: If possible never. It adds synchronization points that mostly only slow down.

Hope this answer your question, let us know ....

[sowuy]

Hi @darioizzo

Thank you so much for your detailed and intelligible explanation.

Maybe just a few questions to react to the first & last Q&A series.

You wrote that "with unconnected topology, islands evolve in parallel and result is the same but parallel speed is achieved." Do you mean that the result is the same for each island ? Therefore only the island that finishes the earliest is useful for result extraction ?

And this brings me to my second question related to last bullet of Q&A;
If I don't use any synchronization point, islands will continue to evolve at different speed. But in the end I just want to use the fastest island to continue the calculations in my script, is that right ? How does it work concretely , how do you proceed usually ? you let all the threads running till the end of your script and they will bring the same result but at different moment, or you stop all the threads except the one that finishes the evolution the earliest ?

Actually, I did not write it but I was using archi.wait() at the end of the evolve loop. Also I am initializing a different population for each island. At end of the optimization (synchronization point), I merge all populations across the islands together and plot the non-dominated Pareto solution and pick the best for my problem.

Thank you.

[darioizzo]

Q: You wrote that "with unconnected topology, islands evolve in parallel and result is the same but parallel speed is achieved." Do you mean that the result is the same for each island ? Therefore only the island that finishes the earliest is useful for result extraction ?
A: No, that would be a waste! Different populations are in different islands (i.e. initial guesses) and different seed are used for the different algos present in the islands. So if the archipelago is built cleverly, all islands will have different results that are useful also in an unconnected archipelago.

Q: If I don't use any synchronization point, islands will continue to evolve at different speed. But in the end I just want to use the fastest island to continue the calculations in my script, is that right ?
A: In an unconnected topology you indeed may want to race islands to then eventually focus your energies on the most promising algo/prob combination. You can achieve adaptively modifying the archipelago. In Pagmo1 we had a racing algorithm shipped with the code. We never ported that to pagmo2.

A nice paper to clarify some of the uses and benchmarks on the migration algorithm might be this one: https://link.springer.com/chapter/10.1007/978-3-642-28789-3_7

[sowuy]

Dear @darioizzo I have read the chapter you recommanded (thank you for sharing it), it helped me to understand deeper but I am still confused on two aspects:

1. You wrote that migration between islands happens at the end of evolution on each island but in the chapter provided, on page 158, a section discusses the "migration interval $\mu$" also called "migration frequency" that specifies the iterations the algorithm must perform before a migration can occur. Does it mean that, by default, migration happens at the end of island evolution BUT the user can specify another frequency ?
2. In most problems, we want to gather the final results from each island and compare them (especially in multiobjective schemes). To me, this translates to use the wait() function on the archipelago after all asynchronous evolutions have been performed. However you wrote that I should try not use this function to reduce the number of synchronization points. But how do you gather your results then for the final comparison ? You still have to wait that all threads are finished at the end of the day (but correct me if I am wrong).