📂最適化理論

遺伝的アルゴリズムにおける突然変異とは？

用語 ¹

遺伝的アルゴリズムでの 突然変異^mutation、あるいは単に変異とは個体の染色体に主にランダムに変化を与える演算を指す。

説明

もし個体が交叉混合のみで生じるなら、初期のランダムな集団に存在しなかった形質は決して現れない。変異と自然選択は実際の進化においても最も重要な二本柱であり、遺伝的アルゴリズムでも同様に変異は個体群の多様性を維持し新しい形質を導入する役割を果たす。

ビット反転

$$ x_{k} ! = x_{k} $$ 個体集合が $\left\{ 0 , 1 \right\}^{n}$ のようにビットで表現される場合、変異を実装する最も単純な方法はランダムにいくつかの位置を選んでビットを反転させることだ。

一様置換

$$ x_{k} = U [ a , b ] $$ 座標で表される連続値からなる染色体のある次元が上限と下限を持ち区間 $[a , b]$ に属するとすると、突然変異はビット反転のようにどの位置の値を変えるかをまず選び、次に一様分布 $U [ a, b ]$に従う乱数を引くことで起こすこともできる。

ガウス変異

$$ \mathbf{x} += \mathcal{N} ( \mathbf{0} , \Sigma ) $$ 座標に特別な境界がない場合、ブラウン運動のように多変量正規分布に従う増分（インクリメント）を継続的に加えていく方式の実装が最も妥当だ。ただしこの方法は座標ごとに変異の強さが異なり得るため、それを調整するハイパーパラメータ $\Sigma$ を把握する必要がある。

レヴィジャンプ

レヴィ飛行を通じて個体集合が移動する方式で変異を引き起こす方法もある。こうした変異は解空間を広く探索したいとき、爆発的な変異を発生させたいときに有用だ。

通常は多変量コーシー分布を用いるが、注意すべき点は正規分布に従う確率変数成分からなるベクトルが多変量正規分布に従うのと異なり、t分布に従う確率変数成分からなるベクトルは多変量t分布に従うとは限らないため、正確には多変量t分布で自由度を $1$ に与えて多変量コーシー分布を構成する必要があるという点だ。

実際に筆者もこの事実を知らずに迷ったことがある。