進化戦略

進化戦略（しんかせんりゃく、英: Evolution Strategy, ES）あるいは進化的戦略（しんかてきせんりゃく）は、メタヒューリスティクスの探索アルゴリズムである。4つの主要な進化的アルゴリズム方法論の一つでもある。

概要

進化戦略は、実数関数の非線形最適化問題を解く手法として、1960年代頃にベルリン工科大学の Ingo Rechenberg と Hans-Paul Schwefel により開発されたアルゴリズムである。

遺伝的アルゴリズムと同時期に提案され内容も「進化的な要素を関数の探索に用いる」という全く同じコンセプトの手法であるが、1990年代頃までは遺伝的アルゴリズムがアメリカを中心に研究が行われていたのに対し、進化戦略は主にヨーロッパを中心に全く独立の分野として研究が行われ、あまりお互いの交流はなかった。その研究内容としては数学的な解析が非常に多いのが特徴である。

進化戦略には大きく分けて、一つの状態から別の一つの状態へ遷移する手法と、複数の状態から複数の状態へ遷移する手法がある。 前者は(1+1)-ESと呼ばれている、後者の方法としては(μ,λ)-ESと選択方法が若干違う(μ+λ)-ESという二つの手法があるがここではまとめて(μ,λ)-ES系と呼ぶことにする。

探索手法は主に突然変異を用いる、ただし(μ,λ)-ES系では遺伝的アルゴリズムに用いられる交叉の処理も補助的な探索手法として用いられる。特に(μ,λ)-ES系は遺伝子型が実数を取るように拡張した遺伝的アルゴリズムや進化的プログラミングあるいは粒子群最適化などとの違いが薄く、現在ではこれらの手法の境界線はあいまいになっている。

(1+1)-ES アルゴリズム

概要

ここでは、(1+1)-ES アルゴリズムについて述べる。このアルゴリズムは次のような単純な局所探索の枠組みから始まる。

まず n 次元空間の上の目的関数 f(x)  の最大値を求める問題を考えてみる。 このとき引数ベクトル[要曖昧さ回避] x  は x = ( x 1 , x 2 , … , x n ) {\displaystyle x=(x_{1},x_{2},\dots ,x_{n})} の成分を持つとする。このとき

x i ′ = x i + N ( 0 , σ 2 ) ( i = 1 , 2 , … , n ) {\displaystyle x'_{i}=x_{i}+N(0,\sigma ^{2})(i=1,2,\dots ,n)}

となるベクトル x ′ = ( x 1 ′ , x 2 ′ , … , x n ′ ) {\displaystyle x'=(x'_{1},x'_{2},\dots ,x'_{n})} を考える、ここで N(0, σ2) は平均 0、分散 σ2（すなわち標準偏差 σ）の正規乱数（乱数列参照）であり、各成分ごとに独立である（同じ数値を全成分に加算するわけではない）。 このときもし f(x) < f(x′) であるなら、x = x′ として上記の処理を繰り返す。

ここで問題になるのはσがどれくらいの数値なら適正であるか である、もしσが小さな数値なら x'   は非常に x  に近い位置のベクトルになり、上記の操作は最も近い極大値を見つけることができる可能性が高い。しかしこの極大値が最大値である保証はなく、もし違うなら最大値ではない極大値に捕まって探索が失敗したことになる（局所解）。逆にσが大きな数値なら局所解の問題は回避できる可能性が高いが探索した結果がその空間付近の極大値である可能性は極めて低い、もしかしたら求めた解は最大値のほんの少し手前であるかもしれない。

(1+1)-ES は上記の探索を行いながらσの値を更新する探索手法である。更新方法には決まった方法の定義は無いが提案者の Schwefel は次のような更新規則と更新方法を推奨している。

1/5 ルール

突然変異（上述の正規乱数を各成分に加える行為）の成功率は 1/5 とするべきである。つまり成功率が 1/5 未満ならσを小さくし、1/5 以上ならσを大きくするべきである。この主張は以下のような数学的な解釈に基づいている。

最適解を x*  としたとき、解の収束への速さを

ψ = E { | | x ∗ − x ( t ) | | − | | x ∗ − x ( t + 1 ) | | } {\displaystyle \psi =E\left\{||x^{*}-x(t)||-||x^{*}-x(t+1)||\right\}}

とおく。ここで t  は探索を繰り返した回数である。このときψを最大化する、すなわち

