Research Findings

キーワード：進化計算，情報幾何，自然勾配，理論解析

CMA-ES は，多変量正規分布から候補解を生成し，その評価結果に基づいて分布の平均ベクトルと共分散行列を更新することを繰り返す最適化法です．その更新則は，経験的に優れた性能を示すように工夫を重ねて設計されてきたものであり，なぜ有効に働くのかについての数理的な理解は十分ではありませんでした．

[PPSN 2010, Algorithmica 2012] では，CMA-ES の平均ベクトルと共分散行列の更新が，正規分布のパラメータ空間において，目的関数値の順位に基づいて定めた期待値を自然勾配法によって改善する更新とみなせることを示しました．この結果は，CMA-ES と自然進化戦略（Natural Evolution Strategies）を統一的に理解する視点を与えるとともに，確率分布のパラメータ空間上の自然勾配法として多くの比較ベースのアルゴリズムを導出する情報幾何的最適化（Information-Geometric Optimization, IGO）の枠組みにつながる成果となりました．私達は，この考え方を，ニューラルネットワークの構造探索（「これまでの研究」を参照）や，カテゴリ変数と連続変数が混在する問題の最適化など，さまざまなアルゴリズムの設計に用いています．

IGO の収束については，学習率を無限小とした連続時間の理想化（IGO フロー）の解析が中心で，実際のアルゴリズムのように有限の学習率で離散的に更新する場合の結果はほとんどありませんでした．[PPSN 2026] では，指数型分布族の期待値パラメータの座標での自然勾配更新として表した離散時間の IGO を，強凸二次関数のもとで，共分散行列をすべて適応し，学習率を正の定数に固定し，分位点に基づく重みを用いる設定で解析しました．共分散行列が零に収束することを証明し，さらに，適切にスケールした共分散行列の条件数が十分な頻度で有界に保たれるという条件のもとで，平均ベクトルが大域的最適解に収束することを示しています．これは，IGO の理論と CMA-ES のような共分散行列適応法との隔たりを埋める一歩です．平均ベクトルの収束に必要な上記の条件を取り除くことや，二次関数以外の関数への拡張が今後の課題です．

Keywords: Evolutionary Computation, Information Geometry, Natural Gradient, Theoretical Analysis

CMA-ES is an optimization method that repeatedly generates candidate solutions from a multivariate normal distribution and updates the mean vector and covariance matrix of the distribution based on their evaluations. Its update rules were refined over many years to perform well empirically, but a mathematical understanding of why they work was lacking.

In [PPSN 2010, Algorithmica 2012], we showed that the updates of the mean vector and covariance matrix in CMA-ES can be viewed as natural gradient steps on the parameter space of normal distributions, improving an expected value defined from the ranking of objective function values. This result provided a unified view of CMA-ES and Natural Evolution Strategies, and led to the framework of Information-Geometric Optimization (IGO), which derives many comparison-based algorithms as natural gradient methods on the parameter space of probability distributions. We use this idea to design various algorithms, including neural architecture search (see "Past Research") and optimization of mixed categorical and continuous variables.

Convergence results for IGO have mostly concerned its continuous-time idealization with an infinitesimal learning rate (the IGO flow); little was known about discrete updates with finite learning rates, as in practical algorithms. In [PPSN 2026], we analyzed discrete-time IGO, expressed as natural gradient updates in the expectation-parameter coordinates of an exponential family, on strongly convex quadratic functions, with full covariance matrix adaptation, a fixed positive learning rate, and quantile-based weights. We proved that the covariance matrix converges to zero, and that the mean vector converges to the global optimum provided that the condition number of the appropriately scaled covariance matrix is bounded at sufficiently frequent iterations. This is a step toward closing the gap between IGO theory and covariance matrix adaptation methods such as CMA-ES. Removing the above condition for the convergence of the mean vector and extending the analysis beyond quadratic functions remain future challenges.

キーワード：進化計算，理論解析

進化戦略（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でも同様の解析を実現することが課題として挙げられます．

離散最適化についても，カテゴリ変数の最適化のための categorical compact GA の実行時間を解析しました [ECJ 2025]．カテゴリ数，変数の数，学習率が実行時間にどう影響するかに着目し，2 つの線形関数（categorical OneMax と KVal）について，高い確率で成り立つ実行時間の上界（裾の確率の評価）を導出しています．これは，2 値の compact GA について知られていた解析の一般化になっています．

Keywords: Evolutionary Computation, Theoretical Analysis

