要旨: 確率的マルチ目的最適化（SMOO）は、不確実な環境において、複数の潜在的に相反する目的の間でトレードオフを行う意思決定において重要である。SMOOは、すべての互いに支配しない意思決定を含むパレートフロンティアの同定を目指す。しかし、周辺分布、事後確率、あるいは期待値の計算などの埋め込まれた確率推論により、この問題は非常に難解である。スカラー化、サンプル平均近似、進化的アルゴリズムといった既存手法は、任意に粗い近似を提供するか、あるいは計算コストが過大になり得る。我々は、XOR-SMOOという新しいアルゴリズムを提案する。これは、確率1-deltaで、SATオラクルをgammaおよびdeltaに関して多対数回照会することで、SMOOに対するgamma近似パレートフロンティア（gamma>1）を得る。gamma近似パレートフロンティアは、真のフロンティアより固定の乗法因子gammaだけ下回るにすぎない。したがって、XOR-SMOOは、SATオラクルへの照会のみで、非常に難解なSMOO問題（#P困難）を解きながら、タイトで一定倍の近似保証を同時に得る。実世界の道路網の強化およびサプライチェーン設計の問題に関する実験では、XOR-SMOOが、より高い目的値を持つパレートフロンティアの同定、最適解へのより良いカバレッジ、見つかった解のより均一な分布において、複数のベースラインを上回ることが示される。全体として、XOR-SMOOはSMOOソルバの実用性と信頼性を大幅に向上させた。
ハッシュ化とランダム化による確率的多目的最適化におけるパレートフロンティアの近似
arXiv cs.LG / 2026/4/2
💬 オピニオンIdeas & Deep AnalysisModels & Research
要点
- 本論文は、パレートフロンティアの探索が、事後マージナルや期待値などの確率推論を要するため計算的に困難になる確率的多目的最適化（SMOO）を対象とする。
- ハッシュ化とランダム化を用いる XOR-SMOO を提案し、SATオラクルへのクエリのみを gamma と delta の双方について多項対数回数に抑えつつ、高い確率で gamma-近似パレートフロンティアを計算する。
- 返されたフロンティアは真のフロンティアに対して乗法的な gamma だけ下回るにとどまり、任意に緩い近似に陥ることはないという、タイトな定数倍近似保証を与える。
- 著者らは、実世界の道路網の補強およびサプライチェーン設計に関する実験を報告しており、いくつかのベースラインと比べて目的値が改善し、最適解のカバレッジが向上し、見つかった解の分布もより一様になることを示す。
- #P困難な SMOO 設定を、近似保証の信頼性を維持したまま SATオラクルによって解ける形へと変換し、確率的な意思決定における SMOO ソルバをより実用的にすることを目指している。
