遺伝的アルゴリズム - tellia @ ウィキ

遺伝的アルゴリズムとは

遺伝的アルゴリズムとは適応によって最適解を導きだすアルゴリズムの一つである。
その仕組みはまず、理想の状態がベクトルx=(a1,a2,a3,a4,...)で表されるとする。
報酬関数E(x)>0を導入しこの値が小さければ状態が理想に近づくということとにする。
以下のアルゴリズムを用いて最適解を求める。

• 交差

x=(a1,a2,a3,...)
y=(b1,b2,b3,...)
これら二つのベクトルのn番目以降の要素を入れ替える。nはランダムに決まる。
つまり
x'=(a1,a2,...,an-1,bn,bn+1,...)
y'=(b1,b2,...,bn-1,an,an+1,...)
という二つのベクトルを新たに生成する。

• 選択

ルーレット式選択
E()の値をもとにより最適解に近いベクトルが生き残る確率が高くなるようにして
ランダムにベクトルを消去する。

• 突然変異

低い確率でたまにの一成分を変化させる。
=(a1,a2,a3,...an,...)
↓
=(a1,a2,a3,...a'n,...)

これらを繰り返すことで最適解を得る。
しかし初期値によっては極大値に収束してしまうなどの問題もはらんでいる。