Parallel multi-objective evolutionary algorithms on graphics processing units

Man Leung WONG

doi:10.1145/1570256.1570354

Parallel multi-objective evolutionary algorithms on graphics processing units

Lingnan University

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Research › peer-review

53 Citations (Scopus)

Abstract

Most real-life optimization problems or decision-making problems are multi-objective in nature, since they normally have several (possibly conflicting) objectives that must be satisfied at the same time. Multi-Objective Evolutionary Algorithms (MOEAs) have been gaining increasing attention among researchers and practitioners. However, they may execute for a long time for some difficult problems, because several evaluations must be performed. Moreover, the non-dominance checking and the non-dominated selection procedures are also very time consuming. From our experiments, more than 99% of the execution time is used in performing the two procedures. A promising approach to overcome this limitation is to parallelize these algorithms. In this paper, we propose a parallel MOEA on consumer-level Graphics Processing Units (GPU). We perform many experiments on two-objective and three-objective benchmark problems to compare our parallel MOEA with a sequential MOEA and demonstrate that the former is much more efficient than the latter.

Original language	English
Title of host publication	Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference Late Breaking Papers
Editors	Franz ROTHLAUF
Publisher	Association for Computing Machinery (ACM)
Pages	2515-2522
Number of pages	8
ISBN (Print)	9781605585055, 9781605583259
DOIs	https://doi.org/10.1145/1570256.1570354
Publication status	Published - Jul 2009
Event	11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009 - Montreal, QC, Canada Duration: 8 Jul 2009 → 12 Jul 2009

Publication series

Name	Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009
Volume	2009-January

Conference

Conference	11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009
Abbreviated title	GECCO09
Country/Territory	Canada
City	Montreal, QC
Period	8/07/09 → 12/07/09
Other	Association for Computing Machinery

Bibliographical note

Funding Information:
This work is supported by the Lingnan University Direct Grant DR08B2.

Publisher Copyright:
© 2009 ACM.

Keywords

Graphic Process- ing Units
Multi-Objective Evolutionary Algorithms
Parallel Programming

Access to Document

10.1145/1570256.1570354

http://portal.acm.org/citation.cfm?doid=1570256.1570354

Cite this

WONG, M. L. (2009). Parallel multi-objective evolutionary algorithms on graphics processing units. In F. ROTHLAUF (Ed.), Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference Late Breaking Papers (pp. 2515-2522). (Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009; Vol. 2009-January). Association for Computing Machinery (ACM). https://doi.org/10.1145/1570256.1570354

WONG, Man Leung. / Parallel multi-objective evolutionary algorithms on graphics processing units. Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference Late Breaking Papers. editor / Franz ROTHLAUF. Association for Computing Machinery (ACM), 2009. pp. 2515-2522 (Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009).

@inproceedings{ac506e4fbece41fe91702d41a5fac012,

title = "Parallel multi-objective evolutionary algorithms on graphics processing units",

abstract = "Most real-life optimization problems or decision-making problems are multi-objective in nature, since they normally have several (possibly conflicting) objectives that must be satisfied at the same time. Multi-Objective Evolutionary Algorithms (MOEAs) have been gaining increasing attention among researchers and practitioners. However, they may execute for a long time for some difficult problems, because several evaluations must be performed. Moreover, the non-dominance checking and the non-dominated selection procedures are also very time consuming. From our experiments, more than 99% of the execution time is used in performing the two procedures. A promising approach to overcome this limitation is to parallelize these algorithms. In this paper, we propose a parallel MOEA on consumer-level Graphics Processing Units (GPU). We perform many experiments on two-objective and three-objective benchmark problems to compare our parallel MOEA with a sequential MOEA and demonstrate that the former is much more efficient than the latter.",

keywords = "Graphic Process- ing Units, Multi-Objective Evolutionary Algorithms, Parallel Programming",

author = "WONG, {Man Leung}",

note = "Funding Information: This work is supported by the Lingnan University Direct Grant DR08B2. Publisher Copyright: {\textcopyright} 2009 ACM.; 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009, GECCO09 ; Conference date: 08-07-2009 Through 12-07-2009",

year = "2009",

month = jul,

doi = "10.1145/1570256.1570354",

language = "English",

isbn = "9781605585055",

series = "Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009",

publisher = "Association for Computing Machinery (ACM)",

pages = "2515--2522",

editor = "Franz ROTHLAUF",

booktitle = "Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference Late Breaking Papers",

address = "United States",

}

