SoftComputing lab.
 
Googleでサイト内検索:

Fuzzy Theory
ファジィ理論
Neural Network
ニューラルネットワーク
Chaos
カオス
Artifical Intelligence <AI>
人工知能
Genetic Algorithm <GA>
遺伝的アルゴリズム
お勧めの本

4.より効果的なGAを目指して


スキーマ(schema)

ビット列として表された遺伝子には、その個体が評価される際に、評価を高くする遺伝子と評価を低くする遺伝子があります。しかし、一般にビット列をただ見ただけでどこがいい評価を与えていて、どこが悪い評価を与えているということはわかりません。(そもそもこんなことがわかるならGAを適用する必要もありませんね。)

そこで、どの遺伝子がプラスの効果を与えていてどの遺伝子がマイナスの効果を与えているのかということが知りたいわけです。しかし、総合的な評価というものは複数の遺伝子の組み合わさり方によって変化している可能性もあります。

例えば、人間で「美形」といった場合に「美男」や「美女」と言われるような人の顔のパーツ(目や鼻など)をたくさん集めてきて適当に混ぜて組み合わせたとしても必ずしも「美形」の顔が出来上がるとは限りません。むしろ、出来上がらない可能性のほうが高いかもしれません。

つまり、個体はたくさんの遺伝子の集合体であり、個体の評価というのはその個体の持つすべての遺伝子の組み合わさったときの評価といえます。したがって、ただ単純にこの遺伝子があればいいとか言い切ることはできません。

そこで、良い遺伝子の組み合わせを探す必要があります。この遺伝子の組み合わせをスキーマと呼びます。スキーマは10**のように、確定している遺伝子の部分には値を、そうでない部分には*を与えて表現します。スキーマ10**では対象個体を(1000,1001,1010,1011)の四種類に限定します。

例えば、4bitの遺伝子の個体において、初めのbitは1最後のbitは0である個体が他の個体よりもよい評価を受けるとすれば、そのスキーマは1**0であり、(1000,1010,1100,1110)は良い評価を受ける個体であるといえます。


スキーマの例
図4.1 スキーマの例

さて、ここで一つ疑問が出てきます。良いスキーマが見つかるたびにそれを組み合わせていき長いスキーマを持つ個体を作っていけばいいのではないか?というものです。確かに、良いスキーマを長くしていけば評価を簡単にあげることができそうな感じがします。このように、スキーマを単純に組み合わせればよいのではないかという考え方を積み木仮説といいます。

この積み木仮説を前提としたロイヤルロード関数というものがあります。これはスキーマを完全積み木であるとして良いスキーマを次々取り込んでいくものですが、あまり良い結果を残せませんでした。実際にはスキーマが長くなってくると評価の高いスキーマの一部に他の部分で評価を下げてしまう遺伝子を内在してしまうことが多く、しかしスキーマ全体としては評価が高くなるので、その結果このスキーマは多くの個体へと広がっていってしまいます。これをヒッチハイキングといいます。

ヒッチハイキングは必ず起こるというわけではありませんが、GAが世代を重ねていくうちに起こってしまう可能性があります。また、ヒッチハイキングが起こったときには最高の解へ行き着くことはできなくなってしまいます。これはある種の局所安定といえます。

グレイ・コーディング

GAで問題を効率よく処理をするにはコーディングも重要な要素になります。もっとも簡単なコーディングはバイナリ・コーディングになります。バイナリ・コーディングは問題の表現型における10進表記を単純に2進表記に直してコーディングしたものです。バイナリ・コーディングの場合、10進表記で隣り合っている値のハミング距離が1にならない部分があります。

※ハミング距離とは遺伝子の異なる部分の数です。


ハミング距離
図4.2 ハミング距離

10進数2進数
0000
1001
2010
3011
4100
5101
6110
7111
図4.3 バイナリ・コーディング

隣り合う値のハミング距離が1でないとなぜ困るのか?これにはだまし問題というものが関ってきます。だまし問題というのは、評価の高い解がハミング距離の離れたところにあるような問題です。例えば、3bitのコードの場合111がもっとも評価が高く、000がその次に評価が高いような場合です。

遺伝的操作では普通新しい個体は、現在の個体群のどれかと比較的ハミング距離の近いものが生成されます。したがって、ほどほどに評価の高い解の周辺に個体が集まってきたとき、最適解がそこからハミング距離の遠いところにあると、遺伝的操作ではそちらへは個体群が移りにくくなってしまいます。

このため、バイナリ・コーディングでは問題がだまし問題となってしまい、最適解が求まらなくなってしまうことがあります。

そこで、グレイ・コーディング(Grayコード)というものが考えられました。グレイ・コーディングでは2進化した遺伝子に対して変換をかけて10進数においてとなりあう数値のハミング距離が必ず1になるようにコード化します。


グレイコーディングの変換式
図4.4 グレイ・コーディングの変換式

10進数2進数Grayコード
0000000
1001001
2010011
3011010
4100110
5101111
6110101
7111100
図4.5 グレイ・コーディング

グレイ・コーディングは隣り合う値をコーディングしたときのハミング距離が1になることから、バイナリ・コーディングに比べて積み木仮説が成り立ちやすいと考えらます。

2000/04/07