DEIM Forum 2023 1a-2-5

悪条件な目的関数に動的に適応する CMA-ES
清水 洸希†

豊田 正史††† 東京大学大学院 情報理工学系研究科 〒 113–8654 東京都文京区本郷 7–3–1†† 東京大学 生産技術研究所 〒 153–8505 東京都目黒区駒場 4–6–1
E-mail: †{shimizu,toyoda}@tkl.iis.u-tokyo.ac.jp
あらまし

CMA-ES (共分散適応進化戦略) はブラックボックス最適化において非常に優れたアルゴリズムとして知られている．一方で，目的関数が高次元かつ悪条件な場合では，解へと到達するまでに要する反復数が大幅に増加
したり，解への到達に失敗する問題が報告されている．座標選択は，そのような場合に，探索の各反復で更新する座
標 (変数) を選択することで，目的関数の条件数を低減し，探索性能を大幅に向上させる手法である．本論文では，この座標選択手法における，目的関数が良条件な場合にも座標の選択を行うことで発生する性能低下の問題を解決する．
本手法では，最適化の過程において目的関数の条件数を推定し，それに基づいた座標の選択方法を提案する．これにより，目的関数が良条件な場合には座標の分割数を減らすことができ，従来の座標選択法よりも効率的な探索が可能となる．ベンチマーク関数を用いた実験では，良条件な場合には従来の座標選択手法から大幅な改善が見られ，悪条
件な場合には同程度の性能が得られることが確認された．
キーワード 学習理論，汎用機械学習技術，ブラックボックス最適化，進化計算
を O(d) に低減した sep-CMA [4] をはじめとして，共分散行列

1. は じ め にを数本のベクトルで近似する VD-CMA [5], VkD-CMA [6] やブラックボックス最適化は，新幹線車両の設計や機械学習モ

LM-MA [7] など多くの手法が提案されている．また，目的関デルにおけるハイパーパラメタの探索など，我々の身の回りの数が超高次元なだけではなく，強い悪条件性を持つ場合に，前様々な場面に現れる重要な課題である．最適解問題とは，与え述の共分散行列の悪条件性への適応が妨げられ，解へ到達する

られた目的関数を最小化 (あるいは最大化) する入力変数を探までに要する時間の大幅な増加や，局所解を持たない単峰性

索することであるが，ブラックボックス最適化は，その中でも関数にも関わらず解に到達できないといった事例が報告されて目的関数の導関数といった情報が明に与えられないものを指す．

いる [8]．このような問題への解決法として，確率的次元選択

一般に目的関数が持ちうる性質として，悪条件性，多峰性，変CMA-ES [9] が提案されている．この手法では，最適化の各反数間依存性が挙げられるが，ブラックボックス最適化において復において，全ての変数を更新するのではなく，ランダムにいは，目的関数がこのような性質を持つかどうかを事前に知るこ

くつかの軸を選んで更新を行うことで，選択された座標空間にとはできないため，最適化の過程においてこれらの性質に適応おける条件数を低減することが可能となる．また，軸を選択す

可能なアルゴリズムを設計することが必要となる [1] [2]．

る際に，目的関数の各軸の曲率を推定し，曲率の値が近い軸同

CMA-ES (Covariance Matrix Adaptation Evolution Strat-

士を選ぶことで，ランダムな選択よりも性能を向上させる手法

egy) [3] は，連続関数を目的関数とするブラックボックス最適も提案されている [10]．これらの手法により，高次元かつ悪条化において，効率よく解を探索可能なアルゴリズムとして知ら

件な問題における性能の大幅な向上が実現したが，一方で，各れている．CMA-ES は，進化戦略 (ES) に共分散行列を導入し反復中に選択する軸の数をハイパーパラメタとして与える必要た手法で，多変量正規分布 N (m, σ C) に基づいた個体の生成があるため，良条件な問題においても不必要な選択が行われてを行い，多変量正規分布の変数 (平均 m 及び共分散行列 C) としまい，従来の手法よりも性能が悪化するという課題が残った．

2

ステップサイズ σ の最適化を通して解の探索を行う．ここでス

本論文では，この座標選択を改良し，最適化の過程で目的関

テップサイズは，探索地点と最適解との距離に応じて増減する

数の悪条件性に対して選択数を適応可能な手法を提案する．本

スカラー値で，分散共分散行列の補正を行い探索速度を高める

手法では，目的関数の各軸の二階偏微分を有限差分法を用いて役割を持つパラメタである．CMA-ES の特徴として，共分散

推定し，選択された座標空間における条件数が予め設定した許行列の非対角成分が変数間の依存性に，対角成分が各変数軸の容条件数を上回らないという制約のもとにクラスタリングを行

スケールに適応することで，前述の悪条件性や変数間依存性をう．これにより，悪条件関数では座標軸の選択数が増大し，良考慮した解候補の生成を行うことができる点が挙げられる．

