研究成果の紹介

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

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

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

関連業績：

[ACM TELO 2022] Youhei Akimoto, Yoshiki Miyauchi, Atsuo Maki. Saddle Point Optimization with Approximate MinimizationOracle and its Application to Robust Berthing Control, ACM Transactions on Evolutionary Learning and Optimization 2(1), pages 1-32 (2022) [doi] [link] [preprint] [repository]

[ACM TELO 2023] Atsuhiro Miyagi, Yoshiki Miyauchi, Atsuo Maki, Kazuto Fukuchi, Jun Sakuma, Youhei Akimoto. Covariance Matrix Adaptation Evolutionary Strategy with Worst-Case Ranking Approximation for Min–Max Optimization and its Application to Berthing Control Tasks, ACM Transactions on Evolutionary Learning and Optimization 3(2), pages 1-32 (2023) [doi] [link] [preprint]

[ASC 2023] Atsuhiro Miyagi, Kazuto Fukuchi, Jun Sakuma, Youhei Akimoto. Adaptive Scenario Subset Selection for Worst-Case Optimization and its Application to Well Placement Optimization, Applied Soft Computing 133, id 109842 (2023) [doi] [link] [preprint] [repository]

安全性や経済性の観点から，シミュレーション上で強化学習を実施して，得られた方策を現実環境で運用する，という方針がしばしば採用されます．とりわけ，強化学習において深層学習技術を採用した深層強化学習の枠組みでは，方策を学習するために必要な環境とエージェントのインタラクション数が膨大になるため，シミュレーションの活用は必要不可欠といえます．しかし，シミュレーションでは運用時の現実環境を完全に表すことが出来ない，現実環境が時々刻々と変化してしまう，などの理由から，学習時に使用したシミュレーション環境と運用時の現実環境には差が生じてしまいます．この差によって，シミュレーション上で学習された方策が，現実環境では低性能で安全性に問題のある方策となる恐れがあります．

私達は，シミュレーションと現実環境の差を考慮した強化学習の検討をしています．[IJCNN 2022]では，シミュレーションと現実環境での状態の表現方法の差に着目し，シミュレーション上で得られた方策を現実環境に転移するための方法を提案しています．[NeurIPS 2022]では，状態遷移確率と報酬関数の差に着目し，考えうる最悪なケースでの性能を最大化するような強化学習アプローチを提案しています．後者については，Max-Min最適化問題として定式化されるため，前項目で紹介したロバスト最適化と深い関わりがあります．

関連業績：

[IJCNN 2022] Rei Sato, Kazuto Fukuchi, Jun Sakuma, Youhei Akimoto. Few-Shot Image-to-Semantics Translation for Policy Transfer in Reinforcement Learning, 2022 International Joint Conference on Neural Networks (IJCNN), pages 01-10 (2022) [doi] [link]

[NeurIPS 2022] Takumi Tanabe, Rei Sato, Kazuto Fukuchi, Jun Sakuma, Youhei Akimoto. Max-Min Off-Policy Actor-Critic Method Focusing on Worst-Case Robustness to Model Misspecification, Advances in Neural Information Processing Systems 35 (NeurIPS 2022), pages 6967--6981 (2022) [preprint] [repository]

近年，深層学習は非常に広い応用を見せています．深層学習の性能は，そこで用いられる深層ニューラルネットワークのアーキテクチャ（各部分で利用されるオペレーションや，ネットワークの接続状態など）に依存します．Neural Architecture Search (NAS) は，これまでの人手によるアーキテクチャ設計を，探索アルゴリズムによって自動化する AutoML（自動機械学習）の一分野です．

私達は，One-shot NASと呼ばれる，ネットワークのアーキテクチャとパラメータを一度の学習サイクルにおいて同時に最適化する枠組みの研究をしています．とりわけ，確率緩和と呼ばれる方法によるパラメータの連続空間への拡張と，連続化されたパラメータ空間上の推定勾配を用いたアーキテクチャ探索の方法に着目しています．アーキテクチャの探索に自然勾配を活用した方法[AAAI 2018]やその一般化と勾配ステップサイズの適応規則の提案[ICML 2019]，強化学習において用いられている貢献度分配の考え方を導入することによる勾配推定分散の削減とそれによる探索高速化[AAAI 2021]などの成果があります．[IJCNN 2024]では，アーキテクチャの探索空間（候補となるアーキテクチャの空間）によっては勾配ベースのNASが不適切なアーキテクチャに収束してしまう脆弱性に着目し，候補アーキテクチャ間の中間出力の統計量の違いが原因の一因となり得ることを，理論解析および数値実験により示しています．

関連業績：

