Homogeneous and heterogeneous island models for the set cover problem

Andrea MAMBRINI; Dirk SUDHOLT; Xin YAO

doi:10.1007/978-3-642-32937-1_2

Homogeneous and heterogeneous island models for the set cover problem

Andrea MAMBRINI
, Dirk SUDHOLT
, Xin YAO

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Research › peer-review

15 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 language	English
Title of host publication	Parallel Problem Solving from Nature : PPSN XII : 12th International Conference, Taormina, Italy, September 1-5, 2012, Proceedings, Part I
Editors	Carlos A. Coello COELLO, Vincenzo CUTELLO, Kalyanmoy DEB, Stephanie FORREST, Giuseppe NICOSIA, Mario PAVONE
Publisher	Springer Berlin Heidelberg
Pages	11-20
Number of pages	10
ISBN (Electronic)	9783642329371
ISBN (Print)	9783642329364
DOIs	https://doi.org/10.1007/978-3-642-32937-1_2
Publication status	Published - 2012
Externally published	Yes
Event	12th International Conference on Parallel Problem Solving from Nature - Taormina, Italy Duration: 1 Sept 2012 → 5 Sept 2012

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Berlin, Heidelberg
Volume	7491
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th International Conference on Parallel Problem Solving from Nature
Country/Territory	Italy
City	Taormina
Period	1/09/12 → 5/09/12

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 10 Reduced Inequalities

Keywords

island model
Parallel evolutionary algorithms
runtime analysis
set cover
theory

Access to Document

10.1007/978-3-642-32937-1_2

Cite this

MAMBRINI, A., SUDHOLT, D., & YAO, X. (2012). Homogeneous and heterogeneous island models for the set cover problem. In C. A. C. COELLO, V. CUTELLO, K. DEB, S. FORREST, G. NICOSIA, & M. PAVONE (Eds.), Parallel Problem Solving from Nature : PPSN XII : 12th International Conference, Taormina, Italy, September 1-5, 2012, Proceedings, Part I (pp. 11-20). (Lecture Notes in Computer Science; Vol. 7491). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-32937-1_2

MAMBRINI, Andrea ; SUDHOLT, Dirk ; YAO, Xin. / Homogeneous and heterogeneous island models for the set cover problem. Parallel Problem Solving from Nature : PPSN XII : 12th International Conference, Taormina, Italy, September 1-5, 2012, Proceedings, Part I. editor / Carlos A. Coello COELLO ; Vincenzo CUTELLO ; Kalyanmoy DEB ; Stephanie FORREST ; Giuseppe NICOSIA ; Mario PAVONE. Springer Berlin Heidelberg, 2012. pp. 11-20 (Lecture Notes in Computer Science).

@inproceedings{a9f285d212864a1580fafa89563babc8,

title = "Homogeneous and heterogeneous island models for the set cover problem",

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. {\textcopyright} 2012 Springer-Verlag.",

keywords = "island model, Parallel evolutionary algorithms, runtime analysis, set cover, theory",

author = "Andrea MAMBRINI and Dirk SUDHOLT and Xin YAO",

year = "2012",

doi = "10.1007/978-3-642-32937-1\_2",

language = "English",

isbn = "9783642329364",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "11--20",

editor = "COELLO, \{Carlos A. Coello\} and Vincenzo CUTELLO and Kalyanmoy DEB and Stephanie FORREST and Giuseppe NICOSIA and Mario PAVONE",

booktitle = "Parallel Problem Solving from Nature : PPSN XII : 12th International Conference, Taormina, Italy, September 1-5, 2012, Proceedings, Part I",

note = "12th International Conference on Parallel Problem Solving from Nature ; Conference date: 01-09-2012 Through 05-09-2012",

}

MAMBRINI, A, SUDHOLT, D & YAO, X 2012, Homogeneous and heterogeneous island models for the set cover problem. in CAC COELLO, V CUTELLO, K DEB, S FORREST, G NICOSIA & M PAVONE (eds), Parallel Problem Solving from Nature : PPSN XII : 12th International Conference, Taormina, Italy, September 1-5, 2012, Proceedings, Part I. Lecture Notes in Computer Science, vol. 7491, Springer Berlin Heidelberg, pp. 11-20, 12th International Conference on Parallel Problem Solving from Nature, Taormina, Italy, 1/09/12. https://doi.org/10.1007/978-3-642-32937-1_2

Homogeneous and heterogeneous island models for the set cover problem. / MAMBRINI, Andrea; SUDHOLT, Dirk; YAO, Xin.
Parallel Problem Solving from Nature : PPSN XII : 12th International Conference, Taormina, Italy, September 1-5, 2012, Proceedings, Part I. ed. / Carlos A. Coello COELLO; Vincenzo CUTELLO; Kalyanmoy DEB; Stephanie FORREST; Giuseppe NICOSIA; Mario PAVONE. Springer Berlin Heidelberg, 2012. p. 11-20 (Lecture Notes in Computer Science; Vol. 7491).

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Research › peer-review

TY - GEN

T1 - Homogeneous and heterogeneous island models for the set cover problem

AU - MAMBRINI, Andrea

AU - SUDHOLT, Dirk

AU - YAO, Xin

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - island model

KW - Parallel evolutionary algorithms

KW - runtime analysis

KW - set cover

KW - theory

UR - https://www.scopus.com/pages/publications/84866355321

U2 - 10.1007/978-3-642-32937-1_2

DO - 10.1007/978-3-642-32937-1_2

M3 - Conference paper (refereed)

SN - 9783642329364

T3 - Lecture Notes in Computer Science

SP - 11

EP - 20

BT - Parallel Problem Solving from Nature : PPSN XII : 12th International Conference, Taormina, Italy, September 1-5, 2012, Proceedings, Part I

A2 - COELLO, Carlos A. Coello

A2 - CUTELLO, Vincenzo

A2 - DEB, Kalyanmoy

A2 - FORREST, Stephanie

A2 - NICOSIA, Giuseppe

A2 - PAVONE, Mario

PB - Springer Berlin Heidelberg

T2 - 12th International Conference on Parallel Problem Solving from Nature

Y2 - 1 September 2012 through 5 September 2012

ER -

MAMBRINI A, SUDHOLT D, YAO X. Homogeneous and heterogeneous island models for the set cover problem. In COELLO CAC, CUTELLO V, DEB K, FORREST S, NICOSIA G, PAVONE M, editors, Parallel Problem Solving from Nature : PPSN XII : 12th International Conference, Taormina, Italy, September 1-5, 2012, Proceedings, Part I. Springer Berlin Heidelberg. 2012. p. 11-20. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-32937-1_2

Homogeneous and heterogeneous island models for the set cover problem

Abstract

Publication series

Conference

UN SDGs

Keywords

Access to Document

Other files and links

Fingerprint

Cite this