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

設計原理と理論解析Design Principles and Theory

CMA-ES をはじめとする進化計算が「なぜうまく働くのか」を数理的に明らかにし,その理解を新しいアルゴリズムの設計に生かしています.We study mathematically why evolutionary algorithms such as CMA-ES work, and use this understanding to design new algorithms.

情報幾何に基づく CMA-ES の設計原理と収束解析Information-Geometric Foundations of CMA-ES and Their Convergence Analysis

キーワード:進化計算,情報幾何,自然勾配,理論解析Keywords: Evolutionary Computation, Information Geometry, Natural Gradient, Theoretical Analysis

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 のような共分散行列適応法との隔たりを埋める一歩です.平均ベクトルの収束に必要な上記の条件を取り除くことや,二次関数以外の関数への拡張が今後の課題です.

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.

関連する論文Related Publications

  1. PPSN 2010 CORE A
    Bidirectional Relation between CMA Evolution Strategies and Natural Evolution Strategies
    Youhei Akimoto, Yuichi Nagata, Isao Ono, Shigenobu Kobayashi
    PPSN 2010: Parallel Problem Solving from Nature -- PPSN XI, pp. 154–163 (2010)
  2. Algorithmica 2012
    Theoretical Foundation for CMA-ES from Information Geometry Perspective
    Youhei Akimoto, Yuichi Nagata, Isao Ono, Shigenobu Kobayashi
    Algorithmica, Vol.Vol. 64(4), pp. 698–716 (2012)
  3. PPSN 2026 学生が筆頭Student-led CORE A
    Beyond IGO-Flow: Toward Convergence Analysis of IGO in Continuous Spaces
    Ryosuke Kimura, Youhei Akimoto
    Parallel Problem Solving from Nature – PPSN XIX, 19th International Conference, PPSN 2026, Trento, Italy, August 29 – September 2, 2026, Proceedings, Part I, pp. 20–35 (2026)

ドリフト解析による進化計算の収束解析Convergence Analysis of Evolutionary Computation via Drift Analysis

キーワード:進化計算,理論解析Keywords: Evolutionary Computation, Theoretical Analysis

進化戦略(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 2022] ではこの困難さを緩和し,非エリート保存戦略の収束解析を可能にするために,ドリフト解析と常微分方程式の安定性解析を組み合わせた収束証明の枠組みを提案しています.これを,非エリート保存戦略のESに適用し,Sphere関数のもとでの一次収束を示すことに成功しています.適用事例が少ないため,より一般の強凸関数での解析が望まれます.また,CMA-ESでも同様の解析を実現することが課題として挙げられます.

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

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.

関連する論文Related Publications

  1. SIOPT 2022 JCR Q1 Scopus Q1
    Global Linear Convergence of Evolution Strategies on More than Smooth Strongly Convex Functions
    Youhei Akimoto, Anne Auger, Tobias Glasmachers, Daiki Morinaga
    SIAM Journal on Optimization, Vol.Vol. 32(2), pp. 1402–1429 (2022)
  2. SPA 2022 JCR Q2 Scopus Q2
    An ODE Method to Prove the Geometric Convergence of Adaptive Stochastic Algorithms
    Youhei Akimoto, Anne Auger, Nikolaus Hansen
    Stochastic Processes and their Applications, Vol.Vol. 145, pp. 269–307 (2022)
  3. IEEE TEVC 2024 学生が筆頭Student-led JCR Q1 Scopus Q1
    Convergence Rate of the (1+1)-Evolution Strategy on Locally Strongly Convex Functions with Lipschitz Continuous Gradient and their Monotonic Transformations
    Daiki Morinaga, Kazuto Fukuchi, Jun Sakuma, Youhei Akimoto
    IEEE Transactions on Evolutionary Computation, Vol.Vol. 28(2), pp. 501–515 (2024)
  4. ECJ 2025 JCR Q1 Scopus Q1
    Tail Bound on Runtime of Categorical Compact Genetic Algorithm
    Ryoki Hamano, Kento Uchida, Shinichi Shirakawa, Daiki Morinaga, Youhei Akimoto
    Evolutionary Computation, Vol.Vol. 33(2), pp. 141–189 (2025)