九州大学 海洋システム工学専攻
システム設計特論 （木村）
非線形数値最適化（３）遺伝的手法（ＧＡ）による数値最適化

授業の資料等はhttp://sysplan.nams.kyushu-u.ac.jp/gen/index.html
p y pyjp g1

背景勾配法 勾配を下 て極小値を探す方法
勾配法＝勾配を下って極小値を探す方法

多峰性関数に勾配法は使えない！

【解決策】

探索性能の下限

１．ランダムに動く → ランダムサーチ・ＳＡ
２．多点で探す→ 滑降シンプレックス法
パラメータ数が5～6個程度までならお奨め

両方の特徴を併せ持つ最適化手法 遺伝的アルゴリズム
両方の特徴を併せ持つ最適化手法：遺伝的アルゴリズム2

【遺伝的手法による最適化】
生物の進化の仕組みを模倣
生物個体 →
優れた個体 →

Mating遺伝子によるコード化
高い評価値・生存率【一般的な処理手順】【般的な処】
１）設計したい物をパラメータ化 → 遺伝子２）いろいろな個体を集めて集団を作り、個体を評価に応じて自然淘汰３）生き残った個体同士で遺伝子を交換 → 新しい個体生成
４）世代交代を繰り返し、集団を進化【探索の特徴】
・評価値の悪い個体でも生き残る
生き残るチャンスが与えられるが与 られる・優れた親同士を掛け合わせる
ことで、両親の優れた形質を受け継いだ子個体が生成される・集団全体が進化していく

たった１つの解候補を改善していくよりも、より優れた解や多様な評価を持つ複数の解を発見できる3

【遺伝的手法による最適化】
Simple GA (SGA) 遺伝的アルゴリズム研究黎明期の方法
１）解候補を固定長文字列に表現 → 遺伝子例） 00101110110000２）いろいろな個体を集めてN個体集団を作り、
２）いろいろな個体を集めてN個体集団を作り各個体の評価値を計算して非負の「適応度(fitness)」を算出
３）〔淘汰(selection)〕
現在の 個の個体集合から 以下の確率 P( xi ) に基づき重複を許してN個選択
現在のN個の個体集合から，以下の確率に基づき重複を許し個選択

