進化的戦略

ウィキペディア

進化戦略

出典: フリー百科事典『ウィキペディア（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  は$x=(x_{1},x_{2},\dots ,x_{n})$

非線形(制約付き)

一般	バリア関数 ペナルティ関数法（英語版）
微分可能	ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）

凸最適化

凸縮小化	切断面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版）
線型 および 二次	内点法 カチヤン楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂シンプレックス法（英語版） 十字法（英語版） レムケの主ピボット操作法（英語版）

組合せ最適化

系列範例 (Paradigms)	近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 切断)
グラフ理論	最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）

メタヒューリスティクス

• 進化的アルゴリズム（進化戦略）
• 山登り法
• 局所探索法
• 焼きなまし法
• タブーサーチ

• カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）