d ψ d σ | σ ∗ = 0 {\displaystyle \left.{\frac {d\psi }{d\sigma }}\right|_{\sigma ^{*}}=0}

となるようなσ*が最適なσであるとする。この式を多くの方程式に適用してσ*を求め、そのときの成功確率を求めた結果、ほとんどの式が 0.2 すなわち 1/5 付近の解を持つことに至ったため、上記の主張がなされるようになった。これを 1/5 ルールという。

σの更新方法

σの更新方法は n （x  の要素数）毎の探索時に過去 10n  回の成功確率を見て、成功率が 2n  回（1/5ルール）未満なら 0 以上 1 以下の実数定数 c  をσにかける。逆に 2n  回以上の成功率なら σをc で割ることが推奨されている。 c の値は一概には決められないが Schwefel は 0.85 を推奨している。

アルゴリズムの流れ

まとめると(1+1)-ES　のアルゴリズムは以下のような流れで行われる。

  1. x  とσの初期値をランダムで決める。
  2. 突然変異操作よりx  の近傍 x'  を求める（求め方は上述の概要を参照）
  3. f(x) < f(x')   であるなら、x = x'   とする。
  4. 1/5 ルールに従いσを更新する。
  5. 適当な終了条件が満たされるまで2. 以下の操作を繰り返す。

(μ,λ)-ES系

概要

ここからは(μ,λ)-ES系のアルゴリズムについて述べる。このアルゴリズムは探索する x を複数にして、より効果的な大域探索を可能とするアルゴリズムの開発を目指したものである。しかしながら、そのような場合 (1+1)-ES のような 1/5 ルールが成り立たなくなってしまい、突然変異のパラメータ調整の具体的な指針が存在しない。

そこで、(μ,λ)-ES系では突然変異のパラメータも個体の中に埋め込み最適解の探索と同時にパラメータの数値も進化させる手法が試みられている。 具体的には個体を a  とした場合、個体は次のような構成となる。

a = ( x , σ , α ) {\displaystyle a=(x,\sigma ,\alpha )}

（探索ベクトル） x = ( x 1 , x 2 , … , x n ) {\displaystyle x=(x_{1},x_{2},\dots ,x_{n})}
（突然変異パラメータ） σ = ( σ 1 , σ 2 , … , σ n ) {\displaystyle \sigma =(\sigma _{1},\sigma _{2},\dots ,\sigma _{n})}
（調整パラメータ） α = ( … , α i j , … ) ( i = 1 , … , n − 1 ) ( j = i + 1 , … , n ) {\displaystyle \alpha =(\dots ,\alpha _{ij},\dots )(i=1,\dots ,n-1)(j=i+1,\dots ,n)}

突然変異の操作

(μ,λ)-ES系の突然変異は上記の個体の各要素全てについて操作を行う。 まず探索のメインである探索ベクトル以外については以下のような操作が提案されている。

σ i ′ = σ i exp ⁡ ( τ ′ ξ + τ ξ i ) {\displaystyle \sigma '_{i}=\sigma _{i}\exp \left(\tau '\xi +\tau \xi _{i}\right)}
α i j ′ = α i j + β ξ i j {\displaystyle \left.\alpha '_{ij}=\alpha _{ij}+\beta \xi _{ij}\right.}

このとき ξ , ξ i , ξ i j {\displaystyle \xi ,\xi _{i},\xi _{ij}} は全て独立に平均 0分散 1の正規乱数である。 また τ , τ ′ , β {\displaystyle \tau ,\tau ',\beta } は定数であり推奨値はそれぞれ、

τ = ( 2 n ) − 1 {\displaystyle \tau =\left({\sqrt {2{\sqrt {n}}}}\right)^{-1}}
τ ′ = ( 2 n ) − 1 {\displaystyle \tau '=\left({\sqrt {2n}}\right)^{-1}}
β = 0.0873

である。 探索ベクトル x  の突然変異については以下のような少々複雑な計算が行われる。

まず各i  について正規分布 N(0, σi2 ) に従う正規乱数を求めそれを η = ( η 1 , η 2 , … , η n ) {\displaystyle \eta =\left(\eta _{1},\eta _{2},\dots ,\eta _{n}\right)} とおく

次に各αij に対して以下のような n×n の行列 R ( α i j ) {\displaystyle R(\alpha _{ij})} を生成する

r i i = r j j = cos ⁡ α i j {\displaystyle \left.r_{ii}=r_{jj}=\cos \alpha _{ij}\right.}
r i j = − r j i = − sin ⁡ α i j {\displaystyle \left.r_{ij}=-r_{ji}=-\sin \alpha _{ij}\right.}
r k k = 1 ( k = 1 , … , n  and  k ≠ i , k ≠ j ) {\displaystyle r_{kk}=1(k=1,\dots ,n{\mbox{ and }}k\neq i,k\neq j)}
それ以外の要素は 0 とする。

この二つの要素を以下の式で掛け合わせてベクトル ζ = ( ζ 1 , ζ 2 , … , ζ n ) {\displaystyle \zeta =(\zeta _{1},\zeta _{2},\dots ,\zeta _{n})} を生成する。

ζ = ∏ i = 1 n − 1 ∏ j = i + 1 n R ( α i j ) η {\displaystyle \zeta =\prod _{i=1}^{n-1}\prod _{j=i+1}^{n}R(\alpha _{ij})\eta }

このベクトルとx  の和をx'   とする。

x ′ = x + ζ {\displaystyle \left.x'=x+\zeta \right.}

これが突然変異操作となる。

組み換え

(μ,λ)-ES系の組み換えは遺伝的アルゴリズムの交叉と同様の操作である。 各個体に上述の突然変異を行う前に、探索ベクトルx  の値を個体間で次のような操作を行う。

  • （入れ換え）個体 a の探索ベクトル x の成分 xaiと個体 b の探索ベクトル x の成分 xbiを入れ換える
  • （中間値）個体 a の探索ベクトル x の成分 xaiと個体 b の探索ベクトル x の成分 xbiをそれぞれ(xai + xbi)/2 に置き換える。

他にも内分点を取るなどの操作が提案されている。

(μ/ρ,λ)-ES と表記した際は、ρ個の親から交叉して1つの新しい個体を作り、それをλ回繰り返してλ個の新しい個体を作る。

アルゴリズムの流れ

アルゴリズムの流れをまとめると(μ,λ)-ES系のアルゴリズムは以下のようになる。

  1. μ個の個体をランダムに生成して、それぞれの個体の目的関数を評価する。
  2. いくつかの個体に対しては組み換え操作を行う。
  3. 各個体を適当に選択し、その個体に突然変異操作を行った個体を新たにλ個生成する。
  4. それぞれの個体の目的関数を評価する。
  5. 生き残る個体を決定する
    1. (μ,λ)-ESの場合は新たに生成したλ個の個体(λ>μ)の内上位μ個を選び、残りを削除する。
    2. (μ+λ)-ESの場合は新たに生成したλ個の個体と生成元のμ個の個体を混ぜ合わせ上位μ個の個体を選び、残りを削除する。
  6. 終了条件を満たすまで2. 以下の操作を繰り返し、最終的に最も成績の良い個体の探索ベクトルを解として出力する。

CMA-ES

詳細は「CMA-ES」を参照

加速するために共分散行列を使用したアルゴリズム。

参考文献

遺伝的アルゴリズムの解説本などの中には進化戦略についてのアルゴリズムの内容を若干解説している本がいくつかある。

  • 坂和正敏・田中雅博 『遺伝的アルゴリズム』、朝倉書店、1995年、ISBN 4-254-20990-8
  • 三宮信夫・喜多 一・玉置 久・岩本貴司『遺伝アルゴリズムと最適化』、朝倉書店、1998年、ISBN 4-254-20977-0

関連項目

外部リンク

  • 表
  • 話
  • 編
  • 歴
非線形(無制約)
… 関数　
勾配法
収束性
準ニュートン法
その他の求解法
… ヘッセ行列
  • 最適化におけるニュートン法（英語版）
The graph of a strictly concave quadratic function is shown in blue, with its unique maximum shown as a red dot. Below the graph appears the contours of the function: The level sets are nested ellipses.
Optimization computes maxima and minima.
非線形(制約付き)
一般
微分可能
凸最適化
凸縮小化
  • 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版）
  • 簡約勾配法
  • 劣勾配法（英語版）
線型 および
二次
内点法
ベイズ-交換
  • 単体法
  • 改訂シンプレックス法（英語版）
  • 十字法（英語版）
  • レムケの主ピボット操作法（英語版）
組合せ最適化
系列範例
(Paradigms)
グラフ理論
最小全域木
最大フロー問題
メタヒューリスティクス
  • カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）