Hypervolume by Slicing Objective Algorithm: An Improved Version

The hypervolume remains a popular performance indicator in evolutionary multi-objective, mainly because of its nice mathematical properties (i.e., it’s the only performance indicator known to be Pareto-compliant). However, its high computational cost (which grows polynomially on the population size but exponentially on the number of objectives) has severely limited its use in many-objective optimization. This has motivated a variety of proposals that attempt to overcome this limitation. One of the most popular proposals currently available is the so-called Hypervolume by Slicing Objectives (HSO) algorithm. Here, we show that the worst-case time complexity of the HSO algorithm, as obtained by its authors, is incorrect. Then, we provide an efficient implementation of the HSO algorithm, which guarantees that unique slices are generated to compute the hypervolume.

I. Introduction

In recent years, the solution of multi-objective optimization problems has received an increasing attention from re-searchers, particularly regarding problems with more than three objectives (the so-called many-objective optimization problems) [1]. This has motivated the development of a wide variety of Multi-objective Evolutionary Algorithms (MOEAs) [2]-[4]. As more MOEAs are proposed, performance assessment becomes crucial, which raises the importance for challenging test problems [5] and reliable performance indicators [6], [7]. Some of the most commonly adopted performance measures to assess convergence include the Hypervolume [8]-[10], R2 [11], the Inverted Generational Distance (IGD) [12], the Inverted Generational Distance plus (IGD⁺) [13], the ϵ indicator [14], and ∆_p [15]. The high computational cost of the hypervolume (which is also called the metric [8] and the Lebesgue measure [16]) in high dimensional spaces, has triggered a significant amount of research during the last few years (see for example [17]-[19].