進化戦略

コンピュータサイエンスにおいて、進化戦略 (ES) は進化の考え方に基づいた最適化手法です。これは、進化計算または人工進化方法論の一般的なクラスに属します。

「進化戦略」最適化手法は 1960 年代初頭に考案され、1970 年代以降にIngo Rechenberg、Hans-Paul Schwefelとその同僚によってさらに開発されました。

進化戦略では、問題に依存する自然な表現を使用するため、問題空間と検索空間は同一です。進化アルゴリズムと同様に、演算子はループ内に適用されます。ループの反復は世代と呼ばれます。世代のシーケンスは、終了基準が満たされるまで継続されます。

ES の特徴は、突然変異ステップ サイズの自己適応とそれに伴う共進化です。ES は標準形式^{[1] [2] [3]}を使用して簡単に説明されており、多くのバリアントがあることが指摘されています。^{[4] [5] [6] [7]}実数値染色体には、決定変数に加えて、突然変異ステップ サイズが含まれます。ここで、 。多くの場合、1 つの突然変異ステップ サイズがすべての決定変数に使用されるか、それぞれが独自のステップ サイズを持ちます。子孫を生み出すための交配選択はランダムであり、つまり適応度とは無関係です。まず、交配ごとに、親の中間組換えとその後の突然変異によって、次のように 新しい突然変異ステップ サイズが生成されます。${\displaystyle n}$${\displaystyle n'}$${\displaystyle {\sigma}_{j}}$${\displaystyle 1\leq j\leq n'\leq n}$${\displaystyle \lambda}$${\displaystyle {\sigma}_{j}}$

${\displaystyle {\sigma }'_{j}=\sigma _{j}\cdot e^{({\mathcal {N}}(0,1)-{\mathcal {N}}_{j}(0,1))}}$

ここで、 は平均および標準偏差を持つ正規分布のランダム変数です。はすべての に適用されますが、は各 に対して新たに決定されます。 次に、決定変数の離散的再結合の後に、新しい突然変異ステップ サイズを正規分布の標準偏差として使用して突然変異が行われます。 新しい決定変数は次のように計算されます。 ${\displaystyle {\mathcal {N}}(0,1)}$${\displaystyle 0}$${\displaystyle 1}$${\displaystyle {\mathcal {N}}(0,1)}$${\displaystyle {\sigma}'_{j}}$${\displaystyle {\mathcal {N}}_{j}(0,1)}$${\displaystyle {\sigma}'_{j}}$${\displaystyle x_{j}'}$

${\displaystyle x_{j}'=x_{j}+{\mathcal {N}}_{j}(0,{\sigma }_{j}')}$

これにより、2 つのレベルでの進化的検索が実現します。1 つ目は問題レベル自体、2 つ目は突然変異ステップ サイズ レベルです。このようにして、ES がターゲットをより細かいステップで検索することを保証できます。ただし、検索空間内のより大きな無効領域をスキップすることが困難になる危険性もあります。

ES は、次の親集団の生成のための最良の選択の 2 つのバリエーションを知っています。-ES では最良の子孫のみが使用されるのに対し、エリート主義の-ES では、最良のものが親と子から選択されます。 ${\displaystyle (\mu ,\lambda )}$${\displaystyle \mu}$${\displaystyle (\mu +\lambda )}$${\displaystyle \mu}$

BäckとSchwefelは、の値は集団サイズの7倍にすべきであると推奨しているが^[2]、強い選択圧のため、をあまり小さく選択してはならない。の適切な値は用途に依存し、実験的に決定する必要がある。 ${\displaystyle \lambda}$${\displaystyle \mu}$${\displaystyle \mu}$${\displaystyle \mu}$

各座標の個々のステップサイズ、または座標間の相関は、本質的には基礎となる共分散行列によって定義され、実際には自己適応または共分散行列適応（CMA-ES）によって制御されます。^[6]突然変異ステップが進化共分散行列を使用して多変量正規分布から抽出される場合、この適応行列は検索ランドスケープの逆ヘッセ行列を近似するという仮説が立てられています。この仮説は、2次近似に依存する静的モデルに対して証明されています。^[8]

進化戦略における次世代の選択は決定論的であり、適応度のランキングのみに基づいており、実際の適応度の値に基づいているわけではない。したがって、結果として得られるアルゴリズムは、目的関数の単調な変換に対して不変である。最も単純な進化戦略は、現在のポイント（親）とその突然変異の結果の 2 つのサイズの集団で動作する。突然変異体の適応度が親の適応度と同等以上の場合にのみ、突然変異体が次世代の親になる。それ以外の場合は、突然変異体は無視される。これは -ES である。より一般的には、突然変異体を生成して親と競合させることができ、これを-ESと呼ぶ。-ES では、最も優れた突然変異体が次世代の親になり、現在の親は常に無視される。これらのバリアントのいくつかについては、単峰性目的関数で線形収束（確率的意味で）の証明が導出されている。^{[9] [10]}${\displaystyle {\mathit {(1+1)}}}$${\displaystyle \lambda}$${\displaystyle {\mathit {(1+\lambda )}}}$${\displaystyle (1,\lambda )}$

• 共分散行列適応進化戦略 (CMA-ES)
• 導関数を使わない最適化
• 進化的計算
• 遺伝的アルゴリズム
• 自然進化戦略
• 進化ゲーム理論

• Ingo Rechenberg (1971): Evolutionsstrategie – Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (博士論文)。 Frommann-Holzboog (1973) によって再版されました。ISBN 3-7728-1642-8 
• Hans-Paul Schwefel (1974): Numericsche Optimierung von Computer-Modellen (博士論文)。 Birkhäuser によって再版されました (1977)。
• ハンス・ポール・シュヴェフェル：進化と最適の探求。ニューヨーク：ワイリー＆サンズ、1995年。ISBN 0-471-57148-2 
• H.-G. BeyerとH.-P. Schwefel。進化戦略：包括的な入門。ジャーナルナチュラルコンピューティング、1（1）：3–52、2002年。
• ハンス・ゲオルク・ベイヤー：進化戦略理論。シュプリンガー、2001年4月27日。ISBN 3-540-67297-4 
• インゴ・レッヒェンベルグ:進化戦略 '94。シュトゥットガルト: Frommann-Holzboog 1994. ISBN 3-7728-1642-8 
• J. Klockgether および HP Schwefel (1970)。2 相ノズルと中空コア ジェットの実験。AEG 研究研究所。MDH Staustrahlrohr プロジェクト グループ。ドイツ連邦共和国ベルリン。第 11 回磁気流体力学の工学的側面に関するシンポジウム議事録、カリフォルニア工科大学、カリフォルニア州パサデナ、1970 年 3 月 24 ～ 26 日。
• M. Emmerich、OM Shir、H. Wang: 進化戦略。Handbook of Heuristics、1-31 ページ。Springer International Publishing (2018)。

• ベルリン工科大学のバイオニクスと進化技術
• アルゴリズム工学科長（Ls11） – ドルトムント工科大学
• 共同研究センター 531 – ドルトムント工科大学