DEIM Forum 2019 A4-3

高次元悪条件最適化問題のための確率的次元選択 CMA-ES
清水 洸希†

小宮山純平††

豊田正史††† 東京大学大学院 情報理工学系研究科 〒 113–8654 東京都文京区本郷 7–3–1†† 東京大学 生産技術研究所 〒 153–8505 東京都目黒区駒場 4–6–1
E-mail: †{shimizu,jkomiyama,toyoda}@tkl.iis.u-tokyo.ac.jp
あらまし 本論文では，高次元かつ悪条件な目的関数の最適化のために，CMA-ES において目的関数の次元を任意の次元の組に確率的に分割し，一組ずつ更新するアルゴリズムを提案する．CMA-ES は，進化戦略 (ES) に分散共分散行列を導入することで，変数間の依存関係を考慮した最適化を行うことを可能としたアルゴリズムで，ブラックボッ
クス最適化問題において優れた性能を発揮している．一方で，100,000 次元の Ellipsoid 関数のような非常に高次元かつ悪条件な最適化問題においては十分な最適化が行えないことが報告されている [1]．本研究では，CMA-ES の変数の一つであるステップサイズが，目的関数が悪条件である場合に，分散共分散行列の適応の妨げとなっていることが，原因の一つとして考えられることを実験を通して確認した．この問題の解決のため，提案手法では，各世代で目的関数の次元 d を次元 s (0 < s <= d) の組に確率的に分割し，その次元の組ごとに分散共分散行列の適応とステップサイズの更新を行う．実験では，Ellipsoid 関数や Star 型の Rosenbrock 関数といったベンチマーク関数を用いて，提案手法と既存の CMA-ES および L-BFGS 法との比較を行い，その有効性を確認した．
キーワード 進化計算, 最適化, 機械学習

1. は じ め に最適化問題とは，与えられた目的関数に対して，それを最小化あるいは最大化する変数の組を求める問題である．特に目的関数が明示的に与えられておらず，入力に対する出力のみが得られるような場合をブラックボックス最適化と呼ぶ．

の対応, CSA (Cumulative Step-size Adaptation) を用いた変数のスケール性を考慮したステップサイズの更新により，一般に前述の悪条件性，多峰性，変数間依存性を持つ目的関数に対して有効であるとされている [5]．

CMA-ES の欠点として，目的関数の次元数 d に対し，時間計算量が O(d3 )，空間計算量が O(d2 ) であることから，高次

ブラックボックス最適化は実世界においても，鉄道のダイヤ

元な最適化問題への適用が困難な点が挙げられるが，これにつグラム作成や航空機の翼の設計等多数の応用が存在する．実

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

世界のブラックボックス最適化において想定される目的関数の算量を O(d) に低減した sep-CMA-ES [6] をはじめとして，さ特徴として，悪条件性，多峰性，変数間依存性が指摘されていまざまな手法が提案されている．特に sep-CMA-ES はその計る [2] [3]．また，近年では，ニューラルネットワークのように算量の小ささにも関わらず，目的関数に変数間の依存性がない

数十万次元に及ぶ非常に高次元なモデルも主流であり，このよ

場合は，CMA-ES より高速に解を発見することができ，非常うなモデルでは前述の特徴がより現れやすいと考えられる．そに優れたアルゴリズムである．これらの計算量を改善したアルのため，これらの特徴に対して有効かつ高次元においても適用

ゴリズムの貢献により 10,000 次元程度までの最適化問題への可能なアルゴリズムの開発は社会的に非常に大きな意義が存在

拡張を可能としたが，それ以上の超高次元な場合では依然としすると言える．

て課題が存在する．Loshchilov は，原因については言及してCMA-ES (Covariance Matrix Adaptation Evolution Strat-

いないものの，実験を通して sep-CMA-ES は 100,000 次元のegy) [4] はブラックボックス最適化における最も優れたアルゴリ

Ellipsoid 関数について，十分な最適化を行えないことを指摘し

ズムの 1 つとして知られている．CMA-ES は，進化戦略 (ES)ている [1]．本論文では，実験を通して，この問題の原因が，目に分散共分散行列を導入したアルゴリズムで，多変量正規分布

的関数が超高次元なだけではなく，非常に強い悪条件性を持つN (m, σ C) に基づいた個体の生成を行い，多変量正規分布の場合に，ステップサイズの収束と分散共分散行列の収束が大き

変数 (平均 m 及び分散共分散行列 C) とステップサイズ σ のく乖離し，探索を妨げているためであることを確かめた．

2

最適化を通して解の探索を行う．ここでステップサイズは，探この問題を解決するため，本論文では確率的に次元を選択す

索地点と最適解との距離に応じて増減するスカラー値で，分散る CMA-ES を提案する．提案手法では，目的関数の次元を任共分散行列の補正を行い探索速度を高める役割を持つパラメ

意の次元の組に確率的に分割する．そして世代毎に組を選択

