On the run-time dynamics of a peer-to-peer evolutionary algorithm

J.L.J. Laredo; A.E. Eiben; M. van Steen; J.J. Merelo

doi:10.1007/978-3-540-87700-4_24

On the run-time dynamics of a peer-to-peer evolutionary algorithm

J.L.J. Laredo, A.E. Eiben, M. van Steen, J.J. Merelo

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

7 Citations (Scopus)

Abstract

In this paper we propose an improvement on a fully distributed Peer-to-Peer (P2P) Evolutionary Algorithm (EA) based on autonomous selection. Autonomous selection means that individuals decide on their own state of reproduction and survival without any central control, using instead estimations about the global population state for decision making. The population size varies at run-time as a consequence of such a decentralized reproduction and death of individuals. In order to keep it stable, we propose a self-adjusting mechanism which has been shown successful in three different search landscapes. Key are the estimations about fitness and size of the population as provided by a gossiping algorithm. Such an algorithm requires several rounds to collect the information while the individuals have to wait for synchronization. As an improvement, we propose a completely asynchronous EA which does not need waiting times. The results show that our approach outperforms quantitatively the execution time of the synchronous version.

Original language	English
Title of host publication	Parallel Problem Solving from Nature - PPSN X
Subtitle of host publication	10th International Conference, Dortmund, Germany, September 13-17, 2008. Proceedings
Editors	Günter Rudolph, Thomas Jansen, Nicola Beume, Simon Lucas, Carlo Poloni
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	236-245
Number of pages	10
ISBN (Electronic)	978-3-540-87700-4
ISBN (Print)	978-3-540-87699-1
DOIs	https://doi.org/10.1007/978-3-540-87700-4_24
Publication status	Published - 26 Nov 2008
Externally published	Yes
Event	10th International Conference on Parallel Problem Solving from Nature, PPSN 2008 - Technische Universität Dortmund, Dortmund, Germany Duration: 13 Sep 2008 → 17 Sep 2008 Conference number: 10 http://ls11-www.cs.tu-dortmund.de/ppsn/ppsn10/index.php

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	5199
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th International Conference on Parallel Problem Solving from Nature, PPSN 2008
Abbreviated title	PPSN 2008
Country	Germany
City	Dortmund
Period	13/09/08 → 17/09/08
Internet address	http://ls11-www.cs.tu-dortmund.de/ppsn/ppsn10/index.php

Keywords

Evolutionary algorithm
Tournament selection
Initial population size
Counting algorithm
Idle cycle

Access to Document

10.1007/978-3-540-87700-4_24

Link to publication in Scopus

Fingerprint Dive into the research topics of 'On the run-time dynamics of a peer-to-peer evolutionary algorithm'. Together they form a unique fingerprint.

Cite this

Laredo, J. L. J., Eiben, A. E., van Steen, M., & Merelo, J. J. (2008). On the run-time dynamics of a peer-to-peer evolutionary algorithm. In G. Rudolph, T. Jansen, N. Beume, S. Lucas, & C. Poloni (Eds.), Parallel Problem Solving from Nature - PPSN X: 10th International Conference, Dortmund, Germany, September 13-17, 2008. Proceedings (pp. 236-245). (Lecture Notes in Computer Science; Vol. 5199). Springer. https://doi.org/10.1007/978-3-540-87700-4_24

Laredo, J.L.J. ; Eiben, A.E. ; van Steen, M. ; Merelo, J.J. / On the run-time dynamics of a peer-to-peer evolutionary algorithm. Parallel Problem Solving from Nature - PPSN X: 10th International Conference, Dortmund, Germany, September 13-17, 2008. Proceedings. editor / Günter Rudolph ; Thomas Jansen ; Nicola Beume ; Simon Lucas ; Carlo Poloni. Berlin, Heidelberg : Springer, 2008. pp. 236-245 (Lecture Notes in Computer Science).

@inproceedings{bc592fc1ec7e4f90a4a990554d2441ae,

title = "On the run-time dynamics of a peer-to-peer evolutionary algorithm",

abstract = "In this paper we propose an improvement on a fully distributed Peer-to-Peer (P2P) Evolutionary Algorithm (EA) based on autonomous selection. Autonomous selection means that individuals decide on their own state of reproduction and survival without any central control, using instead estimations about the global population state for decision making. The population size varies at run-time as a consequence of such a decentralized reproduction and death of individuals. In order to keep it stable, we propose a self-adjusting mechanism which has been shown successful in three different search landscapes. Key are the estimations about fitness and size of the population as provided by a gossiping algorithm. Such an algorithm requires several rounds to collect the information while the individuals have to wait for synchronization. As an improvement, we propose a completely asynchronous EA which does not need waiting times. The results show that our approach outperforms quantitatively the execution time of the synchronous version.",

keywords = "Evolutionary algorithm, Tournament selection, Initial population size, Counting algorithm, Idle cycle",

author = "J.L.J. Laredo and A.E. Eiben and {van Steen}, M. and J.J. Merelo",

year = "2008",

month = nov,

day = "26",

doi = "10.1007/978-3-540-87700-4_24",

language = "English",

isbn = "978-3-540-87699-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "236--245",

editor = "G{\"u}nter Rudolph and Thomas Jansen and Nicola Beume and Simon Lucas and Carlo Poloni",

booktitle = "Parallel Problem Solving from Nature - PPSN X",

address = "Netherlands",

note = "10th International Conference on Parallel Problem Solving from Nature, PPSN 2008, PPSN 2008 ; Conference date: 13-09-2008 Through 17-09-2008",

url = "http://ls11-www.cs.tu-dortmund.de/ppsn/ppsn10/index.php",

}

