Speaker
Description
In this contribution we contrast parallelization of extended
genetic and evolutionary algorithms by global generational
parallelization (a master-slave architecture) with island
models (a message-passing architecture). The first class
of algorithms uses a single large population where mating of individuals
is unrestricted, whereas the second class of algorithms uses multiple
populations (called demes by biologists and used for the modelling of
ecological niches) where mating of individuals is restricted within a single
population and where a few individuals occasionally migrate between
neighboring populations.
As an introduction, we present a few innovations to both approaches:
- For the master-slave architecture, the degree of parallelization can be
configured: The evaluation of the fitness function of a gene
versus the complete genetic machinery except gene selection
by pipeline compilation. In addition, various communication
approaches between master and slaves can be configured.
We concentrate on multicore and mpi based approaches. - For island models, asynchronous parallel algorithms which
communicate by message passing with the goal of using the
assigned computational resources as efficiently as possible. - Combinations of both architectures: Island models with islands parallelized by the master-slave approach.
For this purpose, the migration algorithms are highly configurable:
- The selection methods for emigrants as well as
for the genes which are replaced by immigrants.
-
The communication topology (ring, 2-dimensional torus, 3-dimensional
torus and generalized Petersen graphs, n random neighbors). -
Various communication strategies with and without synchronization.
-
Self-adaptation of the number of generations.
-
Support for configuring heterogeneous island models where
each island runs an algorithm with a different configuration. -
The communication between processes is either by using a common file system (on a notebook) or by using mpi (on a HPC cluster).
Both approaches differ considerably with regard to communication:
The master-slave architecture copies all genes of a population once
per generation to the slaves. Its performance depends
crucially on the communication cost between master and slaves which
is usually acceptable for shared-memory multiprocessors.
The maximal number of genes is limited by the memory available
for the master process. However, exact replicability
of computational experiments can be achieved by proper configuration.
The message-passing architecture of island models has the advantage
that the maximal number genes scales with the number of cores (and
processes) available. The communication cost depends on the number
of genes which migrate between populations and is configurable.
Due to the inherent asynchronicity of the current implementation, exact
replicability of computational experiments must be replaced by
stochastic replicability.
We compare both approaches with regard to scalability and
to the speed of convergence of the resulting
extended and evolutionary algorithms.
We present a proof-of-concept implementation in the form of the
R-package xega, version 0.9.1.0 (https://CRAN.R-project.org/package=xega)
as well as a few results of computational experiments.