P(( xi ) f ( xi )Nj 1f (x j )ルーレット選択，f(x)は適応度

f ((xx1 ) f ( x4 )f ( x2 )f ( x3 )４）〔交叉(crossover)・突然変異(mutation)〕）〔交叉() 突然変異()〕・一定の割合で2個の個体ペアを作り，遺伝子文字列の部分を交換
1110 0011 1111
1110 0011 1010
0000 1110 1010
0000 1110 1111
・一定の割合で個体の遺伝子文字列の一部をランダムに変化
1110 0011 1111
1110 1011 1010
５） 手順２へ戻って繰返す4【遺伝的手法による最適化】
Simple GA (SGA)の性能は、しばしばランダムサーチ以下・連続関数最適化において文字列変換して交叉・突然変異操作することに意味があるか？
連続関数最適化において文字列変換して交叉 突然変異操作することに意味があるか？
・組合せ最適化問題において交叉・突然変異操作すると、ほとんど致死遺伝子になる！
・集団全体が一気に世代交代 → 多様性の喪失／生物現象からの乖離

Simple GA (SGA)は、非実用的実用的なＧＡ
実用的なＧＡへ●連続関数における交叉方法：ＵＮＤＸ，ＳＰＸ，ＲＥＸ●ＴＳＰにおいて致死遺伝子を生成しない交叉方法：ＥＡＸ●序々に世代交代：ＭＧＧモデル，ＪＧＧモデル
5●究極のGA： CMA-ES + NESs

【より洗練された遺伝的手法の枠組み１】（１） ビットストリングにこだわらない遺伝子表現
遺伝子は解のコード化「表現」であるので、遺ド 「解が完全に表現可能で、かつ操作・改変が容易な表現であることがのぞましい（２） 親の形質（特徴）を受け継ぐ交叉オペレーション
交叉は、親の優れた特徴を受け継ぐことが可能なオペレーションでなければならない
ビットストリングＧＡのように親の特徴を破壊しては意味がない6

【遺伝的手法による最適化】
実数値 GA （RGA: Real-coded GA） 実用的手法として初めて認知
連続関数最適化問題における解候補の「形質」 ＝ パラメ
パラメータ空間中の座標
タ空間中の座標
解候補の類似性 ＝ パラメータ空間でのユークリッド距離２つの親個体から、「交叉」オペレーションにより２つの親個体から「交叉」オペレ ションにより形質を継承した子個体を生成する → パラメータ空間でユークリッド幾何学的に考える
例） 正規分布交叉：ＵＮＤＸ
X2

親１と親2を結ぶ主軸

パラメータ空間
親２
親１

多次元正規分布子7X1

単峰性正規分布交叉UNDX[Ono 97]
設計パラメータの連続値ベクトル＝ 遺伝子

設計パラメータベクトル
空間中において、親 す 個体親とする個体同士の間の空間に子個体をランダムに生成

8

シンプレックス交叉（ＳＰＸ） ［樋口，筒井，山村２００１］
p1

1 nx i とする
２） 親個体の重心を g n  1 i 0

親x1

親x2p2１） 探索する
探索するパラメータ空間がｎ次元の場合、ラメ タ空間がｎ次元の場合、ｎ＋１個の親個体 x 0 , x 1 ,  x n を集団からランダムに選ぶ。

g親x0３） 以下の式に従ってベクトル p 0 , p1 ,  p n
およびベクトル c 0 , c1 ,  c nを計算する：

p 0  g  n  2 x 0  g p0c0  0p k  g  n  2 x k  g 

重心からそれぞれの親個体までの重心かられぞれ 親個体まベクトルをn  2 倍まで拡張した
c k  rk 1 p k 1  p k  c k 1 
シンプレックス状多角形の範囲に
ただし rk は区間［０，１］の一様乱数
は区間［０ １］の 様乱数 u から均 に子個体を生成する
均一に子個体を生成する
以下の式で変換された乱数である：

rk  u 1k 1４） 子ベクトル c を次式で得る：

c  p n  cn9多親交叉ＲＥＸ ［小林２００７］

対象とするコスト関数の次元数 ｎ交叉によって生成する子個体数 ｎ＋ｋp1n k

子個体の座標
個体 座標

親x1

親x2

x c  x g    i xi  x gi 1

親個体の重心の座標

xgp2
親x0p0

i2

期待値０，分散  の任意の変数
確率分布に従う確率変数
ただし12 ｋ＝０．５ｎ～２．０ｎ を推奨

nk10



多親交叉ＲＥＸ ［小林２００７］



確率変数 i がが一様分布に従う場合
様分布に従う場合
ただし区間 ［－a, a］ で一様で、確率変数i が正規分布に従う場合
ただし期待値０，3aとするとする。
nk1
分散   nk1（このとき分散   nk22となる）
11

実数値 GA の交叉オペレータにおいて求められる性質
X2

分布の統計量が親個体群の分布と同じになることが望ましい

パラメータ空間
親個体群

ＵＮＤＸもＳＰＸもＲＥＸもこの条件を満たしている

X1
交叉オペレータ適用後
X2

機能分担仮説（山村９８）
交叉オペレータは親個体群が張る部分空間の補間的探索に徹して、探索領域の絞込みは世代交代モデルに委ねるのが望ましい

パラメ タ空間パラメータ空間子個体群

X112

【より洗練された遺伝的手法の枠組み２】（３） 集団の「多様性」を維持する世代交代方法
集団の一部しか生き残れないような世代交代では多様性は維持できない
ビットストリングＧＡで行う「淘汰」のような操作は不適当（英語では「選択」も「淘汰」も「selection」と訳される）

13

（２親）世代交代モデルＭＧＧ ［佐藤１９９７］

個体集団
集団からランダムに2個体を選択し、何らかの交叉オペレーションによって子個体をnc個生成、両親と生成された全ての子を合わせた個体集合から、１つは最良個体、もう１つは14評価値のランクに基づくルーレット選択により選び、両親個体と入れ替える

多親世代交代モデルＪＧＧ ［小林２００７］

ランダムに非復元抽出

交叉ランキング
エリート選択

np個

np個

親個体群

np個子個体を生成したら親を捨てる

子個体群
１０ｎ個を推奨
ただしｎは次元数

個体集団
親個体群と入れ替える

集団サイズは１５ｎ～５０ｎ 個を推奨
ただしｎは次元数

ＭＧＧと比較すると 2.5～13倍の性能アップ

15

究極の実数値 GA： CMA-ES + NESs
CMA-ES：
NESs:

X2

Covariance Matrix Adaptation Evolution Strategies
Natural Evolution Strategies

CMA-ES の学習率に関する理論的考察
秋本洋平，永田裕一，小野功，小林重信（東京工業大学）
進化計算シンポジウム2010 講演論文集 pp.202--207 (2010).

個体群分布：  (x |  )統計量

パラメータ空間
個体群

期待値ベクトル：（λ個）
共分散行列：

m( )
C( )

ある個体の座標ベクトル： x iその個体の目的関数値： f ( x i )

X1
世代交代

Θは確率分布関数を特徴付けるパラメータ

究極の実数値 GA： CMA-ES + NESs
CMA-ES：
NESs:

X2

Covariance Matrix Adaptation Evolution Strategies
Natural Evolution Strategies

CMA-ES の学習率に関する理論的考察
秋本洋平，永田裕一，小野功，小林重信（東京工業大学）
進化計算シンポジウム2010 講演論文集 pp.202--207 (2010).

個体群分布：  (x |  )統計量

パラメータ空間
個体群

期待値ベクトル：（λ個）共分散行列：

m( )
C( )

ある個体の座標ベクトル： x i
その個体の目的関数値： f ( x i )

X1
世代交代
X2

パラメ タ空間パラメータ空間

次世代
個体群

X1

Θは確率分布関数を特徴付けるパラメータ

究極の実数値 GA： CMA-ES + NESs
CMA-ES：
NESs:

X2

Covariance Matrix Adaptation Evolution Strategies
Natural Evolution Strategies

CMA-ES の学習率に関する理論的考察
秋本洋平，永田裕一，小野功，小林重信（東京工業大学）
進化計算シンポジウム2010 講演論文集 pp.202--207 (2010).

個体群分布：  (x |  )統計量

パラメータ空間
個体群

期待値ベクトル：（λ個）
共分散行列：

m( )
C( )

ある個体の座標ベクトル： x i
その個体の目的関数値： f ( x i )

X1
世代交代
X2

パラメ タ空間パラメータ空間

次世代個体群分布：
統計量
期待値ベクトル：

次世代
個体群

共分散行列：

X1m( ' )
C( ' )

 (x |  ' )Θは確率分布関数を特徴付けるパラメータ

究極の実数値 GA： CMA-ES + NESs
CMA-ES：
NESs:

X2

Covariance Matrix Adaptation Evolution Strategies
Natural Evolution Strategies

CMA-ES の学習率に関する理論的考察
秋本洋平，永田裕一，小野功，小林重信（東京工業大学）
進化計算シンポジウム2010 講演論文集 pp.202--207 (2010).

個体群分布：  (x |  )統計量

パラメータ空間
個体群

期待値ベクトル：（λ個）
共分散行列：

Θは確率分布関数を特徴付けるパラメータ

m( )
C( )

期待目的関数値：  ( )ある個体の座標ベクトル： x i
その個体の目的関数値： f ( x i ) ( )   f ( x)  (x |  )dx

X1
世代交代
X2

パラメ タ空間パラメータ空間

次世代個体群分布：
統計量
期待値ベクトル：

次世代個体群

共分散行列：

 (x |  ' )m( ' )
C( ' )

次世代個体群分布をどう決めるべきか？

X1

究極の実数値 GA： CMA-ES + NESs
CMA-ES：
NESs:

X2

Covariance Matrix Adaptation Evolution StrategiesNatural Evolution Strategies

CMA-ES の学習率に関する理論的考察
秋本洋平，永田裕一，小野功，小林重信（東京工業大学）
進化計算シンポジウム2010 講演論文集 pp.202--207 (2010).

個体群分布：  (x |  )統計量

パラメータ空間
個体群

期待値ベクトル：（λ個）
共分散行列：

Θは確率分布関数を特徴付けるパラメータ

m( )
C( )

期待目的関数値：  ( )ある個体の座標ベクトル： x i
その個体の目的関数値： f ( x i ) ( )   f ( x)  (x |  )dx

X1
世代交代
X2

パラメ タ空間パラメータ空間

次世代個体群分布：
統計量
期待値ベクトル：

次世代個体群共分散行列：

 (x |  ' )m( ' )
C( ' )

確率的勾配法次世代個体群分布をどう決めるべきか？
期待目的関数  ( ) の自然勾配方向へ Θ→Θ’

X1

個体群サンプルを利用してモンテカルロ推定

自然勾配：２次微分まで考慮した勾配

通常の「勾配法」と CMA-ES + NESs との関連
「勾配法」では１つの解候補がコスト関数の勾配を下る
解候補の移動方向の期待値＝コスト関数の（共役）勾配「ＣＭＡ-ＥＳ+NESs」では解候補の集団全体がコスト関数の期待値の自然勾配を下る

21

究極の実数値 GA： CMA-ES + NESs
期待目的関数値

 ( ) の自然勾配 ＝ （Fisher情報行列の逆行列）・   ( )個体群分布  (x |  ) が（多次元）正規分布の場合、モンテカルロ推定が簡単

準ニュートン法で出てくるA行列に類似

以降、本来なら情報幾何学に基づいた複雑な式展開が続くが、本講義の趣旨から逸脱するので省略
しかし その結論の簡潔さは以下のとおり驚異に値する
しかし、その結論の簡潔さは以下のとおり驚異に値する：

究極の実数値 GA： CMA-ES + NESs
期待目的関数値

 ( ) の自然勾配 ＝ （Fisher情報行列の逆行列）・   ( )個体群分布  (x |  ) が（多次元）正規分布の場合、モンテカルロ推定が簡単

準ニュートン法で出てくるA行列に類似

以降、本来なら情報幾何学に基づいた複雑な式展開が続くが、本講義の趣旨から逸脱するので省略
しかし その結論の簡潔さは以下のとおり驚異に値する
しかし、その結論の簡潔さは以下のとおり驚異に値する：

多次元(あるいは多変量）正規分布  (x |  ) ただし期待値座標 m( ) 共分散行列 C( )) f (x 2 ),)  f (x  ) を計算に従って個体群 x1 , x 2 ,  x  を生成し、各評価値を生成し 各評価値 f (x1 ),現世代

このとき多次元(あるいは多変量）正規分布の自然勾配方向へと次世代個体群分布  (x |  ' ) を生成：
を生成
期待値座標ベクトル：m'  m   i 1



共分散行列：

C'  C   i 1

ただし η は学習率パラメータで 0 ＜ η ≦ 1f (xi )(x i  m)x  m x  m   Cf (xi )Tii

このアルゴリズムは f(x) が大きくなる方向へ更新  ( ) のモンテカルロ推定  ( x   )2 
1
N (, ) exp
2
 2
 2

2

準備


ln N (, 2 )

正規分布x2
( x   )2   2
2
ln N (, ) 
3

なぜ正規分布にlnを施したものを微分するのか？理由は下の式2 ( )   f ( x)N (, )dx   f ( x) N (, 2 )dx
  x l N (, 2 ) dxd   f ( x) N (, 2 ) 2 dxd  f ( x) N (, 2 ) ln   xxf ( x) 2をたくさんサンプルして E  f ( x) 2  つまり  平均をとれば、それが   ( )24

【復習】 多変量正規分布

期待値ベクトル

確率密度  (x |  )   (x | m, C)  N (m, C)
分散共分散行列 1   1   1
T 1
exp  x  m C x  m 2   detC   2
n２変数正規分布2
 x    2
 


1x
y
y


1122
f ( x, y ) exp 2        
 2 1   2   1 2 1 2 1   222
 1    1

ただただし

1    1

1 ,  2
1, 2

x ，y の期待値
x ，y の分散
x と y との相関25

【復習】 ニュートン法 Newton method
３点を通る２次関数で近似
Approximated quadratic function

f(x)f ( x)  ax  bx  c
2Line search
逆放物線補間Inverse parabolic interpolation

１次元空間上次 空間上（直線）を探索
xdf
 0 より、2ax  b  0dxx  (2a ) 1 (b)

近似した２次関数の極小をサーチ近似した２次関数の極小をサチ
Search this point where gradient of theapproximated function is zero.

26

【復習】

準ニュートン法

Quasi-Newton method

関数 f(x) をテイラー級数で近似(Taylor series)

f1
2 ff (x)  f (P )  xi  xi x j  2 i , j xi x ji xi
この行列A はf(x)のHesse行列1
 f ( P )  f |P x  x  A  x  
22次形式(quadratic)((Hessianmatrix))
各要素はPにおける２階編導関数

極小点では勾配ゼロだから上の式を微分すると

2
A  ij xi x j

f ( x )   f |P  A  x  0P

これを解くとx  A 1 (   f | P )次はこの点を探査すべし
次点を探査すしかし、行列Ａは未知 なので、探索の過程から逐次的に近似する
Since matrix A is unknown, it is estimated from the process of the optimization incrementally.
27

数値最適化を行う遺伝的アルゴリズム：まとめ交叉方法： 正規分布交叉（ＵＮＤＸ）
交叉方法
世代交代： ＭＧＧ

レンズ系設計の最適化
プロペラ形状の最適化
船形最適化など多数の実績

しかし今後はアルゴリズムがずっと簡単かつ強力な交叉方法：
法 多親多親交叉ＲＥＸ （（一様分布使用）様分布使用）
世代交代： 多親世代交代モデルＪＧＧ
OR

最も洗練され、かつ最強の CMA-ES + NESs
を使用すべし28遺伝的アルゴリズム（ＧＡ）の研究課題●いかにして致死遺伝子が出にくいようにパラメータを遺伝子へコード化するか？
→ 問題毎に、ある程度の専門知識を要する
修正オペレータ：致死遺伝子を実行可能解へ修正●どのように子個体を生成するか？
連続関数の最適化問題 → ユークリッド空間中？
組合せ最適化問題→ ？
●どのように世代交代すればよいか？
進化遅い： 無駄な計算量大←→多様な解候補
進化早い： 解候補のバリエーション減少、探索の停滞
29

遺伝的アルゴリズム（ＧＡ）の適用における注意点●数値最適化問題において適用を試みる前に、勾配法やシンプレックス法で解けないか？
●組合せ最適化問題に適用を試みる前に、動的計画法（ＤＰ）で解ける問題ではないか？
有効なヒューリスティクスが存在しないか？
単純な問題においては遺伝的手法は非効率●数値最適化と組合せ最適化の複合問題→ 遺伝的アルゴリズムは有望な選択肢●多目的最適化問題→ 遺伝的アルゴリズムは有効30

参考文献
１）長尾 智晴： 最適化アルゴリズム，昭晃堂（２０００）．
２）W.H.Press,
２）W
H Press B.P.Flannery,B P Flannery S
S.A.Teukolsky
A Teukolsky and W
W.T.Vetterling:
T Vetterling:
ニューメリカルレシピ・イン・シー Ｃ言語による数値計算のレシピ，技術評論社（１９９３）．
３）小野 功，佐藤 浩，小林 重信：
単峰性正規分布交叉ＵＮＤＸを用いた実数値ＧＡによる関数最適化，
人工知能学会誌 Vol.14, No.6, pp.1146—1155 (1999)．
４）樋口隆英，筒井茂義，山村雅幸 : 実数値GAにおけるシンプレックス交叉の提案 ,人工知能学会誌 , Vol.16 , No.1 , pp146-155 , （2001）．
５）小林重信：実数値GAのフロンティア,人工知能学会誌Vol.24, No.1, pp.147--162 (2009)６）秋本洋平，永田裕一，小野功，小林重信（東京工業大学）
CMA-ES の学習率に関する理論的考察，
進化計算シ ポジウム2010 講演論文集 pp.202--207
進化計算シンポジウム2010
202 207 (2010)(2010).
31