So-net無料ブログ作成

遺伝的アルゴリズム [世間話]

遺伝的アルゴリズムというのが面白いなぁと思う今日この頃です。

内容知ってる人から見れば、ゴミみたいな説明だと思いますw



遺伝的アルゴリズムというのは最適化の手法の一つで、ある制限下に置いてある条件に最も適した点を見つける時に使われます。

一番単純な例が、制限下に置ける最大化だと思います。

凸凹した面の中で最も高い頂点を探し出すという行為ですね。

一般的に行われる最大化問題の解き方で最も高い頂点を探し出そうとすると、相当に運がよくなければ局地解、つまりは何番目に高いか解らない様な頂点しか見つける事が出来ません。

なんでかっつーと計算をする際に開始地点を設定しないと行けないからなんですね。

例えば山に囲まれていて、そこから目隠しした状態で高い山を探そうとしましょう。

頂上を見つける方法は至極簡単で、全ての方向に一歩ずつ足を出してみて傾きが急な方向をみつけ、その方向へと登ってゆけば確実に頂上に近づけるわけです。

当然ある地点を超えると坂が下り坂になるので、そこでまた傾きを確かめて高い方向へと登ってゆく。

これを繰り返せば最終的には頂点へとたどり着けます。

しかーし。この方法では頂点が本当に一番高いかは解らない訳です。

ただ、開始地点を上手〜く設定すれば、一番高い山の麓からスタートさせる事が出来て、最大化を達成出来ます。

今日の各分野の偉ーい人達は日夜このベストなスタート地点を探そうと躍起になってる訳です。


さてさて、じゃぁ一体遺伝的アルゴリズムが何するのかというお話。

1,まずランダムに開始地点を(例えば)10個選んで最適化問題を解き、それを値の大きい順に並べる。
2,遺伝。その中から1,5,7位(ここの設定はまちまち)の結果を出した開始地点を抽出。
3,世代交代。選んだ3つの開始地点からある程度分散させた(つまりはある程度似てる)開始地点を9個生成、残りの1つは分散を大きく設定して(突然変異)殆ど別の場所から開始させる。
4,2と3をひたすら繰り返す。

解が殆ど同じになったら出来上がり。
この方法の良い所は、10個中の6、7個が局地解を解いたとしても、突然変異がそれらを再び分散させてより良い解を探せる所にあります。



で、なんで遺伝的アルゴリズムなんて名前がついてるかというと、ダーウィンの進化論における遺伝の発想から作られた手法だからだそうです。
なんか色々書く事あったのだけれども、まぁこの辺でやめとこw
nice!(0)  コメント(0)  トラックバック(0) 
共通テーマ:学問

nice! 0

コメント 0

コメントを書く

お名前:
URL:
コメント:
画像認証:
下の画像に表示されている文字を入力してください。

トラックバック 0

この広告は前回の更新から一定期間経過したブログに表示されています。更新すると自動で解除されます。

×

この広告は1年以上新しい記事の更新がないブログに表示されております。