タである．CMA-ES の持つ大きな特徴として，分散共分散行

し，その選択された次元について，平均，分散共分散行列，ス列の適応による変数間の依存性を考慮した個体生成，大域ス

テップサイズといった変数の更新を行う．このとき，ステップ

テップサイズによる解探索の効率の向上が挙げられ，rank-one

サイズを従来のようなスカラー値ではなく，ベクトルを用いてupdate と rank-µ update の組み合わせによる個体数の増加へ表現する．このように，各世代で一部の次元のみを用いて変数を更新することで，次元間での極端なスケールの違いに適満たすものとする．

応することが可能となり，超高次元の Ellipsoid 関数や Star 型

Rosenbrock 関数といった悪条件性が非常に強い関数の最適化において，従来の CMA-ES よりも探索の速さや解の優劣の観

dy (t) =

λ
∑

(t)

(4)

(t)

(5)

wi yi

i

点から優れた結果を得た．
以下，2 章で関連研究について説明し，次に 3 章で既存のdz (t) =CMA-ES を用いた実験を通して前述の問題の原因について検λ∑wi z ii

討を行う．そして，4 章でその問題を解決するため，確率的に次元を選択する CMA-ES を提案し，5 章で実験を通してその評価を行う．最後に 6 章でまとめと今後の展望について述べる．

2. 関 連 研 究[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

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

本章では，CMA-ES のアルゴリズムの概要と，目的関数の特徴に応じた CMA-ES の改良の研究について述べる．

2. 1 CMA-ES
本節では，CMA-ES のうち最も一般的とされる (µ/µw , λ)-1 ∥p(t+1)
2∥ < (1.4 + n+1)χdσ
hσ(t+1) =0 else√(t+1)(t)= (1 − cσ )pσ +CMA-ES について概要を述べ，次に sep-CMA-ES について述

pσ

べる．最後に CMA-ES のハイパーパラメタの設定について述

pc(t+1) = (1 − cc )p(t)cべる．

+ h(t+1)σ

2. 1. 1 (µ/µw , λ)-CMA-ES
CMA-ES は，一般の進化戦略とは異なり，解候補を直接保2(6)cσ (2 − cσ )µw dz√

cc (2 − cc )µw dy

(7)

(8)

[Step 5.] Step 4. で求めた進化パスを用いて式 (9), (10),

持せず，多変量正規分布 N (m(t) , σ (t) C (t) ) により解候補の集(11) の 通 り 多 変 量 正 規 分 布 の 変 数 の 更 新 を 行 う．こ こ で ，団を生成し，目的関数を用いた評価で高評価を得た候補から平OP (·) ∈ Rn×n は入力ベクトルとそれ自身の直積行列とす

均 m(t) と分散共分散行列 C (t) を更新することで解の探索を行る．また，ηm ∈ R を平均 m の学習率, ηc1 , ηcµ ∈ R をそれぞう．ここで t はステップ数とする．

れ分散共分散行列 C の rank-one update (式 (11) 右辺二項目),

目的関数 f (x) ∈ R, x ∈ Rd を最小化する場合の，具体的なアルゴリズムについて以下に記す．はじめに，変数の初期化を行

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

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

[Step 1.] 式 (1) の通り，正規分布 N (0 ∈ Rd , I ∈ Rd×d ) か(を平方分解し，zとの行列積から y
(t)

をy

∈R

λ×d

して，式 (3) の通り，σとの和から解集団 x

(t)

(t)

(t)

∈R

λ×d

を求める. その各要素にかけ，平均 m

(t+1)
∥pσ
∥

χd

))
−1

+ ηcµ

λ
∑

(

(t)

wi OP (yi ) − C (t)

(9)
(10)

C (t+1) = C (t) + ηc1 OP (p(t+1)) − C (t)cら，λ 個の個体 z ∈ Rλ×d を生成する．次に式 (2) の通り，C (t)
(t)

cσ
dσ

(

)

)
(11)

i

(t)

以上の Step 1.∼Step 5. を繰り返すことで，平均ベクトル mを生成する．

が解に，ステップサイズ σ が 0 に，分散共分散行列 C が 0 に収束することで，多変量正規分布がデルタ関数に収束し，最適z (t) ∼ N (0, I)√
y (t) = z (t) C (t)
x

(t)

= m

(t)

+σ

(t)

(1)
(2)
y

(t)

(3)

解が求まる．

2. 1. 2 sep-CMA-ES
sep-CMA-ES は目的関数が高次元である場合に，時間・空間
計算量の点から CMA-ES の適用が難しいことから，CMA-ES[Step 2.] Step 1. で生成した解集団 x(t) の各個体についての分散共分散行列を対角成分に限定することで，その問題の解

f (xi ), (i = 1, ..., λ) から評価値を計算し，昇順に x(t) , y (t) , z (t)消を図ったアルゴリズムである．sep-CMA-ES では時間計算

