Paper Info
Title
A GPU-Based Algorithm for a Faster Hypervolume Contribution Computation.
Abstract
The hypervolume has become very popular in current multiobjective optimization research. Because of its highly desirable features, it has been used not only as a quality measure for comparing final results of multi-objective evolutionary algorithms (MOEAs), but also as a selection operator (it is, for example, very suitable for many-objective optimization problems). However, it has one serious drawback: computing the exact hypervolume is highly costly. The best known algorithms to compute the hypervolume are polynomial in the number of points, but their cost grows exponentially with the number of objectives. This paper proposes a novel approach which, through the use of Graphics Processing Units (GPUs), computes in a faster way the hypervolume contribution of a point. We develop a highly parallel implementation of our approach and demonstrate its performance when using it within the S-Metric Selection Evolutionary Multi-Objective Algorithm (SMS-EMOA). Our results indicate that our proposed approach is able to achieve a significant speed up (of up to 883x) with respect to its sequential counterpart, which allows us to use SMS-EMOA with exact hypervolume calculations, in problems having up to 9 objective functions.
Year
DOI
Venue
2015
10.1007/978-3-319-15892-1_6
Lecture Notes in Computer Science
Field
DocType
Volume
Graphics,Mathematical optimization,Evolutionary algorithm,Polynomial,Computer science,SIMD,Algorithm,Optimization problem,Speedup,Computation,Exponential growth
Conference
9019
ISSN
Citations 
PageRank 
0302-9743
2
0.35
References 
Authors
13
3
Name
Order
Citations
PageRank
Edgar Manoatl Lopez130.70
Luis Miguel Antonio2583.92
Carlos A. Coello Coello3113853.21