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

CMA-ES の改良と拡張Improving and Extending CMA-ES

最新の CMA-ES である dd-CMA-ES をはじめ,高次元の問題,ハイパーパラメータの自動調整,離散変数と連続変数が混在する問題など,CMA-ES が扱える問題の範囲を広げています.Starting from dd-CMA-ES, the latest version of CMA-ES, we broaden the problems CMA-ES can handle, including high-dimensional problems, automatic hyperparameter adaptation, and problems with mixed discrete and continuous variables.

高次元最適化のための CMA-ES の高速化Accelerating CMA-ES for High-Dimensional Optimization

キーワード:進化計算,連続最適化Keywords: Evolutionary Computation, Continuous Optimization

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

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

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

[ECJ 2020]では,共分散行列の適応を高速化する3つの独立したアイディアを提案しています.これらにより,従来の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 の変種より優れていることを示しています.実装は公開しています.

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

関連する論文Related Publications

  1. GECCO 2014 口頭Oral CORE A
    Comparison-based Natural Gradient Optimization in High Dimension
    Youhei Akimoto, Anne Auger, Nikolaus Hansen
    GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, pp. 373–380 (2014)
  2. GECCO 2016 口頭Oral CORE A
    Projection-Based Restricted Covariance Matrix Adaptation for High Dimension
    Youhei Akimoto, Nikolaus Hansen
    Genetic and Evolutionary Computation Conference, GECCO 2016, Denver, Colorado, USA, July 20-24, 2016, pp. 197–204 (2016)
  3. PPSN 2016 CORE A Best Paper NominationBest Paper Nomination
    Online Model Selection for Restricted Covariance Matrix Adaptation
    Youhei Akimoto, Nikolaus Hansen
    Parallel Problem Solving from Nature - PPSN XIV - 14th International Conference, Edinburgh, UK, September 17-21, 2016, Proceedings, pp. 3–13 (2016)
  4. ECJ 2020 JCR Q1 Scopus Q1
    Diagonal Acceleration for Covariance Matrix Adaptation Evolution Strategies
    Youhei Akimoto, Nikolaus Hansen
    Evolutionary Computation, Vol.Vol. 28(3), pp. 405–435 (2020)
  5. ACM TELO 2026 採録決定To appear Scopus Q1
    dd-RCMA-ES: CMA-ES with Projection-Based Restricted Covariance Matrix Adaptation for High-Dimensional Problems
    Youhei Akimoto, Nikolaus Hansen
    ACM Transactions on Evolutionary Learning and Optimization (2026)

CMA-ES の集団サイズ適応と学習率適応Population Size Adaptation and Learning Rate Adaptation for CMA-ES

キーワード:進化計算,連続最適化,パラメータ適応Keywords: Evolutionary Computation, Continuous Optimization, Parameter Adaptation

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 は既定の集団サイズのままでも,高コストな学習率の調整なしに多峰性やノイズのある問題で良い性能を示すことを確認しています.集団サイズを増やすことと学習率を下げることは,いずれも更新の精度を高めるための手段であり,二つの方法は同じ考え方の異なる実現になっています.

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.

関連する論文Related Publications

  1. GECCO 2016 口頭Oral学生が筆頭Student-led CORE A
    Population Size Adaptation for the CMA-ES Based On the Estimation Accuracy of the Natural Gradient
    Kouhei Nishida, Youhei Akimoto
    Genetic and Evolutionary Computation Conference, GECCO 2016, Denver, Colorado, USA, July 20-24, 2016, pp. 237–244 (2016)
  2. GECCO 2018 口頭Oral学生が筆頭Student-led CORE A
    PSA-CMA-ES: CMA-ES with Population Size Adaptation
    Kouhei Nishida, Youhei Akimoto
    Proceedings of Genetic and Evolutionary Computation Conference, GECCO 2018, Kyoto, Japan, July 15-19, 2018, pp. 865–872 (2018)
  3. GECCO 2023 口頭Oral CORE A Best Paper NominationBest Paper Nomination
    CMA-ES with Learning Rate Adaptation: Can CMA-ES with Default Population Size Solve Multimodal and Noisy Problems?
    Masahiro Nomura, Youhei Akimoto, Isao Ono
    GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 839–847 (2023)
  4. ACM TELO 2025 Scopus Q1
    CMA-ES with Learning Rate Adaptation
    Masahiro Nomura, Youhei Akimoto, Isao Ono
    ACM Transactions on Evolutionary Learning and Optimization, Vol.Vol. 5(1), Art. 6, pp. 1–28 (2025)

カテゴリ変数と連続変数が混在する問題の最適化Optimization of Mixed Categorical-Continuous Variables

キーワード:進化計算,混合変数最適化Keywords: Evolutionary Computation, Mixed-Variable Optimization

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

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

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.

関連する論文Related Publications

  1. GECCO 2025 口頭Oral CORE A
    Challenges of Interaction in Optimizing Mixed Categorical-Continuous Variables
    Youhei Akimoto, Xilin Gao, Ze Kai Ng, Daiki Morinaga
    GECCO 25: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 692–700 (2025)
  2. PPSN 2026 学生が筆頭Student-led CORE A
    Mixed-Categorical Black-Box Optimization via Information-Geometric Bilevel Decomposition
    Marc Ong, Shinichi Shirakawa, Youhei Akimoto
    Parallel Problem Solving from Nature – PPSN XIX, 19th International Conference, PPSN 2026, Trento, Italy, August 29 – September 2, 2026, Proceedings, Part III, pp. 66–81 (2026)

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