P2P evolutionary algorithms: A suitable approach for tackling large instances in hard optimization problems

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

17 Citations (Scopus)

Abstract

In this paper we present a distributed Evolutionary Algorithm (EA) whose population is structured using newscast, a gossiping protocol. This algorithm has been designed to deal with computationally expensive problems via massive scalability; therefore, we analyse the response time of the model using large instances of well-known hard optimization problems that require from EAs a (sometimes exponentially) bigger computational effort as these problems scale. Our approach has been matched against a sequential Genetic Algorithm (sGA) applied to the same set of problems, and we found that it needs less computational effort than the sGA in yielding success. Furthermore, the response time scales logarithmically with respect to the problem size, which makes it suitable to tackle large instances.

Original languageEnglish
Title of host publicationEuro-Par 2008 – Parallel Processing
Subtitle of host publication14th International Euro-Par Conference, Las Palmas de Gran Canaria, Spain, August 26-29, 2008. Proceedings
EditorsEmilio Luque, Tomàs Margalef, Domingo Benítez
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages622-631
Number of pages10
ISBN (Electronic)978-3-540-85451-7
ISBN (Print)978-3-540-85450-0
DOIs
Publication statusPublished - 22 Sep 2008
Externally publishedYes
Event14th International Euro-Par Conferenceon Parallel Processing, Euro-Par 2008 - Las Palmas de Gran Canaria, Spain
Duration: 26 Aug 200829 Aug 2008
Conference number: 14

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume5168
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Euro-Par Conferenceon Parallel Processing, Euro-Par 2008
Abbreviated titleEuro-Par
CountrySpain
CityLas Palmas de Gran Canaria
Period26/08/0829/08/08

Keywords

  • Evolutionary algorithm
  • Large instance
  • Cache size
  • Discrete optimization problem
  • Large problem instance

Fingerprint Dive into the research topics of 'P2P evolutionary algorithms: A suitable approach for tackling large instances in hard optimization problems'. Together they form a unique fingerprint.

Cite this