Homogeneous and Heterogeneous Island Models for the Set Cover Problem

Andrea Mambrini¹, Dirk Sudholt², and Xin Yao¹

¹University of Birmingham, Birmingham, UK

²University of Sheffield, Sheffield, UK

Abstract. We propose and analyse two island models that provably find good approximations for the SetCover problem. A homogeneous island model running parallel instances of the SEMO algorithm—following Friedrich et al. (Evolutionary Computation 18(4), 2010, 617-633)—leads to significant speedups over a single SEMO instance, but at the expense of large communication costs. A heterogeneous island model, where each island optimises a different single-objective fitness function, provides similar speedups at reduced communication costs. We compare different topologies for the homogeneous model and different migration policies for the heterogeneous one.

Keywords: Parallel evolutionary algorithms, set cover, island model, theory, runtime analysis

LNCS 7491, p. 11 ff.

Full article in PDF | BibTeX

lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012