条件関数では減少することで，良条件関数の最適化における不CMA-ES の課題としては，目的関数の次元数 d に対し，時32

必要な座標の選択を防ぐことが可能となる．また，入力変数に間計算量が O(d )，空間計算量が O(d ) であることから，高次

よって条件数が変化するような目的関数の場合にも，探索地点

元な最適化問題への適用が困難な点が挙げられるが，これにつにおける条件数に応じた座標の選択を行うことができる．ベン

いては，共分散行列を対角成分に限定することで双方の計算量

チマーク関数を用いた実験では，提案手法を適用することで，

λ∑

目的関数が悪条件な場合には性能が向上し，良条件な場合におdy (t) =いても適用前と同等の性能が得られることを確認した．

dz

(t)

=

3 章では，提案手法である悪条件性適応座標選択のアルゴリズ
ムについて，有限差分法を用いた条件数の推定方法，条件数の推定頻度の設計，許容条件数を満たすクラスタリング法について述べる．そして，4 章においてベンチマーク関数を用いた実験を通して，悪条件な場合に性能が向上し，良条件な場合に適

(4)

(t)

(5)

i

以下，2 章において CMA-ES の概要と確率的次元選択

CMA-ES が悪条件関数に対して優れる理由について説明する．

(t)wi yi ,

λ∑wi z i .

i[Step 4.] Step 3. で 求 め た dy (t) , dz (t) を 用 い て 式 (6),1(7), (8) の通り進化パスを計算する．ここで，µw = ∥w∥,√
11
χd = E[∥N (0, I)∥] ≃ d(1 − 4d + 21d2 ) ∈ R とし, cσ , cc ∈ R

を各進化パスの学習率とする．

用前と同等の性能を得られることを確認する．最後に，5 章でまとめと今後の展望について記す．

2. 関 連 研 究
本章では，CMA-ES のアルゴリズムの概要と，本手法のベースとなる確率的次元選択 CMA-ES について述べる．

