Combining Simple and Adaptive Monte Carlo Methods for Approximating Hypervolume

Jingda Deng; Qingfu Zhang

doi:10.1109/TEVC.2020.2969965

Combining Simple and Adaptive Monte Carlo Methods for Approximating Hypervolume

Jingda Deng^*, Qingfu Zhang

^*Corresponding author for this work

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

21 Citations (Scopus)

Abstract

The computation of hypervolume is a key issue in multiobjective optimization, particularly, multiobjective evolutionary optimization. However, it is NP-hard to compute the exact hypervolume value. Monte Carlo methods have been widely used for approximating the hypervolume. Observing that the basic Monte Carlo method and the fully polynomial-time randomized approximation scheme (FPRAS) suit different solution sets, we propose a combination of these two methods and show that it performs very well on a number of solution sets.

Original language	English
Pages (from-to)	896-907
Number of pages	12
Journal	IEEE Transactions on Evolutionary Computation
Volume	24
Issue number	5
Online published	28 Jan 2020
DOIs	https://doi.org/10.1109/TEVC.2020.2969965
Publication status	Published - Oct 2020

Research Keywords

Approximation algorithms.
Hypervolume
Multiobjective optimization

Access Output

10.1109/TEVC.2020.2969965

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{371c52b47dbc4c36b8627c6504662a70,

title = "Combining Simple and Adaptive Monte Carlo Methods for Approximating Hypervolume",

abstract = "The computation of hypervolume is a key issue in multiobjective optimization, particularly, multiobjective evolutionary optimization. However, it is NP-hard to compute the exact hypervolume value. Monte Carlo methods have been widely used for approximating the hypervolume. Observing that the basic Monte Carlo method and the fully polynomial-time randomized approximation scheme (FPRAS) suit different solution sets, we propose a combination of these two methods and show that it performs very well on a number of solution sets.",

keywords = "Approximation algorithms., Hypervolume, Multiobjective optimization",

author = "Jingda Deng and Qingfu Zhang",

year = "2020",

month = oct,

doi = "10.1109/TEVC.2020.2969965",

language = "English",

volume = "24",

pages = "896--907",

journal = "IEEE Transactions on Evolutionary Computation",

issn = "1089-778X",

publisher = "IEEE",

number = "5",

}

TY - JOUR

T1 - Combining Simple and Adaptive Monte Carlo Methods for Approximating Hypervolume

AU - Deng, Jingda

AU - Zhang, Qingfu

PY - 2020/10

Y1 - 2020/10

N2 - The computation of hypervolume is a key issue in multiobjective optimization, particularly, multiobjective evolutionary optimization. However, it is NP-hard to compute the exact hypervolume value. Monte Carlo methods have been widely used for approximating the hypervolume. Observing that the basic Monte Carlo method and the fully polynomial-time randomized approximation scheme (FPRAS) suit different solution sets, we propose a combination of these two methods and show that it performs very well on a number of solution sets.

AB - The computation of hypervolume is a key issue in multiobjective optimization, particularly, multiobjective evolutionary optimization. However, it is NP-hard to compute the exact hypervolume value. Monte Carlo methods have been widely used for approximating the hypervolume. Observing that the basic Monte Carlo method and the fully polynomial-time randomized approximation scheme (FPRAS) suit different solution sets, we propose a combination of these two methods and show that it performs very well on a number of solution sets.

KW - Approximation algorithms.

KW - Hypervolume

KW - Multiobjective optimization

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

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85079446169&origin=recordpage

U2 - 10.1109/TEVC.2020.2969965

DO - 10.1109/TEVC.2020.2969965

M3 - RGC 21 - Publication in refereed journal

SN - 1089-778X

VL - 24

SP - 896

EP - 907

JO - IEEE Transactions on Evolutionary Computation

JF - IEEE Transactions on Evolutionary Computation

IS - 5

ER -

Combining Simple and Adaptive Monte Carlo Methods for Approximating Hypervolume

Abstract

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

ANR: Big Multi-objective Optimization

Cite this

Combining Simple and Adaptive Monte Carlo Methods for Approximating Hypervolume

Abstract

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Projects

ANR: Big Multi-objective Optimization

Cite this