Primal Integral

アルゴリズムの性能評価方法：primal integralについて

目次

先週の研究室ミーティングで，「Primal Integral（主積分）」という手法を知ったのでメモ．

アルゴリズムの性能評価方法として，これまで自分は「ある時点での目的関数値を比較」するようなことをよくやっていた．

例えば，最小化問題に対するアルゴリズムの評価として，アルゴリズムAは1800secでobj=100，アルゴリズムBは1800secでobj=120が得られたとする．

この時，1800secをタイムアウトとすると，アルゴリズムAの方が優れている．といった感じで評価できる．

しかし，タイムアウトを3000secにすると同点，3600secにするとアルゴリズムBの方が優れた解を見つけている． このように，タイムアウトの設定によって，評価が大きく変わってしまう．

ここで，特に実用では，早い段階で良い解を得たいということが多い． 最適化に興味がない人にとっては，それなりの時間でそれなりの解が欲しいということらしい．

このような，「より早く，良い解を」見つけられているかを評価する際にPrimal Integralを使うと良い．Primal Integralは，その名の通り，目的関数$f$と横軸$t$で囲まれた部分を$t=1...T$まで積分した値によって評価する． 積分した値が小さいほど，そのアルゴリズムは「より早く，良い解を」見つけたことになる．

Primal Integral を使うと，上記の図の場合，任意のタイムアウト時間に対してアルゴリズムAが優れていると評価できる．

参考文献

数理最適化ソルバの性能評価｜NTTデータ数理システム

数理最適化ソルバの性能評価のページです。MSIISMは、NTTデータ数理システムが監修する数理科学で現実世界の問題を解決するための情報発信」メディアです。

www.msiism.jp