を個体 (λ) の軸について並び替える．

量・空間計算量ともに O(d) となる．

[Step 3.] 各個体の順位についての重み w ∈ Rλ を用いて，式また，sep-CMA-ES では分散共分散行列の学習率を増加さ(4), (5) の通り w と x(t) , y (t) の個体の軸についての内積を取せており，目的関数の入力次元を d として，rank-one update,り，dy (t) , dz (t) ∈ Rd を求める．ここで，重み w は，1 < µ < λとして，w1 >= ··· >
= wµ > 0, wµ+1 , · · · , wλ = 0, ∥w∥1 = 0 を

rank-µ update ともに (d + 2)/3 を係数にかける．

表 1 Benchmark functions

2. 1. 3 ハイパーパラメタ
CMA-ES はアルゴリズム中のハイパーパラメタがいくつか

Function

存在するが，それらは目的関数の入力次元によって定めている．

Sphere

本論文中では，文献 [7] に示されている推奨値を用いる．以下

Ellipsoid
Rosenbrock (Star)

目的関数の入力次元を d とし，各値について示す．

∑n 2
xi
i−1
∑i=1
n
(1000 n−1 xi )2
(
∑i=1
n
2 2
i=2

100(x1 − xi ) + (1 − xi )2

)

ができる．

λ
µ=⌊ ⌋
2

λ = 4 + 3⌊ln (d)⌋,Definition

現在の CMA-ES ステップサイズ更新手法の主流であり，前述

λ+1
wi = ln () − ln (i),2[w1 , w2 , · · · , wλ ]w=∥[w1 , w2 , · · · , wλ ]∥の (µ/µw , λ)-CMA-ES にも採用されている Cumulative Step-µw + 2cσ =,d + µw + 5

4 + µdwのマハラノビス距離を用いて更新することで，悪条件性に対す

cc =dσ = 1 + cσ + 2 max
ηm = 1,

d + 4 + 2µdw

( √0,µw − 1
−1
d+1

2
ηc1 =
(d + 1.3)2 + µw(

ηcµ = min 1 − ηc1 ,2(µw − 2 + µ1w ))size Adaptation (CSA) [9] [10] は，ステップサイズを進化パス
る頑健性の向上を図っている．

(12)

多峰性・大谷構造とは，目的関数が局所最適解を持つ状態(non-convex な状態) を指す．個体数の増加 [11]，再スタート毎に個体数を変化させる再スタート戦略 [12]，最適化の度合いに応)(d + 2)2 + µw

じて世代毎に個体数を変化させる Population Size Adaptation(PSA) [13] が提案されている．
本研究の提案手法では，従来の手法がいずれも，一反復中に

2. 2 ステップサイズの役割

全ての次元を同時に更新するのに対し，一反復中に更新する次

CMA-ES では，多変量正規分布における分散をステップサ

元の選択を行う．

イズ σ と分散共分散行列 C に分割して表現している．ステッ
プサイズの更新には，式 (10) の通り，ステップサイズの進化パスのノルム ∥pσ ∥ と，多変量正規分布のノルムの期待値 χd の

3. 予備実験: 高次元悪条件関数に対する CMAES の挙動比が用いられ，∥pσ ∥ > χd の場合，ステップサイズは増大し，本章では，高次元かつ悪条件な目的関数における CMA-ES∥pσ ∥ < χd の場合，減少する．ステップサイズの進化パス pσの挙動，即ち，良条件な目的関数の場合と比較してどのようなは，式 (7) の通り，良い評価を得た解候補の生成の基になった性能低下やパラメタの推移の変化が見られるかを確認する．は乱数 z (t) の重み付き和 dz (t) を累積した値である．つまり，現じめに，良条件かつ変数間依存性のない Sphere 関数を用いた

在の探索域が最適解から離れている場合，∥pσ ∥ は増大し，最実験を行い，その結果を他の目的関数に対してのベースライン

適解に近い場合は減少する傾向にある．従って，ステップサイとする．次に，悪条件な関数として，Ellipsoid 関数及び Star

ズは探索地点と最適解との間の距離に応じて χd を閾値として型 Rosenbrock 関数を用い，Sphere 関数の結果との比較を行増減することで，探索速度の向上を図る役割を持っていると言う．一般的によく知られる Chain 型の Rosenbrock 関数は隣りえる．

合う変数間の依存性が強い関数として知られているが，Star 型

2. 3 CMA-ES の改良の場合は，一つ目の変数とそれ以降の変数との間に強い依存性

CMA-ES の改良は多く存在し，目的関数の特徴に応じて設計を持つ [14] ことから，一つ目とそれ以降の変数について依存のされる．目的関数の特徴は主に，変数間依存性 (Separability),

度合いが異なり，高次元な場合については悪条件な関数とみな悪条件性 (Ill-Conditioning), 多峰性・大谷構造 (Multimodality)

すことができる．また，本論文中で用いるベンチマーク関数をに分類される [2] [3]．

