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

doi:10.1007/978-3-540-85451-7_66

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 proceeding › Conference contribution › Academic › peer-review

18 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 language	English
Title of host publication	Euro-Par 2008 – Parallel Processing
Subtitle of host publication	14th International Euro-Par Conference, Las Palmas de Gran Canaria, Spain, August 26-29, 2008. Proceedings
Editors	Emilio Luque, Tomàs Margalef, Domingo Benítez
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	622-631
Number of pages	10
ISBN (Electronic)	978-3-540-85451-7
ISBN (Print)	978-3-540-85450-0
DOIs	https://doi.org/10.1007/978-3-540-85451-7_66
Publication status	Published - 22 Sept 2008
Externally published	Yes
Event	14th International Euro-Par Conferenceon Parallel Processing, Euro-Par 2008 - Las Palmas de Gran Canaria, Spain Duration: 26 Aug 2008 → 29 Aug 2008 Conference number: 14

Publication series

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

Conference

Conference	14th International Euro-Par Conferenceon Parallel Processing, Euro-Par 2008
Abbreviated title	Euro-Par
Country/Territory	Spain
City	Las Palmas de Gran Canaria
Period	26/08/08 → 29/08/08

Keywords

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

Access to Document

10.1007/978-3-540-85451-7_66

Cite this

Laredo, J. L. J., Eiben, A. E., van Steen, M., Castillo, P. A., Mora, A. M., & Merelo, J. J. (2008). P2P evolutionary algorithms: A suitable approach for tackling large instances in hard optimization problems. In E. Luque, T. Margalef, & D. Benítez (Eds.), Euro-Par 2008 – Parallel Processing: 14th International Euro-Par Conference, Las Palmas de Gran Canaria, Spain, August 26-29, 2008. Proceedings (pp. 622-631). (Lecture Notes in Computer Science; Vol. 5168). Springer. https://doi.org/10.1007/978-3-540-85451-7_66

Laredo, J.L.J. ; Eiben, A.E. ; van Steen, M. et al. / P2P evolutionary algorithms : A suitable approach for tackling large instances in hard optimization problems. Euro-Par 2008 – Parallel Processing: 14th International Euro-Par Conference, Las Palmas de Gran Canaria, Spain, August 26-29, 2008. Proceedings. editor / Emilio Luque ; Tomàs Margalef ; Domingo Benítez. Berlin, Heidelberg : Springer, 2008. pp. 622-631 (Lecture Notes in Computer Science).

@inproceedings{bc1dbcb5c01d4332ac0a4be0c1fd9389,

title = "P2P evolutionary algorithms: A suitable approach for tackling large instances in hard optimization problems",

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.",

keywords = "Evolutionary algorithm, Large instance, Cache size, Discrete optimization problem, Large problem instance",

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

year = "2008",

month = sep,

day = "22",

doi = "10.1007/978-3-540-85451-7_66",

language = "English",

isbn = "978-3-540-85450-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "622--631",

editor = "Emilio Luque and Tom{\`a}s Margalef and Domingo Ben{\'i}tez",

booktitle = "Euro-Par 2008 – Parallel Processing",

note = "14th International Euro-Par Conferenceon Parallel Processing, Euro-Par 2008, Euro-Par ; Conference date: 26-08-2008 Through 29-08-2008",

}

Laredo, JLJ, Eiben, AE, van Steen, M, Castillo, PA, Mora, AM & Merelo, JJ 2008, P2P evolutionary algorithms: A suitable approach for tackling large instances in hard optimization problems. in E Luque, T Margalef & D Benítez (eds), Euro-Par 2008 – Parallel Processing: 14th International Euro-Par Conference, Las Palmas de Gran Canaria, Spain, August 26-29, 2008. Proceedings. Lecture Notes in Computer Science, vol. 5168, Springer, Berlin, Heidelberg, pp. 622-631, 14th International Euro-Par Conferenceon Parallel Processing, Euro-Par 2008, Las Palmas de Gran Canaria, Spain, 26/08/08. https://doi.org/10.1007/978-3-540-85451-7_66

P2P evolutionary algorithms: A suitable approach for tackling large instances in hard optimization problems. / Laredo, J.L.J.; Eiben, A.E.; van Steen, M. et al.
Euro-Par 2008 – Parallel Processing: 14th International Euro-Par Conference, Las Palmas de Gran Canaria, Spain, August 26-29, 2008. Proceedings. ed. / Emilio Luque; Tomàs Margalef; Domingo Benítez. Berlin, Heidelberg: Springer, 2008. p. 622-631 (Lecture Notes in Computer Science; Vol. 5168).

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

TY - GEN

T1 - P2P evolutionary algorithms

T2 - 14th International Euro-Par Conferenceon Parallel Processing, Euro-Par 2008

AU - Laredo, J.L.J.

AU - Eiben, A.E.

AU - van Steen, M.

AU - Castillo, P.A.

AU - Mora, A.M.

AU - Merelo, J.J.

N1 - Conference code: 14

PY - 2008/9/22

Y1 - 2008/9/22

N2 - 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.

AB - 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.

KW - Evolutionary algorithm

KW - Large instance

KW - Cache size

KW - Discrete optimization problem

KW - Large problem instance

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

U2 - 10.1007/978-3-540-85451-7_66

DO - 10.1007/978-3-540-85451-7_66

M3 - Conference contribution

AN - SCOPUS:51849125144

SN - 978-3-540-85450-0

T3 - Lecture Notes in Computer Science

SP - 622

EP - 631

BT - Euro-Par 2008 – Parallel Processing

A2 - Luque, Emilio

A2 - Margalef, Tomàs

A2 - Benítez, Domingo

PB - Springer

CY - Berlin, Heidelberg

Y2 - 26 August 2008 through 29 August 2008

ER -

Laredo JLJ, Eiben AE, van Steen M, Castillo PA, Mora AM, Merelo JJ. P2P evolutionary algorithms: A suitable approach for tackling large instances in hard optimization problems. In Luque E, Margalef T, Benítez D, editors, Euro-Par 2008 – Parallel Processing: 14th International Euro-Par Conference, Las Palmas de Gran Canaria, Spain, August 26-29, 2008. Proceedings. Berlin, Heidelberg: Springer. 2008. p. 622-631. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-85451-7_66

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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this