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 | |
| 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 |
Fingerprint
Keywords
- Evolutionary algorithm
- Tournament selection
- Initial population size
- Counting algorithm
- Idle cycle
Cite this
}
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.
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
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
ER -