表 1 に示した．

変数間依存性とは，目的関数の変数が分離可能であるか否3. 1 Sphere 関数を用いた実験かを指す．全ての変数について分離可能であるならば，全てはじめに，sep-CMA-ES を用いて 100,000 次元の Sphereの変数を独立に最適化しても最適値に到達することができる

関数の最適化を行う．初期値については，m(0) = U (−5, 5),が，そうでなければ変数間の依存関係を考慮する必要性があC (0) = I, σ (0) = 1.0, λ = 4 + 3⌊ln (d)⌋ と設定し，以降の全る．CMA-ES は分散共分散行列行列を用いることで解決を図っての実験で同一の設定を用いた．
．また，目的関数の目標値はているが，高次元 (large scale) の場合には時間・空間計算量

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

が重大な問題となる．前述の sep-CMA-ES や，LM-CMA [1],評価回数 (Func evals) に対する目的関数の値 (Objective)，

VD-CMA [8] といった研究では，分散共分散行列のうち保持すステップサイズ (Sigma)，分散共分散行列 (Covariance) の変る値を制限することで，時間・空間計算量を削減しつつ，変数化を，図 1 に示した．分散共分散行列については，全ての次元間の共起を考慮した最適化を可能としている．

の平均の値 (Covariance (mean)), 1 次元目の値 (Covariance

悪条件性とは，目的関数における各次元のスケールの差が非(dim=1)), 100,000 次元目の値 (Covariance (dim=100,000))

常に大きい状態を指し，目的関数のヘッセ行列の最大固有値とを示した．図より，約 1.5 × 107 回の評価回数で目標値に到達最小固有値の比で定義される条件数によって定量的に測ること

し，ステップサイズ及び分散共分散行列の値は単調に減少していることが伺える．また，分散共分散行列が次元別に示したものと平均を示したものとでおおよそ同じ値を取りつつ推移していることから，Sphere 関数の良条件性を確認することができる．

3. 2 Ellipsoid 関数を用いた実験
本節では，sep-CMA-ES を用いて，Loshchilov による実験 [1]の再現を行った．目的関数以外の実験設定については，前節と同様に扱った．
評価回数 (Func evals) に対する目的関数の値 (Objective)，
ステップサイズ (Sigma)，分散 (Covariance) の変化を図 2 に示した．また，前節と同様に，分散共分散行列について各次元の値の推移と平均値の推移を示した．図より，約 6.5 × 10 回の7

図 1 100,000 次元の Sphere 関数における各パラメタの推移 (sep-

CMA-ES)

評価回数で目標値に到達しており，前節の Sphere 関数の結果と比較して，約 5.0 × 107 回程度多くなった．目的関数の値の減少は，Sphere 関数の場合と Ellipsoid 関数の場合のいずれも
約 1.0 × 106 回付近から始まっており，Ellipsoid 関数の方が評価回数あたりの最適化速度が遅いことがわかる．また，Sphere関数の場合では，ステップサイズと分散共分散行列が共に単調に減少しているのに対し，Ellipsoid 関数の場合では，分散共分
散行列の平均 (Covariance (mean)) については，スケールの大
きな次元の分散 (Covariance (dim=100,000)) への適応に応じて上昇したのち減少に転じており，ステップサイズについては単調減少ではあるものの，分散共分散行列の平均の上昇中は緩やかであり，スケールの大きな次元の適応後は急速に減少して

図 2 100,000 次元の Ellipsoid 関数における各パラメタの推移 (sep-

CMA-ES)いる．スケールの大小に関わらず単一のステップサイズを適用しているため，スケールの小さな次元についてはステップサイ
ズが過大となり，スケールの大きな次元については過小となることで，結果として分散共分散行列とステップサイズの間の乖
離が Sphere 関数の場合と比較して拡大していると考えられる．
この乖離が Sphere 関数の場合と比較して Ellipsoid 関数の最適化速度を下げていると推測され，ステップサイズをより各次元のスケールの大きさに適応させ，この乖離を抑制することでこの差を軽減することができると考えられる．

3. 3 Star 型 Rosenbrock 関数を用いた実験
本節では，10,000 次元の Star 型 Rosenbrock 関数を用いた実験を行う．Star 型 Rosenbrock 関数では，一つ目の変数はそれ以降の全ての変数との間に依存関係を持つのに対して，二つ

図 3 10,000 次元の Star 型 Rosenbrock 関数における各パラメタの推移 (sep-CMA-ES)

目以降の変数は一つ目の変数との間のみ依存関係を持つため，一つ目とそれ以降の変数との間でスケールの差が生じ，高次元になるほど悪条件性が高まる．

4. 提 案 手 法

前節と同様に結果を，図 3 に示した．目標値には到達せず，本章では，予備実験の結果を受け，ステップサイズの大域的最大評価回数時の目的関数の値は約 2252.2 となった．ステッな収束性を維持しつつ，分散共分散行列の局所的な収束を考慮