[AAAI 2018] Shinichi Shirakawa, Yasushi Iwata, Youhei Akimoto. Dynamic Optimization of Neural Network Structures Using Probabilistic Modeling, Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, New Orleans, Louisiana, USA, February 2-7, 2018, pages 4074-4082 (2018)

[ICML 2019] Youhei Akimoto, Shinichi Shirakawa, Nozomu Yoshinari, Kento Uchida, Shota Saito, Kouhei Nishida. Adaptive Stochastic Natural Gradient Method for One-Shot Neural Architecture Search, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pages 171-180 (2019) 

[AAAI 2021] Rei Sato, Jun Sakuma, Youhei Akimoto. AdvantageNAS: Efficient Neural Architecture Search with Credit Assignment, Proceedings of the AAAI Conference on Artificial Intelligence, 35(11), pages 9489-9496 (2021) [link] [repository]

[IJCNN 2024] Youhei Akimoto, Shinichi Shirakawa. Analysis of Search Space Design for Neural Architecture Search with Weight Sharing, 2024 International Joint Conference on Neural Networks (IJCNN), (2024, accepted)

進化戦略（Evolution Strategy）は連続値の最適化において広く用いられている進化計算アルゴリズムの一つです．連続値最適化のための進化計算アルゴリズムのほとんどは，理論解析が困難であることから，収束の保証を持ちません．

本研究では，離散値最適化の解析にしばしば用いられるDrift Analysisの方法を連続値最適化においても利用できるように拡張し，(1+1)-ES with 1/5-success ruleと呼ばれる有名なアルゴリズムに適用しました．[SIOPT 2022]では，強凸かつ勾配がリプシッツ連続な関数（勾配ベースの最適化法の解析においてしばしば仮定される関数クラス）およびその単調変換，さらには一部の非凸関数をも含む関数クラスにおいて一次収束を示しています．勾配法の解析と同程度に一般的な関数クラスでの一次収束を進化戦略において示したのは，本研究が世界で初めてです．[IEEE TEVC 2024]では，強凸かつ勾配がリプシッツ連続な関数およびその単調変換により定義される目的関数のもと，収束率の上下限を導出することに成功しています．とりわけ，収束率が設計変数の数に反比例すること，また，凸二次関数の場合，ヘッセ行列の固有値分布と収束率の関係をよりタイトに示すことに成功しました．今後の課題としては，強凸でない凸関数のもとでの収束レートの導出，非凸関数での収束保証，対象となるアルゴリズムの一般化，特にCMA-ESへの拡張，などが挙げられます．

(1+1)-ESはエリート保存戦略と呼ばれる，ベスト解を保持する戦略を取るため，目的関数値の単調減少が保証できる，という理論的な利点があります．しかし，最も広く採用されているCMA-ESはこの戦略を取らないため，ドリフト解析を用いた理論解析が困難になります．具体的には，ドリフト条件を満たすようなポテンシャル関数を設計することが難しくなります．[SPA] ではこの困難さを緩和し，非エリート保存戦略の収束解析を可能にするために，ドリフト解析と常微分方程式の安定性解析を組み合わせた収束証明の枠組みを提案しています．これを，非エリート保存戦略のESに適用し，Sphere関数のもとでの一次収束を示すことに成功しています．適用事例が少ないため，より一般の強凸関数での解析が望まれます．また，CMA-ESでも同様の解析を実現することが課題として挙げられます．

関連業績：

[SIOPT 2022] Youhei Akimoto, Anne Auger, Tobias Glasmachers, Daiki Morinaga. Global Linear Convergence of Evolution Strategies on More than Smooth Strongly Convex Functions, SIAM Journal on Optimization 32(2), pages 1402-1429 (2022) [doi] [preprint]

[SPA 2022] Youhei Akimoto, Anne Auger, Nikolaus Hansen. An ODE Method to Prove the Geometric Convergence of Adaptive Stochastic Algorithms, Stochastic Processes and their Applications 145, pages 269-307 (2022) [doi] [preprint]

[IEEE TEVC 2024] Daiki Morinaga, Kazuto Fukuchi, Jun Sakuma, Youhei Akimoto. Convergence Rate of the (1+1)-Evolution Strategy on Locally Strongly Convex Functions with Lipschitz Continuous Gradient and their Monotonic Transformations, IEEE Transactions on Evolutionary Computation 28(2), pages 501-515 (2024) [doi] [link] [preprint]

進化戦略（Evolution Strategy）は連続値の最適化において広く用いられている進化計算アルゴリズムの一つです．とりわけ，多変量正規分布からの候補解生成と平均ベクトルおよび共分散行列の更新を繰り返すことで最適化を進める Covariance Matrix Adaptation Evolution Strategy (CMA-ES) は，ブラックボックス連続最適化に対する最も有力な方法の一つとして広く用いられています．

