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

摘要

The Hausdorff distance $d_{H}$ is 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 $d_{H}$ defines 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, $d_{H}$ should, 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, $d_{H}$ does not find the general approval in the EMO community. The main reason for this is that $d_{H}$ penalizes 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, $Delta_{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 $Delta_{p}$ (as well as for GD and IGD) such as the metric properties and the compliance with state-of-the-art multiobjective evolutionary algorith- s (MOEAs), and will further on demonstrate by empirical results the potential of $Delta_{p}$ as a new performance indicator for the evaluation of MOEAs.