プサイズに注目すると，1.0 × 10 回の評価回数付近で，一次した変数の更新を目的とするアルゴリズムの提案を行う．

6

元目の変数の分散と共に収束に向かってしまっている．その後，

4. 1 更新次元の確率的選択

一次元目の変数の分散も上昇に転じ，全ての次元の分散の平均

本節では，CMA-ES において各世代で更新する次元を確率が大きく上昇しているのに対して，ステップサイズは収束して的に選択するアルゴリズムを提案する．提案手法では，目的関

しまい，最適化が緩やかになっていることがわかる．Star 型

数の入力次元をインデックス化し，そのインデックスの要素をRosenbrock 関数は一次元目の変数の影響が非常に大きく，一ランダムに並び替え，予め指定した次元長の組に分割する．そ次元目の変数の収束がステップサイズに大きな影響を及ぼした

して，分割された組のインデックスに指定された次元について，と考えられる．

CMA-ES の各パラメタから区分行列及びベクトルを抽出し，解候補を生成する．パラメタの更新についても，指定された次元提案手法では，更新に用いられる p′σ の次元の組が毎回異なるについてのみ行う．インデックスの最後の要素まで参照を終えことから，反復を重ねることでステップサイズベクトルの各要

たら，再びインデックスをランダムに並び替える．この手法は素は異なる値を取る．

CMA-ES と sep-CMA-ES の双方に適用でき，アルゴリズムの以上の Step 1.∼Step 6. を通常の CMA-ES と同様に終了条件

変更点は同様なため，CMA-ES への適用について以下の項でを満たすまで繰り返す．sep-CMA-ES についても分散共分散行

述べる．

列の対角成分から ι′ に対応する次元を抽出することで CMA-ES

4. 1. 1 CMA-ES への適用の場合と同様に適用することができる．

最小化したい目的関数を f (x) ∈ R, x ∈ R とする．はじめd4. 1. 2 ハイパーパラメタに，平均 m(0) ∈ Rd ，分散共分散行列 C (0) ∈ Rd×d ，ベクトル提案手法ではハイパーパラメタについて，通常の CMA-ES∈ R をそれぞれ探索領域に応じと同様の式を用いる．ただし，ハイパーパラメタの引数となるて決め，分散共分散行列とステップサイズのそれぞれの進化パ次元の値については，目的関数の入力次元数 d ではなく，各化されたステップサイズ σ
(0)

(0)

n

(0)

∈ Rd , pσ ∈ Rd = 0 と初期化する．次に，目的関数

世代ごとに選択された次元数 s を用いる．また，sep-CMA-ESの入力次元長のインデックスベクトル ι ∈ R = (0, 1, ..., d − 1)への適用の場合は，sep-CMA-ES と同様に分散共分散行列のを新たに導入する．インデックスベクトルは，予め要素をラン

rank-one update, rank-µ update 双方の学習率に (s + 2)/3 のダムに並び替え，インデックスの参照を終えた要素の終端地点

係数をかける．

スを pc

dを e ∈ R = 0 と初期化し，各反復で選択する次元数を s ∈ R と

4. 2 手法の特徴

する．そして，予め定めた終了条件を満たすまで以下のステッ進化計算において，最適化を行う変数を制限する手法は，プを繰り返す．

Zhang らの OpenAI ES [15] でも用いられており，目的関数が[Step 1.] ι から，前世代での終了地点 e から e + s までを取

高次元である場合に，集団サイズを維持した状態で更新する次

り出し，当世代でのインデックスベクトル ι′ ∈ Rs とする．た元を減らすことができ，分割された次元の更新のタイミングを′だし，e + s > d の場合，e から d までのベクトル ι ∈ R

d−eとし，ι の要素を全てランダムに並び替え，e = 0 とする．

揃えることで並列化も可能なため，有効であるとされている．
本研究では，次元のインデックスを最後まで参照した際に，′[Step 2.] 生成した当世代でのインデックスベクトル ι に基インデックスベクトルの要素をランダムに並び替えることで，づいて，各変数から部分ベクトルおよび部分行列を生成する．

制限された次元に含まれる次元の組が毎回変わるように設計を具体的には，平均 m′ ∈ Rs ，分散共分散行列 C ′ ∈ Rs×s ，ス

行なった．これは Rosenbrock 関数のように次元間に依存性が∈ R ，進化パス p′c ∈ Rs , p′σ ∈ Rs となる．分ある場合に有効であると考えられる．また，インデックスベク

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

トルを先頭から順番に参照していくことで，全ての次元が均一

およびそれらの共起成分からなる対称行列を抽出する．

に選択される．これは，選択される回数にばらつきが発生した