CMA-ESの強みは，その不変性にあります．CMA-ESは目的関数の単調変換や設計変数空間のアフィン変換に対して不変であることから，目的関数の不連続性や変数間依存性・悪スケール性といったよく知られる困難さに対して有効であることが示されています．多変量正規分布の共分散行列を適応することは，変数間依存性や悪スケール性に対応するために必要ですが，特に高次元の場合には時間的および空間的計算量，最適化に必要なシミュレーション回数の観点から，その学習時間が最適化のボトルネックとなります．Deep Neural Networkを用いた進化的強化学習法（Deep NeuroEvolution）や自由度の高いトポロジー最適化などのように，数千を超える変数のブラックボックス最適化が求められるようになってきているため，最適化法の高速化が求められています．

私達は，CMA-ESをいくつかの観点から高速化するための方法を提案しています．

[ECJ 2020]では，共分散行列の適応を高速化する３つの独立したアイディアを提案しています．これらにより，従来のCMA-ESの強みを犠牲にすることなく，実用上多くの最適化問題に見られる性質を有する問題において大幅な効率改善が見られることを実験的に確認しています．問題の性質（変数分離可能性など）ごとに効率的に最適化可能なアルゴリズムは異なります．しかし，問題ごとに適切なアルゴリズムを選択することは，ブラックボックス最適化においては感と経験を要します．本研究の成果は，アルゴリズム選択の困難さを解決することに一役買っています．

[GECCO 2014, GECCO 2016, PPSN 2016]では，高次元最適化において変数間の相関関係が変数の数に対して線形のパラメータ数によって表現される（目的関数のヘッセ行列が対角行列や低ランク行列の和や積によって表現される）という仮定を置くことで，時間的計算量と空間的計算量を変数の数に対して線形に抑えつつ，従来よりも少ないシミュレーション回数で最適化する方法を提案しました．連続値の最適化に対して優れているCMA-ESと比較して，計算時間とメモリ使用量の両者において優れていることが実験的に示されています．[GECCO 2014]ではVD-CMAおよび[GECCO 2016]ではVkD-CMAと呼ばれる方法を提案しています．VkD-CMAにおいてk=1とした場合，両者は類似していますが，経験的にはVD-CMAよりもVkD-CMA(k=1)の方が安定して速い収束を示します．

関連業績：

