Hypervolume-based multiobjective optimization: Theoretical foundations and practical implications

In recent years, indicator-based evolutionary algorithms, allowing to implicitly incorporate user preferences into the search, have become widely used in practice to solve multiobjective optimization problems. When using this type of methods, the optimization goal changes from optimizing a set of objective functions simultaneously to the single-objective optimization goal of finding a set of mu points that maximizes the underlying indicator. Understanding the difference between these two optimization goals is fundamental when applying indicator-based algorithms in practice. On the one hand, a characterization of the inherent optimization goal of different indicators allows the user to choose the indicator that meets her preferences. On the other hand, knowledge about the sets of mu points with optimal indicator values - the so-called optimal mu-distributions-can be used in performance assessment whenever the indicator is used as a performance criterion. However, theoretical studies on indicator-based optimization are sparse. One of the most popular indicators is the weighted hypervolume indicator. It allows to guide the search towards user-defined objective space regions and at the same time has the property of being a refinement of the Pareto dominance relation with the result that maximizing the indicator results in Pareto-optimal solutions only. In previous work, we theoretically investigated the unweighted hypervolume indicator in terms of a characterization of optimal mu-distributions and the influence of the hypervolume's reference point for general bi-objective optimization problems. In this paper, we generalize those results to the case of the weighted hypervolume indicator. In particular, we present general investigations for finite mu, derive a limit result for mu going to infinity in terms of a density of points and derive lower bounds (possibly infinite) for placing the reference point to guarantee the Pareto front's extreme points in an optimal mu-distribution. Furthermore, we state conditions about the slope of the front at the extremes such that there is no finite reference point that allows to include the extremes in an optimal mu-distribution-contradicting previous belief that a reference point chosen just above the nadir point or the objective space boundary is sufficient for obtaining the extremes. However, for fronts where there exists a finite reference point allowing to obtain the extremes, we show that for mu to infinity, a reference point that is slightly worse in all objectives than the nadir point is a sufficient choice. Last, we apply the theoretical results to problems of the ZDT, DTLZ, and WFG test problem suites. (C) 2011 Elsevier B.V. All rights reserved.