Implementation of parallel genetic algorithms on graphics processing units

Man Leung WONG, Tien Tsin WONG

Research output: Book Chapters | Papers in Conference ProceedingsBook ChapterResearchpeer-review

29 Citations (Scopus)

Abstract

In this paper, we propose to parallelize a Hybrid Genetic Algorithm (HGA) on Graphics Processing Units (GPUs) which are available and installed on ubiquitous personal computers. HGA extends the classical genetic algorithm by incorporating the Cauchy mutation operator from evolutionary programming. In our parallel HGA, all steps except the random number generation procedure are performed in GPU and thus our parallel HGA can be executed effectively and efficiently. We suggest and develop the novel pseudo-deterministic selection method which is comparable to the traditional global selection approach with significant execution time performance advantages.We perform experiments to compare our parallel HGA with our previous parallel FEP (Fast Evolutionary programming) and demonstrate that the former is much more effective and efficient than the latter. The parallel and sequential implementations of HGA are compared in a number of experiments, it is observed that the former outperforms the latter significantly. The effectiveness and efficiency of the pseudo-deterministic selection method is also studied.
Original languageEnglish
Title of host publicationIntelligent and Evolutionary Systems
PublisherSpringer-Verlag GmbH and Co. KG
Pages197-216
Number of pages20
ISBN (Print)9783540959779
DOIs
Publication statusPublished - 1 Jan 2009

Fingerprint

Parallel algorithms
Genetic algorithms
Evolutionary algorithms
Random number generation
Graphics processing unit
Personal computers
Mathematical operators
Experiments

Cite this

WONG, M. L., & WONG, T. T. (2009). Implementation of parallel genetic algorithms on graphics processing units. In Intelligent and Evolutionary Systems (pp. 197-216). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-540-95978-6_14
WONG, Man Leung ; WONG, Tien Tsin. / Implementation of parallel genetic algorithms on graphics processing units. Intelligent and Evolutionary Systems. Springer-Verlag GmbH and Co. KG, 2009. pp. 197-216
@inbook{cdfdbfebcd5f46fb9a37277d1c71e1bb,
title = "Implementation of parallel genetic algorithms on graphics processing units",
abstract = "In this paper, we propose to parallelize a Hybrid Genetic Algorithm (HGA) on Graphics Processing Units (GPUs) which are available and installed on ubiquitous personal computers. HGA extends the classical genetic algorithm by incorporating the Cauchy mutation operator from evolutionary programming. In our parallel HGA, all steps except the random number generation procedure are performed in GPU and thus our parallel HGA can be executed effectively and efficiently. We suggest and develop the novel pseudo-deterministic selection method which is comparable to the traditional global selection approach with significant execution time performance advantages.We perform experiments to compare our parallel HGA with our previous parallel FEP (Fast Evolutionary programming) and demonstrate that the former is much more effective and efficient than the latter. The parallel and sequential implementations of HGA are compared in a number of experiments, it is observed that the former outperforms the latter significantly. The effectiveness and efficiency of the pseudo-deterministic selection method is also studied.",
author = "WONG, {Man Leung} and WONG, {Tien Tsin}",
year = "2009",
month = "1",
day = "1",
doi = "10.1007/978-3-540-95978-6_14",
language = "English",
isbn = "9783540959779",
pages = "197--216",
booktitle = "Intelligent and Evolutionary Systems",
publisher = "Springer-Verlag GmbH and Co. KG",
address = "Germany",

}

WONG, ML & WONG, TT 2009, Implementation of parallel genetic algorithms on graphics processing units. in Intelligent and Evolutionary Systems. Springer-Verlag GmbH and Co. KG, pp. 197-216. https://doi.org/10.1007/978-3-540-95978-6_14

Implementation of parallel genetic algorithms on graphics processing units. / WONG, Man Leung; WONG, Tien Tsin.

Intelligent and Evolutionary Systems. Springer-Verlag GmbH and Co. KG, 2009. p. 197-216.

Research output: Book Chapters | Papers in Conference ProceedingsBook ChapterResearchpeer-review

TY - CHAP

T1 - Implementation of parallel genetic algorithms on graphics processing units

AU - WONG, Man Leung

AU - WONG, Tien Tsin

PY - 2009/1/1

Y1 - 2009/1/1

N2 - In this paper, we propose to parallelize a Hybrid Genetic Algorithm (HGA) on Graphics Processing Units (GPUs) which are available and installed on ubiquitous personal computers. HGA extends the classical genetic algorithm by incorporating the Cauchy mutation operator from evolutionary programming. In our parallel HGA, all steps except the random number generation procedure are performed in GPU and thus our parallel HGA can be executed effectively and efficiently. We suggest and develop the novel pseudo-deterministic selection method which is comparable to the traditional global selection approach with significant execution time performance advantages.We perform experiments to compare our parallel HGA with our previous parallel FEP (Fast Evolutionary programming) and demonstrate that the former is much more effective and efficient than the latter. The parallel and sequential implementations of HGA are compared in a number of experiments, it is observed that the former outperforms the latter significantly. The effectiveness and efficiency of the pseudo-deterministic selection method is also studied.

AB - In this paper, we propose to parallelize a Hybrid Genetic Algorithm (HGA) on Graphics Processing Units (GPUs) which are available and installed on ubiquitous personal computers. HGA extends the classical genetic algorithm by incorporating the Cauchy mutation operator from evolutionary programming. In our parallel HGA, all steps except the random number generation procedure are performed in GPU and thus our parallel HGA can be executed effectively and efficiently. We suggest and develop the novel pseudo-deterministic selection method which is comparable to the traditional global selection approach with significant execution time performance advantages.We perform experiments to compare our parallel HGA with our previous parallel FEP (Fast Evolutionary programming) and demonstrate that the former is much more effective and efficient than the latter. The parallel and sequential implementations of HGA are compared in a number of experiments, it is observed that the former outperforms the latter significantly. The effectiveness and efficiency of the pseudo-deterministic selection method is also studied.

UR - http://commons.ln.edu.hk/sw_master/4093

U2 - 10.1007/978-3-540-95978-6_14

DO - 10.1007/978-3-540-95978-6_14

M3 - Book Chapter

SN - 9783540959779

SP - 197

EP - 216

BT - Intelligent and Evolutionary Systems

PB - Springer-Verlag GmbH and Co. KG

ER -

WONG ML, WONG TT. Implementation of parallel genetic algorithms on graphics processing units. In Intelligent and Evolutionary Systems. Springer-Verlag GmbH and Co. KG. 2009. p. 197-216 https://doi.org/10.1007/978-3-540-95978-6_14