計算コスト

何を「コスト」として数えるかで、比較の結論が変わる。

3 つの数え方#

尺度	適する場面	問題点
評価回数	目的関数の評価が支配的なとき	アルゴリズム内部の計算を無視
実行時間	実運用に近い	実装品質・言語・ハードに左右される
反復回数	理論解析	1 反復のコストが手法ごとに違う

ブラックボックス最適化では 評価回数が標準。目的関数が実験やシミュレーションなら、 それ以外の計算時間は無視できるため。

評価回数が公平でない場合#

アルゴリズム内部の計算が無視できないとき、評価回数だけでは不公平になる。

• CMA-ES … 固有値分解に $𝒪(n^3)$
• ベイズ最適化 … ガウス過程の更新に $𝒪(N^3)$

目的関数がミリ秒で終わるなら、これらは支配的になる。 「評価が高価」という前提が成り立つかを先に確認する。

並列性#

同じ評価回数でも、並列に実行できるかで実時間が変わる。

手法	並列性
集団ベース（CMA-ES、PSO、ABC）	1 世代の $\lambda$ 個を同時に評価できる
勾配降下法	逐次。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
• Jeffrey Larson, Matt Menickelly, Stefan M. Wild. Derivative-free optimization methods. Acta Numerica 28, 2019. https://arxiv.org/abs/1904.11585