進化戦略

進化戦略とは

進化戦略（Evolution Strategy, ES）は、メタヒューリスティクスに分類される探索アルゴリズムの一つであり、進化的アルゴリズムの主要な方法論の一つです。この手法は、生物の進化プロセスから着想を得て、最適化問題を解くために用いられます。

概要

進化戦略は、1960年代にベルリン工科大学のIngo RechenbergとHans-Paul Schwefelによって開発されました。彼らは、実数関数の非線形最適化問題を解くための手法としてこのアルゴリズムを提案しました。遺伝的アルゴリズムと同時期に提案されたものの、当初は研究分野が異なり、遺伝的アルゴリズムがアメリカを中心に研究されていたのに対し、進化戦略はヨーロッパを中心に発展しました。進化戦略は、数学的な解析に重点を置いているのが特徴です。

進化戦略には、大きく分けて二つのアプローチがあります。

1. 一つの状態から別の状態へ遷移する手法（(1+1)-ES）
2. 複数の状態から複数の状態へ遷移する手法（(μ,λ)-ES）

(μ,λ)-ESには、選択方法が異なる(μ,λ)-ESと(μ+λ)-ESがありますが、ここではまとめて(μ,λ)-ES系とします。

探索手法の主体は突然変異であり、(μ,λ)-ES系では遺伝的アルゴリズムで用いられる交叉も補助的に使用されます。(μ,λ)-ES系は、実数値を扱う遺伝的アルゴリズムや進化的プログラミング、粒子群最適化などとの区別が曖昧になってきています。

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

概要

(1+1)-ESアルゴリズムは、局所探索の枠組みで動作します。目的関数f(x)の最大値を求める問題を考えます。ここで、引数ベクトルxはn次元空間の成分を持ちます。

math
x = (x_1, x_2, ..., x_n)


次に、ベクトルx'を生成します。x'の各成分は、xの対応する成分に平均0、分散σ^2の正規乱数を加えたものです。

math
x' = (x'_1, x'_2, ..., x'_n)


もしf(x) < f(x')であれば、xをx'で更新し、この処理を繰り返します。

重要なのは、σの値の決定です。σが小さい場合、探索は局所的な極大値に陥りやすく、σが大きい場合は探索範囲が広がるものの、解が最適解から遠くなる可能性があります。

(1+1)-ESでは、探索中にσの値を更新することで、この問題を解決します。Schwefelは、以下の1/5ルールを推奨しています。

1/5 ルール

突然変異の成功率（f(x) < f(x')となる確率）は1/5にするべきです。成功率が1/5未満であればσを小さく、1/5以上であればσを大きくします。このルールは、解の収束速度を最大化するための数学的な解析に基づいています。

最適なσの値は、収束速度を表す関数ψを最大化するσとして定義されます。さまざまな方程式に適用した結果、ほとんどの式で成功確率が0.2（1/5）付近の解を持つことが判明しました。

σの更新方法

σの更新は、n個の要素を持つxに対し、過去10n回の探索での成功確率を調べます。成功回数が2n回未満の場合、σに0以上1以下の実数定数cを掛け、2n回以上の場合はσをcで割ります。cの値は一概に決定できませんが、Schwefelは0.85を推奨しています。

アルゴリズムの流れ

1. xとσの初期値をランダムに決定します。
2. 突然変異操作により、xの近傍x'を求めます。
3. f(x) < f(x')であれば、x = x'とします。
4. 1/5ルールに従い、σを更新します。
5. 終了条件を満たすまで、2～4を繰り返します。

(μ,λ)-ES系

概要

(μ,λ)-ES系は、複数の探索ベクトルxを用いて大域探索を可能にするアルゴリズムです。この手法では、突然変異のパラメータも個体内に埋め込み、最適解の探索と同時にパラメータを進化させます。

個体aは、探索ベクトルx、戦略パラメータσ、αから構成されます。

突然変異の操作

(μ,λ)-ES系では、個体のすべての要素に対して突然変異を行います。戦略パラメータσとαの更新は、以下のような式で行われます。

math
σ'_i = σ_i exp(τ ξ + τ' ξ_i)
α'_{ij} = α_{ij} + β ξ_{ij}


ここで、ξ, ξi, ξijは独立に平均0、分散1の正規乱数であり、τ, τ', βは定数です。推奨値は以下の通りです。

math
τ = (sqrt(2sqrt(n)))^{-1}
τ' = (sqrt(2n))^{-1}
β ≒ 0.0873


探索ベクトルxの突然変異は、以下のように行われます。

1. 各iについて、正規分布N(0, σi^2)に従う正規乱数ηiを生成します。
2. 各αijに対して、回転行列R(αij)を生成します。
3. ηとR(αij)を掛け合わせ、ベクトルζを生成します。
4. x + ζをx'とします。

組み換え

(μ,λ)-ES系では、遺伝的アルゴリズムの交叉と同様に、個体間で探索ベクトルxの値を組み換えます。例えば、平均点を取る、内分点を取るなどの方法が提案されています。(μ/ρ,λ)-ESでは、ρ個の親から交叉して1つの新しい個体を生成し、それをλ回繰り返してλ個の新しい個体を生成します。

アルゴリズムの流れ

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

CMA-ES

CMA-ES（共分散行列適応進化戦略）は、共分散行列を用いて探索を加速するアルゴリズムです。

参考文献

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

関連項目

進化的アルゴリズム
遺伝的アルゴリズム
遺伝的プログラミング
進化的プログラミング

外部リンク

Evolution Strategies (英語) - スカラーペディア百科事典「進化戦略」の項目。

もう一度検索