Abstract:
Island models (IMs) are a class of distributed evolutionary algorithms (EAs) in
which the population is split into multiple sub-populations called islands. Separate
EAs run independently on each island, but they interact by means of migrating
individuals. Therefore, IMs are different both from a single-population standard EA,
as well as from a set of multiple isolated EAs.
IMs are interesting for several reasons. They have been reported to yield better
results than standard EAs. IMs are also advantageous when computational tasks must
be distributed across multiple machines because their structure is easy to parallelize.
However, despite many studies, no comprehensive theory describing their behavior
has been developed. Due to the lack of theory and a complex architecture with many
control parameters, setting up IMs has been a trial-and-error process, guided mostly
by “rules of thumb.”
In this dissertation, I adopt a two-level (intra- and inter-island) view of IMs and
show how this approach makes understanding their dynamics easier. They behave
very differently than standard EAs, and in order to take full advantage of this, I
propose a better utilization of the inter-island level of evolution. In particular, I argue
for setups with many relatively small islands, and I also show that compositional
evolution may scale to the inter-island level.
The two levels of evolution influence each other, and I analyze this interaction more
deeply. Migrations profoundly change the local dynamics and stimulate evolution,
which often ultimately results in better performance. I study the role of genetic
operators in this behavior and also create mathematical models of after-migration
dynamics. This analysis gives us a better understanding of mixing and the survival
of genes locally, and these processes in turn determine the type and level of interaction
between islands globally. Further, using island heterogeneity enhances the inter-island
evolution. Following the study, I analyze IM behavior on a range of test problems,
including two complex domains.
This dissertation improves our understanding of the dynamics of IMs and suggests
a qualitative change in the way we think about them. This perspective offers new
guidelines for configuring IM parameters and opens new directions for future work.
