ブラックボックス最適化研究室Black-Box Optimization Lab · 研究成果Research Findingsブラックボックス最適化研究室Black-Box Optimization Lab · 研究成果Research Findings

最悪ケース・リスク・二段階の最適化Worst-Case, Risk-Aware, and Bilevel Optimization

シミュレーションのモデル誤差や環境の不確かさがあっても性能が保証される解を求める最悪ケース最適化やリスクを考慮した最適化と,上位の決定が下位の最適化の結果を通して評価される二段階の最適化を,ブラックボックスの設定で研究しています.We study, in black-box settings, worst-case and risk-aware optimization for solutions whose performance is guaranteed despite simulation model errors and environmental uncertainty, and bilevel optimization in which an upper-level decision is evaluated through the outcome of a lower-level optimization.

シミュレーションベース最適化においてモデルの不確実性を考慮したロバスト解探査Robust Solution Search under Model Uncertainty in Simulation-Based Optimization

キーワード:進化計算,ロバスト性Keywords: Evolutionary Computation, Robustness

シミュレーションベース最適化では,まず現実環境をモデル化したシミュレータを設計し,そのシミュレータのもとで計算される目的関数を最適化することになります.しかし,現実環境をモデル化する際には,現実環境の不確実性により,運用を想定している環境を正確にモデル化することが困難な場合はしばしば見受けられます.必ずしも正しくない推定モデルにおいて最適化した結果は,これを現実世界で運用した場合に想定したパフォーマンスが得られないばかりか,致命的な欠陥を起こすことも考えられます.そのため,最適化結果の信頼性の観点から,モデルの不確実性を考慮したロバスト解を得ることが望まれます.

私達は,このようなモデルの不確実性を考慮したシミュレーションベース最適化を実現する最適化法の開発やその応用事例の研究をしています.[ASC 2023] では,起こり得るシナリオの集合が有限集合で与えられる場合に,最悪シナリオのもとでの目的関数値を効率的に推定しながら探索するAS3-CMA-ESを提案し,坑井配置最適化へと応用しています.[GECCO 2021, ACM TELO 2022] では,シナリオが連続ベクトルで表現される場合において,最悪シナリオとそのもとでの最適解の探索を交互に繰り返すことでミニマックス鞍点を求めるAdversarial-CMA-ESを提案し,強凹凸関数のもとでの収束性を理論的に解析するとともに,数値実験により従来のアプローチに対する優位性を示しています.[ACM TELO 2023] では,Adversarial-CMA-ESを含めた多くの従来法が収束に失敗する非強凹凸関数の最適化の実現を目的に,最悪性能を直接推定しながら最適化するWRA-CMA-ESを提案し,数値実験により従来法に対する優位性を示しています.[ACM TELO 2022, ACM TELO 2023]ではいずれも,船舶の制御則最適化問題へと応用し,外乱やモデル化誤差に対してロバストな制御則の獲得に成功しています.

また,最悪ケースを考えるシナリオの集合(不確実性集合)をどう設計するかは難しく,集合を大きくすればロバスト性は高まる一方で最悪ケースでの性能は下がる,というトレードオフがあります.[GECCO 2023] では,不確実性集合の大きさと最悪ケース性能を 2 つの目的とするパレートフロントを求める方法を提案し,与えられた性能の基準を満たす範囲で最悪ケースにも強い解を探索できるようにしました.船舶の自動着桟への適用を通して,その有用性と限界を示しています.さらに,目的関数値にノイズがある場合に,期待値ではなくリスクの指標である VaR(Value-at-Risk)を最適化するため,ブートストラップで推定した順位のばらつきに基づいて各候補解の再評価回数を個別に適応する IR-CMA-ES を提案しています [GECCO 2025].

