すべてのパレート解を収集する確率的手法
本谷 玲 (1151094)
本発表では，多目的最適化においてパレート解をすべて収集する手法について議論する．
多目的最適化の既存手法は，真のパレート解集合の代わりに，その近似を獲得している．
これは一般に真のパレート解集合を得るためには，無限個のパレート解を必要とするためである．
しかしながらパレート解集合が凸多面体の形状をなすと限定すれば，
有限個のパレート解からでも，真のパレート解集合が獲得できる．
本研究の目的は，この凸多面体の仮定の上で，真のパレート解集合を実用的な処理時間で獲得することである．
この目的を達成するために，我々は確率的な方法論を多目的最適化に取り入れる．
提案手法は，多目的最適化問題をランダムな重みの線形加重和によって単一目的化し，
その単一目的の最適化問題を反復してパレート解を集める．
この提案手法は真のパレート解集合の獲得に失敗しうる手法だが，
その失敗確率を無視できるほど小さくすることで，ほとんど確実にすべてのパレート解を収集できる．
我々はこの提案手法が，完全導出に失敗する平均確率の理論的な上界を，幾何学的な方法で与えた．
求めた理論的上界を解析した結果，サンプル数の増加にともなって，平均失敗確率の上界は指数的に減少することが分かった．
この解析結果は提案手法の効率のよさを表し，短い処理時間ですべてのパレート解を収集できうることを示している．
理論的上界のタイトさを調べるために，
理論的上界の値と，実際に提案手法を使ってパレート解を収集したときの平均失敗確率を，数値実験によって比較した．
この実験の結果，理論的上界と実際の失敗確率との間の誤差は，理論的上界の定数倍であることが示唆された．