Fast hypervolume approximation scheme based on a segmentation strategy

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

6 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)320-342
Journal / PublicationInformation Sciences
Volume509
Online published27 Feb 2019
Publication statusPublished - Jan 2020

Abstract

Hypervolume indicator based evolutionary algorithms have been reported to be very promising in many-objective optimization, but the high computational complexity of hypervolume calculation in high dimensions restrains its further applications and developments. In this paper, we develop a fast hypervolume approximation method with both improved speed and accuracy than the previous approximation methods via a new segmentation strategy. The proposed approach consists of two crucial process: segmentation and approximation. The segmentation process recursively finds areas easy to be measured and quantified from the original geometric figure as many as possible, and then divides the measurement of the rest areas into several subproblems. In the approximation process, an improved Monte Carlo simulation is developed to estimate these subproblems. Those two processes are mutually complementary to simultaneously improve the accuracy and the speed of hypervolume approximation. To validate its effectiveness, experimental studies on four widely-used instances are conducted and the simulation results show that the proposed method is ten times faster than other comparison algorithms with a same measurement error. Furthermore, we integrate an incremental version of this method into the framework of SMS-EMOA, and the performance of the integrated algorithm is also very competitive among the experimental algorithms.

Research Area(s)

  • Evolutionary algorithm, Hypervolume, Many-objective, Monte carlo simulation

Citation Format(s)

Fast hypervolume approximation scheme based on a segmentation strategy. / Tang, Weisen; Liu, Hai-Lin; Chen, Lei; Tan, Kay Chen; Cheung, Yiu-ming.

In: Information Sciences, Vol. 509, 01.2020, p. 320-342.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review