Pygmo2: migration between islands in an archipelago during evolution

I'm trying to use the Python library Pygmo2 (https://esa.github.io/pagmo2/index.html) to parallelize an optimization problem.

To my understanding, parallelization can be achieved with an archipelago of islands (in this case, mp_island).

As a minimal working example, one of the tutorials from the official site can serve: https://esa.github.io/pagmo2/docs/python/tutorials/using_archipelago.html

I extracted the code:

class toy_problem:
    def __init__(self, dim):
        self.dim = dim

    def fitness(self, x):
        return [sum(x), 1 - sum(x*x), - sum(x)]

    def gradient(self, x):
        return pg.estimate_gradient(lambda x: self.fitness(x), x)

    def get_nec(self):
        return 1

    def get_nic(self):
        return 1

    def get_bounds(self):
        return ([-1] * self.dim, [1] * self.dim)

    def get_name(self):
        return "A toy problem"

    def get_extra_info(self):
        return "\tDimensions: " + str(self.dim)

import pygmo as pg
a_cstrs_sa = pg.algorithm(pg.cstrs_self_adaptive(iters=1000))
p_toy = pg.problem(toy_problem(50))
p_toy.c_tol = [1e-4, 1e-4]
archi = pg.archipelago(n=32,algo=a_cstrs_sa, prob=p_toy, pop_size=70)

print(archi)
archi.evolve()
print(archi)