テップサイズ σ′s[Step 3.] 正規分布 N (0 ∈ R , I ∈ Rss×s) から，λ 個の個場合に，選択されなかった次元の共起成分が維持され続け，世体 z ′(t) ∈ Rλ×s を生成する．C ′ を平方分解し，z ′(t) との行列√積から y ′(t) ∈ Rλ×s = z ′(t) C ′ を求める. そして，σ ′(t) を代を重ねるごとに対角成分に対して大きな値をとって最適化を

′(t)

′

妨げることを防ぐためである．

の ι の要素との和から解集団

また，ステップサイズをベクトルに変更し，選択された次元

x(t) ∈ Rλ×d = m(t) + σ ′(t) ◦ y ′(t) を生成する (ここで ◦ は二を用いて更新を行なっている点が，従来の CMA-ES との最大つのベクトル間の要素積を取る演算子とする)．このとき，x(t)の相違点である．ステップサイズは，式 (10) の通り，従来のyの各要素にかけ，平均 m(t)′は通常の CMA-ES と同じ次元の行列となるが，ι 以外のイン

CMA-ES ではスカラーで表すことしかできないが，次元の選択

デックスの次元については，各個体全て同じ値 (m(t) の値) をを行うことでベクトルで表すことが可能となり，ステップサイ

取る．

ズの表現力を向上させることが可能となる．従来の CMA-ES[Step 4.] 通常の CMA-ES と同様に，目的関数を用いて各では，目的関数の各次元のスケールが大きく異なっていた場合個体を評価・順位づけし，昇順に並び替える．また，同様にに，分散共分散行列の局所的な収束との乖離が大きいという問重み w ∈ R との個体の軸 (λ の軸) についての内積 dy
λ

′(t)

,

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

題が生じていたが，提案手法では，大域的な収束を維持しつつ分散共分散行列の局所的な収束にも対応できると考えられる．

[Step 5.] Step 4. で求めた dy

′(t)

′(t)

をもとに，進化パス

最後に，時間・空間計算量について考える．空間計算量にを更新する．このとき，ι で指定された要素のみ更新を行い，ついては元の分散共分散行列の値を保持するため O(d2 ) (sep-

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

CMA-ES の場合は O(d)) で変わらない．一方で，時間計算量

, dz

′

[Step 6.] 進化パスをもとに平均 m
ステップサイズベクトル σ

(t)

(t)

，分散共分散行列 C(t)，の更新を行う．ここでも，Step 4.

と同様に ι′ で指定された要素のみ更新を行い，その他の要素については元の値を維持する．ステップサイズの更新値は，2 章
式 (10) にある通りスカラー値であり，提案手法においても，同一反復中での更新値は ι′ の次元について同一となる．しかし，については，分散共分散行列の固有値分解について，選択した次元のオーダーで行うことができる．

表 2 計算機環境

CPUIntel Xeon E5-2680 v4 2.40GHz

RAM

256GB

GPU

NVIDIA Quadro P6000

GPU 環境 Cuda9.0 Cudnn7.2 CuPy4.3.0
OS

Ubuntu 16.04.3 LTS

図 5 100,000 次元の Ellipsoid 関数における各アルゴリズムの比較

図 4 100,000 次元の Sphere 関数における各アルゴリズムの比較

5. 評 価 実 験
本章では，提案手法の高次元悪条件問題における性能を確認する．目的関数は予備実験と同様の関数を用いた．本実験で用いた計算機環境を表 2 に示した．

図 6 10,000 次元の Star 型 Rosenbrock 関数における各アルゴリズ
ムの比較

5. 1 高次元悪条件関数における各アルゴリズムの比較
本節では，提案手法，既存の CMA-ES，L-BFGS 法との性能の比較を行う．既存の CMA-ES として，sep-CMA-ES 及
び VD-CMA を用いた．VD-CMA は，分散共分散行列のベク
トルを用いた近似を提案したアルゴリズムで，計算量を低減しつつ変数間の依存性を考慮した最適化を行うことができる．

L-BFGS 法は，勾配法をベースとしたアルゴリズムの中で最も優れたものの一つとして知られている．本実験では，L-BFGS
法について目的関数の一階導関数を既知の情報として与え，一反復あたりの評価回数については，目的関数の評価回数に各次
元における導関数の計算回数を加えた回数とした．また，初期値，目標値，最大評価回数等の設定については予備実験と同様とし，提案手法における各反復の選択次元数は 100 とした．

図 7 100,000 次元の Sphere 関数における各パラメタの推移 (提案手法)

各アルゴリズムについて，評価回数 (Func evals) に対する目的関数の値 (Objective) の推移を，Sphere 関数について図 4,

度評価回数が少なくなった．各パラメタについて見ると，予備Ellipsoid 関数について図 5, Star 型 Rosenbrock 関数について実験における sep-CMA-ES の場合と比較して，分散共分散行

図 6 に示した．また，各関数について提案手法における，評価

列とステップサイズの推移間の乖離が小さく抑えられており，回数に対するステップサイズと分散の推移を，Sphere 関数につ乖離の抑制が結果に影響したと考えられる．

