EvAg: A scalable peer-to-peer evolutionary algorithm

J.L.J. Laredo (Corresponding Author), A.E. Eiben, M. van Steen, J.J. Merelo

Research output: Contribution to journalArticleAcademicpeer-review

42 Citations (Scopus)

Abstract

This paper studies the scalability of an Evolutionary Algorithm (EA) whose population is structured by means of a gossiping protocol and where the evolutionary operators act exclusively within the local neighborhoods. This makes the algorithm inherently suited for parallel execution in a peer-to-peer fashion which, in turn, offers great advantages when dealing with computationally expensive problems because distributed execution implies massive scalability. In this paper we show another advantage of this algorithm: We experimentally demonstrate that it scales up better than traditional alternatives even when executed in a sequential fashion. In particular, we analyze the behavior of several EAs on well-known deceptive trap functions with varying sizes and levels of deceptiveness. The results show that the new EA requires smaller optimal population sizes and fewer fitness evaluations to reach solutions. The relative advantage of the new EA is more outstanding as problem hardness and size increase. In some cases the new algorithm reduces the computational efforts of the traditional EAs by several orders of magnitude.

Original languageEnglish
Pages (from-to)227-246
Number of pages20
JournalGenetic Programming and Evolvable Machines
Volume11
Issue number2
DOIs
Publication statusPublished - 1 Jun 2010
Externally publishedYes

Keywords

  • Diversity
  • Evolutionary algorithms
  • Peer-to-peer computing
  • Scalability analysis

Fingerprint Dive into the research topics of 'EvAg: A scalable peer-to-peer evolutionary algorithm'. Together they form a unique fingerprint.

Cite this