Looking at the documentation of the old version of the library (http://esa.github.io/pygmo/documentation/migration.html), migration between islands seems to be an essential feature of the island parallelization model. Also, to my understanding, optimization algorithms like evolutionary algorithms could not work without it.

However, in the documentation of Pygmo2, I can nowhere find how to perform migration.

Is it happening automatically in an archipelago?

Does it depend on the selected algorithm?

Is it not yet implemented in Pygmo2?

Is the documentation on this yet missing or did I just not find it?

Can somebody enlighten me?

The migration framework has not been fully ported from pagmo1 to pagmo2 yet. There is a long-standing PR open here:

https://github.com/esa/pagmo2/pull/102

We will complete the implementation of the migration framework in the next few months, hopefully by the beginning of the summer.

Archipelago class, The individuals migrate across the routes described by the topology, and the islands' will initialise an archipelago with a topology t and n islands built from kwargs. During the evolution of an archipelago, islands will periodically store the  During the evolution of an archipelago, islands will periodically store the individuals selected for migration in a migrant database. This is a list of tuple objects whose size is equal to the number of islands in the archipelago, and which contains the current candidate outgoing migrants for each island. The migrants tuples consist of 3 values each:

IMHO, the PyGMO2/pagmo documentation is confirming the migration feature to be present.

The archipelago class is the main parallelization engine of pygmo. It essentially is a container of island able to initiate evolution (optimization tasks) in each island asynchronously while keeping track of the results and of the information exchange (migration) between the tasks ...

With an exception of thread_island-s ( where some automated inference may take place and enforce 'em for thread-safe UDI-s ), all other island types - { mp_island | ipyparallel_island }-s do create a GIL-independent form of a parallelism, yet the computing is performed via an async-operated .evolve() method

In original PyGMO, the archipelago class was auto .__init__()-ed with attribute topology = unconnected(), unless specified explicitly, as documented in PyGMO, having a tuple of call-interfaces for archipelago.__init__() method ( showing just the matching one ):

 __init__( <PyGMO.algorithm> algo,
           <PyGMO.problem>   prob,
           <int>             n_isl,
           <int>             n_ind [, topology            = unconnected(),
                                      distribution_type   = point_to_point,
                                      migration_direction = destination
                                      ]
           )

But, adding that, one may redefine the default, so as to meet one's PyGMO evolutionary process preferences:

topo = topology.erdos_renyi( nodes = 100,
                             p     = 0.03
                             )              # Erdos-Renyi ( random ) topology

or set a Clustered Barabási-Albert, with ageing vertices graph topology:

topo = topology.clustered_ba( m0    =    3,
                              m     =    3,
                              p     =    0.5,
                              a     = 1000,
                              nodes =    0
                              )            # clustered Barabasi-Albert,
   #                                       # with Ageing vertices topology

or:

topo = topology.watts_strogatz( nodes = 100,
                                p     =   0.1
                                )             # Watts-Strogatz ( circle
                                              #                + links ) topology

and finally, set it by assignment into the class-instance attribute:

archi = pg.archipelago( n        = 32,
                        algo     = a_cstrs_sa,
                        prob     = p_toy,
                        pop_size = 70
                        )              # constructs an archipelago
archi.topology = topo                  # sets the topology to the
#                                      # above selected, pre-defined <topo>

Island class, Through the UDI, the island class manages the asynchronous evolution (or from the island when migration across islands occurs within the archipelago . Island and Archipelago¶. NOTE: There are two different types of islands in PyGMO. The PyGMO.local_island and the PyGMO.py_island. The need for two different types of island is purely technical (it is necessary to give the user the possibility of implementing the problem or the algorithm in python directly) and the user needs not to know any details.

pagmo2 is now implementing migration since v2.11, the PR has benn completed and merged into master. Almost all capabilities present in pagmo1.x are restored. We will still add more topologies in the future, but they can already be implemented manually. Refer to docs here: https://esa.github.io/pagmo2/docs/cpp/cpp_docs.html

Tutorial and example are missing and will be added in the near future (help is welcome)

Could you code an archipelago to use multithreading when it , I have noticed that while archi.evolve() uses multithreading to evolve as many islands as possible with multithreading, the archipelago class does not we first need to finish up the work on migration/topology, which is likely to  Conversely, D-statistic comparisons between the ABC Islands and mainland brown bears for polar bear admixture were consistently and equivalently non-zero (Figure 3, bottom), regardless of the polar bear used in the comparison (D = 0.016, which translates to roughly 0.75% of the genome; Z-score = 1.24).

Archipelago slices · Issue #5 · esa/pygmo2 · GitHub, Currently, an archipelago object allows to access its islands by GitHub is home to over 50 million developers working together to host and Not sure if we should tackle this now however or if it is better to wait for the migration to pybind11, bluescarni transferred this issue from esa/pagmo2 on Jan 10. PyGMO’s implementation of the generalized migration operator allows the user to easily define “migration paths” (topologies) between a large number of “islands” (CPU cores).

pagmo2/Lobby, Is it possible to evolve the islands of a population sequentially? a problem parallelized with parthos and I want to evolve an archipelago to exploit migration. PyGMO (the Python Parallel Global Multiobjective Optimizer) is a scientific library providing a large number of optimisation problems and algorithms under the same powerful parallelization abstraction built around the generalized island-model paradigm.

Genetic diversity and differentiation patterns in Micromeria from the , My understanding how an archipelago with nlopt works is: The populations at each island is independently evolved a number of times (nn). How does migration between islands work when you are using not_population_based solvers, like nlopt? @b-reyes we don't have anything equivalent to Dr. PyGMO in pygmo2. The Maluku Islands or the Moluccas (/ m ə ˈ l ʌ k ə z /) are an archipelago in eastern Indonesia. Tectonically they are located on the Halmahera Plate within the Molucca Sea Collision Zone . Geographically they are located east of Sulawesi , west of New Guinea , and north and east of Timor .

Comments
  • Well, thanks for the answer. I also read this, but I still don't know if I actively have to do something for migration and what it's exactly doing in case it happens automatically.
  • Test it - by .evolve() the exactly same problem on an isolated island, resp. on the archipelago and compare quality of results achieved and time-to-run to see if the same problem + the same optimisation method they both used but each on a different GMO-{ resources, "topology" } to generate a result does indeed match in both the time & the same quality of result or not.