いて図 7, Ellipsoid 関数について図 8, Star 型 Rosenbrock 関

最後に，Star 型 Rosenbrock 関数では，いずれのアルゴリズ
ムも目標値には到達しなかったが，提案手法が最大評価回数時数について図 9 に示した．
はじめに，Sphere 関数では，L-BFGS が最も少ない評価回に目的関数の値が約 59.76 となり最小の値に到達した．こちら

数で目標値に到達し，提案手法は約 2.5 × 10 回で最も多くのの場合でも，ステップサイズと分散の乖離が，sep-CMA-ES よ

評価回数を必要とした．提案手法は，一反復あたりに更新を行

りも小さくなったことが原因であると考えられる．

7

う次元数を制限するため，良条件な関数では優位性を示すこと

5. 2 選択次元の大きさについての比較
本節では，提案手法の選択次元の大きさの違いついての性能はできなかった．
次に，Ellipsoid 関数では，約 4.5 × 10 回と最も少ない評価の比較を行う．100,000 次元の Ellipsoid 関数と 10,000 次元の回数で目標値に到達し，sep-CMA-ES よりも約 2.0 × 107 回程Star 型 Rosenbrock 関数に対して，選択次元を 10, 100, 1,000

7

5. 3 次元の制限方法についての比較
本節では，提案手法における次元の制限方法について，ランダムに制限する場合と，制限する次元の組を固定する場合とで比較を行う．後者については，各次元について先頭から 100 ず
つ制限を行った．
はじめに，Ellipsoid 関数について，評価回数に対する目的関数値，分散共分散行列，ステップサイズの推移を，図 11 に示した．図より，ランダムに制限する場合が約 4.5 × 107 回で目標値に到達したのに対し，組を固定した場合では，約 2.0 × 107 回で到達した．Ellipsoid 関数では，各次元について単調にスケー
図 8 100,000 次元の Ellipsoid 関数における各パラメタの推移 (提案手法)

ルが増大するため，順番に次元を固定した場合，スケールが近い次元同士が同じ組に含まれることが影響したと考えられる．
次に，各次元について係数の順番をランダムに入れ替えた

Ellipsoid 関数について，評価回数に対する目的関数値，分散共分散行列，ステップサイズの推移を，図 12 に示した．前述の通り，従来の Ellipsoid 関数は各次元について単調にスケールが変化するため，順番を入れ替えることでその影響の確認を行う．図より，どちらの制限方法の場合でもほぼ同様の結果が得られた．Ellipsoid 関数の係数をランダムに入れ替えたことにより，次元の組を固定した場合でも，ランダムに制限する場合と同等の状態になったと考えられる．
最後に，Star 型 Rosenbrock 関数について，評価回数に対す
図 9 10,000 次元の Star 型 Rosenbrock 関数における各パラメタの推移 (提案手法)

る目的関数値，分散共分散行列，ステップサイズの推移を，図13 に示した．図より，どちらの場合も目標値に到達できなかったが，ランダムに制限を行ったものが，最大評価回数において，
より良い値に到達することができた．Star 型 Rosenbrock 関数
では，一つ目の変数とそれ以降の変数との間に依存関係がある
ため，変数の組にそれらが同時に含まれることが望ましいと考えられる．ランダムに制限を行う場合は，確率的に依存関係のある変数同士が含まれる次元の選択が実現されるのに対し，固定した場合は，はじめの選択に含まれなかった変数については実現されないため，この点が結果に影響を与えたと考えられる．
以上より，変数の制限方法について，目的関数における変数間のスケールの近さや依存関係が既知の場合は，それらを考慮することで最適化性能を高めることが可能であると言える．一図 10 選択次元数を変化させた場合の評価回数毎の目的関数の値の推移と変えて実験を行った．Ellipsoid 関数に対しては sep 型の提案

方で，目的関数がブラックボックスである場合では，現状ではランダムな制限が妥当であると考えられる．

6. お わ り に手法を用い，Star 型 Rosenbrock 関数については通常の (分散本論文では，CMA-ES が最適化を行う次元を各世代でランダ

共分散行列の全ての要素を考慮する) 提案手法を用いた．目標

ムに制限し，制限された次元からステップサイズをはじめとす

値は 10−10 とした．

る CMA-ES の変数を更新するアルゴリズムを提案し，その評評価回数あたりの目的関数の値を Fig. 10 に示す．Ellipsoid価を行った．実験を通して，提案手法は，制限された次元の局関数では，選択次元を 100 としたものが最も少ない評価回数で所性を考慮したステップサイズの更新を行うことで，Ellipsoid

目標値に到達した．一方で，Star 型 Rosenbrock 関数では，目関数や Star 型 Rosenbrock 関数のような悪条件な目的関数につ標値に到達したものはなかったが，選択次元を 10 としたもの

