An immune-inspired algorithm for the set cover problem

Ayush Joshi; Jonathan E. Rowe; Christine Zarges

doi:10.1007/978-3-319-10762-2_24

An immune-inspired algorithm for the set cover problem

Ayush Joshi, Jonathan E. Rowe, Christine Zarges

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 Citations (Scopus)

Abstract

This paper introduces a novel parallel immune-inspired algorithm based on recent developments in the understanding of the germinal centre reaction in the immune system. Artificial immune systems are relatively new randomised search heuristics and work on parallelising them is still in its infancy. We compare our algorithm with a parallel implementation of a simple multi-objective evolutionary algorithm on benchmark instances of the set cover problem taken from the OR-library. We show that our algorithm finds feasible solutions faster than the evolutionary algorithm using less parameters and communication effort.

Original language	English
Title of host publication	Parallel Problem Solving from Nature
Subtitle of host publication	PPSN XIII - 13th International Conference, Ljubljana, Slovenia, September 13-17, 2014. Proceedings
Editors	Thomas Bartz-Beielstein, Jürgen Branke, Bogdan Filipič , Jim Smith
Publisher	Springer
Pages	243-251
Number of pages	9
Volume	8672
ISBN (Electronic)	9783319107622
ISBN (Print)	9783319107615
DOIs	https://doi.org/10.1007/978-3-319-10762-2_24
Publication status	Published - 2014
Event	13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) - - Ljublijana, Slovenia Duration: 13 Sept 2014 → 17 Sept 2014

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer-Verlag
Volume	8672

Conference

Conference	13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) -
Country/Territory	Slovenia
Period	13/09/14 → 17/09/14

Keywords

Artificial immune systems
GSEMO
Set cover

ASJC Scopus subject areas

General Computer Science
Theoretical Computer Science

Access to Document

10.1007/978-3-319-10762-2_24

Cite this

Joshi, A., Rowe, J. E., & Zarges, C. (2014). An immune-inspired algorithm for the set cover problem. In T. Bartz-Beielstein, J. Branke, B. Filipič , & J. Smith (Eds.), Parallel Problem Solving from Nature: PPSN XIII - 13th International Conference, Ljubljana, Slovenia, September 13-17, 2014. Proceedings (Vol. 8672, pp. 243-251). (Lecture Notes in Computer Science; Vol. 8672). Springer. https://doi.org/10.1007/978-3-319-10762-2_24

Joshi, Ayush ; Rowe, Jonathan E. ; Zarges, Christine. / An immune-inspired algorithm for the set cover problem. Parallel Problem Solving from Nature: PPSN XIII - 13th International Conference, Ljubljana, Slovenia, September 13-17, 2014. Proceedings. editor / Thomas Bartz-Beielstein ; Jürgen Branke ; Bogdan Filipič ; Jim Smith. Vol. 8672 Springer, 2014. pp. 243-251 (Lecture Notes in Computer Science).

@inproceedings{bfe12525fd534792890eff278d37520c,

title = "An immune-inspired algorithm for the set cover problem",

abstract = "This paper introduces a novel parallel immune-inspired algorithm based on recent developments in the understanding of the germinal centre reaction in the immune system. Artificial immune systems are relatively new randomised search heuristics and work on parallelising them is still in its infancy. We compare our algorithm with a parallel implementation of a simple multi-objective evolutionary algorithm on benchmark instances of the set cover problem taken from the OR-library. We show that our algorithm finds feasible solutions faster than the evolutionary algorithm using less parameters and communication effort.",

keywords = "Artificial immune systems, GSEMO, Set cover",

author = "Ayush Joshi and Rowe, {Jonathan E.} and Christine Zarges",

year = "2014",

doi = "10.1007/978-3-319-10762-2_24",

language = "English",

isbn = "9783319107615 ",

volume = "8672",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "243--251",

editor = "{ Bartz-Beielstein}, Thomas and Branke, {J{\"u}rgen } and {Filipi{\v c} }, {Bogdan } and Jim Smith",

booktitle = "Parallel Problem Solving from Nature",

note = "13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) - ; Conference date: 13-09-2014 Through 17-09-2014",

}

Joshi, A, Rowe, JE & Zarges, C 2014, An immune-inspired algorithm for the set cover problem. in T Bartz-Beielstein, J Branke, B Filipič & J Smith (eds), Parallel Problem Solving from Nature: PPSN XIII - 13th International Conference, Ljubljana, Slovenia, September 13-17, 2014. Proceedings. vol. 8672, Lecture Notes in Computer Science, vol. 8672, Springer, pp. 243-251, 13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) - , Slovenia, 13/09/14. https://doi.org/10.1007/978-3-319-10762-2_24

An immune-inspired algorithm for the set cover problem. / Joshi, Ayush; Rowe, Jonathan E.; Zarges, Christine.
Parallel Problem Solving from Nature: PPSN XIII - 13th International Conference, Ljubljana, Slovenia, September 13-17, 2014. Proceedings. ed. / Thomas Bartz-Beielstein; Jürgen Branke; Bogdan Filipič ; Jim Smith. Vol. 8672 Springer, 2014. p. 243-251 (Lecture Notes in Computer Science; Vol. 8672).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - An immune-inspired algorithm for the set cover problem

AU - Joshi, Ayush

AU - Rowe, Jonathan E.

AU - Zarges, Christine

PY - 2014

Y1 - 2014

N2 - This paper introduces a novel parallel immune-inspired algorithm based on recent developments in the understanding of the germinal centre reaction in the immune system. Artificial immune systems are relatively new randomised search heuristics and work on parallelising them is still in its infancy. We compare our algorithm with a parallel implementation of a simple multi-objective evolutionary algorithm on benchmark instances of the set cover problem taken from the OR-library. We show that our algorithm finds feasible solutions faster than the evolutionary algorithm using less parameters and communication effort.

AB - This paper introduces a novel parallel immune-inspired algorithm based on recent developments in the understanding of the germinal centre reaction in the immune system. Artificial immune systems are relatively new randomised search heuristics and work on parallelising them is still in its infancy. We compare our algorithm with a parallel implementation of a simple multi-objective evolutionary algorithm on benchmark instances of the set cover problem taken from the OR-library. We show that our algorithm finds feasible solutions faster than the evolutionary algorithm using less parameters and communication effort.

KW - Artificial immune systems

KW - GSEMO

KW - Set cover

UR - http://www.scopus.com/inward/record.url?scp=84921793436&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-10762-2_24

DO - 10.1007/978-3-319-10762-2_24

M3 - Conference contribution

AN - SCOPUS:84921793436

SN - 9783319107615

VL - 8672

T3 - Lecture Notes in Computer Science

SP - 243

EP - 251

BT - Parallel Problem Solving from Nature

A2 - Bartz-Beielstein, Thomas

A2 - Branke, Jürgen

A2 - Filipič , Bogdan

A2 - Smith, Jim

PB - Springer

T2 - 13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) -

Y2 - 13 September 2014 through 17 September 2014

ER -

Joshi A, Rowe JE, Zarges C. An immune-inspired algorithm for the set cover problem. In Bartz-Beielstein T, Branke J, Filipič B, Smith J, editors, Parallel Problem Solving from Nature: PPSN XIII - 13th International Conference, Ljubljana, Slovenia, September 13-17, 2014. Proceedings. Vol. 8672. Springer. 2014. p. 243-251. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-10762-2_24

An immune-inspired algorithm for the set cover problem

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this