2. 1 (µ/µw , λ)-CMA-ES1 ∥p(t+1)2)χd∥ < (1.4 + n+1
σ,
hσ(t+1) =0 else
√
(t+1)
(t)

pσ

= (1 − cσ )pσ +pc(t+1)= (1 − cc )p(t)c+ h(t+1)σ

本節では，CMA-ES のうち最も一般的とされる (µ/µw , λ)-CMA-ES について概要を述べる．CMA-ES は，一般の進化戦略とは異 なり，解候補を直接保持せず，多変 量正規分布
2

N (m(t) , σ (t) C (t) ) により解候補の集団を生成し，目的関数を用いた評価で高評価を得た候補から平均 m(t) と分散共分散行
列 C (t) を更新することで解の探索を行う．ここで t はステップ数とする．
目的関数 f (x) ∈ R, x ∈ Rd を最小化する場合の，具体的なアルゴリズムについて以下に記す．はじめに，変数の初期化を行(6)

cσ (2 − cσ )µw dz,√

cc (2 − cc )µw dy.

(7)

(8)

[Step 5.] Step 4. で求めた進化パスを用いて式 (9), (10),(11) の 通 り 多 変 量 正 規 分 布 の 変 数 の 更 新 を 行 う．こ こ で ，OP (·) ∈ Rn×n は入力ベクトルとそれ自身の直積行列とする．また，ηm ∈ R を平均 m の学習率, ηc1 , ηcµ ∈ R をそれぞれ分散共分散行列 C の rank-one update (式 (11) 右辺二項目),

rank-µ update (式 (11) 右辺三項目) の学習率とし，dσ ∈ R を
ステップサイズの減衰率とする．

う．平均 m(0) ∈ Rd ，分散共分散行列 C (0) ∈ Rd×d ，ステップ
サイズ σ (0) ∈ R をそれぞれ探索領域に応じて決める．また，分(0)
散共分散行列とステップサイズのそれぞれの進化パス pc ∈ Rd
(0)および pσ ∈ Rd を 0 とする．そして，あらかじめ定めた終了

条件を満たすまで以下のステップを繰り返す．

m(t+1) = m(t) + ηm σ (t) dy (t) ,(σ (t+1) = σ (t) exp(

ら，λ 個の個体 z ∈ Rλ×d を生成する．次に式 (2) の通り，C (t)+ ηcµを平方分解し，z (t) との行列積から y (t) ∈ Rλ×d を求める. そして，式 (3) の通り，σ (t) を y (t) の各要素にかけ，平均 m(t)との和から解集団 x

∈R

λ×d

(t+1)
∥pσ
∥

χd

を生成する．

λ
∑

(

(t)

(9)

))
−1

,

C (t+1) = C (t) + ηc1 OP (p(t+1)) − C (t)c[Step 1.] 式 (1) の通り，正規分布 N (0 ∈ Rd , I ∈ Rd×d ) か

(t)

cσ
dσ

(

(10)

)

)

wi OP (yi ) − C (t) .

(11)

i

以上の Step 1.∼Step 5. を繰り返すことで，平均ベクトル mが解に，ステップサイズ σ が 0 に，分散共分散行列 C が 0 に収束することで，多変量正規分布がデルタ関数に収束し，最適解が求まる．

z (t) ∼ N (0, I),√y (t) = z (t) C (t) ,
x

(t)

= m

(t)

+σ

(t)

y

(t)

.

(1)

2. 2 確率的次元選択 CMA-ES(2)

本節では，本手法のベースとなる確率的次元選択 CMA-ES(3)について述べる．同アルゴリズムは目的関数が高次元かつ悪条件な場合に，更新する座標軸をランダムに選択することで，条[Step 2.] Step 1. で生成した解集団 x(t) の各個体について件数の低減とステップサイズのベクトル化を達成し，より高速

f (xi ), (i = 1, ..., λ) から評価値を計算し，昇順に x(t) , y (t) , z (t)な解の探索を実現したアルゴリズムである．以下に具体的なアを個体 (λ) の軸について並び替える．

ルゴリズムを記す．

[Step 3.] 各個体の順位についての重み w ∈ Rλ を用いて，式(4), (5) の通り w と x

(t)

,y

(t)

の個体の軸についての内積を取り，dy (t) , dz (t) ∈ Rd を求める．ここで，重み w は，1 < µ < λとして，w1 >= ··· >
= wµ > 0, wµ+1 , · · · , wλ = 0, ∥w∥1 = 0 を満たすものとする．

最小化したい目的関数を f (x) ∈ R, x ∈ Rd とする．はじめに，平均 m(0) ∈ Rd ，分散共分散行列 C (0) ∈ Rd×d ，ベクトル化されたステップサイズ σ (0) ∈ Rn をそれぞれ探索領域に応じて決め，分散共分散行列とステップサイズのそれぞれの進化パ
(0)

スを pc

(0)

∈ Rd , pσ ∈ Rd = 0 と初期化する．次に，目的関数の入力次元長のインデックスベクトル ι ∈ Rd = (0, 1, ..., d − 1)

を新たに導入する．インデックスベクトルは，予め要素をランれることに起因している．悪条件な場合では条件数の低減の影ダムに並び替え，インデックスの参照を終えた要素の終端地点

響が大きいため性能が改善されるが，良条件な場合にはすでにを e ∈ R = 0 と初期化し，各反復で選択する次元数を s ∈ R と条件数が小さいためその恩恵を受けることができず，変数全体する．そして，予め定めた終了条件を満たすまで以下のステッを更新するためにより多くの反復回数が必要となるためである．

プを繰り返す．

そこで，本手法では，従来の手法のようにあらかじめ決めら[Step 1.] ι から，前世代での終了地点 e から e + s までを取れた選択数で座標軸を分割するのではなく，有限差分法によりり出し，当世代でのインデックスベクトル ι′ ∈ Rs とする．た

求めた各座標軸の二階偏微分値に基づき，あらかじめ設定した′

だし，e + s > d の場合，e から d までのベクトル ι ∈ R

d−eと許容条件数を超えない範囲で座標軸を分割する．これにより，し，ι の要素を全てランダムに並び替え，e = 0 とする．

条件数の分散が大きい悪条件な目的関数の場合には，選択数が′増大し，良条件な場合には減少させることができる．以下にア[Step 2.] 生成した当世代でのインデックスベクトル ι に基づいて，各変数から部分ベクトルおよび部分行列を生成する．
′′

具体的には，平均 m ∈ R ，分散共分散行列 C ∈ R

s×s

，ス

ルゴリズムの詳細を記す．

3. 1 有限差分法を用いた二階偏微分値の推定∈ R ，進化パス p′c ∈ Rs , p′σ ∈ Rs となる．分

目的関数の条件数を推定するにあたり，目的関数の各座標

散共分散行列については，指定されたインデックスの対角成分

軸の二階偏微分値を有限差分法により求める．入力 x ∈ Rd に対して xj , 1 <=j<= d における目的関数 f (x) の二階微分を 3 点

テップサイズ σ′ssおよびそれらの共起成分からなる対称行列を抽出する．

[Step 3.] 正規分布 N (0 ∈ Rs , I ∈ Rs×s ) から，λ 個の個
体 z ′(t) ∈ Rλ×s を生成する．C ′ を平方分解し，z ′(t) との行列√積から y ′(t) ∈ Rλ×s = z ′(t) C ′ を求める. そして，σ ′(t) を公式を用い，h を微小な刻み幅として，
∂2f
∂x2
i

(x1 ,...,xi −h,...,xd )≈ f (x1 ,...,xi +h,...,xd )−2fh(x)+f
,
2

(12)

y ′(t) の各要素にかけ，平均 m(t) の ι′ の要素との和から解集団と算出する．この際に要する目的関数の評価回数は入力次元 dx(t) ∈ Rλ×d = m(t) + σ ′(t) ◦ y ′(t) を生成する (ここで ◦ は二に対して 3 点ずつ評価を行うため，3d となる．

つのベクトル間の要素積を取る演算子とする)．このとき，x(t)

3. 2 二階偏微分値に基づいた座標選択

は通常の CMA-ES と同じ次元の行列となるが，ι′ 以外のイン本手法では，前節で求めた各軸の二階偏微分の値に対して，デックスの次元については，各個体全て同じ値 (m(t) の値) を分割された各クラスタに含まれる二階偏微分値の絶対値の最大取る．

値と最小値の比がハイパーパラメタ α を用いて表現する許容条[Step 4.] 通常の CMA-ES と同様に，目的関数を用いて各個体を評価・順位づけし，昇順に並び替える．また，同様に
重み w ∈ R との個体の軸 (λ の軸) についての内積 dy
λ

′(t)

,

dz ′(t) ∈ Rs を求める．

件数 1 + α を超えないという制約のもとに座標の分割を行う．

3. 3 二階偏微分値を求める頻度
上述のように，目的関数の各軸の二階偏微分を求めるには一回につき 3d の関数評価回数が必要となり，最適化の各反復[Step 5.] Step 4. で求めた dy ′(t) , dz ′(t) をもとに，進化パスのたびに算出する場合その計算コストは無視できないものとなを更新する．このとき，ι′ で指定された要素のみ更新を行い，る．変数間に依存関係を持たない二次関数のように二階偏微分

その他の要素については元の値を維持する．

をした段階で全ての変数が消去され定数となるような場合には，[Step 6.] 進化パスをもとに平均 m(t)，分散共分散行列 C(t)，

最初の一度のみ二階偏微分を求めればよく，計算コストの大幅ステップサイズベクトル σ (t) の更新を行う．ここでも，Step 4.

な削減が可能となる．そこで，本手法では，二階偏微分値の変′と同様に ι で指定された要素のみ更新を行い，その他の要素に化量が元の値の 50%以上となった場合は，次回の反復でも二階ついては元の値を維持する．ステップサイズの更新値は，2 章

偏微分を計算し，そうでない場合には，反復回数が入力次元数

式 (10) にある通りスカラー値であり，提案手法においても，同の倍数となった場合にのみ計算を行う．

′

一反復中での更新値は ι の次元について同一となる．しかし，以下に，提案手法のアルゴリズムの具体的な動作を示す．

提案手法では，更新に用いられる p′σ の次元の組が毎回異なる[Step 1.] 有限差分法により目的関数の各軸の二階偏微分の絶ことから，反復を重ねることでステップサイズベクトルの各要対値を推定する．ここで，現在の最適化における反復数が入力

素は異なる値を取る．

次元数の正数倍となっている場合には，全ての軸について二階以上の Step 1.∼Step 6. を通常の CMA-ES と同様に終了条件

偏微分を求める．それ以外の場合には，前回と前々回に求めたを満たすまで繰り返す．sep-CMA-ES についても分散共分散行

二階偏微分の値が 50% 以上変化した軸についてのみ求め，そ′列の対角成分から ι に対応する次元を抽出することで CMA-ES

れ以外の軸については，前回の二階偏微分の値をそのまま用いの場合と同様に適用することができる．

る．このステップにおいて，d 次元の二階偏微分の絶対値を要

3. 提 案 手 法素とするベクトル a = (a1 , ..., ad ) を得る．

[Step 2.] Step 1. で得られた二階偏微分ベクトルについて，

確率的次元選択 CMA-ES や推定曲率に基づいて座標軸を最小の要素 amin = min(a) を求め，ai <= amin (1 + α) を満た選択する手法は，悪条件な目的関数の場合には高い性能を発揮

す要素を a から抽出する．a から抽出した要素を取り除いたベ

するが，良条件な場合には適用前よりも性能が悪化する．これ

クトルを新たな a とする．これにより，条件数が 1 + α 以下とは，座標選択により一回の反復で更新される変数の数が制限さなる座標軸のクラスタが形成される．

表 1: 実験に用いたベンチマーク関数．R はランダムに生成した n × n の直交行列である．
関数名

定義

SphereEllipsoid
Rot Ellipsoid

fell (x) =

i=1

i−1

fs−ros (x) =∑d−1 2 2[10 (xi − xi+1 )2 + (xi − 1)2 ]
(
)
∑i=1
d
2 2
2
i=2

悪条件性

多峰性

✓

(1000 d−1 xi )2

fellrot (x) = fell (Rx)Chain-Rosenbrock fc−ros (x) =Star-Rosenbrock

変数間依存性∑d 2
fsph (x) =x∑di=1 i100(x1 − xi ) + (1 − xi )

✓

✓

✓

✓

✓

✓

✓

表 2: 適用元のアルゴリズム (sep-CMA, LM-MA, VD-CMA) 毎の比較．解に到達するまでに要した関数の評価回数を示した．解に到達しなかったものについては最適化の過程で最も小さい目的関数値を記載した．いずれの場合も小さい値を持つ手法が優れているとみなすことができる (目標値に到達した場合は，目標値未到達の場合よりも優れているとみなす)．各関数毎に最も良い結果が得られた数字を太字で示した．
sep-CMA +ランダム座標選択

sep-CMA

ベースライン

sep-CMA + 動的座標選択
提案手法

105 -D Sphere1.45 × 107

2.22 × 107

1.60 × 107

105 -D Ellipsoid6.57 × 107

4.45 × 107

2.05 × 107

104 -D Rot Ellipsoid

8623479.1 (目標値未到達) 24458.8 (目標値未到達)

9125044.1 (目標値未到達)

104 -D Chain-Rosenbrock 6813.8 (目標値未到達)

9311.2 (目標値未到達)

2.04 × 108

104 -D Star-Rosenbrock2384.8 (目標値未到達)

35.9 (目標値未到達)

2290.9 (目標値未到達)

LM-MA

LM-MA +ランダム座標選択

LM-MA + 動的座標選択

ベースライン

提案手法

105 -D Sphere1.03 × 107

1.87 × 107

1.15 × 107

105 -D Ellipsoid2335.5 (目標値未到達)

571053.2 (目標値未到達)

1.57 × 107

104 -D Rot Ellipsoid1.87 × 108

566.2 (目標値未到達)

2.05 × 108

104 -D Chain-Rosenbrock 1.90 × 108

9895.4 (目標値未到達)

1.06 × 108

104 -D Star-Rosenbrock1343.1 (目標値未到達)

106.1 (目標値未到達)

1415.9 (目標値未到達)

VD-CMA

VD-CMA +ランダム座標選択 VD-CMA + 動的座標選択
ベースライン

提案手法

105 -D Sphere1.04 × 107

2.32 × 107

1.45 × 107

105 -D Ellipsoid1.69 × 108

6.21 × 107

1.57 × 107

104 -D Rot Ellipsoid1327940.9 (目標値未到達) 6948.4 (目標値未到達)

1342470.9 (目標値未到達)

104 -D Chain-Rosenbrock8830.1 (目標値未到達)

8985.3 (目標値未到達)

1.71 × 108

104 -D Star-Rosenbrock926.3 (目標値未到達)

67.7 (目標値未到達)

823.9 (目標値未到達)[Step 3.] Step 2. において a から要素を抽出したことで，aを用いた．目的関数毎の関数評価回数に対する目的関数値の推の要素数が 0 となった場合は，クラスタリングを終了し，そう移を図 1 に示した．実線 (solid line) が従来手法，破線 (dashedでない場合は，Step 2. を繰り返す．

line) が従来手法に提案手法 (適応座標選択) を適用したもの，
点線 (dotted line) が従来手法にランダム座標選択を適用した

4. 評 価 実 験

ものを表している．赤線が sep-CMA, 黒線が LM-MA, 水色線

本章では，提案手法のベンチマーク関数における性能を確

が VD-CMA に関する各アルゴリズムに対応している．また，認する．評価実験に用いたベンチマーク関数を表 1 に示した．

表 2 に，各適用元アルゴリズム毎に，目標値に到達するまでに

(0)

(0)

= I,

要した関数の評価回数，目標値に到達しなかった場合は最大評

σ (0) = 1.0, λ = 4 + 3⌊ln (d)⌋ とし，目的関数の目標値は 10−10 ，価回数内で得られた最も小さな目的関数値を示した．各ベンチ

最大評価回数は λ × 10 と設定した．

マーク関数に対して最も良い結果が得られた数字を太字で表し

いずれの関数の場合も初期値は，m= U (−5, 5), C

7

4. 1 ベンチマーク関数を用いた各アルゴリズムの比較
本節では，悪条件適応座標選択を sep-CMA-ES, LM-MA,ている．

Sphere 関数を用いた比較

VD-CMA に適用し，従来のアルゴリズム，従来のアルゴリズ

Sphere 関数は表 1 の通り，いずれの性質も持たない最も解

ムにランダム座標選択を適用したものとの比較を行う．各アルの探索が容易な関数である．図 1 (a) より，いずれの適用元ア

ゴリズムにおけるハイパーパラメータは，提案手法における許ルゴリズムの場合にも，座標選択を適用しない手法において最容条件数を α = 0.5 とし，ランダム座標選択における座標選択

も良い結果が得られ，ランダム座標選択が最も悪い結果となり，数を 100 とした．それ以外については，各論文で推奨される値提案手法を適用した場合はその中間の性能が得られた．Sphere図 1: 目的関数毎の関数評価回数に対する目的関数値の推移．より左下を推移するアルゴリズムが優れているとみなすことができる．実線 (solid line) が従来手法，破線 (dashed line) が従来手法に提案手法 (適応座標選択) を適用したもの，点線 (dotted line) が従来手法にランダム座標選択を適用したものを表している．赤線が sep-CMA, 黒
線が LM-MA, 水色線が VD-CMA に関する各アルゴリズムに対応している．Sphere 関数においては，黒線の実線(LM-MA) と水色線の実線 (VD-CMA) 及び黒破線 (LM-MA+ 提案手法) と水色破線 (VD-CMA+ 提案手法) が同様の推移をするためグラフ上では線が重なっている．Ellipsoid 関数においては，黒破線 (LM-MA+ 提案手法) と水色破線 (VD-CMA+ 提案手法) が同様の推移をするためグラフ上では線が重なっている．

関数は表 1 からも明らかなように，条件数は 1 の完全に良条る．図 1 (b) より，いずれの適用元アルゴリズムの場合にも，件な関数であるため，座標選択により条件数を低減させること提案手法を適用した際に最も良い結果が得られた．ランダム座ができない関数である．ランダム座標選択では，ハイパーパラ

標選択では，LM-MA に適用した場合に，適用前よりも性能がメータとして与えた座標選択数に基づいて必ず座標軸を分割す

悪化することが明らかとなった．また，LM-MA では適用前でるため，適用前と比べて約 50% 関数評価回数が増大しており，

は目標値に到達することができていないが，提案手法を適用す

性能が大幅に悪化している．一方で，提案手法では，二階偏微ることで，表 1 の通り VD-CMA に提案手法を適用した場合と分を推定したことにより，座標を分割することなく探索を行っほぼ等しい関数評価回数で解に到達することができており，提た結果，二階偏微分の推定に必要なコストのみが加算され，性案手法の優位性を示している (図 1 (b) では黒破線 (LM-MA+

能の悪化を適用前と比べて約 10% に抑えることができている．

提案手法) と水色破線 (VD-CMA+提案手法) が重なってプロッ

Ellipsoid 関数を用いた比較
Ellipsoid 関数は表 1 の通り，悪条件性のみを持つ関数であトされている)．

図 2: sep-CMA における許容条件数と性能の関係．Rot-Ellipsoid 関数では，許容条件数 1.3 以上で座標選択が行われずクラスタ
数 1 となるため，値の差は誤差である．Rot-Ellipsoid 関数の許容条件数 3 以降は許容条件数 2 の結果をプロットした．

図 3: LM-MA における許容条件数と性能の関係．Rot-Ellipsoid 関数では，許容条件数 1.3 以上で座標選択が行われずクラスタ数

1 となるため，値の差は誤差である．Rot-Ellipsoid 関数の許容条件数 3 以降は許容条件数 2 の結果をプロットした．

Rot Ellipsoid 関数を用いた比較ることができない．実際には二階偏微分の値は各軸についてほ

Rot Ellipsoid 関数は表 1 の通り，ランダムに生成した直行行

ぼ等しい値を取り，それに基づいて条件数を推定すると良条件

列を用いて回転させた入力ベクトルを Ellipsoid 関数で評価すな関数であると誤認してしまい，今回のケースでは提案手法でる関数であり，悪条件性と変数間依存性を持つ．図 1 (c) より，は座標の分割が行われず，適用前の手法と同様の結果が得られこのケースでは，提案手法は優位性を示すことはできなかった．

た (Sphere 関数の場合と同様に，二階偏微分の推定コストの分

Rot Ellipsoid 関数は，入力ベクトルを直行行列で回転させてだけ性能が僅かに悪化している)．

いるが，この写像により，入力の各軸全体に均一に依存関係がChain-Rosenbrock 関数を用いた比較発生するため，二階偏微分の値だけでは条件数を十分に推定す

Chain-Rosenbrock 関数は表 1 の通り，変数間依存性と多峰図 4: LM-MA における許容条件数と性能の関係．Rot-Ellipsoid 関数では，許容条件数 1.3 以上で座標選択が行われずクラスタ数

1 となるため，値の差は誤差である．Rot-Ellipsoid 関数の許容条件数 3 以降は許容条件数 2 の結果をプロットした．

性を持つ関数である．図 1 (d) よりこの場合には，いずれの適と性能の関係を図示した．Ellipsoid 関数，Chain-Rosenbrock

用元アルゴリズムについても提案手法を適用することで大幅な関数については関数の評価回数を，Rot-Ellipsoid 関数，Star-

性能の良化がみられた．Chain-Rosenbrock 関数は，良条件なRosenbrock 関数については最大評価回数内における目的関数関数であると一般的に見なされており，条件数を軽減することの最小値を示した．Rot-Ellipsoid 関数では，許容条件数が 1.3で性能を向上させる手法である座標分割によって性能が向上す以上の場合でクラスタ数が 1 となり座標分割が行われないため，ることは，直感に反する現象であると言える．実際にランダム値の差は試行毎の誤差である．また，Rot-Ellipsoid 関数にお座標分割では，いずれの場合にも性能が悪化している．今回得ける許容条件数 3 以上の結果は，許容条件数 2 で行ったシミュ

られた結果は，非常に興味深い事象であり，次節でその分析をレーションの結果をプロットした．Chain-Rosenbrock 関数に行う．

ついては，許容条件数 1.1, 1.3, 5.0 では，目的関数値が目標値

Star-Rosenbrock 関数を用いた比較
Star-Rosenbrock 関数は表 1 の通り，悪条件性，変数間依存に到達しなかったため，最大評価回数の値をプロットした．
図 3 に LM-MA に提案手法を適用した場合の許容条件数性，多峰性を持つ関数である．一つ目の変数とそれ以降の変数と性能の関係を図示した．Ellipsoid 関数，Chain-Rosenbrockとの間にのみ依存関係を持つことが大きな特徴である．図 1 (e)関数，Rot-Ellipsoid 関数については関数の評価回数を，Star-

よりこの場合には，いずれの適用元アルゴリズムについても，

Rosenbrock 関数については最大評価回数内における目的関数

ランダム座標選択を行った場合に最良の結果が得られ，提案手の最小値を示した．Rot-Ellipsoid 関数では，許容条件数が 1.3法を用いた場合には適用前とほぼ同等の結果となった．本関数

以上の場合でクラスタ数が 1 となり座標分割が行われないため，

は，前述の通り，一つ目の変数がそれ以外の全ての変数に対し値の差は試行毎の誤差である．また，Rot-Ellipsoid 関数におて依存関係を持つため，座標を分割する際に一つ目の変数が均ける許容条件数 3 以上の結果は，許容条件数 2 で行ったシミュ

等な頻度で他の軸のクラスタに割り当てられるランダム座標分

レーションの結果をプロットした．Rot-Ellipsoid 関数の許容条割が最も適していたと考えられる．

件数 1.1 では，目的関数値が目標値に到達しなかったため，最4. 2 許容条件数と性能の関係

大評価回数の値をプロットした．Chain-Rosenbrock 関数につ提案手法では，許容条件数をハイパーパラメタとして事前にいては，許容条件数 1.3, 5.0 では，目的関数値が目標値に到達設定する必要がある．そこで本節では，許容条件数の値をどのしなかったため，最大評価回数の値をプロットした．

範囲に設定するべきであるかを確認するために，各アルゴリ

図 4 に VD-CMA に提案手法を適用した場合の許容条件数

ズムとベンチマーク関数毎に許容条件数と性能の関係をシミュと性能の関係を図示した．Ellipsoid 関数，Chain-Rosenbrockレーションを通して分析する．以下では，許容条件数を [1.1,関数については関数の評価回数を，Rot-Ellipsoid 関数，Star-

1.3, 1.5, 2.0, 3.0, 4.0, 5.0, 11.0] の範囲で実験を行った．

Rosenbrock 関数については最大評価回数内における目的関数

図 2 に sep-CMA に提案手法を適用した場合の許容条件数の最小値を示した．Rot-Ellipsoid 関数では，許容条件数が 1.3

回避する性能が向上する可能性が示唆されているが，本事象に関しては更なる分析が必要であると言える．

5. お わ り に
本論文では，CMA-ES において座標選択を行う場合に，選択する座標数を目的関数の悪条件性に適応させる悪条件性適応
座標選択手法を提案した．本手法により，目的関数が悪条件な場合には選択する座標数が増大し，良条件な場合では減少する
ことで，従来の座標選択が抱えていた良条件関数における性能の低下という課題を解決した．また，Chain-Rosenbrock 関数のように，探索地点によって条件数が変化するような目的関数
図 5: LM-MA に提案手法を適用した場合のクラスタ数 (赤線)と条件数 (青線) の変化．黄線は通常の LM-MA の条件数の変化を表している．縦軸左が各反復におけるクラスタ数，縦軸右が各反復における条件数を示している．

においても提案手法により性能が向上することを確認した．
今後の展望として，設定した許容条件数と得られた座標軸のクラスタから，最適化問題における目的関数の景観分析や，大規模機械学習モデルにおけるパラメタの分布の分析に応用することが期待される．

以上の場合でクラスタ数が 1 となり座標分割が行われないため，値の差は試行毎の誤差である．また，Rot-Ellipsoid 関数における許容条件数 3 以上の結果は，許容条件数 2 で行ったシミュ
レーションの結果をプロットした．Chain-Rosenbrock 関数については，許容条件数 1.1, 1.3, 5.0, 11.0 では，目的関数値が目標値に到達しなかったため，最大評価回数の値をプロットした．
以上の実験から，いずれの場合でも許容条件数を 1.5 4.0 の範囲に設定することで，プロットの曲線がベースラインの線を概ね下回り，良好な性能を示すことが明らかとなった．厳密に最も優れる許容条件数は，目的関数とアルゴリズムの組み合わせによって異なるため，更なる分析が必要であると言える．

4. 3 Chain-Rosenbrock 関数の最適化における提案手法の動作の分析
前節で述べた通り，一般的に良条件とされる Rosenbrock 関数の最適化に提案手法を用いることで，直感に反し優れた結果が得られた．本節では，最適化中における提案手法のクラスタ
リングの振る舞いや条件数の変化から本事象の分析を行う．
図 5 に，LM-MA に提案手法を適用した場合のクラスタ数(赤線) 及び推定条件数の絶対値 (青線) の変化を示した．また，黄線は通常の LM-MA の条件数の変化を表している．本図より，Chain-Rosenbrock 関数では最適化の反復中に大きく条件数が変化していることが読み取れる．実際に，表 1 に示す

Chain-Rosenbrock 関数の式を二階偏微分すると，

202 + 400(3x2 − xi+1 ) , 1 < i < d − 1
∂ f
i
= =
=
, (13)∂x2i
200,d = n2となり，入力の値 (各反復における探索の中心点) によって，値が大きく変化することが分かる．図 5 より，提案手法におけるクラスタ数は，条件数の変化に応じて同様の軌跡を描いており，
条件数が増大した場合にはクラスタ数を増やすことで座標軸をより分割し，条件数が減少した場合には座標の分割を抑制していることが分かる．Chain-Rosenbrock 関数のように多峰性を持ち，条件数が大きく変化するような目的関数について，提案
手法のように条件数を考慮した座標分割を行うことで局所解を謝

辞

本研究は，JST CREST JPMJCR19A4 及び JSPS 科研費

JP21H03445 の支援を受けたものである．
文

献[1] 坂井節子, 高濱徹行. 最適化手法における関数評価回数の削減手
法 -ポテンシャルモデルに基づく比較推定法の提案-. 数理解析
研究所講究録, Vol. 1548, No. 7, pp. 61–70, 2007.
[2] 秋本洋平. Evolution Strategies による連続最適化 CMA-ESの設計原理と理論的基盤. 進化計算の時代 特集号, Vol. 60, pp.
292–297, 2016.
[3] Nikolaus Hansen. The CMA evolution strategy: A tutorial.
2016.
[4] Raymond Ros and Nikolaus Hansen. A Simple Modiﬁcationin CMA-ES Achieving Linear Time and Space Complexity.
In Parallel Problem Solving from Nature – PPSN X, Vol.
5199, pp. 296–305. Springer Berlin Heidelberg, 2008.
[5] Youhei Akimoto, Anne Auger, and Nikolaus Hansen.
Comparison-based natural gradient optimization in high dimension. In Proceedings of the 2014 Conference on Genetic
and Evolutionary Computation - GECCO ’14, pp. 373–380.
ACM Press, 2014.
[6] Youhei Akimoto and Nikolaus Hansen. Projection-Based restricted covariance matrix adaptation for high dimension. In
Proceedings of the Genetic and Evolutionary Computation
Conference 2016, GECCO ’16, pp. 197–204, New York, NY,
USA, July 2016. Association for Computing Machinery.
[7] Ilya Loshchilov, Tobias Glasmachers, and Hans-Georg
Beyer. Large scale Black-Box optimization by LimitedMemory matrix adaptation. IEEE Trans. Evol. Comput.,Vol. 23, No. 2, pp. 353–358, April 2019.
[8] Ilya Loshchilov. LM-CMA: An Alternative to L-BFGS for
Large-Scale Black Box Optimization. Evolutionary Computation, Vol. 25, No. 1, pp. 143–171, 2017.
[9] 清水洸希, 小宮山純平, 豊田正史. CMA-ES における高次元・悪条件最適化のための確率的次元選択手法. 電子情報通信学会論文
誌 D, Vol. J103-D, No. 05, 2020.
[10] Hiroki Shimizu and Masashi Toyoda. CMA-ES with Coordinate Selection for High-Dimensional and Ill-Conditioned
Functions. Proceedings of the Genetic and Evolutionary
Computation Conference Companion, p. 209–210, 2021.