ハイパーボリュームインジケータを計算するボックス分解アルゴリズム

A box decomposition algorithm to compute the hypervolume indicator
Lacour, Renaud and Klamroth, Kathrin and Fonseca, Carlos M
Computers & Operations Research, 79: 347-360, 2017

“私たちは,支配領域を一組の軸平行ハイパーレクタングルまたはボックスに分割することに基づいて,ハイパー ボリュームインジケータの計算に対する新しいアプローチを提案する.私たちは非増加アルゴリズムとインクリ2 メンタルアルゴリズムを提示し,点の挿入を可能にします.このアルゴリズムでは時間複雑度は O(n[ p ‐ 1 ]+1) とO(n[ p ]+1) であり,n は点の数であり,p は客観的空間の次元である.一方,このような方法の理論的な複雑さは, 最悪の場合,ハイパーボリューム計算の複雑さに対する最良の上限よりも大きい隔たりの複雑さによって制限され るが,実際に効率的であることが示される.特に,非インクリメンタルアルゴリズムは,現在最も効率的なアルゴ リズムと競合する.最後に,私たちは WFG アルゴリズムの最悪の場合の複雑さに対して p ≥ 4 における O(n[p−1])の上限と O(n[ p ] ∗ log n) の下限を強化することを証明する.”