いては，従来の CMA-ES より少ない評価回数で優れた解に到が最もよい値を得た．以上の結果より，さらなる検証が必要で達できることを明らかにした．一方で，Sphere 関数のように良はあるが，目的関数の入力次元数に対して 0.1%程度の選択次条件な関数に対しては，世代毎に更新する変数を制限している

元が適しているという推測が得られた．

ことから，目標値への到達までの評価回数で従来の CMA-ESを下回った．また，次元の制限方法については，目的関数がブ文

図 11 100,000 次元の Ellipsoid 関数における次元の選択方法による比較

図 12 係数を入れ替えた 100,000 次元の Ellipsoid 関数における次元の選択方法による比較

図 13 10,000 次元の Star 型 Rosenbrock 関数における選択方法による比較

ラックボックスである場合はランダムな制限が最も妥当である
ことを示した．
今後は，提案手法の性質についての更なる検証，本手法のニューラルネットワークの学習への適用，各反復における次元の制限について次元毎のスケールの近さや共起関係に最適化中に適応可能な選択方法の提案，世代毎の変数を選択することな
くステップサイズをベクトル化する手法の提案等を行いたい．

謝辞

本研究は JSPS 科研費 16H02905, 17K12736 の助成を受けたものです.

献[1] Ilya Loshchilov. A computationally eﬃcient limited memory CMA-ES for large scale optimization. In Proceedings ofthe 2014 Conference on Genetic and Evolutionary Computation - GECCO ’14, pages 397–404. ACM Press, 2014.
[2] Nikolaus Hansen, Steﬀen Finck, Raymond Ros, and Anne
Auger. Real-Parameter Black-Box Optimization Benchmarking 2009: Noiseless Functions Definitions. 37(1):55–57,
2009.
[3] 阪井 節子 and 高濱 徹行. 最適化手法における関数評価回数の削減手法-ポテンシャルモデルに基づく比較推定法の提案-. 数理解析研究所講究録, 2007.
[4] Nikolaus Hansen. The CMA Evolution Strategy: A Tutorial. http://arxiv.org/abs/1604.00772, 2018-11-18.
[5] 秋本 洋平. Evolution Strategies による連続最適化 CMA-ESの設計原理と理論的基盤. 進化計算の時代 特集号, 2016.
[6] Raymond Ros and Nikolaus Hansen. A Simple Modificationin CMA-ES Achieving Linear Time and Space Complexity.
In Günter Rudolph, Thomas Jansen, Nicola Beume, Simon
Lucas, and Carlo Poloni, editors, Parallel Problem Solving from Nature – PPSN X, volume 5199, pages 296–305.
Springer Berlin Heidelberg, 2008.
[7] Nikolaus Hansen and Anne Auger. Principled Design ofContinuous Stochastic Search: From Theory to Practice. In
Yossi Borenstein and Alberto Moraglio, editors, Theory andPrincipled Methods for the Design of Metaheuristics, pages
145–180. Springer Berlin Heidelberg, 2014.
[8] 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, pages 373–
380. ACM Press, 2014.
[9] Andreas Ostermeier, Andreas Gawelczyk, and Nikolaus
Hansen. Step-size adaptation based on non-local use of selection information. In Yuval Davidor, Hans-Paul Schwefel, and Reinhard Männer, editors, Parallel Problem Solving from Nature ― PPSN III, volume 866, pages 189–198.
Springer Berlin Heidelberg, 1994.
[10] Nikolaus Hansen and Andreas Ostermeier. Completely Derandomized Self-Adaptation in Evolution Strategies. Evolutionary Computation, 9(2):159–195, 2001.
[11] Nikolaus Hansen and Stefan Kern. Evaluating the CMA
Evolution Strategy on Multimodal Test Functions. In
Xin Yao, Edmund K. Burke, José A. Lozano, Jim
Smith, Juan Julián Merelo-Guervós, John A. Bullinaria,
Jonathan E. Rowe, Peter Tiňo, Ata Kabán, and Hans-Paul
Schwefel, editors, Parallel Problem Solving from Nature PPSN VIII, volume 3242, pages 282–291. Springer Berlin
Heidelberg, 2004.
[12] A. Auger and N. Hansen. A Restart CMA Evolution
Strategy With Increasing Population Size. In 2005 IEEE
Congress on Evolutionary Computation, volume 2, pages
1769–1776. IEEE, 2005.
[13] Kouhei Nishida and Youhei Akimoto. PSA-CMA-ES: CMAES with population size adaptation. In Proceedings of the
Genetic and Evolutionary Computation Conference on GECCO ’18, pages 865–872. ACM Press, 2018.
[14] Shigenobu Kobayashi. The frontiers of real-coded genetic
algorithms. Transactions of the Japanese Society for Artificial Intelligence, 24(1):147–162, 2009.
[15] Xingwen Zhang, Jeﬀ Clune, and Kenneth O. Stanley. On the
Relationship Between the OpenAI Evolution Strategy andStochastic Gradient Descent. http://arxiv.org/abs/
1712.06564, 2018-11-18.