ハイパーボリュームの高速計算アルゴリズム

A Faster Algorithm for Calculating Hypervolume

While, Lyndon and Hingston, Philip and Barone, Luigi and Huband, Simon IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 10, NO. 1, FEBRUARY 2006

ハイパーボリュームを正確に計算するためのアルゴリズムとして,hypervolume by slicing objectives (HSO) algorithmを提案する.これはこれまでに発表されたアルゴリズムと比較してより高速である.HSOはポイントの代わりに目的を処理する.アイデアはすでに考えられていたが,文献で正確に評価されたことはなかった.これまでに研究されていた正確なハイパーボリュームを求めるアルゴリズムは目的の数に対して指数関数的に計算量が増加する.HSOも最悪な場合では指数関数的であるが,優位に短い計算時間すなわちランダムに生成される3~8つの目的に対して2~3桁少ない計算時間を示した.したがって,HSOは一般的な最適化アルゴリズムのメトリックとしても,進化アルゴリズムの多様性メカニズムとしても,ハイパーボリュームの有用性を高める.