進化戦略

コンピュータサイエンスにおける進化戦略（ES）は、最適化手法として機能する進化アルゴリズムのサブクラスである。^{[ 1 ]}突然変異、組換え、親の選択といった主要な遺伝的演算子を使用する。^{[ 2 ]}

「進化戦略」最適化手法は1960年代初頭に考案され、1970年代以降、インゴ・レヒェンベルク、ハンス＝パウル・シュヴェーフェル、および彼らの共同研究者によってさらに発展した。^{[ 1 ]}

進化戦略は数値最適化のために開発されたため、連続決定変数のベクトルに基づいています。 ^{[ 16 ]}離散値の場合は、適切な丸め方法または適切に適応した突然変異を整数に使用できます。^{[ 17 ]}その結果、多くのESアプリケーションでは、問題空間と探索空間は同一です。このような直接表現は、たとえばスケジューリング などの多くの組み合わせアプリケーションでは不可能であり、そこでは進化戦略の適切に修正されたバリアントが使用されます。^{[ 18 ]}進化アルゴリズムと同様に、演算子はループ内で適用されます。ループの反復は世代と呼ばれます。世代のシーケンスは、終了条件が満たされるまで続きます。

ES の特別な特徴は、突然変異ステップサイズの自己適応とそれに伴う共進化です。ES は標準形式を使用して簡単に説明されていますが、^{[ 19 ] [ 20 ] [ 21 ]}多くのバリアントがあることが指摘されています。^{[ 18 ] [ 22 ] [ 23 ] [ 24 ]}実数値染色体には、${\displaystyle n}$決定変数、${\displaystyle n'}$突然変異ステップサイズ$\displaystyle \sigma_j \$、 どこ：${\displaystyle 1\leq j\leq n'\leq n}$多くの場合、すべての決定変数に対して1つの突然変異ステップサイズが使用されるか、それぞれに独自のステップサイズが設定されます。${\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つのレベルで進化的探索を行うことを意味します。このようにして、進化的探索（ES）はより細かいステップで目標を探索することが保証されます。しかし、探索空間内の大きな無効領域をスキップすることが困難になるという危険性も伴います。

ES は、次の親集団を生成するための最適な選択の 2 つのバリアントを知っています (${\displaystyle \mu }$- 親の数、${\displaystyle \lambda }$- 子孫の数): ^{[ 2 ]}

• ${\displaystyle (\mu ,\lambda )}$: その${\displaystyle \mu }$最良の子孫は次世代に使用されます（通常${\displaystyle \mu ={\frac {\lambda }{2}}}$)
• ${\displaystyle (\mu +\lambda )}$: 最良のものは、${\displaystyle \mu }$両親と${\displaystyle \lambda }$子孫。

バックとシュヴェーフェルは、${\displaystyle \lambda }$およそ7倍であるべき${\displaystyle \mu }$[ ^{20 ]それ}によって${\displaystyle \mu }$強い選択圧のため、小さすぎる値を選んではいけません。${\displaystyle \mu }$これらはアプリケーションに依存するため、実験的に決定する必要があります。進化戦略における次世代の選択は決定論的であり、実際の適応度値ではなく、適応度ランキングのみに基づいて行われます。したがって、結果として得られるアルゴリズムは、目的関数の単調変換に対して不変です。

最も単純で古い^{[ 1 ]}進化戦略${\displaystyle {\mathit {(1+1)}}}$は、現在の点（親）とその突然変異の結果である2つの個体群に対して作用します。突然変異体の適応度が親の適応度以上である場合にのみ、次の世代の親になります。そうでない場合は、突然変異体は無視されます。より一般的には、${\displaystyle \lambda }$突然変異体は親株と競合することができ、${\displaystyle (1+\lambda )}$。 で${\displaystyle (1,\lambda )}$最良の突然変異体が次世代の親となり、現在の親は常に無視される。これらの変異体の一部については、単峰性の目的関数に関して（確率的な意味での）線形収束の証明が導出されている。^{[ 25 ] [ 26 ]}

各座標の個々のステップサイズ、または座標間の相関関係は、本質的には基礎となる共分散行列によって定義され、実際には自己適応または共分散行列適応（ CMA-ES ）によって制御されます。^{[ 23 ]}進化する共分散行列を使用して多変量正規分布から突然変異ステップが抽出される場合、この適応された行列は探索ランドスケープの逆ヘッセ行列を近似すると仮説が立てられています。この仮説は、二次近似に依存する静的モデルに対して証明されています。 ^{[ 27 ]} 2025年に、Chenら^{[ 28 ]}は、合意に基づく分散最適化のためのマルチエージェント進化戦略を提案しました。この戦略では、複数のエージェントが協調してステップサイズを制御するのに役立つ新しいステップ適応方法が設計されています。

• 共分散行列適応進化戦略（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。「進化戦略：包括的な入門」。Journal Natural Computing、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)。二相ノズルおよび中空コアジェット実験。AEG 研究所。MDH Staustrahlrohr プロジェクトグループ。ベルリン、ドイツ連邦共和国。第 11 回磁気流体力学の工学的側面に関するシンポジウム議事録、Caltech、パサデナ、カリフォルニア州、1970 年 3 月 24 日～ 26 日。
• M. Emmerich、OM Shir、H. Wang:進化戦略。『ヒューリスティクスハンドブック』1-31頁。Springer International Publishing (2018)。

• ベルリン工科大学のバイオニクスと進化技術
• ドルトムント工科大学アルゴリズム工学講座（LS11 ）
• 共同研究センター531 –ドルトムント工科大学[^{リンク削除]}