本研究プロジェクトの課題として,理論的な収束保証が挙げられます.[ACM TELO 2022]では強凹凸関数以外での収束は保証されておらず,実際,少なくとも局所的にこれを満たさない場合,数値実験でも収束しない現象が見られています.[ACM TELO 2023]では,数値実験上はより広い問題で収束する振る舞いが確認されていますが,理論的な保証がなく,また,解ける問題と困難な問題の明確な違いが判明していません.困難な問題を明確にしていくとともに,解ける問題を拡大していくことが求められます.加えて,必要なシミュレーション回数が多く,非常に高コストなシミュレーションを必要とする場合には現実的な時間で許容できる程度の解を得ることが難しいといった課題もあります.

In simulation-based optimization, one first designs a simulator to model a real-world environment, then optimizes an objective function calculated within that simulator. However, when modeling a real-world environment, it's often difficult to accurately capture the intended operational environment due to inherent uncertainties. A solution optimized under a model that isn't perfectly accurate may not only fail to achieve the expected performance when deployed in the real world but could also lead to critical failures. Therefore, from the perspective of solution reliability, it is desirable to obtain a robust solution that accounts for model uncertainty.

We are conducting research on developing optimization methods and their applications to achieve this type of simulation-based optimization. In [ASC 2023], we proposed AS3-CMA-ES, a method that efficiently searches for a solution while estimating the objective function value under the worst-case scenario when the set of possible scenarios is finite. We applied this method to well-placement optimization. In [GECCO 2021, ACM TELO 2022], when scenarios can be represented by a continuous vector, we proposed Adversarial-CMA-ES, which finds a minimax saddle point by alternately searching for the worst-case scenario and the optimal solution under that scenario. We theoretically analyzed its convergence for strongly convex-concave functions and demonstrated its superiority over conventional approaches through numerical experiments.

In [ACM TELO 2023], aiming to solve the optimization of non-strongly convex-concave functions—a task for which many conventional methods, including Adversarial-CMA-ES, fail to converge—we proposed WRA-CMA-ES. This method optimizes by directly estimating the worst-case performance, and we demonstrated its superiority over conventional methods through numerical experiments. Both [ACM TELO 2022] and [ACM TELO 2023] applied these methods to a ship control law optimization problem and successfully acquired a control law that is robust to disturbances and modeling errors.

Designing the set of scenarios to consider (the uncertainty set) is also difficult: a larger set increases robustness but lowers the worst-case performance. In [GECCO 2023], we proposed a bi-objective approach that finds the Pareto front between the size of the uncertainty set and the worst-case performance, so that solutions performing well in the worst case can be found while meeting a given performance threshold. An application to automatic ship berthing showed its usefulness and limitations. Furthermore, to optimize Value-at-Risk (VaR), a risk measure, instead of the expected value of a noisy objective, we proposed IR-CMA-ES, which individually adapts the number of reevaluations of each candidate solution based on ranking deviations estimated by bootstrapping [GECCO 2025].

A key challenge for this research project is providing a theoretical convergence guarantee. In [ACM TELO 2022], convergence is not guaranteed for functions other than strongly convex-concave ones. In fact, in numerical experiments, we have observed non-convergence when this condition is not met, at least locally. While [ACM TELO 2023] was observed to converge on a wider range of problems in numerical experiments, there is no theoretical guarantee, and a clear distinction between solvable and difficult problems has not yet been identified. It is necessary to clarify the difficult problems and expand the range of solvable problems. Additionally, another challenge is that when a large number of very high-cost simulations are required, it becomes difficult to obtain an acceptable solution within a realistic timeframe.

