Using the Averaged Hausdorff Distance as a Performance Measure in Evolutionary Multiobjective Optimization

Abstract

The Hausdorff distance dHis a widely used tool to measure the distance between different objects in several research fields. Possible reasons for this might be that it is a natural extension of the well-known and intuitive distance between points and/or the fact that dHdefines in certain cases a metric in the mathematical sense. In evolutionary multiobjective optimization (EMO) the task is typically to compute the entire solution set-the so-called Pareto set-respectively its image, the Pareto front. Hence, dHshould, at least at first sight, be a natural choice to measure the performance of the outcome set in particular since it is related to the terms spread and convergence as used in EMO literature. However, so far, dHdoes not find the general approval in the EMO community. The main reason for this is that dHpenalizes single outliers of the candidate set which does not comply with the use of stochastic search algorithms such as evolutionary strategies. In this paper, we define a new performance indicator, Δp, which can be viewed as an “averaged Hausdorff distance” between the outcome set and the Pareto front and which is composed of (slight modifications of) the well-known indicators generational distance (GD) and inverted generational distance (IGD). We will discuss theoretical properties of Δp(as well as for GD and IGD) such as the metric properties and the compliance with state-of-theart multiobjective evolutionary algorithms (MOEAs), and will further on demonstrate by empirical results the potential of Δpas a new performance indicator for the evaluation of MOEAs.