WONG, ML 2009, Parallel multi-objective evolutionary algorithms on graphics processing units. in F ROTHLAUF (ed.), Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference Late Breaking Papers. Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009, vol. 2009-January, Association for Computing Machinery (ACM), pp. 2515-2522, 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009, Montreal, QC, Canada, 8/07/09. https://doi.org/10.1145/1570256.1570354

Parallel multi-objective evolutionary algorithms on graphics processing units. / WONG, Man Leung.
Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference Late Breaking Papers. ed. / Franz ROTHLAUF. Association for Computing Machinery (ACM), 2009. p. 2515-2522 (Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009; Vol. 2009-January).

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Research › peer-review

TY - GEN

T1 - Parallel multi-objective evolutionary algorithms on graphics processing units

AU - WONG, Man Leung

PY - 2009/7

Y1 - 2009/7

N2 - Most real-life optimization problems or decision-making problems are multi-objective in nature, since they normally have several (possibly conflicting) objectives that must be satisfied at the same time. Multi-Objective Evolutionary Algorithms (MOEAs) have been gaining increasing attention among researchers and practitioners. However, they may execute for a long time for some difficult problems, because several evaluations must be performed. Moreover, the non-dominance checking and the non-dominated selection procedures are also very time consuming. From our experiments, more than 99% of the execution time is used in performing the two procedures. A promising approach to overcome this limitation is to parallelize these algorithms. In this paper, we propose a parallel MOEA on consumer-level Graphics Processing Units (GPU). We perform many experiments on two-objective and three-objective benchmark problems to compare our parallel MOEA with a sequential MOEA and demonstrate that the former is much more efficient than the latter.

AB - Most real-life optimization problems or decision-making problems are multi-objective in nature, since they normally have several (possibly conflicting) objectives that must be satisfied at the same time. Multi-Objective Evolutionary Algorithms (MOEAs) have been gaining increasing attention among researchers and practitioners. However, they may execute for a long time for some difficult problems, because several evaluations must be performed. Moreover, the non-dominance checking and the non-dominated selection procedures are also very time consuming. From our experiments, more than 99% of the execution time is used in performing the two procedures. A promising approach to overcome this limitation is to parallelize these algorithms. In this paper, we propose a parallel MOEA on consumer-level Graphics Processing Units (GPU). We perform many experiments on two-objective and three-objective benchmark problems to compare our parallel MOEA with a sequential MOEA and demonstrate that the former is much more efficient than the latter.

KW - Graphic Process- ing Units

KW - Multi-Objective Evolutionary Algorithms

KW - Parallel Programming

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

U2 - 10.1145/1570256.1570354

DO - 10.1145/1570256.1570354

M3 - Conference paper (refereed)

SN - 9781605585055

SN - 9781605583259

T3 - Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009

SP - 2515

EP - 2522

BT - Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference Late Breaking Papers

A2 - ROTHLAUF, Franz

PB - Association for Computing Machinery (ACM)

T2 - 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009

Y2 - 8 July 2009 through 12 July 2009

ER -

WONG ML. Parallel multi-objective evolutionary algorithms on graphics processing units. In ROTHLAUF F, editor, Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference Late Breaking Papers. Association for Computing Machinery (ACM). 2009. p. 2515-2522. (Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009). doi: 10.1145/1570256.1570354

Parallel multi-objective evolutionary algorithms on graphics processing units

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this