Homogeneous and heterogeneous island models for the set cover problem

Andrea MAMBRINI, Dirk SUDHOLT, Xin YAO

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

14 Citations (Scopus)

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. © 2012 Springer-Verlag.
Original languageEnglish
Title of host publicationParallel Problem Solving from Nature : PPSN XII : 12th International Conference, Taormina, Italy, September 1-5, 2012, Proceedings, Part I
EditorsCarlos A. Coello COELLO, Vincenzo CUTELLO, Kalyanmoy DEB, Stephanie FORREST, Giuseppe NICOSIA, Mario PAVONE
PublisherSpringer Berlin Heidelberg
Pages11-20
Number of pages10
ISBN (Electronic)9783642329371
ISBN (Print)9783642329364
DOIs
Publication statusPublished - 2012
Externally publishedYes
Event12th International Conference on Parallel Problem Solving from Nature - Taormina, Italy
Duration: 1 Sept 20125 Sept 2012

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin, Heidelberg
Volume7491
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Conference on Parallel Problem Solving from Nature
Country/TerritoryItaly
CityTaormina
Period1/09/125/09/12

Keywords

  • island model
  • Parallel evolutionary algorithms
  • runtime analysis
  • set cover
  • theory

Fingerprint

Dive into the research topics of 'Homogeneous and heterogeneous island models for the set cover problem'. Together they form a unique fingerprint.

Cite this