最良解到達率

目標値に到達した試行の割合。 success rate。 確率的な手法を評価するときの基本指標。

なぜ平均では足りないか#

確率的手法は試行ごとに結果が変わる。 平均値だけを見ると、次の 2 つが区別できない。

• A … 10 回中 10 回、そこそこの解に到達
• B … 10 回中 3 回は最適解、7 回は局所解

平均は同じでも性格はまったく違う。B は再始動を併用すれば強く、 A は安定だが伸びしろが無い。分布を見る必要がある。

ERT#

期待実行時間 (Expected Running Time) は、 到達率と評価回数をまとめた指標。

$$\mathrm{ERT}=\frac{\text{全試行の総評価回数}}{\text{成功した試行数}}$$

「成功するまでに平均で何回評価が要るか」を表し、 再始動を繰り返す運用を前提とした量になっている。 到達率が低くても 1 回が速ければ ERT は良くなる。 COCO/BBOB の標準指標。

目標値の設定#

「到達」の基準をどこに置くかで結果が変わる。

• 最適値との絶対差 $f(x)-f^{\star }<{10}^{-8}$
• 相対差
• 複数の目標値を設定して、到達率の曲線を描く

最後が最も情報量が多く、どの精度まで求めるかによって どの手法が良いかが変わることが見える。

参考文献#

• Nikolaus Hansen et al. COCO: A Platform for Comparing Continuous Optimizers in a Black-Box Setting. Optimization Methods and Software 36(1), 2021. https://doi.org/10.1080/10556788.2020.1808977
• Anne Auger, Nikolaus Hansen. Performance evaluation of an advanced local search evolutionary algorithm. IEEE CEC, 2005. https://doi.org/10.1109/CEC.2005.1554903