Evolution Strategy (ES) is a widely used evolutionary computation algorithm for continuous-valued optimization. Most evolutionary computation algorithms for continuous optimization lack a convergence guarantee because their theoretical analysis is difficult.

In this research, we extended the method of Drift Analysis, which is often used for the analysis of discrete-valued optimization, to be applicable to continuous-valued optimization and applied it to a well-known algorithm called (1+1)-ES with the 1/5-success rule. In [SIOPT 2022], we demonstrated linear convergence for a class of functions that includes strongly convex functions with Lipschitz-continuous gradients (a class of functions often assumed in the analysis of gradient-based optimization methods), their monotonic transformations, and even some non-convex functions. This study was the first in the world to show linear convergence for an evolution strategy on a class of functions as general as those used in the analysis of gradient methods. In [IEEE TEVC 2024], we successfully derived the upper and lower bounds of the convergence rate for objective functions defined by strongly convex functions with Lipschitz-continuous gradients and their monotonic transformations. Specifically, we succeeded in showing that the convergence rate is inversely proportional to the number of design variables, and for convex quadratic functions, we provided a tighter relationship between the distribution of the eigenvalues of the Hessian matrix and the convergence rate. Future challenges include deriving convergence rates for convex but not strongly convex functions, providing convergence guarantees for non-convex functions, and generalizing the target algorithms, particularly extending the analysis to CMA-ES.

The (1+1)-ES has a theoretical advantage: it uses an elite preservation strategy, which keeps the best solution, thereby guaranteeing a monotonic decrease in the objective function value. However, CMA-ES, the most widely adopted algorithm, does not use this strategy, making theoretical analysis using drift analysis difficult. Specifically, it becomes hard to design a potential function that satisfies the drift condition. In [SPA 2022], to alleviate this difficulty and enable the convergence analysis of non-elite preservation strategies, we proposed a framework for convergence proof that combines drift analysis with ordinary differential equation (ODE) stability analysis. We applied this to a non-elite preservation ES and successfully demonstrated its linear convergence on the Sphere function. As there are few application examples, analysis for more general strongly convex functions is desired. A further challenge is to perform a similar analysis for CMA-ES.

For discrete optimization, we analyzed the runtime of the categorical compact GA, which optimizes categorical variables [ECJ 2025]. Focusing on how the number of categories, the number of variables, and the learning rate affect the runtime, we derived tail bounds on the runtime for two linear functions, categorical OneMax and KVal, generalizing known results for the binary compact GA.

キーワード：進化計算，連続最適化

進化戦略（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)の方が安定して速い収束を示します．

[ACM TELO 2026] では，[GECCO 2016, PPSN 2016] を発展させ，少数の方向だけに目的関数が敏感に反応する「疎な感度構造」をもつ高次元の問題を対象とした dd-RCMA-ES を提案しました．新しい制限付き共分散行列のモデルにより，必要な記憶容量を変数の数の 2 乗から 1 次に抑え，その適応も 1 反復あたり変数の数に線形の計算時間で行えるようにしています．また，ステップサイズの適応には，累積ステップサイズ適応（CSA）に代えて 2 点ステップサイズ適応（TPA）を用いています．TPA は，高次元で目的関数に影響しない変数が含まれる場合に生じる「効かない部分空間」による悪影響を受けません．ハイパーパラメータは変数の数とモデルの複雑さから自動的に定まるため，標準の CMA-ES と同じく調整なしで使え，必要であればモデルの複雑さに上限を設けることもできます．80 次元から 10240 次元までの 18 のテスト問題での実験により，目標の精度に達するまでの関数評価回数の点で dd-RCMA-ES が効率的であり，特に，非常に敏感な方向と鈍感な方向をそれぞれ少数含む疎な構造をもつ問題で，他の CMA-ES の変種より優れていることを示しています．実装は公開しています．

Keywords：Evolutionary Computation, Continuous Optimization

Evolutionary Strategy (ES) is one of the most widely used evolutionary computation algorithms for continuous-valued optimization. In particular, the Covariance Matrix Adaptation Evolution Strategy (CMA-ES), which proceeds by repeatedly generating candidate solutions from a multivariate normal distribution and updating the mean vector and covariance matrix, is one of the most powerful methods for black-box continuous optimization.

The strength of CMA-ES lies in its invariance. Because CMA-ES is invariant to monotonic transformations of the objective function and affine transformations of the design variable space, it has proven effective against well-known challenges like objective function discontinuities, variable dependencies, and ill-scaling. Adapting the covariance matrix of the multivariate normal distribution is essential for handling variable dependencies and ill-scaling. However, especially in high-dimensional spaces, the computational time and memory required, as well as the number of simulations needed for optimization, become a bottleneck. As the demand for black-box optimization with thousands of variables grows—for example, in evolutionary reinforcement learning with deep neural networks (Deep NeuroEvolution) and high-degree-of-freedom topology optimization—the need for faster optimization methods has become critical.

