はじめに

最適化手法は主に評価回数とそれに伴う目的関数の変動を可視化することで複数手法の経時的な性能を比較します．
一方で多目的最適化においては複数の目的関数が存在するため，そのような可視化が簡単ではありません．
従って，今回の記事では複数手法の複数試行における性能を可視化する方法 ($k$% attainment surface) を書きます．

なお，以下がattainment surfaceの提案論文になります

[1] On the Performance Assessment and Comparison of Stochastic Multi-objective Optimizers

記号の定義

多出力目的関数 $f: \mathbb{R}^D \rightarrow \mathbb{R}^M$とする．
$f$ の最適化を $N$ 試行したものとし，各試行で得られた Pareto解集合を $\forall i \in \{1,\dots,M\}, \mathcal{F}_i \subseteq \mathbb{R}^M$ とする．
目的関数ベクトル $\boldsymbol{f}$ が目的関数空間内のある点 $\boldsymbol{y}$ をdominateするとは任意の要素に対して $f_i \leq y_i$ であることを指し，$\boldsymbol{f} \preceq \boldsymbol{y}$と書く．
目的関数ベクトル集合 $F$ が目的関数空間内の点をdominateするとはある要素 $\boldsymbol{f} \in F$ に関して$\boldsymbol{f} \preceq \boldsymbol{y}$ を満たすことを指し，$F \preceq \boldsymbol{y}$ と書く．

Attainment surface

以下の図にあるように最適化中に得られたPareto解を基に目的空間を階段状に区切る面のことをAttainment surfaceと呼びます．
このような面は1試行につき1つPlotすることができますが，複数試行に関してこのようなPlotを行うには工夫が必要となります．
この工夫に関して説明するのが本記事の目的になります．

Figure 4. in Indicator-Based Evolutionary Algorithm with Hypervolume Approximation by Achievement Scalarizing Functions.

k% attainment surface

まず，empirical attainment functionという関数を以下のように定義します．

\alpha(\boldsymbol{y}) := \alpha(\boldsymbol{y}|\mathcal{F}_1,\dots,\mathcal{F}_N) = \frac{1}{N} \sum_{n=1}^N \mathbb{1}[\mathcal{F}_n \preceq \boldsymbol{y}]

ここで，$k$% attainment surfaceとは $S = \{\boldsymbol{y}\mid\alpha(\boldsymbol{y}) \geq k/100\}$ のような点集合を指します．
従って，$\{1/N,50,100\}$% attainment surfaceはそれぞれbest, median, worstなattainment surfaceを指すことがわかります．

[2] An Approach to Visualizing the 3D Empirical Attainment Function

[3] On the Computation of the Empirical Attainment Function

実装

可視化に用いるのは主に2次元であり，2次元の実装は比較的簡単であるため，2次元の実装のみ行いgithub上に公開した．