[GECCO 2014] Youhei Akimoto, Anne Auger, and Nikolaus Hansen. 2014. Comparison-based natural gradient optimization in high dimension. In Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation (GECCO '14). ACM, New York, NY, USA, 373-380. [PDF with proofs] [Python code]

[GECCO 2016] Youhei Akimoto and Nikolaus Hansen. 2016. Projection-Based Restricted Covariance Matrix Adaptation for High Dimension. In Proceedings of the Genetic and Evolutionary Computation Conference 2016 (GECCO '16), Tobias Friedrich (Ed.). ACM, New York, NY, USA, 197-204. [Python code]

[PPSN 2016] Akimoto Y., Hansen N. (2016) Online Model Selection for Restricted Covariance Matrix Adaptation. In: Handl J., Hart E., Lewis P., López-Ibáñez M., Ochoa G., Paechter B. (eds) Parallel Problem Solving from Nature – PPSN XIV. PPSN 2016. Lecture Notes in Computer Science, vol 9921. Springer, Cham [Python code] Best Paper Nomination

[ECJ 2020] Youhei Akimoto, Nikolaus Hansen. 2020. Diagonal Acceleration for Covariance Matrix Adaptation Evolution Strategies. Evolutionary Computation, vol. 28, no. 3, pages 379--404. [Python code]

シミュレーションベース最適化において，制約条件はしばしばペナルティ関数法やこれに準ずる方法がその汎用性や容易さから採用されています．私達の研究[GECCO 2019] においても，修正オペレータと適応的ペナルティ関数法に基づく制約対処法を提案しています．しかし，制約条件を満たす領域（実行可能領域）が探索空間全体に対して（測度の観点で）狭い複数の非連結な集合となっているような場合 [GECCO 2020] や，そもそも制約条件を明示的に表現することが難しいような場合 [GECCO 2021] には，これらの方法が有効でない場面が見受けられます．

私達は，このような場面を想定し，深層生成モデルを活用した制約付きシミュレーションベース最適化のための最適化フレームワークを設計しています．深層生成モデルは，何らかの潜在空間からデータ空間への写像を深層ニューラルネットワークを用いて表現します．私達の方法では，データ空間を制約を満たす実行可能領域，潜在空間を最適化法が探索する設計変数空間に対応付けます．このような深層生成モデルを最適化に先立って学習しておくことで，制約を満たした解を探索することが可能となります．

[GECCO 2020]では，制約条件を明示的に書き下すことが可能な問題を対象に，実行可能領域が非連結集合となる場合に，対応する潜在空間が連結集合になるように深層生成モデルを学習する方法を提案しています．[GECCO 2021]では，Angry Birds というビデオゲームのレベル（ステージ）生成問題を対象に，「プレイ可能であり自然なレベルである」という暗黙の制約条件を満たすように，この条件を満たしているであろう既存のレベルを訓練データとして深層生成モデルを学習する方法を提案しています．

関連業績：

[GECCO 2019] Naoki Sakamoto, Youhei Akimoto. Adaptive Ranking Based Constraint Handling for Explicitly Constrained Black-Box Optimization, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ’19), July 13–17, 2019, Prague, Czech Republic, pages 700-708 (2019). Best Paper Nomination

[GECCO 2020] Naoki Sakamoto, Eiji Semmatsu, Kazuto Fukuchi, Jun Sakuma, Youhei Akimoto. 2020. Deep Generative Model for Non-convex Constraint Handling, GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pages 636-644 (2020)

[GECCO 2021] Takumi Tanabe, Kazuto Fukuchi, Jun Sakuma, Youhei Akimoto. 2021. Level Generation for Angry Birds with Sequential VAE and Latent Variable Evolution. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '21), pages 1052-1060 (2021) [doi] [preprint] Best Paper Nomination

[ECJ 2022] Naoki Sakamoto, Youhei Akimoto. Adaptive Ranking-based Constraint Handling for Explicitly Constrained Black-Box Optimization, Evolutionary Computation 30(4), pages 503-529 (2022) [doi] [link] [preprint] [repository]

シミュレーション精度の調整は，最適化に必要な時間と解の信頼性の間のトレードオフを定める重要な意思決定項目です．最適化困難さを度外視すれば，可能な限り自由度の高い設計変数表現を採用し，可能な限り高精度なシミュレータを用いることが望ましいのですが，高精度なシミュレータは往々にして計算時間も長くなり，限られた時間で実行できるシミュレーション回数が限られるなど，最適化が困難となる要因となります．

本研究では，CMA-ESが複数の解のランキングに基づいて探索することに着目し，精度の低く計算時間の短いシミュレータと，精度の高く計算時間の長いシミュレータを用いた場合に求まる目的関数値の順位相関が，十分に高ければ高速なシミュレータを採用，低ければより精度の高いシミュレータを採用するといった方法により，自動的にシミュレーション精度を選択する方法を開発しました．テスト問題を用いた数値実験により，開発した方法は，固定精度のシミュレータを採用した場合よりも精度と速度の両面において改善が見られることを確認しています[GECCO 2019]．また，トポロジー最適化の一問題に提案手法を適用し，同様の効果が確認しています[PPSN 2020]．本研究の成果により，必要な意思決定項目の自動化だけでなく，複数シミュレータが利用可能な場合に最適化効率の改善も見られるため，計算精度を比較的自由に調整が可能な，深層学習におけるハイパーパラメータ最適化などへの応用も期待されます．

また，これに関する理論的な分析も行っています．真に最適化したい目的関数と，実際に最適化法が計算する目的関数が異なる（代理関数と呼ぶ）シチュエーションは，上述のようなマルチフィデリティ設定限らずしばしば見られます．代理関数を用いた場合，代理関数の最適化が真の目的関数の最適化に繋がらない恐れがあります．[Algorithmica 2024]では，代理関数を改善する方向に探索した場合に目的関数が改善されるための十分条件を理論的に導出しています．ケンドールおよびスピアマンの順位相関係数を用いた場合に，上述の条件を満たすために必要な相関係数の下限値を導くとともに，順位毎に与えられる重み係数のピアソン相関係数についても同様の下限値を導いています．後者の下限値の方が低い値を示していることから，上述の研究成果を改善できる可能性が示唆されており，これら手法のさらなる改善が期待されています．また，ワーストケース最適化（前述）などにおいても，真のワーストケース関数値は得られず，近似最適化によって得られた値を代理として用いていることから，これについての理論的妥当性の分析にもつながる可能性があります．

関連業績：

[GECCO 2019] Youhei Akimoto, Takuma Shimizu, Takahiro Yamaguchi. Adaptive Objective Selection for Multi-Fidelity Optimization, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ’19), pages 880-888 (2019) 

[PPSN 2020] Youhei Akimoto, Naoki Sakamoto and Makoto Ohtani. Multi-Fidelity Optimization Approach under Prior and Posterior Constraints and its Application to Compliance Minimization, Parallel Problem Solving from Nature – PPSN XVI, pages 81-94 (2020)

[Algorithmica 2024] Youhei Akimoto. Analysis of Surrogate-Assisted Information-Geometric Optimization Algorithms, Algorithmica 86, pages 33-63 (2024)