A GPU-Based Algorithm for a Faster Hypervolume Contribution Computation View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2015-03-18

AUTHORS

Edgar Manoatl Lopez , Luis Miguel Antonio , Carlos A. Coello Coello

ABSTRACT

The hypervolume has become very popular in current multi-objective 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {S}$$\end{document}-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. More... »

PAGES

80-94

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-15892-1_6

DOI

http://dx.doi.org/10.1007/978-3-319-15892-1_6

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1039579840


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Departamento de Computaci\u00f3n, CINVESTAV-IPN (Evolutionary Computation Group), 07300, Mexico D.F., Mexico", 
          "id": "http://www.grid.ac/institutes/grid.418275.d", 
          "name": [
            "Departamento de Computaci\u00f3n, CINVESTAV-IPN (Evolutionary Computation Group), 07300, Mexico D.F., Mexico"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lopez", 
        "givenName": "Edgar Manoatl", 
        "id": "sg:person.014266672624.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014266672624.05"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Departamento de Computaci\u00f3n, CINVESTAV-IPN (Evolutionary Computation Group), 07300, Mexico D.F., Mexico", 
          "id": "http://www.grid.ac/institutes/grid.418275.d", 
          "name": [
            "Departamento de Computaci\u00f3n, CINVESTAV-IPN (Evolutionary Computation Group), 07300, Mexico D.F., Mexico"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Antonio", 
        "givenName": "Luis Miguel", 
        "id": "sg:person.015676004474.68", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015676004474.68"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Departamento de Computaci\u00f3n, CINVESTAV-IPN (Evolutionary Computation Group), 07300, Mexico D.F., Mexico", 
          "id": "http://www.grid.ac/institutes/grid.418275.d", 
          "name": [
            "Departamento de Computaci\u00f3n, CINVESTAV-IPN (Evolutionary Computation Group), 07300, Mexico D.F., Mexico"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Coello Coello", 
        "givenName": "Carlos A.", 
        "id": "sg:person.01345625161.61", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01345625161.61"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015-03-18", 
    "datePublishedReg": "2015-03-18", 
    "description": "The hypervolume has become very popular in current multi-objective 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 \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\mathcal {S}$$\\end{document}-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\u00a0to 883x) with respect to its sequential counterpart, which allows us to use SMS-EMOA with exact hypervolume calculations, in problems having up\u00a0to 9 objective functions.", 
    "editor": [
      {
        "familyName": "Gaspar-Cunha", 
        "givenName": "Ant\u00f3nio", 
        "type": "Person"
      }, 
      {
        "familyName": "Henggeler Antunes", 
        "givenName": "Carlos", 
        "type": "Person"
      }, 
      {
        "familyName": "Coello", 
        "givenName": "Carlos Coello", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-15892-1_6", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-15891-4", 
        "978-3-319-15892-1"
      ], 
      "name": "Evolutionary Multi-Criterion Optimization", 
      "type": "Book"
    }, 
    "keywords": [
      "graphics processing units", 
      "multi-objective evolutionary algorithm", 
      "evolutionary multi-objective algorithm", 
      "multi-objective algorithm", 
      "multi-objective optimization research", 
      "exact hypervolume calculations", 
      "number of objectives", 
      "SMS-EMOA", 
      "sequential counterpart", 
      "parallel implementation", 
      "processing units", 
      "evolutionary algorithm", 
      "hypervolume calculation", 
      "significant speed", 
      "hypervolume contribution", 
      "exact hypervolume", 
      "algorithm", 
      "hypervolume", 
      "fast way", 
      "selection operator", 
      "desirable features", 
      "objective function", 
      "novel approach", 
      "quality measures", 
      "number of points", 
      "optimization research", 
      "serious drawback", 
      "final results", 
      "compute", 
      "computation", 
      "implementation", 
      "drawbacks", 
      "operators", 
      "performance", 
      "cost", 
      "features", 
      "speed", 
      "point", 
      "number", 
      "way", 
      "results", 
      "research", 
      "objective", 
      "use", 
      "units", 
      "respect", 
      "contribution", 
      "measures", 
      "approach", 
      "function", 
      "problem", 
      "counterparts", 
      "calculations", 
      "paper", 
      "current multi-objective optimization research", 
      "Selection Evolutionary Multi-Objective Algorithm", 
      "Faster Hypervolume Contribution Computation", 
      "Hypervolume Contribution Computation", 
      "Contribution Computation"
    ], 
    "name": "A GPU-Based Algorithm for a Faster Hypervolume Contribution Computation", 
    "pagination": "80-94", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1039579840"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-15892-1_6"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-15892-1_6", 
      "https://app.dimensions.ai/details/publication/pub.1039579840"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:58", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_370.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-15892-1_6"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-15892-1_6'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-15892-1_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-15892-1_6'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-15892-1_6'


 

This table displays all metadata directly associated to this object as RDF triples.

151 TRIPLES      23 PREDICATES      86 URIs      77 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-15892-1_6 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 anzsrc-for:08
4 anzsrc-for:0802
5 schema:author Nfa752f68e33c4a488dcf8c13b3e2f420
6 schema:datePublished 2015-03-18
7 schema:datePublishedReg 2015-03-18
8 schema:description The hypervolume has become very popular in current multi-objective 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {S}$$\end{document}-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.
9 schema:editor Ncc4c47e6b96f4ead80f996d13e20cf19
10 schema:genre chapter
11 schema:inLanguage en
12 schema:isAccessibleForFree false
13 schema:isPartOf Nc4a56e7699c64acda457fc2597eb1bb0
14 schema:keywords Contribution Computation
15 Faster Hypervolume Contribution Computation
16 Hypervolume Contribution Computation
17 SMS-EMOA
18 Selection Evolutionary Multi-Objective Algorithm
19 algorithm
20 approach
21 calculations
22 computation
23 compute
24 contribution
25 cost
26 counterparts
27 current multi-objective optimization research
28 desirable features
29 drawbacks
30 evolutionary algorithm
31 evolutionary multi-objective algorithm
32 exact hypervolume
33 exact hypervolume calculations
34 fast way
35 features
36 final results
37 function
38 graphics processing units
39 hypervolume
40 hypervolume calculation
41 hypervolume contribution
42 implementation
43 measures
44 multi-objective algorithm
45 multi-objective evolutionary algorithm
46 multi-objective optimization research
47 novel approach
48 number
49 number of objectives
50 number of points
51 objective
52 objective function
53 operators
54 optimization research
55 paper
56 parallel implementation
57 performance
58 point
59 problem
60 processing units
61 quality measures
62 research
63 respect
64 results
65 selection operator
66 sequential counterpart
67 serious drawback
68 significant speed
69 speed
70 units
71 use
72 way
73 schema:name A GPU-Based Algorithm for a Faster Hypervolume Contribution Computation
74 schema:pagination 80-94
75 schema:productId N3bd66d44d746458980ecaf0639df06c6
76 N6991cccd8850401ea8e7f50db21986a0
77 schema:publisher N37325373badc41268d52004b4632810e
78 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039579840
79 https://doi.org/10.1007/978-3-319-15892-1_6
80 schema:sdDatePublished 2021-11-01T18:58
81 schema:sdLicense https://scigraph.springernature.com/explorer/license/
82 schema:sdPublisher Nf4078f395c6547358db5146507418a6b
83 schema:url https://doi.org/10.1007/978-3-319-15892-1_6
84 sgo:license sg:explorer/license/
85 sgo:sdDataset chapters
86 rdf:type schema:Chapter
87 N111e998e7ff94d7293d56ea8c0f8dba2 rdf:first Nc3fbfd26fc844b67ba93d4a4157dcc8d
88 rdf:rest N6802d1d2cb6f42a89d1fc9f8c3ac2fd5
89 N28c2a634d18f4c558a5aa989ea42ed18 schema:familyName Gaspar-Cunha
90 schema:givenName António
91 rdf:type schema:Person
92 N37325373badc41268d52004b4632810e schema:name Springer Nature
93 rdf:type schema:Organisation
94 N3bd66d44d746458980ecaf0639df06c6 schema:name doi
95 schema:value 10.1007/978-3-319-15892-1_6
96 rdf:type schema:PropertyValue
97 N6802d1d2cb6f42a89d1fc9f8c3ac2fd5 rdf:first Na5b23272b53d4df7b8dbd6bdb3276641
98 rdf:rest rdf:nil
99 N6991cccd8850401ea8e7f50db21986a0 schema:name dimensions_id
100 schema:value pub.1039579840
101 rdf:type schema:PropertyValue
102 Na5b23272b53d4df7b8dbd6bdb3276641 schema:familyName Coello
103 schema:givenName Carlos Coello
104 rdf:type schema:Person
105 Nc3fbfd26fc844b67ba93d4a4157dcc8d schema:familyName Henggeler Antunes
106 schema:givenName Carlos
107 rdf:type schema:Person
108 Nc4a56e7699c64acda457fc2597eb1bb0 schema:isbn 978-3-319-15891-4
109 978-3-319-15892-1
110 schema:name Evolutionary Multi-Criterion Optimization
111 rdf:type schema:Book
112 Ncc4c47e6b96f4ead80f996d13e20cf19 rdf:first N28c2a634d18f4c558a5aa989ea42ed18
113 rdf:rest N111e998e7ff94d7293d56ea8c0f8dba2
114 Nde8ada2fbc2a4287a1009db7ac9fdb42 rdf:first sg:person.01345625161.61
115 rdf:rest rdf:nil
116 Nf4078f395c6547358db5146507418a6b schema:name Springer Nature - SN SciGraph project
117 rdf:type schema:Organization
118 Nf7672a93b8c140138790834f3d96e124 rdf:first sg:person.015676004474.68
119 rdf:rest Nde8ada2fbc2a4287a1009db7ac9fdb42
120 Nfa752f68e33c4a488dcf8c13b3e2f420 rdf:first sg:person.014266672624.05
121 rdf:rest Nf7672a93b8c140138790834f3d96e124
122 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
123 schema:name Mathematical Sciences
124 rdf:type schema:DefinedTerm
125 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
126 schema:name Numerical and Computational Mathematics
127 rdf:type schema:DefinedTerm
128 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
129 schema:name Information and Computing Sciences
130 rdf:type schema:DefinedTerm
131 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
132 schema:name Computation Theory and Mathematics
133 rdf:type schema:DefinedTerm
134 sg:person.01345625161.61 schema:affiliation grid-institutes:grid.418275.d
135 schema:familyName Coello Coello
136 schema:givenName Carlos A.
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01345625161.61
138 rdf:type schema:Person
139 sg:person.014266672624.05 schema:affiliation grid-institutes:grid.418275.d
140 schema:familyName Lopez
141 schema:givenName Edgar Manoatl
142 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014266672624.05
143 rdf:type schema:Person
144 sg:person.015676004474.68 schema:affiliation grid-institutes:grid.418275.d
145 schema:familyName Antonio
146 schema:givenName Luis Miguel
147 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015676004474.68
148 rdf:type schema:Person
149 grid-institutes:grid.418275.d schema:alternateName Departamento de Computación, CINVESTAV-IPN (Evolutionary Computation Group), 07300, Mexico D.F., Mexico
150 schema:name Departamento de Computación, CINVESTAV-IPN (Evolutionary Computation Group), 07300, Mexico D.F., Mexico
151 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...