Laredo, JLJ, Eiben, AE, van Steen, M & Merelo, JJ 2008, On the run-time dynamics of a peer-to-peer evolutionary algorithm. in G Rudolph, T Jansen, N Beume, S Lucas & C Poloni (eds), Parallel Problem Solving from Nature - PPSN X: 10th International Conference, Dortmund, Germany, September 13-17, 2008. Proceedings. Lecture Notes in Computer Science, vol. 5199, Springer, Berlin, Heidelberg, pp. 236-245, 10th International Conference on Parallel Problem Solving from Nature, PPSN 2008, Dortmund, Germany, 13/09/08. https://doi.org/10.1007/978-3-540-87700-4_24

On the run-time dynamics of a peer-to-peer evolutionary algorithm. / Laredo, J.L.J.; Eiben, A.E.; van Steen, M.; Merelo, J.J.

Parallel Problem Solving from Nature - PPSN X: 10th International Conference, Dortmund, Germany, September 13-17, 2008. Proceedings. ed. / Günter Rudolph; Thomas Jansen; Nicola Beume; Simon Lucas; Carlo Poloni. Berlin, Heidelberg : Springer, 2008. p. 236-245 (Lecture Notes in Computer Science; Vol. 5199).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - On the run-time dynamics of a peer-to-peer evolutionary algorithm

AU - Laredo, J.L.J.

AU - Eiben, A.E.

AU - van Steen, M.

AU - Merelo, J.J.

N1 - Conference code: 10

PY - 2008/11/26

Y1 - 2008/11/26

N2 - In this paper we propose an improvement on a fully distributed Peer-to-Peer (P2P) Evolutionary Algorithm (EA) based on autonomous selection. Autonomous selection means that individuals decide on their own state of reproduction and survival without any central control, using instead estimations about the global population state for decision making. The population size varies at run-time as a consequence of such a decentralized reproduction and death of individuals. In order to keep it stable, we propose a self-adjusting mechanism which has been shown successful in three different search landscapes. Key are the estimations about fitness and size of the population as provided by a gossiping algorithm. Such an algorithm requires several rounds to collect the information while the individuals have to wait for synchronization. As an improvement, we propose a completely asynchronous EA which does not need waiting times. The results show that our approach outperforms quantitatively the execution time of the synchronous version.

AB - In this paper we propose an improvement on a fully distributed Peer-to-Peer (P2P) Evolutionary Algorithm (EA) based on autonomous selection. Autonomous selection means that individuals decide on their own state of reproduction and survival without any central control, using instead estimations about the global population state for decision making. The population size varies at run-time as a consequence of such a decentralized reproduction and death of individuals. In order to keep it stable, we propose a self-adjusting mechanism which has been shown successful in three different search landscapes. Key are the estimations about fitness and size of the population as provided by a gossiping algorithm. Such an algorithm requires several rounds to collect the information while the individuals have to wait for synchronization. As an improvement, we propose a completely asynchronous EA which does not need waiting times. The results show that our approach outperforms quantitatively the execution time of the synchronous version.

KW - Evolutionary algorithm

KW - Tournament selection

KW - Initial population size

KW - Counting algorithm

KW - Idle cycle

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

U2 - 10.1007/978-3-540-87700-4_24

DO - 10.1007/978-3-540-87700-4_24

M3 - Conference contribution

AN - SCOPUS:56449084500

SN - 978-3-540-87699-1

T3 - Lecture Notes in Computer Science

SP - 236

EP - 245

BT - Parallel Problem Solving from Nature - PPSN X

A2 - Rudolph, Günter

A2 - Jansen, Thomas

A2 - Beume, Nicola

A2 - Lucas, Simon

A2 - Poloni, Carlo

PB - Springer

CY - Berlin, Heidelberg

T2 - 10th International Conference on Parallel Problem Solving from Nature, PPSN 2008

Y2 - 13 September 2008 through 17 September 2008

ER -

Laredo JLJ, Eiben AE, van Steen M, Merelo JJ. On the run-time dynamics of a peer-to-peer evolutionary algorithm. In Rudolph G, Jansen T, Beume N, Lucas S, Poloni C, editors, Parallel Problem Solving from Nature - PPSN X: 10th International Conference, Dortmund, Germany, September 13-17, 2008. Proceedings. Berlin, Heidelberg: Springer. 2008. p. 236-245. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-540-87700-4_24