📂最適化理論

遺伝的アルゴリズムにおける微分進化とは何ですか？

用語 ¹

遺伝的アルゴリズムで 微分進化^{differential evolution}とは 突然変異を起こすときに特定の方向^directionを与える戦略を指す。

説明

方向を与えるという点から推測できるように、微分進化はそれ自体で 勾配降下法と似たアイデアに基づく。目的関数が微分可能であれば変異自体を 導関数の方向に起こすことができ、微分のためのコストがあまりに大きいか微分できない場合には問題に応じていくつかの戦略を試すことができる².

微分はできないが関数の評価^evaluationが大きな負担でないなら、解集合が ベクトル空間である場合、以下のようにランダムに選んだ解同士の差を利用して変異方向を決められる:

1. 個体の中から $\mathbf{a}, \mathbf{b}, \mathbf{c}$ をランダムに選ぶ。
2. ハイパーパラメータ $w \in \mathbb{R}$ に対して暫定ベクトル $\mathbf{z} = \mathbf{a} + w(\mathbf{b}-\mathbf{c})$ を計算する。
3. $\mathbf{z}$ と $\mathbf{a}$ を比較し、$\mathbf{z}$ の適合度^fitnessがより高い場合は、$\mathbf{a}$ を $\mathbf{z}$ に置き換える。

ここで $\mathbf{b}-\mathbf{c}$ は正確に微分の意味というよりも、多様体の形状がまったく分からない目的関数に対して攻める場合における「筋の通った方向」程度の意味を持つ。たとえば、すべての次元で1だけ増加するようなベクトルというわけではなく、遺伝的アルゴリズムの反復過程の中で実際に発見されうることが重要だ。