1. Fast hypervolume approximation scheme based on a segmentation strategy.
- Author
-
Tang, Weisen, Liu, Hai-Lin, Chen, Lei, Tan, Kay Chen, and Cheung, Yiu-ming
- Subjects
- *
APPROXIMATION algorithms , *MEASUREMENT errors , *MONTE Carlo method , *COMPUTER simulation , *COMPUTATIONAL complexity - Abstract
• A fast hypervolume approximation algorithm is proposed that accelerates the hypervolume calculation with a steady accuracy error, through a segmentation strategy and the Monte Carlo simulation. The proposed algorithm achieves ten times faster than other compared algorithms in experiments. • Base on above the fast approximation method, an incremental version algorithm is proposed to solve many objective optimization problem and promotes the performance of hypervolume based algorithms. 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. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF