# The Porcupine Measure for Comparing the Performance of Multi-Objective Optimization Algorithms
## 3 Background and Related Work  
[PERSON] and [PERSON] [1] suggested that the non-dominated solutions that make up the approximated POF be used to construct an attainment surface. The attainment surface's envelope is defined as the boundary in the objective space that separates those points that are dominated by, or equal to, at least one of the non-dominated solutions that make up the approximated POF from those points for which no non-dominated solution dominates or equals. Figure 1 depicts an attainment surface and the corresponding approximated POF. The attainment surface envelope is identical to the envelope used during the calculation of the hypervolume metric [2; 3]. In contrast to the hypervolume calculation, in the case of an attainment surface, the envelope is not used directly in the calculation of a performance metric. Instead, the attainment surface can be used to visually compare algorithms' performance by plotting the attainment surfaces for both algorithms. For stochastic algorithms, variations in the performance over multiple runs (also referred to as samples) are expected. [PERSON] and [PERSON] [1] described a procedure to generate an attainment surface that represents a given algorithm's performance over multiple independent runs. The attainment surface for multiple independent runs is computed by first determining the attainment surface for each run's approximated POF. Next, a number of random imaginary lines is chosen, pointing in the direction of improvement for all the objectives. For each line, the points of intersection with each of the lines and the attainment surfaces are calculated. Figure 2a,b depict three attainment surfaces with intersection lines and intersection points. For each line, the intersection points can be seen as a sample distribution that is un-dimensional and can thus be strictly ordered. By calculating the median for each of the sample distributions, the objective vectors that are likely to be attained in exactly 50% of the runs can be identified. The envelope formed by the median points is known as the 50% grand attainment surface. Similar to how the median is used to construct the 50% grand attainment surface, the lower and upper quantiles (25 th and 75 th percentiles) are used to construct the 25% and 75% grand attainment surfaces. Figure 1: Example Pareto-optimal front and attainment surface. (**a**) An approximated Pareto-optimal front. (**b**) Attainment surface. Figure 2: Attainment surfaces. (**a**) Example attainment surfaces with intersection lines. (**b**) Example attainment surfaces with unequally spread intersection lines. (**c**) Grand attainment surface. The sample distribution approach can also be used to compare performance between algorithms. In order to compare two algorithms, two sample distributions--one for each of the algorithms--are calculated per intersection line. Standard non-parametric statistical test procedures can then be used to determine if there is a statistically significant difference between the two sample distributions. Using the statistical test results, a combined grand attainment surface, as depicted in Figure 2c, can be constructed, showing the regions where each of the algorithms outperforms the other. [PERSON] and [PERSON] [1] suggested that suitable test procedures include the median test, its extensions to other quantiles, and tests of the Kolmogorov-Smirnov type [9]. [PERSON] and [PERSON] [8] extended the work carried out by [PERSON] and [PERSON] and used attainment surfaces to quantify the performance of their Pareto archives evolution strategy (PAES) algorithm. [PERSON] and [PERSON] identified four variables in the approach proposed by [PERSON] and [PERSON], namely:  
* How many comparison lines should be used;
* Where the comparison lines should go;
* Which statistical test should be used to compare the univariate distribution;
* In what form should the results be presented. From their empirical analysis, [PERSON] and [PERSON] found that at least 1000 lines should be used.