アルゴリズム比較

比較実験を読む、あるいは自分で行うときの確認事項。

ノーフリーランチが前提#

すべての問題を平均すれば、どの手法も同じ性能になる。 つまり無条件の優劣は原理的に存在しない。 「A が B より良い」は必ず条件付きの主張であり、 その条件が書かれていなければ主張として不完全。

確認する項目#

1. 問題群 — 標準的なベンチマークか。恣意的に選んでいないか。 実問題を含むか
2. 予算 — 評価回数を揃えているか
3. 調整 — 比較対象も同じ手間で調整したか
4. 試行回数 — 検定を行っているか
5. 指標 — 平均だけでなく到達率や分布を出しているか
6. 実装 — 比較対象は著者実装か。劣った再実装ではないか
7. 再現性 — コードと乱数種が公開されているか

特に疑うべき兆候#

• 提案手法がすべての関数で勝っている — ノーフリーランチに反する。 問題群が偏っている可能性が高い
• 比較対象が古い手法ばかり — 現在の標準（CMA-ES、L-SHADE など）が無い
• 「有意に優れる」とあるが検定名も試行回数も書かれていない
• 実行時間だけで比較している — 実装品質の差を測っている可能性

アブレーション#

提案手法が複数の工夫の組み合わせなら、 部品を 1 つずつ外して測ることで、どれが効いたかが分かる。 これが無いと、良い結果がどの要素によるものか判断できない。 ハイブリッド手法では特に重要。

参考文献#

• 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
• Joaquín Derrac et al. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and Evolutionary Computation 1(1), 2011. https://doi.org/10.1016/j.swevo.2011.02.002
• David H. Wolpert, William G. Macready. No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation 1(1), 1997. https://doi.org/10.1109/4235.585893