2016年07月07日
できるだけわかりやすく説明してみるという実験:遺伝的アルゴリズムにおける”突然変異”について
前回の「できるだけわかりやすく説明してみるという実験:(前回の説明がちょっとアレだったので再実験)遺伝的アルゴリズム」では、コンピューターが「0と1の世界である」ということを元に、遺伝的アルゴリズムで「交配」をどういうふうにするのか、ということを説明した。
交配によって生まれた次の世代は、親の特徴を持つものになるが、交差点によってはいずれの親の特徴でもない新たな値を持つことがある、交配によって生まれた個体のうち、より優性なものを選択し、優性どうしを掛けあわせることを繰り返すことでより優性な個体を発生させる、ということがポイントだった。
ここでの例では異なる遺伝子を持った二つの親を例として挙げたが、実際は様々な遺伝子を持った個体をいくつも用意し、その中から「優性である」と思われるものを選択して何度か交配することで次の世代を作り、さらにそこでできたたくさんの子供の中から優性なものを選択して、、、ということを繰り返すので、常にどの世代においても何種類もの遺伝子を持った個体がいることになる。
ところが世代ごとの個体数が少ない場合は、交配を繰り返すことによって似たような遺伝子配列を持つ個体に収束してしまうことがある。
実世界で近縁個体どうしをかけあわせることによって「血が濃くなる」というものだ。
これによって個体の多様性は無くなる。
また、この遺伝的アルゴリズムを応用する目的によっては、交配の繰り返しによって最適解を求める、という際に、ある「飛躍」がおもしろい結果を産み出すことも期待できる。
個体に多様性を持たせること、交配の際に「飛躍」を起こすことで新しい解を導くこと、のために、遺伝的アルゴリズムでは「突然変異」を取り入れることがある。
自然界での突然変異とは、遺伝の際の遺伝子の交差時に、"エラー"が起こることである。
遺伝的アルゴリズムで突然変異を起こす際にはこの"エラー"を故意に起こす。
具体的にはある充分小さな確率で、遺伝子のあるビットを反転させてしまうのだ。
本来はこうなるところを、
と任意のビットを反転させることにより、
両親が持ち得なかった値を持つ子供が発生することになる。
上記の例では、子供1は突然変異により、両親が持っていなかった形が11という値を持つようになっている。両親の形を表す値はそれぞれ9、4ということなので、新しい形が発生したことになる。ただし、これが次の世代の中で優性になるのか劣性になるのかはわからない。ただ、新しい可能性が生まれた、ということである。
また、子供2は食べ物の好みが0になっている。これも両親のいずれも持っていなかったあたらしい値であるが、おそらくこれは劣性になるだろう。
食べることを嫌うので何も食べず、餓死することが考えられる。
以上のように遺伝的アルゴリズムでは、極まれに突然変異を意図的に起こすことにより、遺伝子が収束してしまうことを避け、また飛躍的な解の候補を作ることがある。
【今回のまとめ】
交配によって生まれた次の世代は、親の特徴を持つものになるが、交差点によってはいずれの親の特徴でもない新たな値を持つことがある、交配によって生まれた個体のうち、より優性なものを選択し、優性どうしを掛けあわせることを繰り返すことでより優性な個体を発生させる、ということがポイントだった。
ここでの例では異なる遺伝子を持った二つの親を例として挙げたが、実際は様々な遺伝子を持った個体をいくつも用意し、その中から「優性である」と思われるものを選択して何度か交配することで次の世代を作り、さらにそこでできたたくさんの子供の中から優性なものを選択して、、、ということを繰り返すので、常にどの世代においても何種類もの遺伝子を持った個体がいることになる。
ところが世代ごとの個体数が少ない場合は、交配を繰り返すことによって似たような遺伝子配列を持つ個体に収束してしまうことがある。
実世界で近縁個体どうしをかけあわせることによって「血が濃くなる」というものだ。
これによって個体の多様性は無くなる。
また、この遺伝的アルゴリズムを応用する目的によっては、交配の繰り返しによって最適解を求める、という際に、ある「飛躍」がおもしろい結果を産み出すことも期待できる。
個体に多様性を持たせること、交配の際に「飛躍」を起こすことで新しい解を導くこと、のために、遺伝的アルゴリズムでは「突然変異」を取り入れることがある。
自然界での突然変異とは、遺伝の際の遺伝子の交差時に、"エラー"が起こることである。
遺伝的アルゴリズムで突然変異を起こす際にはこの"エラー"を故意に起こす。
具体的にはある充分小さな確率で、遺伝子のあるビットを反転させてしまうのだ。
本来はこうなるところを、
と任意のビットを反転させることにより、
両親が持ち得なかった値を持つ子供が発生することになる。
上記の例では、子供1は突然変異により、両親が持っていなかった形が11という値を持つようになっている。両親の形を表す値はそれぞれ9、4ということなので、新しい形が発生したことになる。ただし、これが次の世代の中で優性になるのか劣性になるのかはわからない。ただ、新しい可能性が生まれた、ということである。
また、子供2は食べ物の好みが0になっている。これも両親のいずれも持っていなかったあたらしい値であるが、おそらくこれは劣性になるだろう。
食べることを嫌うので何も食べず、餓死することが考えられる。
以上のように遺伝的アルゴリズムでは、極まれに突然変異を意図的に起こすことにより、遺伝子が収束してしまうことを避け、また飛躍的な解の候補を作ることがある。
【今回のまとめ】
- 遺伝的アルゴリズムでは、交配を繰り返すことにより、遺伝子がひとつの種類に収束してしまうことがある。
- これを避けるため、低い確率で意図的に「突然変異」を発生させることがある。
- 遺伝的アルゴリズムの突然変異は、遺伝子上の任意のビットを反転させることで起こす。
- 突然変異により、飛躍的な解の候補が発生することがある。ただし、それが優性であるとは限らない。