「遺伝的アルゴリズム」の編集履歴(バックアップ)一覧はこちら
「遺伝的アルゴリズム」(2010/10/17 (日) 22:52:49) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
**遺伝的アルゴリズムとは
遺伝的アルゴリズムとは適応によって最適解を導きだすアルゴリズムの一つである。
その仕組みはまず、理想の状態がベクトル&bold(){x}=(a1,a2,a3,a4,...)で表されるとする。
報酬関数E(&bold(){x})>0を導入しこの値が小さければ状態が理想に近づくということとにする。
以下のアルゴリズムを用いて最適解を求める。
-交差
&bold(){x}=(a1,a2,a3,...)
&bold(){y}=(b1,b2,b3,...)
これら二つのベクトルのn番目以降の要素を入れ替える。nはランダムに決まる。
つまり
&bold(){x'}=(a1,a2,...,an-1,bn,bn+1,...)
&bold(){y'}=(b1,b2,...,bn-1,an,an+1,...)
という二つのベクトルを新たに生成する。
-選択
ルーレット式選択
E(&bold(x))の値をもとにより最適解に近いベクトルが生き残る確率が高くなるようにして
ランダムにベクトルを消去する。
-突然変異
低い確率でたまに&bold(x)の一成分を変化させる。
&bold(x)=(a1,a2,a3,...an,...)
↓
&bold(x')=(a1,a2,a3,...a'n,...)
これらを繰り返すことで最適解を得る。
しかし初期値によっては極大値に収束してしまうなどの問題もはらんでいる。