We have proposed several methods to accelerate CMA-ES from various perspectives.

In [ECJ 2020], we proposed three independent ideas to speed up the covariance matrix adaptation. Through experiments, we have confirmed that these ideas lead to significant efficiency improvements for many practical optimization problems without sacrificing the traditional strengths of CMA-ES. Different algorithms are more efficient for problems with specific properties (such as variable separability). However, selecting the appropriate algorithm for each problem in black-box optimization requires intuition and experience. The results of this research help to solve the difficulty of algorithm selection.

In [GECCO 2014, GECCO 2016, PPSN 2016], we proposed a method that, for high-dimensional optimization, reduces both computational time and memory usage to be linear with respect to the number of variables, while also requiring fewer simulations than conventional methods. This is achieved by assuming that the correlations between variables can be represented by a number of parameters that is linear with the number of variables (i.e., the Hessian matrix of the objective function can be expressed as a sum or product of diagonal and low-rank matrices). Experimental results show that these methods are superior to the standard CMA-ES in terms of both computation time and memory usage. Specifically, we proposed a method called VD-CMA in [GECCO 2014] and VkD-CMA in [GECCO 2016]. While the two methods are similar when k=1 in VkD-CMA, VkD-CMA (k=1) has been empirically shown to converge more stably and faster than VD-CMA.

In [ACM TELO 2026], extending [GECCO 2016, PPSN 2016], we proposed dd-RCMA-ES for high-dimensional problems with sparse-sensitivity structures, where only a small number of directions are highly sensitive. A new restricted covariance matrix model reduces the storage requirement from quadratic to linear in the number of variables, and its adaptation runs in linear time per iteration. For step-size adaptation, we use two-point step-size adaptation (TPA) instead of cumulative step-size adaptation (CSA); unlike CSA, TPA is not negatively affected by ineffective subspaces, which are prevalent in high dimensions where non-relevant design variables may be introduced. The hyperparameters are determined from the problem dimension and the model complexity, maintaining the out-of-the-box usability of the standard CMA-ES while allowing the model complexity to be bounded if desired. Experiments on 18 test problems in dimensions from 80 to 10240 showed that dd-RCMA-ES is efficient in terms of the number of function evaluations needed to reach a target precision, and that it excels over other CMA-ES variants on problems with sparse structures comprising a small number of both highly sensitive and insensitive directions. The code is publicly available.

キーワード：進化計算，連続最適化，パラメータ適応

CMA-ES は，利用者がハイパーパラメータを調整しなくても多くの問題で良い性能を示すように既定値が設計されています．しかし，多峰性の問題やノイズのある問題のような難しい問題では，既定の設定のままではうまく解けないことが多く，集団サイズ（1 反復で生成する候補解の数）や学習率を問題に合わせて調整する必要があります．適切な値は問題によって大きく異なり，ブラックボックス最適化では事前に知ることができないため，その調整には多くの試行錯誤が必要です．

私達は，この調整を自動化するため，分布パラメータの更新がどの程度正確に行えているか，という観点から，集団サイズと学習率をそれぞれ適応する方法を提案してきました．集団サイズは，CMA-ES の更新を自然勾配の推定とみなす（「設計原理と理論解析」を参照）と，勾配を推定するためのモンテカルロ標本の数にあたります．多峰性やノイズのある関数では，推定した自然勾配の向きが反復ごとにばらつきやすくなります．[GECCO 2016] では，この観察に基づき，自然勾配の推定の精度（SN 比）が一定の水準に保たれるように集団サイズを適応する方法を，情報幾何的最適化から導かれる CMA-ES の簡略版に対して提案しました．[GECCO 2018] では，これを標準の CMA-ES に拡張した PSA-CMA-ES を提案しています．分布パラメータ（平均ベクトル，ステップサイズ，共分散行列）の更新量を，フィッシャー計量を考慮して分布パラメータの空間で累積する進化パスを新たに導入し，その長さによって更新の精度を測って，精度が目標の水準に保たれるように集団サイズを増減させます．また，最適なステップサイズは集団サイズに依存するため，品質利得（quality gain）の解析から導いたステップサイズの補正を加え，適応を安定させています．雑音のない関数と雑音のある関数での実験により，PSA-CMA-ES は大域的な構造をもつ多峰性関数やノイズのある関数でよく働き，ノイズと多峰性を同時に扱えることを示しました．一方で，単峰性関数では集団サイズが不必要に大きくなる非効率さも明らかになっています．[GECCO 2023, ACM TELO 2025] では，学習率に着目し，常微分方程式を用いた解析により，このような難しい問題では小さな学習率が必要であることを示したうえで，理想的な学習率の定め方を議論しました．これに基づき，更新の信号対雑音比（SN 比）が一定に保たれるように学習率を適応する LRA-CMA-ES を提案しました．学習率を固定した CMA-ES や PSA-CMA-ES との比較実験により，LRA-CMA-ES は既定の集団サイズのままでも，高コストな学習率の調整なしに多峰性やノイズのある問題で良い性能を示すことを確認しています．集団サイズを増やすことと学習率を下げることは，いずれも更新の精度を高めるための手段であり，二つの方法は同じ考え方の異なる実現になっています．