関連する論文Related Publications

  1. GECCO 2021 口頭Oral CORE A
    Saddle Point Optimization with Approximate Minimization Oracle
    Youhei Akimoto
    GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 493–501 (2021)
  2. ACM TELO 2022
    Saddle Point Optimization with Approximate MinimizationOracle and its Application to Robust Berthing Control
    Youhei Akimoto, Yoshiki Miyauchi, Atsuo Maki
    ACM Transactions on Evolutionary Learning and Optimization, Vol.Vol. 2(1), Art. 2, pp. 1–32 (2022)
  3. ACM TELO 2023 学生が筆頭Student-led Scopus Q1
    Covariance Matrix Adaptation Evolutionary Strategy with Worst-Case Ranking Approximation for Min–Max Optimization and its Application to Berthing Control Tasks
    Atsuhiro Miyagi, Yoshiki Miyauchi, Atsuo Maki, Kazuto Fukuchi, Jun Sakuma, Youhei Akimoto
    ACM Transactions on Evolutionary Learning and Optimization, Vol.Vol. 3(2), Art. 8, pp. 1–32 (2023)
  4. ASC 2023 学生が筆頭Student-led JCR Q1
    Adaptive Scenario Subset Selection for Worst-Case Optimization and its Application to Well Placement Optimization
    Atsuhiro Miyagi, Kazuto Fukuchi, Jun Sakuma, Youhei Akimoto
    Applied Soft Computing, Vol.Vol. 133, Art. 109842 (2023)
  5. GECCO 2023 口頭Oral学生が筆頭Student-led CORE A
    Trade-off Between Robustness and Worst-Case Performance in Min-Max Optimization
    Hinata Edo, Yoshiki Miyauchi, Atsuo Maki, Youhei Akimoto
    GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 1339–1347 (2023)
  6. GECCO 2025 学生が筆頭Student-led
    CMA-ES with Individual Adaptive Reevaluation for Black Box Value-At-Risk Optimization
    Ze Kai Ng, Daiki Morinaga, Youhei Akimoto
    GECCO '25: Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 495–498 (2025)

ブラックボックス二段階最適化Black-Box Bilevel Optimization

キーワード:進化計算,二段階最適化Keywords: Evolutionary Computation, Bilevel Optimization

二段階(bilevel)最適化は,上位の決定の良し悪しが,それに応じて行われる下位の最適化の結果を通して評価される問題です.目的関数がブラックボックスである場合には進化計算が有力な手段ですが,上位の解を 1 つ評価するたびに下位の最適化を入れ子にして実行する必要があり,非常に高コストになります.これを高速化する従来のヒューリスティックは,多峰性の問題や,上位と下位の変数が強く相互作用する問題でうまく働かないことが知られていました.

[GECCO 2026] では,順位に基づく進化計算アルゴリズムが目的関数の単調変換に対して不変であることに着目し,上位の各反復で下位の最適化を収束まで実行する代わりに,上位の目的関数値の順位を近似する枠組みを提案しました.CMA-ES を用いて連続の二段階最適化問題に適用し,標準的なベンチマークで既存手法と同等の性能を示すとともに,従来法では解けなかった,多峰的で変数間の相互作用が強い問題を解けることを示しています.実装は公開しています.上位の決定が下位の最適化の結果を通して評価されるという構造は,二段階強化学習とも共通しています.

Bilevel optimization is a problem in which an upper-level decision is evaluated through the outcome of a lower-level optimization performed in response to it. Evolutionary computation is a powerful tool when the objective functions are black boxes, but each evaluation of an upper-level solution requires a nested lower-level optimization, which makes the search very expensive. Existing heuristics for speeding this up are known to fail on multimodal problems and on problems with strong interactions between upper- and lower-level variables.

In [GECCO 2026], exploiting the invariance of rank-based evolutionary algorithms to monotonic transformations of the objective function, we proposed a framework that approximates the ranking of upper-level objective values instead of running the lower-level optimization to convergence at every upper-level iteration. Applied to continuous bilevel problems with CMA-ES, it performed competitively on standard benchmarks and solved problems that previous methods could not, particularly multimodal ones with strong variable interactions. The code is publicly available. The structure in which an upper-level decision is evaluated through the outcome of a lower-level optimization is shared with bilevel reinforcement learning.

関連する論文Related Publications

  1. GECCO 2026 口頭Oral学生が筆頭Student-led CORE A
    Accelerating Black-Box Bilevel Optimization with Rank-Based Upper-Level Value Function Approximation
    Marc Ong, Youhei Akimoto
    GECCO '26: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 591–599 (2026)

このトピックのソフトウェアSoftware for this topic