A comparative study of three GPU-based metaheuristics

Youssef S.G. Nashed; Pablo Mesejo; Roberto Ugolotti; Jérémie Dubois-Lacoste; Stefano Cagnoni

doi:10.1007/978-3-642-32964-7_40

A comparative study of three GPU-based metaheuristics

Youssef S.G. Nashed^*, Pablo Mesejo, Roberto Ugolotti, Jérémie Dubois-Lacoste, Stefano Cagnoni

^*Corresponding author for this work

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 Scopus citations

Abstract

In this paper we compare GPU-based implementations of three metaheuristics: Particle Swarm Optimization, Differential Evolution, and Scatter Search. A GPU-based implementation, obviously, does not change the general properties of the algorithms. As well, we give for granted that GPU-based implementation of both algorithm and fitness function produces a significant speed-up with respect to a sequential implementation. Accordingly, the main goal of this work has been to fairly assess the efficiency of the GPU-based implementations of the three metaheuristics, based on the statistical analysis of the results they obtain in optimizing a benchmark of twenty functions within a prefixed limited time.

Original language	English (US)
Title of host publication	Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings
Pages	398-407
Number of pages	10
Edition	PART 2
DOIs	https://doi.org/10.1007/978-3-642-32964-7_40
State	Published - 2012
Event	12th International Conference on Parallel Problem Solving from Nature, PPSN 2012 - Taormina, Italy Duration: Sep 1 2012 → Sep 5 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 2
Volume	7492 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	12th International Conference on Parallel Problem Solving from Nature, PPSN 2012
Country	Italy
City	Taormina
Period	9/1/12 → 9/5/12

Keywords

Differential Evolution
GPGPU
Global Continuous Optimization
Particle Swarm Optimization
Scatter Search

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-32964-7_40

Fingerprint Dive into the research topics of 'A comparative study of three GPU-based metaheuristics'. Together they form a unique fingerprint.

Cite this

Nashed, Y. S. G., Mesejo, P., Ugolotti, R., Dubois-Lacoste, J., & Cagnoni, S. (2012). A comparative study of three GPU-based metaheuristics. In Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings (PART 2 ed., pp. 398-407). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7492 LNCS, No. PART 2). https://doi.org/10.1007/978-3-642-32964-7_40

Nashed, Youssef S.G. ; Mesejo, Pablo ; Ugolotti, Roberto ; Dubois-Lacoste, Jérémie ; Cagnoni, Stefano. / A comparative study of three GPU-based metaheuristics. Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings. PART 2. ed. 2012. pp. 398-407 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2).

@inproceedings{389969fb4feb49218f140c8580be33d4,

title = "A comparative study of three GPU-based metaheuristics",

abstract = "In this paper we compare GPU-based implementations of three metaheuristics: Particle Swarm Optimization, Differential Evolution, and Scatter Search. A GPU-based implementation, obviously, does not change the general properties of the algorithms. As well, we give for granted that GPU-based implementation of both algorithm and fitness function produces a significant speed-up with respect to a sequential implementation. Accordingly, the main goal of this work has been to fairly assess the efficiency of the GPU-based implementations of the three metaheuristics, based on the statistical analysis of the results they obtain in optimizing a benchmark of twenty functions within a prefixed limited time.",

keywords = "Differential Evolution, GPGPU, Global Continuous Optimization, Particle Swarm Optimization, Scatter Search",

author = "Nashed, {Youssef S.G.} and Pablo Mesejo and Roberto Ugolotti and J{\'e}r{\'e}mie Dubois-Lacoste and Stefano Cagnoni",

year = "2012",

doi = "10.1007/978-3-642-32964-7_40",

language = "English (US)",

isbn = "9783642329630",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 2",

pages = "398--407",

booktitle = "Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings",

edition = "PART 2",

note = "12th International Conference on Parallel Problem Solving from Nature, PPSN 2012 ; Conference date: 01-09-2012 Through 05-09-2012",

}

Nashed, YSG, Mesejo, P, Ugolotti, R, Dubois-Lacoste, J & Cagnoni, S 2012, A comparative study of three GPU-based metaheuristics. in Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings. PART 2 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 2, vol. 7492 LNCS, pp. 398-407, 12th International Conference on Parallel Problem Solving from Nature, PPSN 2012, Taormina, Italy, 9/1/12. https://doi.org/10.1007/978-3-642-32964-7_40

A comparative study of three GPU-based metaheuristics. / Nashed, Youssef S.G.; Mesejo, Pablo; Ugolotti, Roberto; Dubois-Lacoste, Jérémie; Cagnoni, Stefano.

Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings. PART 2. ed. 2012. p. 398-407 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7492 LNCS, No. PART 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A comparative study of three GPU-based metaheuristics

AU - Nashed, Youssef S.G.

AU - Mesejo, Pablo

AU - Ugolotti, Roberto

AU - Dubois-Lacoste, Jérémie

AU - Cagnoni, Stefano

PY - 2012

Y1 - 2012

N2 - In this paper we compare GPU-based implementations of three metaheuristics: Particle Swarm Optimization, Differential Evolution, and Scatter Search. A GPU-based implementation, obviously, does not change the general properties of the algorithms. As well, we give for granted that GPU-based implementation of both algorithm and fitness function produces a significant speed-up with respect to a sequential implementation. Accordingly, the main goal of this work has been to fairly assess the efficiency of the GPU-based implementations of the three metaheuristics, based on the statistical analysis of the results they obtain in optimizing a benchmark of twenty functions within a prefixed limited time.

AB - In this paper we compare GPU-based implementations of three metaheuristics: Particle Swarm Optimization, Differential Evolution, and Scatter Search. A GPU-based implementation, obviously, does not change the general properties of the algorithms. As well, we give for granted that GPU-based implementation of both algorithm and fitness function produces a significant speed-up with respect to a sequential implementation. Accordingly, the main goal of this work has been to fairly assess the efficiency of the GPU-based implementations of the three metaheuristics, based on the statistical analysis of the results they obtain in optimizing a benchmark of twenty functions within a prefixed limited time.

KW - Differential Evolution

KW - GPGPU

KW - Global Continuous Optimization

KW - Particle Swarm Optimization

KW - Scatter Search

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

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

U2 - 10.1007/978-3-642-32964-7_40

DO - 10.1007/978-3-642-32964-7_40

M3 - Conference contribution

AN - SCOPUS:84866378206

SN - 9783642329630

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 398

EP - 407

BT - Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings

T2 - 12th International Conference on Parallel Problem Solving from Nature, PPSN 2012

Y2 - 1 September 2012 through 5 September 2012

ER -

Nashed YSG, Mesejo P, Ugolotti R, Dubois-Lacoste J, Cagnoni S. A comparative study of three GPU-based metaheuristics. In Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings. PART 2 ed. 2012. p. 398-407. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2). https://doi.org/10.1007/978-3-642-32964-7_40