Keywords: Evolutionary Computation, Continuous Optimization, Parameter Adaptation

The default hyperparameters of CMA-ES are designed so that it performs well on many problems without tuning by the user. On difficult problems such as multimodal or noisy ones, however, the default setting often fails, and the population size (the number of candidate solutions generated per iteration) or the learning rate must be tuned to the problem. Appropriate values differ greatly between problems and cannot be known in advance in black-box optimization, so tuning them requires a lot of trial and error.

To automate this tuning, we have proposed methods that adapt the population size and the learning rate, respectively, from the viewpoint of how accurately the distribution parameters are updated. When the update of CMA-ES is viewed as a natural gradient estimate (see "Design Principles and Theory"), the population size corresponds to the number of Monte Carlo samples used for the estimate. On multimodal and noisy functions, the direction of the estimated natural gradient tends to fluctuate over iterations. Based on this observation, in [GECCO 2016], we proposed a method that adapts the population size so that the accuracy (signal-to-noise level) of the natural gradient estimate is kept at a fixed level, for a simplified variant of CMA-ES derived from information-geometric optimization. In [GECCO 2018], we extended it to the standard CMA-ES and proposed PSA-CMA-ES. A new evolution path accumulates the updates of the distribution parameters (mean vector, step-size, and covariance matrix) in the distribution parameter space, taking the Fisher metric into account; its length measures the accuracy of the update, and the population size is increased or decreased so that the accuracy stays at a target level. Since the optimal step-size depends on the population size, a step-size correction derived from quality gain analysis is added to stabilize the adaptation. Experiments on noiseless and noisy functions showed that PSA-CMA-ES works well on well-structured multimodal and/or noisy functions and can tackle noise and multimodality at the same time, while it also revealed an inefficient increase of the population size on unimodal functions. In [GECCO 2023, ACM TELO 2025], we focused on the learning rate. Using an analysis based on ordinary differential equations, we showed that a small learning rate is necessary on such difficult problems, and discussed how an ideal learning rate should be chosen. Based on these findings, we proposed LRA-CMA-ES, which adapts the learning rate so that the signal-to-noise ratio of the update is kept constant. Experiments comparing it with CMA-ES with a fixed learning rate and with PSA-CMA-ES showed that LRA-CMA-ES performs well on multimodal and/or noisy problems even with the default population size, without costly learning rate tuning. Increasing the population size and decreasing the learning rate are both ways to improve the accuracy of the update, and the two methods are different realizations of the same idea.

キーワード：進化計算，混合変数最適化

実際のブラックボックス最適化では，設計の選択肢を表すカテゴリ変数と連続値のパラメータが混在することがよくあります．機械学習のハイパーパラメータ最適化はその典型例です．CMA-ES をカテゴリ変数にも拡張した CatCMA は，こうした問題で優れた性能を示していますが，目的関数においてカテゴリ変数と連続変数が相互作用する場合には性能が低下します．これは，探索分布がカテゴリ変数と連続変数を独立なものとして扱っているためです．

[GECCO 2025] では，2 値変数と連続変数が混在する場合を対象に，CatCMA にとって特に難しい 2 種類の相互作用を特定しました．それぞれに対処する要素技術として，ウォームスタートの戦略とハイパー表現（hyper-representation）の技法を提案し，これらの相互作用をもつテスト問題で理論的に解析しています．両者を組み込んだ ICatCMA は，元の CatCMA を上回る性能を示しました．[PPSN 2026] では，外側のループでカテゴリ変数を，内側のループでカテゴリ変数の値ごとに連続変数を最適化する二段階の枠組みを提案しました．それぞれの段階を情報幾何的最適化における確率緩和として定式化し，二段階にすることによる計算コストを抑えるため，保持している複数の設定のうち最良のものから内側の最適化を始めるウォームスタートを導入しています．2 値・連続変数のベンチマークで，既知の相互作用と新たに提案した相互作用のどちらに対しても，最先端の手法より相互作用にうまく対処し，計算効率も高いことを示しています．

