進化戦略
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/18 03:28 UTC 版)
ナビゲーションに移動 検索に移動進化戦略（しんかせんりゃく、英: 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 は
| 一般 |
|
|---|---|
| 微分可能 |
|
| 凸縮小化 |
| ||||
|---|---|---|---|---|---|
| 線型 および 二次 |
|
| 系列範例 (Paradigms) | |||||
|---|---|---|---|---|---|
| グラフ理論 |
|
