Fast hypervolume approximation scheme based on a segmentation strategy

Weisen Tang, Hai Lin Liu*, Lei Chen, Kay Chen Tan, Yiu Ming CHEUNG

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)320-342
Number of pages23
JournalInformation Sciences
Volume509
DOIs
Publication statusPublished - Jan 2020

Scopus Subject Areas

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

User-Defined Keywords

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

Fingerprint

Dive into the research topics of 'Fast hypervolume approximation scheme based on a segmentation strategy'. Together they form a unique fingerprint.

Cite this