Keywords: Evolutionary Computation, Mixed-Variable Optimization

In real-world black-box optimization, categorical variables representing design choices are often mixed with continuous parameters; hyperparameter optimization in machine learning is a typical example. CatCMA, which extends CMA-ES to categorical variables, performs well on such problems, but it struggles when categorical and continuous variables interact in the objective function, because its search distribution treats the two types of variables as independent.

In [GECCO 2025], focusing on mixed binary and continuous variables, we identified two types of interaction that are particularly difficult for CatCMA. We proposed two components to address them, a warm-starting strategy and a hyper-representation technique, and analyzed them theoretically on test problems exhibiting these interactions. CatCMA enhanced with both components, called ICatCMA, outperformed the original CatCMA. In [PPSN 2026], we proposed a bilevel framework in which an outer loop optimizes the categorical variables and an inner loop optimizes the continuous variables for each categorical configuration. Each level is formulated as a stochastic relaxation under information-geometric optimization, and to reduce the cost of the bilevel structure, the inner optimization is warm-started from the best of several cached configurations. On binary-continuous benchmarks, the method handled both previously reported interactions and a newly proposed one better than state-of-the-art approaches, with higher computational efficiency.

キーワード：進化計算，ロバスト性

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

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

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

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

Keywords: Evolutionary Computation, Robustness

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 [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.

キーワード：進化計算，二段階最適化

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

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

Keywords: Evolutionary Computation, Bilevel Optimization

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, described below.

二段階強化学習によるインセンティブや環境の設計

Designing Incentives and Environments via Bilevel Reinforcement Learning

キーワード：強化学習，二段階最適化，マルチエージェント

社会や工学のシステムでは，設計者（リーダー）がインセンティブや環境を定め，それに応じて別のエージェント（フォロワー）が自らの目的のために学習し行動する，という構造がしばしば見られます．このとき設計者は，フォロワーの学習の過程に直接介入することはできず，その結果として現れる振る舞いを観測して設計を改善しなければなりません．私達は，このような問題を，リーダーの目的がフォロワーの解くマルコフ決定過程の最適方策に依存する二段階強化学習として定式化し，フォロワーをブラックボックスとみなして設計を最適化する方法を研究しています．

[ACML 2025] では，2 人一般和の確率的シュタッケルベルクゲームについて，リーダーの性能の単調な改善を保証する方策反復法を提案しました．既存の方策勾配法や価値反復法にはこの保証がなく，また定常なシュタッケルベルク均衡が存在するとも限らないことから，より広い概念としてパレート最適性を導入し，リーダーが近視眼的な場合に提案法がパレートフロントに収束することを示しています．[ICAPS 2026] では，リーダーの戦略に応じてフォロワーの最適方策がどう変わるかを含めたリーダーの目的関数の勾配（超勾配，hypergradient）を導出し，ボルツマン共分散トリックを用いることで，リーダーの決定空間が高次元であっても，相互作用のサンプルだけから超勾配を推定できる方法を提案しました．分散型（decentralized）の設定の 2 人マルコフゲームに対する，初めての超勾配に基づく方法です．

[NeurIPS 2026] では，さらに，フォロワーの報酬関数がリーダーに分からないブラックボックスなフォロワーを扱いました．観測した軌跡から逆強化学習によってフォロワーの報酬を推定し，超勾配を計算する RE-HG を提案しています．素朴に逆強化学習を用いると生じる報酬整形によるバイアスと数値的な不安定さを，多様な環境ダイナミクスの情報を集約してバイアスを打ち消す仕組みと，固有値の打ち切りによる暗黙の正則化で抑えています．報酬が既知の場合（オラクル）の超勾配とよく一致し，同等以上の性能を示すとともに，オラクルが局所解にとらわれる鋭い報酬地形でも安定した勾配が得られることを示しました．[PPSN 2026] では，報酬の整形を上位の問題として進化計算で最適化し，強化学習エージェントの未知の環境への汎化性能を高める GERS を提案しました．下位では少数の訓練環境で整形した報酬のもとでエージェントを学習し，上位では CMA-ES が，検証環境での整形前の累積報酬（スコア）だけを観測して整形のパラメータを調整します．検証環境の軌跡を見ずにスコアだけを用いる設定でも，検証環境の軌跡を使えるドメインランダム化と同程度の汎化性能が得られています．

Keywords: Reinforcement Learning, Bilevel Optimization, Multi-Agent Systems

In social and engineering systems, a designer (leader) often sets incentives or environments, and another agent (follower) learns and acts for its own purpose in response. The designer cannot intervene in the follower's learning process directly and must improve the design by observing the resulting behavior. We formulate such problems as bilevel reinforcement learning, in which the leader's objective depends on the optimal policy of the Markov decision process solved by the follower, and develop methods that optimize the design while treating the follower as a black box.

In [ACML 2025], we proposed a policy iteration algorithm for two-player general-sum stochastic Stackelberg games that guarantees monotone improvement of the leader's performance. Since existing policy gradient and value iteration methods lack this guarantee, and a stationary Stackelberg equilibrium does not always exist, we introduced Pareto optimality as a broader notion and showed that the proposed method converges to the Pareto front when the leader is myopic. In [ICAPS 2026], we derived the gradient of the leader's objective that accounts for how the follower's optimal policy changes with the leader's strategy (the hypergradient), and proposed a method that, using the Boltzmann covariance trick, estimates it from interaction samples alone, even when the leader's decision space is high-dimensional. It is the first hypergradient-based method for two-player Markov games in decentralized settings.

In [NeurIPS 2026], we further addressed black-box followers whose reward function is unknown to the leader. We proposed RE-HG, which recovers the follower's reward from observed trajectories by inverse reinforcement learning and uses it to compute the hypergradient. The reward-shaping bias and numerical instability caused by naive inverse reinforcement learning are suppressed by a bias-cancellation mechanism that aggregates information across diverse environment dynamics, and by implicit regularization through eigenvalue truncation. Its gradient estimates align with those of the white-box oracle, with comparable or better performance, and remain stable and useful in sharp reward landscapes where the oracle gets stuck in local optima. In [PPSN 2026], we proposed GERS, which treats reward shaping as an upper-level problem solved by evolutionary computation to improve the generalization of reinforcement learning agents to unseen environments. At the lower level, an agent is trained on a few environments with a shaped reward; at the upper level, CMA-ES tunes the shaping parameters by observing only the unshaped cumulative reward (score) on validation environments. Even without access to trajectories in the validation environments, it achieved generalization comparable to domain randomization, which uses those trajectories.

キーワード：強化学習，大規模言語モデル，アラインメント，RLHF

大規模言語モデル（LLM）を人の価値観や好みに沿うように調整するアラインメントでは，人や AI が 2 つの応答のどちらが良いかを判定した選好データを用いて，RLHF（人のフィードバックからの強化学習）や DPO などの方法でモデルを学習します．学習する側から見ると，選好を与える評価者はブラックボックスであり，その判断の偏りや誤り，さらには意図的な改ざんが学習の結果を左右します．私達は，有用性と安全性を両立するアラインメントの方法と，選好データに起因する弱点の分析に取り組んでいます．

[NeurIPS 2023 Workshop] では，LLM に選好を判定させる場合に，人に比べて長い応答を好む冗長性バイアス（verbosity bias）があることを示し，このバイアスを測る指標を提案しました．[NeurIPS 2024] では，有用性（報酬）を最大化しつつ安全性を制約の範囲内に保つ制約付き最適化としてアラインメントを定式化し，DPO などの方法を用いて 1 つの指標ずつ段階的にアラインメントする SACPO を提案しました．報酬についてアラインメントしたモデルから，報酬と安全性を両立する最適な方策が導けることを理論的に示し，準最適性と安全性の制約違反の上界を与えています．Alpaca-7B のファインチューニングで，有用性と無害性の両面で代表的な従来手法を上回りました．[AAAI 2026] では，選好ラベルの反転によるデータ汚染（ポイズニング）攻撃を扱い，モデルを攻撃者の目標に誘導するために必要な最小のラベル反転数を，線形制約をもつ凸最適化問題として定式化して，その下界と上界を導出しました．既存の攻撃に後処理として適用すると，同じ効果を保ったまま反転数を大きく減らせることを示しており，RLHF や DPO の弱点を明らかにするとともに，その頑健性を評価する手段を与えています．

Keywords: Reinforcement Learning, Large Language Models, Alignment, RLHF

In the alignment of large language models (LLMs) with human values and preferences, models are trained by methods such as RLHF (reinforcement learning from human feedback) and DPO, using preference data in which humans or AI judge which of two responses is better. From the learner's point of view, the evaluator providing preferences is a black box, and its biases, errors, and even deliberate manipulation affect the outcome of learning. We work on alignment methods that achieve both helpfulness and safety, and on analyzing weaknesses arising from preference data.

In [NeurIPS 2023 Workshop], we showed that LLMs used to label preferences favor longer responses more than humans do (verbosity bias), and proposed a metric to measure this bias. In [NeurIPS 2024], we formulated alignment as constrained optimization that maximizes helpfulness (reward) while keeping safety within a limit, and proposed SACPO, which aligns a model step by step, one metric at a time, using methods such as DPO. We showed theoretically that the optimal policy balancing reward and safety can be derived from a model aligned for reward, and gave upper bounds on suboptimality and safety constraint violation. In fine-tuning Alpaca-7B, SACPO outperformed a leading prior method in both helpfulness and harmlessness. In [AAAI 2026], we studied data poisoning attacks that flip preference labels, formulated the minimum number of label flips needed to steer the model toward an attacker's target as a convex optimization problem with linear constraints, and derived its lower and upper bounds. Applied as post-processing to existing attacks, our method greatly reduces the number of flips while keeping the same effect, which reveals weaknesses of RLHF and DPO and provides a way to evaluate their robustness.

キーワード：強化学習，安全性

強化学習を実際のシステムに使うには，学習した方策を運用する段階だけでなく，学習の途中でも安全性の制約を守る必要があります．しかし，既存の安全な強化学習の多くは，学習から運用までを通して安全性を保つことが困難でした．

[NeurIPS 2025] では，学習から運用までを通して安全性を保証する PLS（Provably Lifetime Safe RL）を提案しました．まず，オフラインのデータから，目標とする累積報酬（リターン）を条件とする教師あり学習によって方策を学習し，運用時には，少数の目標リターンの値をガウス過程を用いて慎重に調整します．目標リターンと実際に得られるリターンの関係を解析してこの設計を正当化し，高い確率で安全性を保ちながら，最適に近い目標リターンを見つけられることを証明しています．実験では，安全性と報酬の両面で既存手法を上回りました．

Keywords: Reinforcement Learning, Safety

To use reinforcement learning in real systems, safety constraints must be satisfied not only when the learned policy is deployed but also during learning. However, most existing safe reinforcement learning methods have difficulty maintaining safety throughout, from learning to deployment.

In [NeurIPS 2025], we proposed PLS (Provably Lifetime Safe RL), which guarantees safety from learning to deployment. A policy is first learned offline by return-conditioned supervised learning, and is then deployed while a small number of target return values are cautiously tuned with Gaussian processes. We justified this design by analyzing the relationship between target and actual returns, and proved that PLS finds near-optimal target returns while guaranteeing safety with high probability. In experiments, PLS outperformed baselines in both safety and reward.

キーワード：強化学習，転移学習，ロバスト性

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

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

Keywords: Reinforcement Learning, Transfer Learning, Robustness

From the perspectives of safety and economics, the strategy of performing reinforcement learning in a simulation and then deploying the resulting policy in a real-world environment is often adopted. This is particularly crucial in the framework of deep reinforcement learning, which uses deep learning to learn policies. Since the number of interactions between the environment and the agent required to learn a policy is vast, leveraging simulations is essential. However, because simulations can't perfectly represent the real world and the real world itself is constantly changing, a gap exists between the simulation environment used for training and the real-world environment where the policy will be deployed. This gap means that a policy trained in simulation might perform poorly and even pose safety risks in the real world.

We are investigating reinforcement learning approaches that account for this gap between simulation and the real world. In [IJCNN 2022], we focused on the differences in state representation between simulation and reality and proposed a method for transferring a policy learned in simulation to a real-world environment. In [NeurIPS 2022], we focused on the differences in state transition probabilities and reward functions and proposed a reinforcement learning approach that maximizes performance in the worst-case scenario. The latter is formulated as a Max-Min optimization problem, which has a deep connection to the robust solution search introduced under "Worst-Case, Risk-Aware, and Bilevel Optimization."

現在は主なテーマではありませんが，これまでに取り組んできた研究です．

キーワード：自動機械学習，深層学習

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

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

Keywords: Automated Machine Learning, Deep Learning

In recent years, deep learning has found extremely broad applications. The performance of deep learning models depends on the architecture of the deep neural network used, including the operations and connectivity between layers. Neural Architecture Search (NAS) is a subfield of AutoML (Automated Machine Learning) that automates the traditional, manual process of designing network architectures using search algorithms.

We are researching a framework called one-shot NAS, which simultaneously optimizes network architecture and parameters in a single training cycle. In particular, we are focusing on methods that use stochastic relaxation to extend parameters into a continuous space and then employ an estimated gradient to search this continuous space for the optimal architecture. Our research includes: a method that leverages natural gradients for architectural search [AAAI 2018], a generalization of this method with a proposed adaptive rule for the gradient step size [ICML 2019], and a way to reduce gradient estimation variance and accelerate the search by introducing a concept of credit assignment used in reinforcement learning [AAAI 2021]. In [IJCNN 2024], we focused on a vulnerability of gradient-based NAS where it can converge to an inappropriate architecture depending on the design of the search space. We used theoretical analysis and numerical experiments to show that one contributing factor is the statistical differences in the intermediate outputs between candidate architectures.

Related Publications:

[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)

キーワード：深層学習，制約対処，進化計算

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

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

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

Keywords: Deep Learning, Constraint Handling, Evolutionary Computation

In simulation-based optimization, penalty function methods and similar approaches are often used for handling constraints due to their versatility and simplicity. Our research in [GECCO 2019] also proposed a constraint-handling method based on a modification operator and an adaptive penalty function. However, these methods are not always effective, such as when the feasible region (the area that satisfies the constraints) consists of multiple disconnected subsets that are narrow in relation to the overall search space [GECCO 2020], or when the constraints are difficult to express explicitly [GECCO 2021].

To address these situations, we have designed an optimization framework for constrained simulation-based optimization that uses deep generative models. A deep generative model uses a deep neural network to learn a mapping from a latent space to a data space. Our method maps the data space to the constraint-satisfying feasible region and the latent space to the design variable space that the optimization algorithm explores. By pre-training such a deep generative model before optimization, it becomes possible to search for solutions that satisfy the constraints.

In [GECCO 2020], for problems with explicit constraints, we proposed a method to train a deep generative model so that the corresponding latent space is a connected set, even when the feasible region is a disconnected set. In [GECCO 2021], we tackled the problem of generating levels for the video game Angry Birds. We proposed a method for training a deep generative model using existing levels as training data, assuming they satisfy the implicit constraints of being "playable and natural levels."

キーワード：マルチフィデリティ最適化，進化計算

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

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

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

Keywords: Multi-fidelity Optimization, Evolutionary Computation

Adjusting simulation fidelity is a crucial decision-making process that determines the trade-off between the time required for optimization and the reliability of the solution. If we ignore optimization difficulties, it would be ideal to use the highest-fidelity simulator possible with the most flexible design variable representation. However, high-fidelity simulators often require significant computational time, limiting the number of simulations that can be run within a given timeframe and making optimization more difficult.

In this research, we developed a method that automatically selects simulation fidelity by focusing on the fact that CMA-ES explores solutions based on the ranking of multiple candidates. Our approach is to use a faster, lower-fidelity simulator if the rank correlation of objective function values is sufficiently high compared to a slower, high-fidelity one. If the rank correlation is low, we switch to the more accurate simulator. Numerical experiments on test problems have confirmed that our method improves both speed and accuracy compared to using a fixed-fidelity simulator [GECCO 2019]. We also applied this technique to a topology optimization problem and observed a similar positive effect [PPSN 2020]. This research not only automates a critical decision-making process but also improves optimization efficiency when multiple simulators are available. As a result, we expect it to be applied to fields like hyperparameter optimization for deep learning, where computational fidelity can be adjusted relatively freely.

We have also conducted a theoretical analysis related to this work. Situations where the true objective function to be optimized differs from the one actually computed by the optimization algorithm (often called a surrogate function) are common, not just in the multi-fidelity setting described above. In these cases, optimizing the surrogate function may not lead to the optimization of the true objective function. In [Algorithmica 2024], we theoretically derived the sufficient conditions for the objective function to be improved when the search is conducted in the direction that improves the surrogate function. We derived the minimum required rank correlation coefficient for these conditions to be met when using Kendall's and Spearman's rank correlation coefficients. We also derived a similar lower bound for the Pearson correlation coefficient with rank-based weighting. The fact that the latter lower bound is a smaller value suggests a potential for improving the methods mentioned above, and further enhancements to these techniques are expected. This work also has implications for analyzing the theoretical validity of worst-case optimization (as previously mentioned), where an approximate value is used as a proxy for the true worst-case function value.